Moje rodzinne miasto, Rhyl , ma jednokierunkowy system ruchu, który wydaje się być zaprojektowany tak, aby trzymać ludzi z dala od ich miejsca docelowego tak długo, jak to możliwe. Twoim zadaniem, jeśli zdecydujesz się spróbować, jest stworzenie programu, który poda najkrótszą trasę przez taki system ruchu.

Wejście

Wejście będzie włączone STDINi będzie listą punktów początkowych i końcowych, a następnie pustą linią i listą zapytań w następujący sposób:

A B
B A
B C
C D
D C

A D
C A
B A

Każdą drogą można podróżować tylko w podanym kierunku (kierunkach), więc w powyższym przykładzie droga A - B jest drogą dwukierunkową, podczas gdy B - C jest drogą jednokierunkową z B do C. Podróż z C do B jest zabronione.

Punkty początkowe i końcowe będą reprezentowane przez jedną wielką literę.

Wynik

Dane wyjściowe powinny być najkrótszą drogą (mierzoną liczbą odwiedzonych punktów) od danego punktu początkowego do danego punktu końcowego dla każdego otrzymanego zapytania. Jeśli taka trasa nie istnieje, wypisz pusty wiersz. Jeśli istnieje więcej niż jedna najkrótsza trasa, wypisz pierwszą, sortując wszystkie najkrótsze trasy leksykograficznie.

W powyższym przykładzie wynikiem byłoby:

A B C D

B A

Skrypty testowe

Tak jak poprzednio zapewniam testy dla tego zadania na podstawie skryptów napisanych przez Joeya i Ventero : -

• Grzmotnąć
• PowerShell

a także testy i oczekiwane wyniki dla każdego, kto nie może używać powyższych skryptów

• Zwykły tekst

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

Nagrody

Wszystkie odpowiedzi, które oczywiście miały jakąś próbę gry w golfa, które spełniają specyfikację i przejdą wszystkie testy, otrzymają moją opinię. Najkrótsza robocza odpowiedź do 26.01.2012 zostanie zaakceptowana.

Haskell, 223 207 znaków

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

Python (2.x), 382 369 358 338 323 318 znaków

Wszystkie wskazówki i komentarze mile widziane!

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))

Powinny przejść testy w tej formie. Wprowadzanie paszy za pomocą standardowego wejścia, np python shortestroute.py < test.txt.

C: 450 , 437 , 404 , 390 znaków

#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);
}