Jalur terpendek dalam grafik

12

Tulis program untuk mengambil grafik (dari input standar atau file, pilihan Anda) dan temukan jalur terpendek dalam grafik.

Grafik ditentukan menggunakan format berikut:

A---S   F--T
|  / \  |
| /   5 0
|/     \|
D----3--E

    A-Z: nodes in the graph
   -|/\: edges in the graph
    0-9: weights on the edges
<space>: all the holes

Semua tepi tidak terarah dan terletak di sepanjang salah satu dari 8 arah mata angin (yaitu, tidak ada tikungan). Tepi secara opsional dapat mengandung bobot dari 0 hingga 9. Berat tidak akan berada pada simbol terakhir yang menghubungkan tepi ke sebuah simpul (yaitu tepi harus memiliki setidaknya 3 simbol untuk mengandung bobot). Tepi tak berbobot memiliki bobot default 1.

Kode Anda harus menghitung jalur terpendek antara node Sdan Tdan mencetak panjang dan jalur, seperti ini:

5:SDEFT

Program terpendek yang benar menang.

code-golf graph-theory path-finding Keith Randall
sumber
1
Apakah diagram grafik harus diuraikan atau dapatkah Anda menggunakan format Anda sendiri? Salah satu contoh format - grafik Anda dapat direpresentasikan sebagai: AS0,SD0,SE5,DE3,FE0,FT0(Anda dapat menghilangkan koma jika setiap entri panjangnya 3 byte).
Thomas O
1
Ya, Anda harus menguraikan grafik seperti yang saya tentukan. Sebenarnya sebagian besar masalahnya. Bagian jalur terpendek hanya memastikan parsing Anda benar.
Keith Randall
3
Format input terlalu rumit dan imho tidak terlalu menambah masalah.
JPvdMerwe
1
Hanya berpikir orang-orang di sini ingin mencoba sesuatu yang sedikit lebih menantang.
Keith Randall
2
@SimpleCoder: Saya akan menganggap monospace
JPvdMerwe

Jawaban:

5

Ini kode saya, 494 karakter dengan python:

import sys,re
m=sys.stdin.readlines()
Z=lambda c,s:re.findall(r'(\w)%s+(\d*)[^\w]*(\w)'%c,''.join(x*2for x in s))
T=lambda n:''.join(x for a in map(None,*n)for x in a if x)
E=Z('-',''.join(m))+Z('\\|',T(m))+Z('/',T(' '*m.index(s)+s for s in m))+Z('\\\\',T(' '*m[::-1].index(s)+s for s in m))
E+=[x[::-1]for x in E]
S={}
for x in E:S[x[0]]=1e9
S['S']=0
P={}
for i in E:
 for x,w,y in E:
  w=int('1'+w)%10
  if S[y]>S[x]+w:S[y]=S[x]+w;P[y]=x
i=p='T'
while i!='S':i=P[i];p=i+p
print'%d:'%S['T']+p
Keith Randall
sumber