Choose Your Own Adventure-Bücher sind eine Form interaktiver Literatur, bei der der Leser Entscheidungen treffen muss, die sich auf das Ergebnis der Geschichte auswirken. An bestimmten Stellen in der Geschichte stehen dem Leser mehrere Optionen zur Verfügung, von denen jede den Leser auf eine andere Seite im Buch weiterleitet.

In einer Fantasy-Umgebung muss man sich beispielsweise auf Seite 14 entscheiden, ob man sich in eine mysteriöse Höhle wagt, indem man zu Seite 22 "springt" oder den nahe gelegenen Wald erkundet, indem man zu Seite 8 springt. Diese "Sprünge" können ausgedrückt werden als Seitenzahlenpaare, wie folgt:

14 22
14 8

In den meisten Fällen gibt es viele Enden der Geschichte, aber nur wenige gute. Das Ziel ist es, durch die Geschichte zu navigieren, um ein gutes Ende zu erreichen.

Aufgabe:

Mit einer Liste von "Sprüngen" für ein bestimmtes Buch müssen Sie eine Route ermitteln, die zu einem bestimmten Ende führt. Da dies ziemlich einfach ist, besteht die wahre Herausforderung darin, so wenig Zeichen wie möglich zu verwenden.

Das ist Code Golf .

Beispieleingabe (wobei 1 der Anfang und 100 das Ziel ist):

1 10
10 5
10 13
5 12
5 19
13 15
12 20
15 100

Beispielausgabe:

1 10 13 15 100

Beispieleingabe:

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

Beispielausgabe:

1 15 2 12 80 100

Anmerkungen:

• Die Liste der Sprünge wird vom Benutzer entweder aus einer Datei oder von stdin eingegeben. Sie können wählen, was am bequemsten ist.
• Die Eingabe enthält 1 Sprung pro Zeile, wobei Ursprung und Ziel durch ein einzelnes Leerzeichen getrennt sind.
• Es wird nicht garantiert, dass sich die Zeilen in der Eingabe in einer bestimmten Reihenfolge befinden.
• Ein erfolgreicher Pfad beginnt auf Seite 1 und endet auf Seite 100.
• Sie können davon ausgehen, dass mindestens 1 Pfad zum Ziel vorhanden ist. Sie müssen nicht alle Pfade finden und auch nicht die kürzesten. Finde einfach mindestens einen.
• Die kleinste Seitenzahl ist 1. Die größte Seitenzahl ist unbegrenzt. (Sie können davon ausgehen, dass es in den Bereich eines Int. Passt.)
• Möglicherweise sind Schleifen vorhanden. Beispielsweise kann die Liste Sprünge von Seite 5 bis 10, 10 bis 19 und 19 bis 5 aufweisen.
• Es kann Sackgassen geben. Das heißt, auf eine Zielseite kann möglicherweise nirgendwo gesprungen werden.
• Umgekehrt sind möglicherweise nicht erreichbare Seiten vorhanden. Das heißt, eine Ursprungsseite ist möglicherweise nicht das Ziel von Sprüngen.
• Es wird garantiert, dass nicht alle Seitenzahlen zwischen 1 und 100 verwendet werden.
• Ihre Ausgabe sollte aus einer gültigen Route von Seitenzahlen bestehen, die mit 1 beginnen und mit 100 enden, getrennt durch Leerzeichen.

Denken Sie daran, dies ist Codegolf, also gewinnt die kürzeste Lösung!

BEARBEITEN: Ein weiteres Beispiel zum Testen hinzugefügt.

Golfscript, 58 57 Zeichen

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

Achtung : das ist super ineffizient. Es funktioniert, indem die Adjazenzmatrix wiederholt quadriert und dann nach einer Route gesucht wird. Wenn Edas Diagramm Kanten enthält, werden alle Pfade mit einer Länge von bis zu 2 ^{E gefunden} (und die kürzeren werden häufig gefunden). Es sollte Ihnen in angemessener Zeit ein Ergebnis für den ersten Testfall liefern, aber wenn Sie den zweiten Testfall ausprobieren möchten, stellen Sie sicher, dass Sie ein paar Gigs Speicherplatz frei haben und einen langen Spaziergang machen.

Wenn Sie eine einigermaßen effiziente Lösung suchen, biete ich bei 67 Zeichen:

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

Python, 232 213 157 143 135 132 Zeichen (kürzester Weg)

Diese Implementierung kann alle beschriebenen Randfälle (Schleifen, Sackgassen, verwaiste Seiten usw.) verarbeiten und garantiert, dass der kürzeste Weg zum Ende gefunden wird. Es basiert auf dem kürzesten Weg-Algorithmus von Djikstra.

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 Zeichen

Dies ist eine rekursive Lösung, die den kürzesten Weg durch das Abenteuer findet.

Code-Golf:

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)

Zum Testen ( WARNUNG: Endlosschleife für schlechte Eingabe! ):

1. Kopieren Sie eine der folgenden Eingabezeichenfolgen (oder verwenden Sie ein ähnliches Format, um Ihre eigenen auszuwählen, und wählen Sie Ihr eigenes Abenteuer aus):

   • 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 , die in die Test Geige ‚s prompt.

Formatierter und kommentierter 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);

Zum Testen ( WARNUNG: Endlosschleife für schlechte Eingabe! ):

1. Kopieren Sie eine der folgenden Eingabezeichenfolgen (oder verwenden Sie ein ähnliches Format, um Ihre eigenen auszuwählen, und wählen Sie Ihr eigenes Abenteuer aus):

   • 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 , die in die Test Geige ‚s prompt.

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

Perl, 88 Zeichen

im Grunde eine perlisierte Version von Clueless 'Eintrag; Vor- und Nachspiele machen Spaß :)

@t=<>;%s=(100,100);until($s{1}){for(@t){chomp;/ /;$s{$`}="$` $s{$'}"if$s{$'}}}print$s{1}

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,[])

Leider ist diese schwanzrekursive Lösung anfällig für Schleifen in der "Geschichte" ...

Verwendung : cat ./test0 | ./sol.py Ausgabe für Testfall 1:

1 10 13 15 100

Ausgabe für Testfall 2:

1 15 2 12 80 100

Scala 2.9, 260 256 254 252 248 247 241 239 234 227 225 212 205 Zeichen

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

Verwendung:

Kompiliere mit scalac filenameund starte mit scala C. Die Eingabe erfolgt über STDIN.
Wechseln Sie object C extends Appzur Ausführung auf ideone.com zu object Main extends ApplicationScala 2.8.

PHP, 166 146 138 Zeichen

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

Verwendung :

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

Ich würde alle in ein 2D-Array einfügen und alle Elemente mit mehreren Schleifen durchsuchen. Wenn sie das letzte Element erreichen können, würde ich verwandte Elemente in einem anderen Ergebnis-Array sammeln und aus den Ergebnissen ein Array auswählen, das kleiner ist .

BEARBEITEN => JAVA: Ich habe auch rekursive Funktion verwendet, vollständiger Code unten;

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

            }

        }
    }

}