Choose Your Own Adventure

Question

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.

Answer 1

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 2^E (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?)}?' '*

Answer 2

Python, 232 213 157 143 135 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"]

Answer 3

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
alert(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.

Answer 4

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
                # jump to the second page in the line
                f *path, to
            end
        end
    end
end

Answer 5

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}

Answer 6

Python - 239 237 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

Answer 7

Scala 2.9, 260 256 254 252 248 247 241 239 234 227 225 212 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.

Answer 8

PHP, 166 146 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"

Answer 9

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.FileReader;
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
        BufferedReader in = new BufferedReader(new FileReader("list.txt"));
        ArrayList<String> s = new ArrayList<String>();
        String line = null; 
        while ((line = in.readLine()) != null){s.add(line);}
        c.add(new ArrayList<String>());
            //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){
                    c.get(x).add(list.get(i));
                    if(b==dest){
                        c.add(new ArrayList<String>());
                        x++;
                    }else{
                        checkPages(i, list, b,dest);
                        c.get(x).remove(list.get(i));
                    }
                }

            }

        }
    }

}