Cluck cluck. Nikt nie wie, dlaczego kurczak przeszedł przez ulicę, może po drugiej stronie był dobrze wyglądający kogut. Ale możemy dowiedzieć się, jak to zrobić. Napisz program, który od lewej do prawej przecina tę (lub dowolną) „drogę”.

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

Twój program „przecina” go, przesuwając od lewej do prawej. Zaczynasz od dowolnej liczby w lewej kolumnie, którą lubisz. Stamtąd możesz przejść do dowolnej sąsiedniej postaci po prawej stronie. Jeśli zacząłeś w lewym górnym rogu, 1, możesz przejść do 3 lub 8. Każdy numer, do którego się wybierasz, w tym numer początkowy, jest dodawany do sumy. Miejsca nie dodają się do twojej sumy. „|” zmusza cię do poruszania się w górę lub w dół, a nie gdzieś po prawej stronie. (NIE MOŻESZ przejść do tej postaci) Twoim celem jest przejście na drugą stronę z możliwie najmniejszą sumą. Twój program musi wydrukować sumę na końcu i musi być w stanie rozwiązać każdą drogę. Najlepiej może mieć również wkład w drogę, ale nie jest to wymagane. Twój program musi wydrukować zarówno ścieżkę, jak i sumę. Wygrywa najmniej bajtów kodu.

Aby to wyjaśnić, możesz poruszać się diagnostycznie, chyba że jesteś na pionowym pasku. Możesz poruszać się w górę iw dół tylko wtedy, gdy jesteś na pionowym pasku.

Aby uzyskać jaśniejszą specyfikację dróg, jest to w zasadzie ciąg tekstowy (lub tablica kolumn lub wierszy, jeśli wolisz myśleć w ten sposób) zgodny z regułami znaków i nie może być nic, ALE te znaki w droga. Może być dowolna liczba, spacja, kreska („|”) lub nowa linia. Jeśli pijany facet wybrukował drogę, jak w odpowiedzi ProgrammerDan, nadal jest to droga ważna, a Twój program musi być w stanie rozwiązać taką drogę. Droga nie jest uważana za drogę, jeśli nie można przedostać się na drugą stronę (na przykład nie ma wyjścia z prostej linii pasków).

Twój program nie jest wymagany do ustalenia, czy droga jest nieważna.

Klucz:
Dowolna liczba - dodaje liczbę do sumy, przejdź do przodu.
Spacja - idź naprzód, nic nie zostanie dodane do twojej sumy.
„|” - Przesuń w górę lub w dół, nic nie jest dodawane do twojej sumy.

EDYCJA: Przykładowe rozwiązanie, zgodnie z sugestią. Nie mogę zrobić strasznie dużego, nie mogę dostać IDE, aby rozwiązać dla mnie bankomat.

Jedź tą małą drogą:

9191 | 8282
1919 | 2727
5555   5555

Rozwiązaniem byłoby ścieżka 1, 1, 1, 1, spacja, dzielnik, dzielnik, spacja, spacja, 2, 2, 2, 2, w sumie 12.

EDYCJA 2: Rozwiązanie pierwszej drogi w tym pytaniu, określone przez programy Geobitów i ludów, wynosi 0,2,0,1,,, 1,4,1,4 dla sumy 13.

Pyth, 168 143 141 bajtów [teraz kompatybilny z Drunken Road]

Mój przypadek testowy działa, ale z powodu nieporozumień z mojej strony nie będzie działał poprawnie z początkowym przykładem. Pracuję nad naprawą.

Teraz działa na oryginalny przykład i pijane drogi

Niektóre NAPRAWDĘ nieco mniej brzydki kod:

=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

Przetestuj tutaj

Przetestowałem to na drodze 10 + 9 x 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

Java, 955 bajtów

Oczywiście nie zamierzam wygrywać żadnych nagród, będąc Javą i wszystkim, ale uwielbiam ten problem i chciałem wrzucić własne zgłoszenie.

Funkcje i ograniczenia:

