Książki „Wybierz własną przygodę” to forma interaktywnej literatury, w której czytelnik musi podejmować decyzje wpływające na wynik opowieści. W niektórych momentach historii czytelnik ma wiele opcji do wyboru, z których każda wysyła czytelnika na inną stronę w książce.

Na przykład w otoczeniu fantasy może być konieczne podjęcie decyzji na stronie 14, czy zapuścić się do tajemniczej jaskini, „skacząc” na stronę 22, lub eksplorować pobliski las, skacząc na stronę 8. Te „skoki” można wyrazić jako pary numerów stron, takie jak:

14 22
14 8

W większości przypadków historia ma wiele zakończeń, ale tylko kilka dobrych. Celem jest nawigacja w historii, aby osiągnąć dobre zakończenie.

Zadanie:

Biorąc pod uwagę listę „skoków” do danej książki, Twoim zadaniem jest określenie trasy, która doprowadzi do określonego zakończenia. Ponieważ jest to dość łatwe, prawdziwym wyzwaniem jest zrobienie tego w jak najmniejszej liczbie postaci.

To jest kod golfowy .

Przykładowe dane wejściowe (gdzie 1 to początek, a 100 to cel):

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

Przykładowe dane wyjściowe:

1 10 13 15 100

Przykładowe dane wejściowe:

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

Przykładowe dane wyjściowe:

1 15 2 12 80 100

Uwagi:

• Lista skoków zostanie wprowadzona przez użytkownika albo z pliku, albo ze standardowego wejścia. Możesz wybrać najbardziej dogodną.
• Dane wejściowe będą zawierać 1 skok na linię, z punktem początkowym i docelowym oddzielonymi pojedynczą spacją.
• Nie ma gwarancji, że wiersze na wejściu będą w określonej kolejności.
• Pomyślna ścieżka rozpocznie się na stronie 1 i zakończy na stronie 100.
• Możesz założyć, że do celu jest co najmniej 1 ścieżka. Nie musisz znaleźć wszystkich ścieżek ani znaleźć najkrótszej. Znajdź przynajmniej jeden.
• Najmniejszy numer strony to 1. Nie ma limitu największego numeru strony. (Możesz założyć, że będzie pasować do zakresu int.)
• Pętle mogą istnieć. Na przykład lista może zawierać skoki ze strony 5 na 10, 10 na 19 i 19 na 5.
• Mogą istnieć ślepe zaułki. Oznacza to, że na stronie docelowej może nie być nigdzie skakać.
• I odwrotnie, mogą istnieć nieosiągalne strony. Oznacza to, że strona początkowa może nie być celem żadnych skoków.
• Nie wszystkie numery stron od 1 do 100 są gwarantowane.
• Dane wyjściowe powinny składać się z prawidłowej trasy numerów stron, zaczynając od 1 i kończąc na 100, oddzielone spacjami.

Pamiętaj, to jest golf golfowy, więc wygrywa najkrótsze rozwiązanie!

EDYCJA: Dodano kolejną próbkę do testowania.

Golfscript, 58 57 znaków

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

Ostrzeżenie : jest to bardzo nieefektywne. Działa poprzez wielokrotne kwadratowanie macierzy przylegania, a następnie szukanie trasy; jeśli Ena wykresie znajdują się krawędzie, znajdzie każdą ścieżkę o długości do 2 ^E (a krótszą - wiele razy). Powinien dać ci wynik dla pierwszego przypadku testowego w rozsądnym czasie, ale jeśli chcesz wypróbować drugi, upewnij się, że masz kilka koncertów wolnej pamięci i idź na długi spacer.

Jeśli szukasz rozsądnie wydajnego rozwiązania, oferuję 67 znaków:

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

Python, 232 213 157 143 135 135 znaków (najkrótsza ścieżka)

Ta implementacja może obsłużyć wszystkie opisane przypadki krawędzi (pętle, ślepe zaułki, strony osierocone itp.) I gwarantuje, że znajdzie najkrótszą drogę do zakończenia. Opiera się na algorytmie najkrótszej ścieżki Djikstry.

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 znaków

Jest to rekurencyjne rozwiązanie, które znajduje najkrótszą drogę przez przygodę.

Gra w golfa:

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)

Aby przetestować ( OSTRZEŻENIE: nieskończona pętla pod kątem złych danych wejściowych! ):

1. Skopiuj jeden z poniższych ciągów wejściowych (lub użyj podobnego formatu, aby wybrać własny, wybierz własną przygodę):

   • 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. Wklej to do monitu o skrzypce testowe .

Sformatowany i skomentowany kod:

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

Aby przetestować ( OSTRZEŻENIE: nieskończona pętla pod kątem złych danych wejściowych! ):

1. Skopiuj jeden z poniższych ciągów wejściowych (lub użyj podobnego formatu, aby wybrać własny, wybierz własną przygodę):

   • 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. Wklej to do monitu o skrzypce testowe .

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]

Nie golfowany:

$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 znaków

w zasadzie perlizowana wersja hasła Clueless; przed meczem i po meczu są fajne :)

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

niestety to rekurencyjne rozwiązanie jest podatne na pętle w „historii” ...

Zastosowanie : cat ./test0 | ./sol.py Dane wyjściowe dla przypadku testowego 1:

1 10 13 15 100

Dane wyjściowe dla przypadku testowego 2:

1 15 2 12 80 100

Scala 2,9, 260 256 254 252 248 247 241 239 234 227 225 212 205 znaków

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

Nie golfowany:

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

Stosowanie:

Kompiluj scalac filenamei uruchamiaj z scala C. Dane wejściowe są pobierane za pośrednictwem STDIN.
Aby uruchomić na ideone.com, zmień object C extends Appna object Main extends Applicationna Scala 2.8.

PHP, 166 146 138 znaków

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

Nie golfowany:

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

Stosowanie :

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

Umieściłem je wszystkie w tablicy 2d i przeszukałem wszystkie elementy z wieloma pętlami, jeśli mogą one dotrzeć do ostatniego elementu, wówczas zebrałbym powiązane elementy, aby uzyskać kolejną tablicę wyników, a z wyników wybrałbym tablicę, która jest mniejsza .

EDYCJA => JAVA: Użyłem również funkcji rekurencyjnej, poniżej pełny kod;

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

            }

        }
    }

}