Najkrótsza ścieżka na wykresie

12

Napisz program, który pobierze wykres (ze standardowego wejścia lub pliku, do wyboru) i znajdzie najkrótszą ścieżkę na wykresie.

Wykresy są określane przy użyciu następującego formatu:

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

Wszystkie krawędzie są bezkierunkowe i leżą wzdłuż jednego z 8 głównych kierunków (tj. Bez zagięć). Krawędzie mogą opcjonalnie zawierać ciężar od 0 do 9. Ciężar nie będzie na ostatnim symbolu, który łączy krawędź z węzłem (tzn. Krawędzie muszą mieć co najmniej 3 symbole, aby zawierać ciężar). Nieważone krawędzie mają domyślną wagę 1.

Kod powinien obliczyć najkrótszą ścieżkę między węzłami Si Toraz wydrukować i długość ścieżki, na przykład:

5:SDEFT

Zwycięża najkrótszy prawidłowy program.

code-golf graph-theory path-finding Keith Randall
źródło
1
Czy diagram wykresu musi zostać przeanalizowany, czy możesz użyć własnego formatu? Jeden przykład formatu - wykres można przedstawić w następujący sposób: AS0,SD0,SE5,DE3,FE0,FT0(można pominąć przecinki, jeśli każdy wpis ma długość 3 bajtów)
Thomas O
1
Tak, musisz przeanalizować wykres zgodnie z tym, co określiłem. To właściwie większość problemu. Najkrótsza część ścieżki tylko upewnia się, że parsowanie jest prawidłowe.
Keith Randall
3
Format wejściowy jest naprawdę zbyt skomplikowany, a imho tak naprawdę nie dodaje zbyt wiele do problemu.
JPvdMerwe 28.01.11
1
Pomyślałem, że ludzie tutaj chcieliby spróbować czegoś bardziej wymagającego.
Keith Randall
2
@SimpleCoder: Zakładam, że monospace
JPvdMerwe

Odpowiedzi:

5

Oto mój kod, 494 znaków w 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
źródło