• Może obsługiwać nieregularne drogi (super pijane!), W tym zmienne szerokości, złożone linie itp.
• Oczekuje wprowadzenia drogi jako parametrów przy wykonywaniu; wersja bez golfa obsługuje również odczyt ze standardowego wejścia, ale ponieważ nie określono metody wprowadzania danych, wersja z golfem oczekuje najmniejszych!
• Używa techniki programowania dynamicznego, z której nie korzystałem przez około 6 lat, aby efektywnie rozwiązywać w czasie O (n * m), gdzie n to wiersze, a m to kolumny.
  • Rozwiązuje się od prawej do lewej, znakowanie najlepszy kierunek do podjęcia od bieżącego indeksu do następnego indeksu.
  • „linie” są obsługiwane przez rozstrzygnięcie ich kolumny, a następnie zaadresowanie ich, jeśli jest osiągalne w następnej kolumnie. Rozwiązuje się je, zapisując kierunek w górę lub w dół, a kosztem nieosiągalnej linii docelowej.
• Śledzi, ale nie drukuje (w wersji golfowej) indeksu początkowego najlepszego rozwiązania.

Ok, wystarczy jibba jabba. Wersja golfowa:

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

Zgodnie z moim zwyczajem github z nie golfowym kodem .

Rozwiązanie dla „pierwszej” drogi:

$ 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

Drugi przykład:

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

Próbka Briana Tucka:

$ 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

Przykład „Drunkified” Briana:

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

Wizualizowane rozwiązanie:

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

Cieszyć się!

Edycja: Teraz się popisuję (dwie drogi łączą się! Czy da radę?)

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

Rozwiązanie:

$ 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

(premia: ścieżka od nie golfa):

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

Szczegóły dotyczące algorytmu

Poproszono o pełniejsze wyjaśnienie zastosowanej przeze mnie techniki programowania dynamicznego, więc oto:

Korzystam z metody mark-and-pre-compute. Ma właściwe imię, ale już dawno o nim zapomniałem; może ktoś inny może to zaoferować?

Algorytm:

• Zaczynając od kolumny najbardziej po prawej i przechodząc do lewej, obliczyć następujące informacje o każdej komórce w kolumnie:
  • Podsumowanie ruchu o najniższych kosztach, zdefiniowanego jako aktualny koszt komórki + komórka o najniższym koszcie osiągalnym w następnej kolumnie
  • Działanie ruchu, które należy podjąć, aby osiągnąć ten najniższy koszt, jako po prostu prawidłowe przejście z tej komórki do innej pojedynczej komórki.
• Rury są odraczane. Aby rozwiązać potok, musisz obliczyć pełną kolumnę, więc nie obliczamy potoków do następnej kolumny.
  • Przy określaniu najniższego kosztu komórki po lewej stronie potoku najpierw obliczamy najlepszy kierunek podróży wzdłuż potoku - zawsze rozwinie się w górę lub w dół, więc obliczamy go raz.
  • Następnie przechowujemy, podobnie jak w przypadku wszystkich innych komórek, najlepszy koszt (zdefiniowany jako koszt komórki, którą osiągamy, podróżując w górę lub w dół rurą) i kierunek podróży, aby do niej dotrzeć.

Uwagi:

Otóż ​​to. Raz skanujemy od góry do dołu, od prawej do lewej; jedynymi komórkami dotkniętymi (potencjalnie) więcej niż jeden raz są rury, jednak każda rura jest „rozwiązana” tylko raz, pozostawiając nas w naszym oknie O (m * n).

Aby obsłużyć „nieparzyste” rozmiary map, postanowiłem po prostu wstępnie przeskanować i znormalizować długości wierszy, wypełniając je znakami zerowymi. Znaki zerowe liczą się jako ruchy „zero kosztów” tak samo jak rury i spacje. Następnie, drukując rozwiązanie, przestaję drukować koszty lub przesuwać się, gdy zostanie osiągnięta krawędź znormalizowanej drogi lub znak zerowy.

Piękno tego algorytmu jest bardzo proste, stosuje te same reguły do ​​każdej komórki, tworząc pełne rozwiązanie, rozwiązując podproblemy O (m * n), a pod względem szybkości jest dość szybki. Wymienia pamięć, tworząc skutecznie dwie kopie w pamięci mapy drogi, pierwsza przechowująca dane „najlepszego kosztu”, a druga przechowująca dane „najlepszego ruchu” na komórkę; jest to typowe dla programowania dynamicznego.