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


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.

• Can we assume that there are no jumps from page 100? – Peter Taylor Aug 17 '11 at 19:44
• Yes, you may assume that. – migimaru Aug 17 '11 at 23:19
• 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 Sep 28 '11 at 13:46

### Golfscript, 58 57 chars

~]2/.,{:A{){=}+{0=}\+A\,\{\+}+/}/]A+}*{)100=\0=1=*}?' '*


Warning: this is super-inefficient. It works by repeatedly squaring the adjacency matrix and then looking for a route; if there are E edges in the graph then it will find every path of length up to 2E (and the shorter ones it will find lots of times). It should give you a result for the first test case in a reasonable time, but if you want to try the second one make sure that you've got a few gigs of memory free and go for a long walk.

If you want a reasonably efficient solution then I offer at 67 chars:

~]2/:A,[1]]({A{{{?)}+1$\,,}%~!*},{({\-1==}+2$?\[+]+}/}*{100?)}?' '*

• I didn't realize you could do matrix multiplication in Golfscript! – migimaru Aug 18 '11 at 12:26
• @migimaru, it's a Turing-powerful language, however many shortcomings its array handling may have. – Peter Taylor Aug 18 '11 at 13:19
• That's true. I guess I just didn't expect to see adjacency matrices fit into such a small space ;) – migimaru Aug 18 '11 at 13:34
• @Peter Sorry, I tried running this with cat input | ruby1.9 golfscript.rb peter.gs and all that happened was my MacBook got really hot. How should I run it? – Gareth Aug 18 '11 at 14:27
• @Gareth, yep. When I killed it after half an hour, it was up to 2GB of memory. I'll make the warning a bit more explicit. – Peter Taylor Aug 18 '11 at 14:54

## Python, 232213157143135 132 chars (shortest path)

This implementation can handle all of the edge cases described (loops, dead ends, orphan pages etc.) and guarantees that it will find the shortest route to the ending. It is based on Djikstra's shortest path algorithm.

import sys
l=[k.split()for k in sys.stdin]
s={"100":"100"}
while"1"not in s:
for i,j in l:
if j in s:s[i]=i+" "+s[j]
print s["1"]


## Javascript: 189 Characters

This is a recursive solution that finds the shortest path through the adventure.

Code-Golfed:

a=prompt().split('\\n');b=0;while(!(d=c(b++,1)));function c(e,f,i,g){if(e>0)for(i=0;h=a[i++];){g=h.split(' ');if(g[0]==f){if(g[1]==100)return h;if(j=c(e-1,g[1]))return g[0]+' '+j}}}alert(d)


To test (WARNING: infinite loop for bad input!):

1. Copy one of the following input strings (or use a similar format to choose your own choose your own adventure):

• 1 10\n10 5\n10 13\n5 12\n5 19\n13 15\n12 20\n15 100
• 15 2\n1 4\n2 12\n1 9\n3 1\n1 15\n9 3\n12 64\n4 10\n2 6\n80 100\n5 10\n6 24\n12 80\n6 150\n120 9\n150 120
2. Paste that into the test fiddle's prompt.

Formatted and Commented code:

//Get Input from user
inputLines = prompt().split('\\n');

//Starting at 0, check for solutions with more moves
moves = 0;
while (!(solution = getSolution(moves++, 1)));

/**
* Recursive function that returns the moves string or nothing if no
* solution is available.
*
* @param numMoves - number of moves to check
* @param startPage - the starting page to check
* @param i - A counter.  Only included to make this a local variable.
* @param line - The line being tested.  Only included to make this a local variable.
*/
function getSolution(numMoves, startPage, i, line) {
//Only check for solutions if there are more than one moves left
if (numMoves > 0) {
//Iterate through all the lines
for (i=0; text = inputLines[i++];) {
line = text.split(' ');
//If the line's start page matches the current start page
if (line[0] == startPage) {
//If the goal page is the to page return the step
if (line[1] == 100) {
return text;
}
//If there is a solution in less moves from the to page, return that
if (partialSolution = getSolution(numMoves - 1, line[1])) {
return line[0] + ' ' + partialSolution;
}
}
}
}
}

//Output the solution


To test (WARNING: infinite loop for bad input!):

1. Copy one of the following input strings (or use a similar format to choose your own choose your own adventure):

• 1 10\n10 5\n10 13\n5 12\n5 19\n13 15\n12 20\n15 100
• 15 2\n1 4\n2 12\n1 9\n3 1\n1 15\n9 3\n12 64\n4 10\n2 6\n80 100\n5 10\n6 24\n12 80\n6 150\n120 9\n150 120
2. Paste that into the test fiddle's prompt.

• Nice use of recursion here. I also like the trick of giving the function extra arguments just to limit the variables' scope :) – migimaru Aug 18 '11 at 12:32
• @migimaru: Thanks! A related side note: This problem was a bugger to debug until I learned that JavaScript variables without the var keyword have global scope :) – Briguy37 Aug 18 '11 at 13:47

