Kota asal saya, Rhyl , memiliki sistem lalu lintas satu arah yang tampaknya telah dirancang untuk menjauhkan orang dari tujuan mereka selama mungkin. Tugas Anda, jika Anda memilih untuk mencobanya, adalah menghasilkan program untuk memberikan rute terpendek melalui sistem lalu lintas tersebut.

Memasukkan

Input akan aktif STDIN, dan akan menjadi daftar titik awal dan akhir diikuti oleh baris kosong diikuti oleh daftar pertanyaan, sebagai berikut:

A B
B A
B C
C D
D C

A D
C A
B A

Setiap jalan hanya dapat dilalui dengan arah yang diberikan, jadi, dalam contoh di atas jalan A - B adalah jalan dua arah sedangkan B - C adalah jalan satu arah dari B ke C. Bepergian dari C ke B terlarang.

Titik awal dan akhir semua akan diwakili oleh satu huruf besar.

Keluaran

Output harus menjadi rute terpendek (diukur dengan jumlah titik yang dikunjungi) dari titik awal yang diberikan ke titik akhir yang diberikan untuk setiap permintaan yang diterima. Jika tidak ada rute seperti itu, output baris kosong. Jika ada lebih dari satu rute terpendek, hasilkan yang pertama saat mengurutkan semua rute terpendek secara leksikografis.

Untuk contoh di atas, hasilnya adalah:

A B C D

B A

Tes Script

Seperti sebelumnya saya memberikan tes untuk tugas ini berdasarkan pada skrip yang ditulis oleh Joey dan Ventero : -

• Pesta
• PowerShell

dan juga tes dan output yang diharapkan untuk siapa saja yang tidak dapat menggunakan skrip di atas

• Teks biasa

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

Hadiah

Semua jawaban yang jelas-jelas telah mencoba golf yang memenuhi spesifikasi dan lulus semua tes akan mendapatkan upvote saya. Jawaban kerja terpendek pada 26/01/2012 akan diterima.

Haskell, 223 207 karakter

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 karakter

Semua tips dan komentar diterima!

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

Harus lulus tes dalam formulir ini. Masukan umpan melalui stdin, mis python shortestroute.py < test.txt.

C: 450 , 437 , 404 , 390 karakter

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