17
1
Choose Your Own Adventure books are a form of interactive literature where the reader must make decisions that affect the outcome of the story. At certain points in the story, the reader has multiple options that can be chosen, each sending the reader to a different page in the book.
For example, in a fantasy setting, one might have to decide on page 14 whether to venture into a mysterious cave by "jumping" to page 22, or to explore the nearby forest by jumping to page 8. These "jumps" can be expressed as pairs of page numbers, like so:
14 22
14 8
In most cases, there are many endings to the story but only a few good ones. The goal is to navigate the story to reach a good ending.
Task:
Given a list of "jumps" for a given book, your task is to determine a route that will lead to a specific ending. Since this is fairly easy, the true challenge is to do it in as few characters as possible.
This is code golf.
Sample input (where 1 is the start and 100 is the goal):
1 10
10 5
10 13
5 12
5 19
13 15
12 20
15 100
Sample output:
1 10 13 15 100
Sample input:
15 2
1 4
2 12
1 9
3 1
1 15
9 3
12 64
4 10
2 6
80 100
5 10
6 24
12 80
6 150
120 9
150 120
Sample output:
1 15 2 12 80 100
Notes:
- The list of jumps will be input by the user, either from a file or stdin. You may choose whichever is most convenient.
- The input will contain 1 jump per line, with the origin and destination separated by a single space.
- The lines in the input are not guaranteed to be in any specific order.
- A successful path will start at page 1 and end at page 100.
- You may assume there is at least 1 path to the goal. You do not need to find all paths, nor do you need to find the shortest. Just find at least one.
- The smallest page number will be 1. There is no limit to the largest page number. (You can assume that it will fit in the range of an int.)
- Loops may exist. For example, the list may have jumps from page 5 to 10, 10 to 19, and 19 to 5.
- There may be dead-ends. That is, a destination page might not have anywhere to jump to.
- Conversely, there may be unreachable pages. That is, an origin page might not be the destination of any jumps.
- Not all page numbers between 1 and 100 are guaranteed to be used.
- Your output should consist of a valid route of page numbers, starting with 1 and ending at 100, separated by spaces.
Remember, this is code golf, so the shortest solution wins!
EDIT: Added another sample for testing.
1Can we assume that there are no jumps from page 100? – Peter Taylor – 2011-08-17T19:44:16.520
Yes, you may assume that. – migimaru – 2011-08-17T23:19:56.380
i have a feeling that something like lisp or alloy could accomplish this in very few chars, i will attempt it later when i get off work. – JoséNunoFerreira – 2011-09-28T13:46:21.037