Книги «Выбери свое приключение» - это форма интерактивной литературы, в которой читатель должен принимать решения, которые влияют на исход истории. В определенные моменты истории читатель может выбрать несколько опций, каждый из которых отправляет читателя на отдельную страницу в книге.

Например, в фантастической обстановке на странице 14 может потребоваться решить, отправиться ли в таинственную пещеру, «прыгнув» на страницу 22, или исследовать близлежащий лес, перейдя на страницу 8. Эти «прыжки» можно выразить. как пары номеров страниц, вот так:

14 22
14 8

В большинстве случаев в истории есть много концовок, но только несколько хороших. Цель состоит в том, чтобы провести историю, чтобы достичь хорошего конца.

Задача:

Учитывая список «прыжков» для данной книги, ваша задача - определить маршрут, который приведет к определенному окончанию. Поскольку это довольно просто, истинная задача состоит в том, чтобы сделать это как можно меньше символов.

Это код гольф .

Пример ввода (где 1 - начало, а 100 - цель):

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

Образец вывода:

1 10 13 15 100

Пример ввода:

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

Образец вывода:

1 15 2 12 80 100

Примечания:

• Список переходов будет введен пользователем из файла или стандартного ввода. Вы можете выбрать тот, который наиболее удобен.
• Ввод будет содержать 1 переход на строку с началом и назначением, разделенными одним пробелом.
• Строки на входе не обязательно должны быть в определенном порядке.
• Успешный путь начинается со страницы 1 и заканчивается на странице 100.
• Вы можете предположить, что есть хотя бы 1 путь к цели. Вам не нужно находить все пути, и при этом вам не нужно искать самый короткий. Просто найди хотя бы одну.
• Наименьший номер страницы будет 1. Нет ограничений на максимальный номер страницы. (Вы можете предположить, что он будет соответствовать диапазону int.)
• Петли могут существовать. Например, в списке могут быть переходы со страниц 5 на 10, с 10 на 19 и с 19 на 5.
• Там могут быть тупики. То есть странице назначения может некуда перейти.
• И наоборот, могут быть недоступные страницы. То есть исходная страница не может быть пунктом назначения каких-либо переходов.
• Не все номера страниц от 1 до 100 гарантированно будут использоваться.
• Ваш вывод должен состоять из действительного маршрута номеров страниц, начиная с 1 и заканчивая на 100, разделенных пробелами.

Помните, это кодовый гольф, поэтому выигрывает самое короткое решение!

РЕДАКТИРОВАТЬ: Добавлен еще один образец для тестирования.

Golfscript, 58 57 символов

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

Предупреждение : это супер-неэффективно. Это работает путем многократного возведения в квадрат матрицы смежности и затем поиска маршрута; если Eв графе есть ребра, то он найдет каждый путь длиной до 2 ^E (а более короткие - много раз). Он должен дать вам результат для первого тестового примера за разумное время, но если вы хотите попробовать второй тест, убедитесь, что у вас есть несколько свободных гигабайт памяти и отправляйтесь на длинную прогулку.

Если вы хотите достаточно эффективное решение, я предлагаю за 67 символов:

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

Python, 232 213 157 143 135 132 символа (кратчайший путь)

Эта реализация может обрабатывать все описанные крайние случаи (циклы, тупики, потерянные страницы и т. Д.) И гарантирует, что найдет кратчайший путь к окончанию. Он основан на алгоритме кратчайшего пути Джикстры.

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 символов

Это рекурсивное решение, которое находит кратчайший путь через приключение.

Код-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)

Для проверки ( ВНИМАНИЕ: бесконечный цикл при неправильном вводе! ):

1. Скопируйте одну из следующих строк ввода (или используйте аналогичный формат, чтобы выбрать свой собственный, выберите свое собственное приключение):

   • 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. Вставьте это в подсказку тестовой скрипки .

Отформатированный и закомментированный код:

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

Для проверки ( ВНИМАНИЕ: бесконечный цикл при неправильном вводе! ):

1. Скопируйте одну из следующих строк ввода (или используйте аналогичный формат, чтобы выбрать свой собственный, выберите свое собственное приключение):

   • 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. Вставьте это в подсказку тестовой скрипки .

Руби 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 символов

в основном перлизованная версия записи Clueless; до матчей и после матчей весело :)

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

к сожалению, это хвостово-рекурсивное решение уязвимо для циклов в «истории» ...

Использование : cat ./test0 | ./sol.py Вывод для тестового примера 1:

1 10 13 15 100

Выход для тестового примера 2:

1 15 2 12 80 100

Scala 2.9, 260 256 254 252 248 247 241 239 234 227 225 212 205 символов

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

Использование:

Скомпилируйте scalac filenameи запустите scala C. Ввод осуществляется через STDIN.
Для запуска на ideone.com перейдите object C extends Appна object Main extends ApplicationScala 2.8.

PHP, 166 146 138 символов

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

Использование :

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

Я бы поместил их все в двумерный массив и провел поиск по всем элементам с многократным циклом; если они могут достичь последнего элемента, я бы собрал связанные элементы по порядку в другой массив результатов, и из результатов я бы выбрал массив, размер которого меньше ,

РЕДАКТИРОВАТЬ => JAVA: я также использовал рекурсивную функцию, полный код ниже;

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

            }

        }
    }

}