Gackern gackern Niemand weiß, warum das Huhn die Straße überquerte, vielleicht war da ein gut aussehender Hahn auf der anderen Seite. Aber wir können herausfinden, wie. Schreiben Sie ein Programm, das von links nach rechts diese (oder jede andere) "Straße" kreuzt.

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

Ihr Programm "kreuzt" es und bewegt sich von links nach rechts. Sie beginnen mit einer beliebigen Zahl in der Spalte ganz links, die Sie möchten. Von dort aus können Sie zu einem beliebigen benachbarten Zeichen auf der rechten Seite wechseln. Wenn Sie oben links mit 1 begonnen haben, können Sie entweder mit 3 oder 8 beginnen. Jede Zahl, die Sie aufrufen, einschließlich der Startnummer, wird zu einer Summe addiert. Leerzeichen addieren sich nicht zu Ihrer Summe. "|" zwingt dich, dich nach oben oder unten zu bewegen, anstatt irgendwo rechts. (Sie KÖNNEN sich bei diesem Charakter NICHT vorwärtsbewegen) Ihr Ziel ist es, mit der kleinstmöglichen Summe auf die andere Seite zu gelangen. Ihr Programm muss die Summe am Ende ausdrucken und in der Lage sein, jede Straße zu lösen. Vorzugsweise könnte es auch Eingaben für eine Straße geben, dies ist jedoch nicht erforderlich. Ihr Programm muss sowohl den Pfad als auch die Summe ausgeben. Nur wenige Bytes Code gewinnen.

Zur Verdeutlichung können Sie sich diagnostisch bewegen, sofern Sie sich nicht auf einer vertikalen Leiste befinden. Sie können sich nur auf und ab bewegen, wenn Sie sich auf einer vertikalen Leiste befinden.

Für eine klarere Spezifikation von Straßen ist es im Grunde eine Zeichenfolge (oder ein Array von Spalten oder Zeilen, falls Sie dies bevorzugen), die den Regeln der Zeichen folgt, und es kann nichts ABER diese Zeichen enthalten die Straße. Es kann eine beliebige Zahl, ein Leerzeichen, ein Strich ("|") oder ein Zeilenumbruch sein. Wenn eine Straße, wie in ProgrammerDans Antwort, von einem Betrunkenen asphaltiert wurde, ist sie immer noch gültig, und Ihr Programm muss in der Lage sein, eine solche Straße zu lösen. Es wird nicht als Straße betrachtet, wenn es nicht möglich ist, auf die andere Seite zu gelangen (es gibt beispielsweise keinen Ausweg aus einer geraden Linie von Balken).

Ihr Programm muss nicht feststellen, ob eine Straße ungültig ist.

Taste:
Beliebige Zahl - addiert die Zahl zu Ihrer Summe und rückt vor.
Leertaste - Bewegen Sie sich vorwärts, es wird nichts zu Ihrer Summe hinzugefügt.
"|" - Bewegen Sie sich nach oben oder unten, es wird nichts zu Ihrer Summe hinzugefügt.

EDIT: Eine beispielhafte Lösung, wie vorgeschlagen. Ich kann keine schrecklich große machen, ich kann keine IDE finden, um sie für mich am Geldautomaten zu lösen.

Nehmen Sie diese kleine Straße:

9191 | 8282
1919 | 2727
5555   5555

Die Lösung wäre ein Pfad von 1, 1, 1, 1, Raum, Teiler, Teiler, Raum, Raum, 2, 2, 2, 2 für insgesamt 12.

EDIT # 2: Die Lösung für den ersten Weg zu dieser Frage, wie von Geobits und Völkerprogrammen bestimmt, ist 0,2,0,1,,, 1,4,1,4 für eine Summe von 13.

Pyth, 168 143 141 bytes [jetzt Drunken Road kompatibel]

Mein Testfall funktioniert, aber aufgrund eines Missverständnisses von meiner Seite, wird es mit dem ersten Beispiel nicht richtig funktionieren. Ich arbeite daran, es zu reparieren.

Ich arbeite jetzt für ein Originalbeispiel und betrunkene Straßen

Einige wirklich etwas weniger hässlichen Code:

=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

Teste es hier

Ich habe es auf einer Straße von 10 + 9 x 40 getestet.

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

Java, 955 Bytes

Ich werde natürlich keine Preise gewinnen, weil ich Java und so bin, aber ich liebe dieses Problem und wollte meinen eigenen Beitrag einreichen.

Funktionen und Grenzen:

• Kann unregelmäßige Straßen (super betrunken!) Einschließlich variabler Breiten, komplexer Linien usw. unterstützen.
• Erwartet, dass die Straße bei der Ausführung als Parameter eingegeben wird. die ungolfed version unterstützt auch das lesen von stdin, aber da die eingabemethode nicht spezifiziert wurde, erwartet die golfed version die kleinste!
• Verwendet eine dynamische Programmiertechnik, die ich seit ungefähr 6 Jahren nicht mehr verwendet habe, um effizient in O (n * m) zu lösen, wobei n Zeilen und m Spalten sind.
  • Löst von rechts nach links und markiert die beste Richtung, um vom aktuellen Index zum nächsten Index zu gelangen.
  • "Zeilen" werden behandelt, indem ihre Spalte aufgelöst und dann adressiert wird, wenn sie in der nächsten Spalte erreichbar sind. Sie lösen sich auf, indem sie die Richtung nach oben oder unten speichern, wobei die Kosten für die eventuell erreichbare Nichtleitung anfallen.
• Track, aber nicht gedruckt (in golf'd Version) , um den Startindex der besten Lösung.

Ok, genug Jibba Jabba. Golf Version:

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

Wie es meine Gewohnheit ist, Github mit dem ungolfed Code .

Lösung für "erste" Straße:

$ 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

Zweites Beispiel:

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

Brian Tucks Beispiel:

$ 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

"Betrunken" Brians Beispiel:

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

Visualisierte Lösung:

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

Genießen!

Edit: Jetzt zeige ich nur noch (zwei Fahrbahnen verschmelzen! Kann er es schaffen?)

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

Lösung:

$ 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

(Bonus: Weg von ungolfed):

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

Details zum Algorithmus

Eine ausführlichere Erklärung der von mir angewendeten dynamischen Programmiertechnik wurde angefordert.

Ich verwende eine vorberechnete Lösungsmethode. Es hat einen richtigen Namen, aber ich habe ihn längst vergessen. vielleicht kann es jemand anderes anbieten?

Algorithmus:

• Beginnen Sie in der äußersten rechten Spalte und gehen Sie nach links. Berechnen Sie für jede Zelle in der Spalte Folgendes:
  • Die Summe der Bewegungen mit den niedrigsten Kosten, definiert als aktuelle Zellenkosten + Zellen mit den niedrigsten Kosten, die in der nächsten Spalte erreichbar sind
  • Die Bewegungsaktion, die durchgeführt werden muss, um die niedrigsten Kosten zu erzielen, ist einfach eine gültige Bewegung von dieser Zelle in eine andere einzelne Zelle.
• Rohre werden aufgeschoben. Um eine Pipe aufzulösen, muss die gesamte Spalte berechnet werden, damit wir die Pipes erst in der nächsten Spalte berechnen können.
  • Wenn Sie die niedrigsten Kosten einer Zelle links von einer Pipe ermitteln, berechnen Sie zunächst die beste Fahrtrichtung für die Pipe. Sie wird immer nach oben oder unten aufgelöst, sodass wir sie einmal berechnen.
  • Wir speichern dann, wie bei allen anderen Zellen, die besten Kosten (definiert als die Kosten der Zelle, die wir erreichen, indem wir auf dem Rohr nach oben oder unten fahren) und die Fahrtrichtung, um sie zu erreichen.

Anmerkungen:

Das ist es. Wir scannen einmal von oben nach unten, von rechts nach links; Die einzigen Zellen, die (möglicherweise) mehrmals berührt werden, sind Pipes. Jedes Pipes wird jedoch nur einmal "gelöst", wodurch wir in unserem O (m * n) -Fenster bleiben.

Um mit "ungeraden" Kartengrößen fertig zu werden, habe ich mich dafür entschieden, die Zeilenlängen durch Auffüllen mit Nullzeichen vorab zu scannen und zu normalisieren. Nullzeichen gelten als "Nullkosten" und werden genauso wie Pipes und Leerzeichen verschoben. Dann stoppe ich beim Drucken der Lösung die Druckkosten oder bewege mich, wenn entweder der Rand der normalisierten Straße erreicht ist oder ein Nullzeichen erreicht ist.

Das Schöne an diesem Algorithmus ist, dass er sehr einfach ist, auf jede Zelle die gleichen Regeln anwendet, eine vollständige Lösung durch Lösen von O (m * n) -Unterproblemen liefert und hinsichtlich der Geschwindigkeit ziemlich schnell ist. Dabei wird der Arbeitsspeicher gegeneinander abgewogen, und es werden effektiv zwei Kopien der Straßenkarte erstellt, wobei die erste "Best-Cost" -Daten und die zweite "Best-Move" -Daten pro Zelle speichert. Dies ist typisch für die dynamische Programmierung.