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.
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
1 10 13 15 100
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
1 15 2 12 80 100
- 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.