Chemin le plus court dans un graphique

12

Écrivez un programme pour prendre un graphique (à partir d'une entrée standard ou d'un fichier, votre choix) et trouvez le chemin le plus court dans le graphique.

Les graphiques sont spécifiés au format suivant:

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

Tous les bords ne sont pas orientés et se trouvent le long de l'une des 8 directions cardinales (c.-à-d., Aucun pli). Les bords peuvent éventuellement contenir un poids de 0 à 9. Le poids ne sera pas sur le dernier symbole qui relie le bord à un nœud (c'est-à-dire que les bords doivent avoir au moins 3 symboles pour contenir un poids). Les bords non pondérés ont un poids par défaut de 1.

Votre code doit calculer le chemin le plus court entre les nœuds Set Tet imprimer la longueur et le chemin, comme ceci:

5:SDEFT

Le programme correct le plus court gagne.

code-golf graph-theory path-finding Keith Randall
la source
1
Le graphique doit-il être analysé ou pouvez-vous utiliser votre propre format? Un exemple de format - votre graphique pourrait être représenté comme suit: AS0,SD0,SE5,DE3,FE0,FT0(vous pouvez omettre les virgules si chaque entrée fait 3 octets de long.)
Thomas O
1
Oui, vous devez analyser le graphique comme je l'ai spécifié. C'est l'essentiel du problème, en fait. La partie du chemin le plus court s'assure simplement que votre analyse est correcte.
Keith Randall
3
Le format d'entrée est vraiment beaucoup trop compliqué et à mon humble avis, cela n'ajoute pas grand-chose au problème.
JPvdMerwe
1
Je pensais juste que les gens ici aimeraient essayer quelque chose d'un peu plus difficile.
Keith Randall
2
@SimpleCoder: Je suppose que monospace
JPvdMerwe

Réponses:

5

Voici mon code, 494 caractères 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
la source