10
\$\begingroup\$

My home town, Rhyl, has a one-way traffic system which seems to have been designed to keep people away from their destination for as long as possible. Your task, should you choose to attempt it, is to produce a program to give the shortest route through such a traffic system.

Input

Input will be on STDIN, and will be a list of start and end points followed by a blank line followed by a list of queries, as follows:

A B
B A
B C
C D
D C

A D
C A
B A

Each road can only be travelled in the direction(s) given, so, in the above example the road A - B is a two way street whereas B - C is a one-way street from B to C. Travelling from C to B is prohibited.

Start and end points will all be represented by a single upper-case letter.

Output

Output should be the shortest route (measured by number of points visited) from the given start point to the given end point for each query received. If no such route exists, output a blank line. If more than one shortest route exists, output the first when sorting all shortest routes lexicographically.

For the above example the output would be:

A B C D

B A

Test Scripts

As before I'm providing tests for this task based on scripts written by Joey and Ventero:-

and also tests and expected output for anyone who can't use the above scripts

Usage: ./test [your program and its arguments]

Rewards

All answers which have obviously had some attempt at golfing that meet the spec and pass all the tests will get my upvote. The shortest working answer by 26/01/2012 will be accepted.

\$\endgroup\$
10
  • \$\begingroup\$ output the first when sorting all shortest routes lexicographically - So if A B D and A C D are both valid solutions, output A B D instead? \$\endgroup\$
    – Mr. Llama
    Jan 12, 2012 at 16:08
  • \$\begingroup\$ @GigaWatt Yes, that's right. \$\endgroup\$
    – Gareth
    Jan 12, 2012 at 16:12
  • \$\begingroup\$ This is awfully close to a duplicate of codegolf.stackexchange.com/questions/3474/… \$\endgroup\$ Jan 12, 2012 at 16:29
  • 1
    \$\begingroup\$ @PeterTaylor Why didn't you raise that while it was in the question sandbox? What do you suggest? I could delete it while there are no answers on it, I suppose? \$\endgroup\$
    – Gareth
    Jan 12, 2012 at 16:45
  • \$\begingroup\$ @Gareth, because for once there was activity on a few threads on meta at the same time, and I didn't notice that there was a new reply in the question sandbox. Deletion is one possibility; or you could extend it to weight the edges - we haven't had a directed Dijkstra question yet. \$\endgroup\$ Jan 12, 2012 at 17:12

3 Answers 3

3
\$\begingroup\$

Haskell, 223 207 characters

main=interact$unlines.f.break null.map words.lines
s%[f,t]=[[f]]#t where[]#_="";x#t|y@(_:_)<-[z|z<-x,last z==t]=unwords$minimum y|1<3=s&x#t
s&z=[x++[b]|x<-z,[a,b]<-s,last x==a,notElem b x];f(s,_:q)=map(s%)q
\$\endgroup\$
2
\$\begingroup\$

Python (2.x), 382 369 358 338 323 318 characters

All tips and comments welcome!

import os;u=str.split;l=u(os.read(0,1e9),'\n')
p,g,c=l.index(''),{},map;o=g.setdefault
def f(g,s,e,q=[]):q=q+[s];y=([],[q])[s==e];[c(y.append,f(g,n,e,q))for n in set(o(s,[]))-set(q)];return y
for k,v in c(u,l[:p]):o(k,[]);g[k]+=v
for w,e in c(u,l[p+1:]):h=sorted(f(g,w,e));print''if not h else' '.join(min(h,key=len))

Should pass the tests in this form. Feed input via stdin, e.g. python shortestroute.py < test.txt.

\$\endgroup\$
2
  • \$\begingroup\$ Seems to fail query 2 of test 4. Returns A B I J M instead of A B G J M. \$\endgroup\$
    – Gareth
    Jan 16, 2012 at 0:18
  • \$\begingroup\$ @Gareth: there was indeed a small bug considering lexographical sort of similar length solutions, should be fixed now... \$\endgroup\$ Jan 16, 2012 at 9:18
1
\$\begingroup\$

C:450,437,404,390 characters

#include<stdio.h>
#include <string.h>
r[99][99],p[99],q[99],m[99],i,j,x,y,s;
char t[9],e[9999];
F(k)
{
    m[k]^s?r[p[k]=q[i]][k]?m[q[j++]=k]=s:0:0;
    if(++k<99)F(k);
}
f()
{
    F(0);
    if(++i^j)f();
}
P(o)
{
    if(p[o])P(p[o]);
    *t=m[o]^s?0:o;
    strcat(e,t);
}
w()
{
    gets(t);
    r[*t][t[2]]=*t?w():0;
}
W()
{
    gets(t);
    x=*t,x?y=t[j=2],s=x+y*99,m[q[t[2]=i=p[x]=0]=x]=s,f(),P(y),strcat(e,"\n"),W():0; 
}
main()
{
    w();
    W();
    puts(e);
}
\$\endgroup\$
3
  • \$\begingroup\$ puts("\n") prints two newlines. puts() automatically adds an end-of-line terminator to the strings it prints. To avoid that behavior, use fputs(str, stdout) or simply printf(str). \$\endgroup\$
    – J B
    Jan 13, 2012 at 9:34
  • \$\begingroup\$ Bends the rules slightly - should take all the input in one go and then output all the answers to the queries in one go. I'll +1 it because it works fine (and found mistakes in the tests), but I won't be able to accept it over a longer program that fully complies with the input/output requirements. \$\endgroup\$
    – Gareth
    Jan 13, 2012 at 10:46
  • \$\begingroup\$ @Gareth: fixed. though, answer output should not be as longer than 9999 characters! \$\endgroup\$
    – Ali1S232
    Jan 13, 2012 at 11:32

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.