Meine Heimatstadt Rhyl verfügt über ein Einbahnstraßensystem, das anscheinend so konzipiert ist, dass die Menschen so lange wie möglich von ihrem Ziel ferngehalten werden. Ihre Aufgabe ist es, ein Programm zu erstellen, das den kürzesten Weg durch ein solches Verkehrssystem bietet, falls Sie es versuchen möchten.

Eingang

Die Eingabe ist aktiviert STDINund enthält eine Liste der Start- und Endpunkte, gefolgt von einer leeren Zeile gefolgt von einer Liste der Abfragen wie folgt:

A B
B A
B C
C D
D C

A D
C A
B A

Jede Straße kann nur in der / den angegebenen Richtung (en) befahren werden. Im obigen Beispiel ist die Straße A - B eine Einbahnstraße, während B - C eine Einbahnstraße von B nach C ist. Fahren von C nach B. ist verboten.

Start- und Endpunkte werden alle durch einen einzigen Großbuchstaben dargestellt.

Ausgabe

Die Ausgabe sollte für jede empfangene Abfrage die kürzeste Route (gemessen an der Anzahl der besuchten Punkte) vom angegebenen Startpunkt zum angegebenen Endpunkt sein. Wenn keine solche Route vorhanden ist, geben Sie eine leere Zeile aus. Wenn mehr als eine kürzeste Route vorhanden ist, geben Sie die erste aus, wenn Sie alle kürzesten Routen lexikografisch sortieren.

Für das obige Beispiel wäre die Ausgabe:

A B C D

B A

Testskripte

Nach wie vor biete ich Tests für diese Aufgabe an, die auf Skripten von Joey und Ventero basieren : -

• Bash
• Power Shell

und auch Tests und erwartete Ausgabe für alle, die die oben genannten Skripte nicht verwenden können

• Klartext

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

Belohnung

Alle Antworten, bei denen offensichtlich versucht wurde, Golf zu spielen, die der Spezifikation entsprechen und alle Tests bestehen, werden positiv bewertet. Die kürzeste Arbeitsantwort bis zum 26.01.2012 wird akzeptiert.

Haskell, 223 207 Zeichen

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 Zeichen

Alle Tipps und Kommentare sind willkommen!

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

Sollte die Tests in dieser Form bestehen. Feed-Eingabe über stdin, z python shortestroute.py < test.txt.

C: 450 , 437 , 404 , 390 Zeichen

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