Choisissez vos propres livres d'aventure sont une forme de littérature interactive où le lecteur doit prendre des décisions qui affectent le résultat de l'histoire. À certains moments de l'histoire, le lecteur a plusieurs options qui peuvent être choisies, chacune envoyant le lecteur vers une page différente du livre.

Par exemple, dans un cadre fantastique, on pourrait avoir à décider à la page 14 s'il faut s'aventurer dans une grotte mystérieuse en "sautant" à la page 22, ou pour explorer la forêt voisine en sautant à la page 8. Ces "sauts" peuvent être exprimés sous forme de paires de numéros de page, comme ceci:

14 22
14 8

Dans la plupart des cas, il y a de nombreuses fins à l'histoire, mais seulement quelques bonnes. L'objectif est de naviguer dans l'histoire pour arriver à une bonne fin.

Tâche:

Étant donné une liste de «sauts» pour un livre donné, votre tâche est de déterminer un itinéraire qui mènera à une fin spécifique. Comme c'est assez facile, le vrai défi est de le faire avec le moins de caractères possible.

C'est le golf de code .

Exemple d'entrée (où 1 est le début et 100 est l'objectif):

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

Exemple de sortie:

1 10 13 15 100

Exemple d'entrée:

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

Exemple de sortie:

1 15 2 12 80 100

Remarques:

• La liste des sauts sera saisie par l'utilisateur, soit à partir d'un fichier, soit de stdin. Vous pouvez choisir celui qui vous convient le mieux.
• L'entrée contiendra 1 saut par ligne, avec l'origine et la destination séparées par un seul espace.
• Il n'est pas garanti que les lignes de l'entrée soient dans un ordre spécifique.
• Un chemin réussi commencera à la page 1 et se terminera à la page 100.
• Vous pouvez supposer qu'il existe au moins 1 chemin vers l'objectif. Vous n'avez pas besoin de trouver tous les chemins, ni de trouver le plus court. Trouvez-en au moins un.
• Le plus petit numéro de page sera 1. Il n'y a pas de limite au plus grand numéro de page. (Vous pouvez supposer qu'il rentrera dans la plage d'un int.)
• Des boucles peuvent exister. Par exemple, la liste peut contenir des sauts des pages 5 à 10, 10 à 19 et 19 à 5.
• Il peut y avoir des impasses. Autrement dit, une page de destination peut ne pas avoir de destination.
• Inversement, il peut y avoir des pages inaccessibles. Autrement dit, une page d'origine peut ne pas être la destination de sauts.
• Tous les numéros de page entre 1 et 100 ne sont pas garantis pour être utilisés.
• Votre sortie doit consister en un itinéraire valide de numéros de page, commençant par 1 et se terminant à 100, séparés par des espaces.

N'oubliez pas qu'il s'agit de code golf, donc la solution la plus courte l'emporte!

EDIT: Ajout d'un autre échantillon pour les tests.

Golfscript, 58 57 caractères

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

Attention : c'est super-inefficace. Il fonctionne en quadrillant la matrice d'adjacence à plusieurs reprises, puis en recherchant un itinéraire; s'il y a des Ebords dans le graphique, il trouvera tous les chemins de longueur jusqu'à 2 ^E (et les plus courts, il trouvera beaucoup de fois). Il devrait vous donner un résultat pour le premier cas de test dans un délai raisonnable, mais si vous voulez essayer le second, assurez-vous que vous avez quelques Go de mémoire libre et faites une longue marche.

Si vous voulez une solution raisonnablement efficace, je propose à 67 caractères:

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

Python, 232 213 157 157 143 135 132 caractères (chemin le plus court)

Cette implémentation peut gérer tous les cas marginaux décrits (boucles, impasses, pages orphelines, etc.) et garantit qu'elle trouvera le chemin le plus court vers la fin. Il est basé sur l'algorithme de chemin le plus court de 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 caractères

Il s'agit d'une solution récursive qui trouve le chemin le plus court dans l'aventure.

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)

Pour tester ( ATTENTION: boucle infinie pour mauvaise entrée! ):

1. Copiez l'une des chaînes de saisie suivantes (ou utilisez un format similaire pour choisir la vôtre, choisissez votre propre aventure):

   • 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. Collez-le dans l' invite du violon de test .

Code formaté et commenté:

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

Pour tester ( ATTENTION: boucle infinie pour mauvaise entrée! ):

1. Copiez l'une des chaînes de saisie suivantes (ou utilisez un format similaire pour choisir la vôtre, choisissez votre propre aventure):

   • 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. Collez-le dans l' invite du violon de test .

Rubis 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]

Non golfé:

$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 caractères

essentiellement une version améliorée de l'entrée de Clueless; les pré-matchs et les post-matchs sont amusants :)

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

malheureusement, cette solution récursive de queue est vulnérable aux boucles de "l'histoire" ...

Utilisation : cat ./test0 | ./sol.py Sortie pour le cas de test 1:

1 10 13 15 100

Sortie pour le cas de test 2:

1 15 2 12 80 100

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

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

Non golfé:

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:

Compilez avec scalac filenameet exécutez avec scala C. L'entrée est prise via STDIN.
Pour exécuter sur ideone.com, passez object C extends Appà object Main extends Applicationpour l'exécuter en tant que Scala 2.8.

PHP, 166 146 138 caractères

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

Non golfé:

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

Utilisation:

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

Je les mettrais tous dans un tableau 2D et rechercherais tous les éléments avec plusieurs boucles, s'ils peuvent atteindre le dernier élément, je collecterais les éléments associés dans un autre tableau de résultats, et à partir des résultats, je choisirais un tableau dont l'un est plus petit .

EDIT => JAVA: J'ai également utilisé la fonction récursive, le code complet ci-dessous;

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

            }

        }
    }

}