Os livros Escolha sua própria aventura são uma forma de literatura interativa em que o leitor deve tomar decisões que afetam o resultado da história. Em certos pontos da história, o leitor tem várias opções que podem ser escolhidas, cada uma enviando o leitor para uma página diferente do livro.

Por exemplo, em um cenário de fantasia, talvez seja necessário decidir na página 14 se aventurar em uma caverna misteriosa "pulando" na página 22 ou explorar a floresta próxima pulando na página 8. Esses "saltos" podem ser expressos como pares de números de páginas, assim:

14 22
14 8

Na maioria dos casos, existem muitos finais para a história, mas apenas alguns bons. O objetivo é navegar na história para alcançar um bom final.

Tarefa:

Dada uma lista de "saltos" para um determinado livro, sua tarefa é determinar uma rota que levará a um final específico. Como isso é bastante fácil, o verdadeiro desafio é fazê-lo com o menor número possível de caracteres.

Isso é código de golfe .

Entrada de amostra (onde 1 é o início e 100 é o objetivo):

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

Saída de amostra:

1 10 13 15 100

Entrada de amostra:

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

Saída de amostra:

1 15 2 12 80 100

Notas:

• A lista de saltos será inserida pelo usuário, a partir de um arquivo ou stdin. Você pode escolher o que for mais conveniente.
• A entrada conterá 1 salto por linha, com a origem e o destino separados por um único espaço.
• As linhas na entrada não são garantidas em nenhuma ordem específica.
• Um caminho bem-sucedido começará na página 1 e terminará na página 100.
• Você pode assumir que há pelo menos 1 caminho para a meta. Você não precisa encontrar todos os caminhos, nem o mais curto. Basta encontrar pelo menos um.
• O menor número de página será 1. Não há limite para o maior número de página. (Você pode supor que ele caiba no intervalo de um int.)
• Podem existir loops. Por exemplo, a lista pode ter saltos das páginas 5 a 10, 10 a 19 e 19 a 5.
• Pode haver becos sem saída. Ou seja, uma página de destino pode não ter para onde ir.
• Por outro lado, pode haver páginas inacessíveis. Ou seja, uma página de origem pode não ser o destino de quaisquer saltos.
• Nem todos os números de página entre 1 e 100 têm garantia de uso.
• Sua saída deve consistir em uma rota válida de números de página, começando com 1 e terminando em 100, separados por espaços.

Lembre-se, este é um código de golfe, então a solução mais curta vence!

EDIT: Adicionada outra amostra para teste.

Golfscript, 58 57 caracteres

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

Aviso : isso é supereficiente. Ele funciona quadrando repetidamente a matriz de adjacência e procurando uma rota; se houver Earestas no gráfico, ele encontrará todos os caminhos de comprimento até 2 ^E (e os mais curtos encontrará muitas vezes). Ele deve fornecer um resultado para o primeiro caso de teste em um tempo razoável, mas se você quiser tentar o segundo, verifique se você tem alguns shows de memória livre e faça uma longa caminhada.

Se você deseja uma solução razoavelmente eficiente, ofereço 67 caracteres:

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

Python, 232 213 157 143 135 132 caracteres (caminho mais curto)

Essa implementação pode lidar com todos os casos de borda descritos (loops, becos sem saída, páginas órfãs etc.) e garante que encontrará o caminho mais curto para o final. É baseado no algoritmo de caminho mais curto do 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 é uma solução recursiva que encontra o caminho mais curto da aventura.

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

Para testar ( AVISO: loop infinito para entrada incorreta! ):

1. Copie uma das seguintes seqüências de entrada (ou use um formato semelhante para escolher sua própria escolha sua própria 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. Cole isso no prompt do violino de teste .

Código formatado e 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 testar ( AVISO: loop infinito para entrada incorreta! ):

1. Copie uma das seguintes seqüências de entrada (ou use um formato semelhante para escolher sua própria escolha sua própria 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. Cole isso no prompt do violino de teste .

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 caracteres

basicamente uma versão perlizada da entrada de Clueless; pré-partidas e pós-partidas são divertidas :)

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

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

infelizmente, esta solução recursiva da cauda é vulnerável a loops na "história" ...

Uso : cat ./test0 | ./sol.py Saída para o caso de teste 1:

1 10 13 15 100

Saída para o caso de teste 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")}

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

Uso:

Compilar scalac filenamee executar com scala C. A entrada é obtida via STDIN.
Para executar no ideone.com, altere object C extends Apppara object Main extends Applicationpara executá-lo 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);

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

Uso:

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

Eu colocaria todos eles em uma matriz 2D e pesquisaria todos os itens com loop múltiplo; se eles atingirem o último item, eu coletaria itens relacionados em ordem em outra matriz de resultados e, a partir dos resultados, eu escolheria uma matriz menor. .

EDIT => JAVA: Eu também usei função recursiva, código completo abaixo;

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

            }

        }
    }

}