17
\$\begingroup\$

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.

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

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?)}?' '*
\$\endgroup\$
  • \$\begingroup\$ I didn't realize you could do matrix multiplication in Golfscript! \$\endgroup\$ – migimaru Aug 18 '11 at 12:26
  • \$\begingroup\$ @migimaru, it's a Turing-powerful language, however many shortcomings its array handling may have. \$\endgroup\$ – Peter Taylor Aug 18 '11 at 13:19
  • \$\begingroup\$ That's true. I guess I just didn't expect to see adjacency matrices fit into such a small space ;) \$\endgroup\$ – migimaru Aug 18 '11 at 13:34
  • \$\begingroup\$ @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? \$\endgroup\$ – Gareth Aug 18 '11 at 14:27
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Aug 18 '11 at 14:54
14
\$\begingroup\$

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"]
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice use of recursion here. I also like the trick of giving the function extra arguments just to limit the variables' scope :) \$\endgroup\$ – migimaru Aug 18 '11 at 12:32
  • \$\begingroup\$ @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 :) \$\endgroup\$ – Briguy37 Aug 18 '11 at 13:47
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Very nice use of the splat there. \$\endgroup\$ – migimaru Aug 19 '11 at 12:21
3
\$\begingroup\$

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}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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"
\$\endgroup\$
  • \$\begingroup\$ This doesn't produce any output for me when I run it from the command line in windows or on ideone.com? \$\endgroup\$ – Gareth Aug 24 '11 at 10:20
  • \$\begingroup\$ It works on my computer (windows). I added a usage exemple. I can't get it works on ideone.com though \$\endgroup\$ – Alfwed Aug 24 '11 at 10:39
  • \$\begingroup\$ Ah...that explains it, I was trying to send input through STDIN rather than as arguments. \$\endgroup\$ – Gareth Aug 24 '11 at 11:12
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Sep 28 '11 at 8:07
-1
\$\begingroup\$

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));
                    }
                }

            }

        }
    }

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.