Mi ciudad natal, Rhyl , tiene un sistema de tráfico unidireccional que parece haber sido diseñado para mantener a las personas lejos de su destino el mayor tiempo posible. Su tarea, si elige intentarlo, es producir un programa para dar la ruta más corta a través de dicho sistema de tráfico.

Entrada

La entrada estará activada STDIN, y será una lista de puntos de inicio y finalización seguida de una línea en blanco seguida de una lista de consultas, de la siguiente manera:

A B
B A
B C
C D
D C

A D
C A
B A

Cada camino solo se puede recorrer en la (s) dirección (es) dada (s), por lo tanto, en el ejemplo anterior, el camino A - B es una calle de doble sentido, mientras que B - C es una calle de un solo sentido de B a C. Viajar de C a B esta prohibido.

Los puntos de inicio y fin estarán representados por una sola letra mayúscula.

Salida

La salida debe ser la ruta más corta (medida por el número de puntos visitados) desde el punto de inicio dado hasta el punto final dado para cada consulta recibida. Si no existe tal ruta, muestre una línea en blanco. Si existe más de una ruta más corta, envíe la primera al ordenar todas las rutas más cortas lexicográficamente.

Para el ejemplo anterior, la salida sería:

A B C D

B A

Scripts de prueba

Como antes, proporciono pruebas para esta tarea basadas en scripts escritos por Joey y Ventero :

• Golpetazo
• Potencia Shell

y también pruebas y resultados esperados para cualquiera que no pueda usar los scripts anteriores

• Texto sin formato

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

Recompensas

Todas las respuestas que obviamente han tenido algún intento de golf que cumplan con las especificaciones y pasen todas las pruebas obtendrán mi voto positivo. Se aceptará la respuesta de trabajo más breve antes del 26/01/2012.

Haskell, 223 207 caracteres

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 caracteres

Todos los consejos y comentarios son bienvenidos!

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

Debe pasar las pruebas en este formulario. Alimentación de entrada a través de stdin, por ejemplo python shortestroute.py < test.txt.

C: 450 , 437 , 404 , 390 caracteres

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