Kürzester Pfad in einem Diagramm

12

Schreiben Sie ein Programm, um ein Diagramm (entweder aus der Standardeingabe oder aus einer Datei Ihrer Wahl) zu erstellen und einen kürzesten Pfad im Diagramm zu finden.

Diagramme werden im folgenden Format angegeben:

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

Alle Kanten sind ungerichtet und liegen in einer der 8 Hauptrichtungen (dh keine Biegungen). Kanten können optional eine Gewichtung von 0 bis 9 enthalten. Die Gewichtung befindet sich nicht auf dem letzten Symbol, das die Kante mit einem Knoten verbindet (dh Kanten müssen mindestens 3 Symbole enthalten, um eine Gewichtung zu enthalten). Nicht gewichtete Kanten haben eine Standardgewichtung von 1.

Der Code sollte den kürzesten Weg zwischen den Knoten berechnen Sund Tund drucken Sie die Länge und den Weg, wie folgt aus :

5:SDEFT

Kürzeste richtige Sendung gewinnt.

code-golf graph-theory path-finding Keith Randall
quelle
1
Muss das Diagramm analysiert werden oder können Sie ein eigenes Format verwenden? Ein Beispiel für ein Format - Ihre Grafik könnte folgendermaßen dargestellt werden: AS0,SD0,SE5,DE3,FE0,FT0(Sie können die Kommas weglassen, wenn jeder Eintrag 3 Byte lang ist.)
Thomas O
1
Ja, Sie müssen das Diagramm wie angegeben analysieren. Das ist eigentlich der größte Teil des Problems. Der kürzeste Pfadteil stellt nur sicher, dass Ihre Analyse korrekt ist.
Keith Randall
3
Das Eingabeformat ist wirklich viel zu kompliziert und imho fügt dem Problem nicht wirklich viel hinzu.
JPvdMerwe
1
Ich dachte nur, die Leute hier würden gerne etwas herausfordernderes ausprobieren.
Keith Randall
2
@ SimpleCoder: Ich würde Monospace annehmen
JPvdMerwe

Antworten:

5

Hier ist mein Code, 494 Zeichen in 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
quelle