La ruta más corta en un gráfico

12

Escriba un programa para tomar un gráfico (ya sea de entrada estándar o de un archivo, su elección) y encuentre la ruta más corta en el gráfico.

Los gráficos se especifican con el siguiente formato:

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

Todos los bordes no están dirigidos y se encuentran a lo largo de una de las 8 direcciones cardinales (es decir, sin curvas). Los bordes pueden contener opcionalmente un peso de 0 a 9. El peso no estará en el último símbolo que conecta el borde a un nodo (es decir, los bordes deben tener al menos 3 símbolos para contener un peso). Los bordes no ponderados tienen un peso predeterminado de 1.

El código debe calcular la ruta más corta entre los nodos Sy Te imprimir la longitud y el camino, así:

5:SDEFT

El programa correcto más corto gana.

code-golf graph-theory path-finding Keith Randall
fuente
1
¿El diagrama gráfico debe analizarse o puede usar su propio formato? Un ejemplo de formato: su gráfico podría representarse como: AS0,SD0,SE5,DE3,FE0,FT0(podría omitir las comas si cada entrada tiene 3 bytes de longitud).
Thomas O
1
Sí, debe analizar el gráfico como lo especifiqué. Esa es la mayor parte del problema, en realidad. La parte del camino más corto solo se asegura de que su análisis sea correcto.
Keith Randall
3
El formato de entrada es realmente demasiado complicado y, en mi opinión, no agrega mucho al problema.
JPvdMerwe
1
Solo pensé que a la gente de aquí le gustaría probar algo un poco más desafiante.
Keith Randall el
2
@SimpleCoder: asumiría el monoespacio
JPvdMerwe

Respuestas:

5

Aquí está mi código, 494 caracteres en 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
fuente