Los libros Choose Your Own Adventure son una forma de literatura interactiva donde el lector debe tomar decisiones que afectan el resultado de la historia. En ciertos puntos de la historia, el lector tiene múltiples opciones que se pueden elegir, cada una de las cuales envía al lector a una página diferente del libro.

Por ejemplo, en un entorno de fantasía, uno debería decidir en la página 14 si aventurarse en una cueva misteriosa "saltando" a la página 22, o explorar el bosque cercano saltando a la página 8. Estos "saltos" se pueden expresar como pares de números de página, así:

14 22
14 8

En la mayoría de los casos, la historia tiene muchos finales pero solo unos pocos buenos. El objetivo es navegar por la historia para llegar a un buen final.

Tarea:

Dada una lista de "saltos" para un libro dado, su tarea es determinar una ruta que conduzca a un final específico. Como esto es bastante fácil, el verdadero desafío es hacerlo en la menor cantidad de caracteres posible.

Este es el código de golf .

Entrada de muestra (donde 1 es el comienzo y 100 es el objetivo):

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

Salida de muestra:

1 10 13 15 100

Entrada de muestra:

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

Salida de muestra:

1 15 2 12 80 100

Notas:

• La lista de saltos será ingresada por el usuario, ya sea desde un archivo o stdin. Puede elegir el que sea más conveniente.
• La entrada contendrá 1 salto por línea, con el origen y el destino separados por un solo espacio.
• No se garantiza que las líneas en la entrada estén en ningún orden específico.
• Una ruta exitosa comenzará en la página 1 y finalizará en la página 100.
• Puede suponer que hay al menos 1 camino hacia la meta. No necesita encontrar todos los caminos, ni tampoco encontrar el más corto. Solo encuentra al menos uno.
• El número de página más pequeño será 1. No hay límite para el número de página más grande. (Puede suponer que encajará en el rango de un int.)
• Los lazos pueden existir. Por ejemplo, la lista puede tener saltos de la página 5 a la 10, de la 10 a la 19 y de la 19 a la 5.
• Puede haber callejones sin salida. Es decir, una página de destino podría no tener un lugar al que saltar.
• Por el contrario, puede haber páginas inalcanzables. Es decir, una página de origen podría no ser el destino de ningún salto.
• No se garantiza el uso de todos los números de página entre 1 y 100.
• Su salida debe consistir en una ruta válida de números de página, comenzando con 1 y terminando en 100, separados por espacios.

Recuerde, este es el código de golf, por lo que gana la solución más corta.

EDITAR: se agregó otra muestra para probar.

Golfscript, 58 57 caracteres

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

Advertencia : esto es super ineficiente. Funciona cuadrando repetidamente la matriz de adyacencia y luego buscando una ruta; Si hay Ebordes en el gráfico, encontrará cada ruta de longitud hasta 2 ^E (y las más cortas encontrará muchas veces). Debería darte un resultado para el primer caso de prueba en un tiempo razonable, pero si quieres probar el segundo, asegúrate de tener algunos conciertos libres de memoria y dar un largo paseo.

Si desea una solución razonablemente eficiente, entonces ofrezco en 67 caracteres:

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

Python, 232 213 157 143 135 132 caracteres (ruta más corta)

Esta implementación puede manejar todos los casos límite descritos (bucles, callejones sin salida, páginas huérfanas, etc.) y garantiza que encontrará la ruta más corta hasta el final. Se basa en el algoritmo de ruta más corta 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 caracteres

Esta es una solución recursiva que encuentra el camino más corto a través de la aventura.

Código de 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)

Para probar ( ADVERTENCIA: bucle infinito para entradas incorrectas ):

1. Copie una de las siguientes cadenas de entrada (o use un formato similar para elegir el suyo, elija su propia aventura):

   • 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. Pegue eso en el indicador del violín de prueba .

Código formateado y comentado:

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

Para probar ( ADVERTENCIA: bucle infinito para entradas incorrectas ):

1. Copie una de las siguientes cadenas de entrada (o use un formato similar para elegir el suyo, elija su propia aventura):

   • 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. Pegue eso en el indicador del violín de prueba .

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]

Sin 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 caracteres

básicamente una versión perlizada de la entrada de Clueless; los partidos previos y posteriores son divertidos :)

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

desafortunadamente, esta solución recursiva de cola es vulnerable a los bucles en la "historia" ...

Uso : cat ./test0 | ./sol.py Salida para el caso de prueba 1:

1 10 13 15 100

Salida para el caso de prueba 2:

1 15 2 12 80 100

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

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

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

Uso:

Compilar scalac filenamey ejecutar con scala C. La entrada se toma vía STDIN.
Para ejecutar en ideone.com, cambie object C extends Appa object Main extends Applicationpara ejecutarlo como Scala 2.8.

PHP, 166 146 138 caracteres

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

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

Uso:

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

Los pondría a todos en una matriz 2d y buscaría todos los elementos con múltiples ciclos, si pueden alcanzar el último elemento, reuniría los elementos relacionados en orden en otra matriz de resultados, y de los resultados elegiría una matriz que sea más pequeña .

EDITAR => JAVA: También he usado la función recursiva, el código completo a continuación;

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

            }

        }
    }

}