I am a teacher who was given a problem a few years ago. Every year since I have given it to my advanced students as a bonus assignment, but in ~10 years only 8 solved it, each with a slightly different approach. The problem is as follows:
You have some input (from stdin), in the following format (the //comments are not included in the input):
6 //Route Begin 1 2 //Route data... 1 3 3 4 3 5 4 6 5 6 2 3 2 4 0 0 //Route end 4 //Route Begin 2 3 //Route Data... 3 4 5 1 1 6 7 8 8 9 2 5 5 7 3 1 1 8 4 6 6 9 0 0 //Route end // continued... The input begins with the destination, an integer. It is followed by a 'map' of all streets in the city. Each line represents a connection, so you can get from street 1 to street 2, and vice-versa. On every rout you start at street 1, then work your way to your destination.
The objective: List all possible routes, and tell the user the shortest one (least amount of street changes). Also, the code beads to be human readable. So you would wont to output something like:
Destination 1 (6): 1 2 3 4 6 1 2 3 5 6 1 2 4 3 5 6 1 2 4 6 1 3 2 4 6 1 3 4 6 1 3 5 6 There are 7 routes from the firetruck station to street 6. The shortest of these is the route "1 2 4 6", with 4 streets. Destination 2 (4): 1 3 2 5 7 8 9 6 4 1 3 4 1 5 2 3 4 1 5 7 8 9 6 4 1 6 4 1 6 9 8 7 5 2 3 4 1 8 7 5 2 3 4 1 8 9 6 4 There are 8 routes from the firetruck station to street 4. The shortest of these is the route "1 3 4", with 3 streets. Now personally, I rather java or python (and java is preferred more), but I leave this open ended to my students, so they can choose any language they like.
The original document is here
HOW TO WIN: Create the described program in a readable programming language, with the following criteria:
- Readable
- takes the input from the user(stdin/file)
- Is mildly easy to understand.