12
\$\begingroup\$

Write a program to take a graph (from either standard input or a file, your choice) and find a shortest path in the graph.

Graphs are specified using the following format:

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

All edges are undirected and lie along one of the 8 cardinal directions (i.e., no bends). Edges may optionally contain a weight from 0 to 9. The weight will not be on the last symbol that connects the edge to a node (i.e. edges need to have at least 3 symbols to contain a weight). Unweighted edges have a default weight of 1.

Your code should compute the shortest path between nodes S and T and print the length and the path, like this:

5:SDEFT

Shortest correct program wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Does the graph diagram have to be parsed or can you use your own format? One example of a format - your graph could be represented as: AS0,SD0,SE5,DE3,FE0,FT0 (you could omit the commas if each entry is 3 bytes long.) \$\endgroup\$ – Thomas O Jan 28 '11 at 20:21
  • 1
    \$\begingroup\$ Yes, you have to parse the graph as I specified. That's most of the problem, actually. The shortest path part just makes sure your parsing is correct. \$\endgroup\$ – Keith Randall Jan 28 '11 at 20:26
  • 3
    \$\begingroup\$ The input format is really far too complicated and imho doesn't really add that much to the problem. \$\endgroup\$ – JPvdMerwe Jan 28 '11 at 23:32
  • 1
    \$\begingroup\$ Just thought folks here would like to try something a bit more challenging. \$\endgroup\$ – Keith Randall Jan 29 '11 at 4:10
  • 2
    \$\begingroup\$ @SimpleCoder: I would assume monospace \$\endgroup\$ – JPvdMerwe Jan 29 '11 at 16:16
5
\$\begingroup\$

Here's my code, 494 characters 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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.