Caminho mais curto em um gráfico

12

Escreva um programa para obter um gráfico (da entrada padrão ou de um arquivo, sua escolha) e encontre o caminho mais curto no gráfico.

Os gráficos são especificados usando o seguinte 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

Todas as arestas não são direcionadas e ficam ao longo de uma das oito direções principais (ou seja, sem dobras). As arestas podem opcionalmente conter um peso de 0 a 9. O peso não estará no último símbolo que conecta a borda a um nó (ou seja, as bordas precisam ter pelo menos três símbolos para conter um peso). As arestas não ponderadas têm um peso padrão de 1.

Seu código deve calcular o caminho mais curto entre os nós Se Te imprimir o comprimento eo caminho, como este:

5:SDEFT

O programa correto mais curto vence.

code-golf graph-theory path-finding Keith Randall
fonte
1
O diagrama do gráfico precisa ser analisado ou você pode usar seu próprio formato? Um exemplo de formato - seu gráfico pode ser representado como: AS0,SD0,SE5,DE3,FE0,FT0(você pode omitir as vírgulas se cada entrada tiver 3 bytes de comprimento).
Thomas O
1
Sim, você precisa analisar o gráfico conforme especificado. Esse é o maior problema, na verdade. A parte do caminho mais curto apenas garante que sua análise esteja correta.
Keith Randall
3
O formato de entrada é realmente muito complicado e o imho não adiciona muito ao problema.
JPvdMerwe
1
Apenas pensei que as pessoas daqui gostariam de tentar algo um pouco mais desafiador.
Keith Randall
2
@SimpleCoder: Eu assumiria o espaço
único

Respostas:

5

Aqui está o meu código, 494 caracteres em 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
fonte