Щёлкни щёлкни Никто не знает, почему курица перешла дорогу, возможно, с другой стороны был красивый петух. Но мы можем выяснить, как. Напишите программу, которая слева направо пересекает эту (или любую) «дорогу».

1356 | 1738
3822 | 1424
3527   3718
9809 | 5926
0261 | 1947
7188   4717
6624 | 9836
4055 | 9164
2636   4927
5926 | 1964
3144 | 8254

Ваша программа «пересекает» его, двигаясь слева направо. Вы начинаете с любого числа в крайнем левом столбце, который вам нравится. Оттуда вы можете перейти к любому соседнему персонажу справа. Если вы начали в левом верхнем углу, 1, вы можете перейти к 3 или 8. Каждый номер, на который вы идете, включая начальный номер, добавляется к сумме. Пробелы не добавляют к вашей сумме. "|" заставляет вас двигаться вверх или вниз, а не куда-то направо. (Вы НЕ МОЖЕТЕ продвинуться вперед в этом персонаже) Ваша цель - добраться до другой стороны с наименьшей возможной суммой. Ваша программа должна распечатать сумму в конце, и она должна быть в состоянии решить любую дорогу. Предпочтительно, он также может иметь вход для дороги, но это не обязательно. Ваша программа должна напечатать как путь, так и сумму. Побеждает несколько байтов кода.

Чтобы уточнить, вы можете двигаться диагностически, если вы не находитесь на вертикальной планке. Вы можете двигаться только вверх и вниз, когда находитесь на вертикальной полосе.

Для более точной спецификации дорог это в основном строка текста (или массив столбцов или строк, если вы предпочитаете так думать), которая следует правилам символов, и ничего не может быть, НО эти символы в дорога. Это может быть любое число, пробел, строка ("|") или перевод строки. Если дорога была проложена пьяным парнем, как в ответе ProgrammerDan, она все еще является действительной дорогой, и ваша программа должна быть в состоянии решить эту дорогу. Дорога не считается дорогой, если невозможно добраться до другой стороны (например, из прямой линии баров нет выхода).

Ваша программа не обязана определять, является ли дорога недействительной.

Ключ:
любое число - добавление числа к вашей сумме, движение вперед.
Пробел - двигаться вперед, к вашей сумме ничего не добавляется.
"|" - Перемещение вверх или вниз, ничего не добавляется к вашей сумме.

РЕДАКТИРОВАТЬ: пример решения, как предлагается. Я не могу сделать ужасно большой, я не могу войти в IDE, чтобы решить это для меня банкомат.

Возьми эту маленькую дорогу:

9191 | 8282
1919 | 2727
5555   5555

Решением будет путь 1, 1, 1, 1, пробел, делитель, делитель, пробел, пробел, 2, 2, 2, 2, всего 12.

РЕДАКТИРОВАТЬ # 2: Решение первой дороги в этом вопросе, как определено в программах Geobits и людей, составляет 0,2,0,1,,, 1,4,1,4 на сумму 13.

Pyth, 168 143 141 байт [теперь совместим с Drunken Road]

Мой тестовый пример работает, но из-за недопонимания с моей стороны он не будет работать должным образом с первоначальным примером. Я работаю над тем, чтобы исправить это.

Сейчас работаю на оригинальном примере и пьяных дорогах

Какой-то ДЕЙСТВИТЕЛЬНО чуть менее уродливый код:

=Z.dC,++\ `MUT\|++0UT=^T5Ltu+G]?&qeeG\|<heGhH+eGeHHtb,0hbKhohNum++hed@ZhhdtedC,H_y_y.b+N]YmhohNd.:++TGT3HCm.[d\ lh.MlZ.z.z*hl.z]]0j\,t.sK\ hK

Проверьте это здесь

Я проверил это на дороге 10 + 9 х 40.

6417443208|153287613
8540978161|726772300
7294922506 263609552
0341937695 498453099
9417989188 370992778
2952186385|750207767
7049868670 756968872
1961508589|379453595
0670474005 070712970
4817414691|670379248
0297779413|980515509
6637598208 090265179
6872950638 767270459
7375626432 439957105
1387683792|544956696
6974831376 545603884
0949220671|632555651
3952970630|379291361
0456363431|275612955
2973230054|830527885
5328382365|989887310
4034587060 614168216
4487052014|969272974
5015479667 744253705
5756698090|621187161
9444814561|169429694
7697999461|477558331
3822442188 206942845
2787118311|141642208
2669534759 308252645
6121516963|554616321
5509428225|681372307
6619817314|310054531
1759758306 453053985
9356970729|868811209
4208830142 806643228
0898841529|102183632
9692682718|103744380
5839709581|790845206
7264919369|982096148

Ява, 955 байт

Очевидно, я не собираюсь выигрывать какие-либо награды, будучи Java и все такое, но я люблю эту проблему и хочу добавить свою собственную запись.

Особенности и ограничения:

• Может поддерживать нерегулярные дороги (супер пьяный!), Включая переменную ширину, сложные линии и т. Д.
• Ожидается, что дорога будет введена в качестве параметров при исполнении; версия ungolfed также поддерживает чтение из stdin, но поскольку метод ввода не был указан, версия для гольфа ожидает наименьшее!
• Использует некоторую технику динамического программирования, которую я не использовал около 6 лет, чтобы эффективно решить за O (n * m) время, где n - строки, а m - столбцы.
  • Решает справа налево, отмечая наилучшее направление от текущего индекса к следующему.
  • «строки» обрабатываются путем разрешения их столбца, а затем их адресации, если они достижимы в следующем столбце. Они разрешаются путем сохранения направления вверх или вниз, за ​​счет стоимости в конечном итоге недоступной линии.
• Отслеживает, но не печатает (в версии для гольфа) начальный индекс лучшего решения.

Хорошо, достаточно Джибба Джабба. Гольф версия:

class C{public static void main(String[]a){int n=a.length,m=0,i=0,j=0,h=0,p=0,q=0,s=0,t=0,b=-1,c=2147483647,x=0,y=0;char[][]r=new char[n][];char u;for(String k:a){j=k.length();m=(j>m)?j:m;}for(String k:a)r[i++]=java.util.Arrays.copyOf(k.toCharArray(),m);int[][][]d=new int[n][m][2];for(j=m-1;j>=0;j--){for(i=0;i<n;i++){u=r[i][j];p=(u=='\0'||u==' '||u=='|'?0:u-'0');if(j==m-1)d[i][j][1]=p;else{if(u=='|')d[i][j][0]=-1;else{for(h=-1;h<2;h++){x=i+h;y=j+1;if(x>=0&&x<n){if(d[x][y][0]==-1){s=x-1;while(s>=0&&r[s][y]=='|')s--;t=x+1;while(t<n&&r[t][y]=='|')t++;if((s>=0&&t<n&&d[s][y][1]<d[t][y][1])||(s>=0&&t>=n)){t=d[s][y][1];s=4;}else{s=6;t=d[t][y][1];}d[x][y][0]=s;d[x][y][1]=t;}q=d[x][y][1]+p;if(d[i][j][0]==0||q<d[i][j][1]){d[i][j][0]=h+2;d[i][j][1]=q;}}}}}if(j==0&&(b<0||d[i][j][1]<c)){b=i;c=d[i][j][1];}}}String o="";i=b;j=0;while(j<m){u=r[i][j];if(u=='\0')j=m;else{o+=u+",";h=d[i][j][0]-2;if(h>1)i+=h-3;else{i+=h;j++;}}}System.out.println(o+"\b:"+c);}}

По моей привычке, github с нечистым кодом .

Решение для «первой» дороги:

$ java C "1356 | 1738" "3822 | 1424" "3527   3718" "9809 | 5926" "0261 | 1947" "7188   4717" "6624 | 9836" "4055 | 9164" "2636   4927" "5926 | 1964" "3144 | 8254"
0,2,0,1, , , ,1,4,1,4:13

Второй пример:

$ java C "9191 | 8282" "1919 | 2727" "5555   5555"
1,1,1,1, ,|,|, , ,2,2,2,2:12

Образец Брайана Така:

$ java C "6417443208|153287613" "8540978161|726772300" "7294922506 263609552" "0341937695 498453099" "9417989188 370992778" "2952186385|750207767" "7049868670 756968872" "1961508589|379453595" "0670474005 070712970" "4817414691|670379248" "0297779413|980515509" "6637598208 090265179" "6872950638 767270459" "7375626432 439957105" "1387683792|544956696" "6974831376 545603884" "0949220671|632555651" "3952970630|379291361" "0456363431|275612955" "2973230054|830527885" "5328382365|989887310" "4034587060 614168216" "4487052014|969272974" "5015479667 744253705" "5756698090|621187161" "9444814561|169429694" "7697999461|477558331" "3822442188 206942845" "2787118311|141642208" "2669534759 308252645" "6121516963|554616321" "5509428225|681372307" "6619817314|310054531" "1759758306 453053985" "9356970729|868811209" "4208830142 806643228" "0898841529|102183632" "9692682718|103744380" "5839709581|790845206" "7264919369|982096148"
2,1,0,1,5,1,2,1,1,1, ,1,0,1,2,1,2,3,0,1:26

Пример «пьяного» Брайана:

6417443208 | 153287613
8540978161 | 726772300
7294922506 263609552
0341937695 498453099
9417989188 370992778
2952186385 | 750207767
7049868670 756968872
1961508589 | 379453595
0670474005 070712970
4817414691 | 670379248
0297779413 | 980515509
6637598208 090265179
6872950638 767270459
7375626432 439957105
1387683792 | 544956
697483176 5456034
09492201 | 6325551
395297030 | 3792913
 456363431 | 275612
  73230054 | 830527885
    8382365 | 989887310
    4587060 614168216
  87052014 | 96927297
 50479667 7442537
57566980 | 621187161
944481456 | 169429694
7697999461 | 477558331
3822442188 206942845
2787118311 | 141642208
2669534759 308252645
6121516963 | 554616321
5509428225 | 681372307
6619817314 | 310054531
1759758306 453053985
9356970729 | 868811209
4208830142 806643228
0898841529 | 102183632
9692682718 | 103744380
5839709581 | 790845206
7264919369 | 982096148

$ java C "6417443208|153287613" "8540978161|726772300" "7294922506 263609552" "0341937695 498453099" "9417989188 370992778" "2952186385|750207767" "7049868670 756968872" "1961508589|379453595" "0670474005 070712970" "4817414691|670379248" "0297779413|980515509" "6637598208 090265179" "6872950638 767270459" "7375626432 439957105" "1387683792|544956" "697483176 5456034" "09492201|6325551" "395297030|3792913" " 456363431|275612" "  73230054|830527885" "    8382365|989887310" "    4587060 614168216" "  87052014|96927297" " 50479667 7442537" "57566980 | 621187161" "944481456 | 169429694" "7697999461|477558331" "3822442188 206942845" "2787118311|141642208" "2669534759 308252645" "6121516963|554616321" "5509428225|681372307" "6619817314|310054531" "1759758306 453053985" "9356970729|868811209" "4208830142 806643228" "0898841529|102183632" "9692682718|103744380" "5839709581|790845206" "7264919369|982096148"
 , , , ,0,5,2,0,1, , , ,1,1,1,3,2:16

Решение визуализировано:

09492201 | 6325551
395297030 | 3792913
\ 456363431 | 275612
 \ 73230054 | 830527885
  \ 8382365 | 989887310
   \ 4 \ 87060 614168216
  87/5 - \ 4 | 96927 \ 97
 50479667 \ 74425/7
57566980 | \ 62- / 87161
944481456 | \ / 69429694
7697999461 | 477558331

Наслаждайтесь!

Изменить: Теперь я просто хвастаюсь (две дороги сливаются! Он может сделать это?)

948384 | 4288324 324324 | 121323
120390 | 1232133 598732 | 123844
 293009 | 2394023 432099 | 230943
 234882 | 2340909 843893 | 849728
  238984 | 328498984328 | 230949
  509093 | 904389823787 | 439898
   438989 | 3489889344 | 438984
   989789 | 7568945968 | 989455
    568956 | 56985869 | 568956
    988596 | 98569887 | 769865
     769879 | 769078 | 678977
     679856 | 568967 | 658957
      988798 | 8776 | 987979
      987878 | 9899 | 989899
       999889 | | 989899
       989999 | | 989999
        989898 | | 998999
        989999 | | 999999
         989998 || 899999
         989998 || 998999

Решение:

$ java C "948384 | 4288324   324324 | 121323" "120390 | 1232133   598732 | 123844" " 293009 | 2394023 432099 | 230943" " 234882 | 2340909 843893 | 849728" "  238984 | 328498984328 | 230949" "  509093 | 904389823787 | 439898" "   438989 | 3489889344 | 438984" "   989789 | 7568945968 | 989455" "    568956 | 56985869 | 568956" "    988596 | 98569887 | 769865" "     769879 | 769078 | 678977" "     679856 | 568967 | 658957" "      988798 | 8776 | 987979" "      987878 | 9899 | 989899" "       999889 |    | 989899" "       989999 |    | 989999" "        989898 |  | 998999" "        989999 |  | 999999" "         989998 || 899999" "         989998 || 998999"
 ,2,0,3,0,0, ,|,|, ,|,|, ,|,|, ,|,|, ,|,|, ,|,|, ,|,|, , , , , , , ,|, ,|, ,|, ,|, ,|, ,|, ,|,|, , ,1,0,7,2:15

(бонус: путь от негольфированного):

$ java Chicken < test5.txt
best start: 3 cost: 15
  -> 2 -> 0 -> 3 -> 0 -> 0 ->   -> | -> | ->   -> | -> | ->   -> | -> | ->   -> | -> | ->   -> | -> | ->   -> | -> | ->
  -> | -> | ->   ->   ->   ->   ->   ->   ->   -> | ->   -> | ->   -> | ->   -> | ->   -> | ->   -> | ->   -> | -> | ->
  ->   -> 1 -> 0 -> 7 -> 2 -> 15
/ -> - -> - -> \ -> / -> / -> - -> , -> , -> - -> , -> , -> - -> , -> , -> - -> , -> , -> - -> , -> , -> - -> , -> , ->
- -> , -> , -> / -> \ -> - -> - -> - -> / -> / -> ^ -> / -> ^ -> / -> ^ -> / -> ^ -> / -> ^ -> / -> ^ -> / -> , -> , ->
/ -> - -> \ -> \ -> - -> \ -> across

Подробности об алгоритме

Было запрошено более полное объяснение техники динамического программирования, которую я использовал, поэтому здесь:

Я использую метод решения с использованием меток и предварительных вычислений. У него правильное имя, но я давно его забыл; возможно кто-то еще может предложить это?

Алгоритм:

• Начиная с самого правого столбца и продолжая влево, вычислите следующее для каждой ячейки столбца:
  • Суммирование движения с наименьшей стоимостью, определяемого как текущая стоимость ячейки + ячейка с наименьшей стоимостью, достижимая в следующем столбце
  • Движение, которое необходимо предпринять для достижения этой наименьшей стоимости, просто допустимое перемещение из этой ячейки в другую отдельную ячейку.
• Трубы откладываются. Чтобы разрешить канал, вам нужно вычислить полный столбец, чтобы мы не вычисляли каналы до следующего столбца.
  • При определении наименьшей стоимости ячейки слева от трубы мы сначала рассчитываем наилучшее направление движения по трубе - она ​​всегда будет разрешаться либо вверх, либо вниз, поэтому вычисляем ее один раз.
  • Затем мы сохраняем, как и во всех других ячейках, наилучшую стоимость (определяемую как стоимость ячейки, которую мы достигаем, путешествуя вверх или вниз по трубе) и направление движения, чтобы достичь ее.

Примечания:

Вот и все. Мы сканируем сверху вниз, справа налево, один раз; единственные ячейки, которые были затронуты (потенциально) более одного раза, - это трубы, однако каждая труба «решается» только один раз, удерживая нас в нашем окне O (m * n).

Для обработки «нечетных» размеров карты я предпочел просто предварительно отсканировать и нормализовать длину строк, дополнив их нулевыми символами. Нулевые символы считаются как "нулевые затраты", такие же, как трубы и пробелы. Затем при печати решения я прекращаю печатать затраты или перемещения, когда достигается либо край нормализованной дороги, либо нулевой символ.

Прелесть этого алгоритма в том, что он очень прост, применяет одни и те же правила к каждой ячейке, создавая полное решение путем решения подзадач O (m * n), и с точки зрения скорости довольно быстро. Он компенсирует память, эффективно создавая две копии в памяти карты проезжей части: первая для хранения данных с «наилучшей стоимостью», а вторая для хранения данных «с наилучшим перемещением» на ячейку; это типично для динамического программирования.