## Ruby 1.9, 98

j=$<.map &:split f=->*p,c{c=='100'?abort(p*' '):j.map{|a,b|a==c&&!p.index(b)&&f[*p,b,b]}} f[?1,?1]  Ungolfed: $lines = $<.map &:split def f (*path) if path[-1] == '100' # story is over abort path.join ' ' # print out the path and exit else # for each jump from the current page$lines.each do |from, to|
if from == path[-1] && !path.include?(to) # avoid loops
f *path, to
end
end
end
end

• Very nice use of the splat there. – migimaru Aug 19 '11 at 12:21

## Perl, 88 chars

basically a perlized version of Clueless' entry; pre-matches and post-matches are fun :)

@t=<>;%s=(100,100);until($s{1}){for(@t){chomp;/ /;$s{$}="$ $s{$'}"if$s{$'}}}print$s{1}  # Python - 239237 236 import sys global d d={} for i in sys.stdin: a,b=[int(c) for c in i.split(' ')] try: d[b]+=[a] except: d[b]=[a] def f(x,h): j=h+[x] if x==1: print ''.join([str(a)+" " for a in j[::-1]]) exit() for i in d[x]: f(i,j) f(100,[])  unfortunately, this tail-recursive solution is vulnerable to loops in the "story"... Usage: cat ./test0 | ./sol.py Output for test case 1: 1 10 13 15 100  Output for test case 2: 1 15 2 12 80 100  ## Scala 2.9, 260256254252248247241239234227225212 205 characters object C extends App{var i=io.Source.stdin.getLines.toList.map(_.split(" ")) def m(c:String):String=(for(b<-i)yield if(b(1)==c)if(b(0)!="1")m(b(0))+" "+b(0)).filter(()!=).mkString print(1+m("100")+" 100")}  Ungolfed: object Choose extends App { var input=io.Source.stdin.getLines.toList.map(_.split(" ")) def findroute(current:String):String= ( for(branch<-input) yield if(branch(1)==current) if(branch(0)!="1")findroute(branch(0))+" "+branch(0) ).filter(()!=).mkString print(1+findroute("100")+" 100") }  Usage: Compile with scalac filename and run with scala C. Input is taken via STDIN. To run on ideone.com, change object C extends App to object Main extends Application to run it as Scala 2.8. ## PHP, 166146 138 chars $a[]=100;while(1<$c=$a[0])for($i=1;$i<$argc;$i++){list($p,$q)=explode(' ',$argv[$i]);if($q==$c)array_unshift($a,$p);}echo implode(' ',$a);  Ungolfed : $a[]=100;
while(1<$c=$a[0])
for($i=1;$i<$argc;$i++){
list($p,$q)=explode(' ',$argv[$i]);
if($q==$c)array_unshift($a,$p);
}
echo implode(' ',\$a);


Usage :

php golf.php "1 10" "10 5" "10 13" "5 12" "5 19" "13 15" "12 20" "15 100"

• This doesn't produce any output for me when I run it from the command line in windows or on ideone.com? – Gareth Aug 24 '11 at 10:20
• It works on my computer (windows). I added a usage exemple. I can't get it works on ideone.com though – Alfwed Aug 24 '11 at 10:39
• Ah...that explains it, I was trying to send input through STDIN rather than as arguments. – Gareth Aug 24 '11 at 11:12
• User genesis φ proposed an edit to correct the character count. It might be worth putting a golfed version without whitespace before the ungolfed version, to meet people's expectations of the local convention. – Peter Taylor Sep 28 '11 at 8:07

I would put all of them into a 2d array and search all items with multiple loop, if they can reach the last item then I would collect related items in order into another results array, and from results I would choose an array which one is smaller.

EDIT => JAVA:I have also used recursive function, full code below;

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
public class Jumper {
static int x = 0;
public static ArrayList<ArrayList<String>> c = new ArrayList<ArrayList<String>>();
public static void main(String[] args) throws IOException {
//Read from line and parse into array
ArrayList<String> s = new ArrayList<String>();
String line = null;
//When you get all items forward to method
checkPages(0, s,Integer.parseInt(s.get(0).split(" ")[0]),Integer.parseInt(s.get(s.size()-1).split(" ")[1]));
}

public static void checkPages (int level,ArrayList<String> list,int from, int dest){
if(level <= list.size()){
for(int i=level;i<list.size();i++){
int a = Integer.parseInt(list.get(i).split(" ")[0]);
int b = Integer.parseInt(list.get(i).split(" ")[1]);
if(a == from){
if(b==dest){
x++;
}else{
checkPages(i, list, b,dest);
c.get(x).remove(list.get(i));
}
}

}

}
}

}
`
• This is code-golf, so you need to provide an implementation. – Gareth Sep 9 '11 at 14:37
• Hi Gareth, I should leave now I will add asap when I arrive to home. – burak Sep 9 '11 at 15:35