9
1
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.
output the first when sorting all shortest routes lexicographically
- So ifA B D
andA C D
are both valid solutions, outputA B D
instead? – Mr. Llama – 2012-01-12T16:08:47.527@GigaWatt Yes, that's right. – Gareth – 2012-01-12T16:12:55.433
This is awfully close to a duplicate of http://codegolf.stackexchange.com/questions/3474/choose-your-own-adventure
– Peter Taylor – 2012-01-12T16:29:02.8971@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? – Gareth – 2012-01-12T16:45:08.017
@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. – Peter Taylor – 2012-01-12T17:12:11.627
@PeterTaylor Fair enough. A rewrite to weight the edges would take a fair amount of time though, especially re-doing the tests. – Gareth – 2012-01-12T17:26:56.513
D'oh! I forgot that one when I was looking for similar questions. Sorry, GigaWatt. There is none-the less a small difference that arises from the shortes path and lexical sorting conditions. I think it can stay, though as @Peter says weighting is always fun. – dmckee --- ex-moderator kitten – 2012-01-12T17:31:29.403
@dmckee Ok, I'll leave it as it is and accept that people may ignore it as a duplicate. I'll come up with a weighted graph question next time if no-one beats me to it. – Gareth – 2012-01-12T18:42:43.670
test cases seem to have problem, in testcase#2, J->A->I is a path, while you marked "J B I" as the answer. – Ali1S232 – 2012-01-13T01:51:06.167
@Gajet Okay, fixed it. Doing it by hand is no match for getting a program to do it for you. :-) – Gareth – 2012-01-13T08:22:07.320