Cluck Cluck. Tidak ada yang tahu mengapa ayam itu menyeberang jalan, mungkin ada ayam jago di sisi lain. Tapi kita bisa mencari tahu caranya. Tulis sebuah program, yang, dari kiri ke kanan, melintasi "jalan" ini (atau apa pun).

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

Program Anda "memotong" nya, bergerak dari kiri ke kanan. Anda mulai pada nomor apa pun di kolom paling kiri yang Anda suka. Dari sana, Anda dapat pindah ke karakter yang berdekatan di sebelah kanan. Jika Anda mulai di sudut kiri atas, 1, Anda bisa pergi ke 3 atau 8. Setiap nomor yang Anda tuju, termasuk nomor awal, ditambahkan ke jumlah. Spasi tidak menambah jumlah Anda. "|" memaksa Anda untuk bergerak ke atas atau ke bawah, bukan ke suatu tempat ke kanan. (Anda TIDAK BISA bergerak maju pada karakter ini) Tujuan Anda adalah untuk sampai ke sisi lain dengan jumlah sekecil mungkin. Program Anda harus mencetak jumlah di bagian akhir, dan itu harus dapat menyelesaikan jalan apa pun. Lebih disukai, bisa juga memiliki input untuk jalan, tetapi itu tidak diperlukan. Program Anda harus mencetak path dan jumlahnya. Byte kode yang paling sedikit menang.

Untuk memperjelas, Anda dapat memindahkan secara diagnosis kecuali jika Anda berada di bilah vertikal. Anda hanya dapat bergerak ke atas dan ke bawah saat berada di bilah vertikal.

Untuk spesifikasi jalan yang lebih jelas, ini pada dasarnya adalah serangkaian teks (atau array kolom atau baris, jika Anda lebih suka berpikir seperti itu) yang mengikuti aturan karakter, dan tidak mungkin ada apa-apa TAPI karakter-karakter tersebut di jalan. Bisa ada angka, spasi, baris ("|"), atau baris baru. Jika jalan diaspal oleh orang mabuk, seperti dalam jawaban ProgrammerDan, itu masih jalan yang valid, dan program Anda harus dapat menyelesaikan jalan tersebut. Itu tidak dianggap sebagai jalan jika tidak mungkin untuk pergi ke sisi lain (Misalnya, tidak ada jalan keluar dari garis lurus bar).

Program Anda tidak diharuskan untuk menentukan apakah jalan tidak valid.

Kunci:
Nomor apa saja - menambahkan nomor ke jumlah Anda, bergerak maju.
Spasi - Maju, tidak ada yang ditambahkan ke jumlah Anda.
"|" - Naik atau turun, tidak ada yang ditambahkan ke jumlah Anda.

EDIT: Contoh solusi, seperti yang disarankan. Saya tidak bisa membuat yang sangat besar, saya tidak bisa mendapatkan IDE untuk menyelesaikannya untuk saya ATM.

Ambil jalan kecil ini:

9191 | 8282
1919 | 2727
5555   5555

Solusinya akan menjadi jalur 1, 1, 1, 1, ruang, pembagi, pembagi, ruang, ruang, 2, 2, 2, 2 dengan total 12.

EDIT # 2: Solusi untuk jalan pertama pada pertanyaan ini, sebagaimana ditentukan oleh program Geobits dan masyarakat, adalah 0,2,0,1,,,, 1,4,1,4 dengan jumlah 13.

Pyth, 168 143 141 byte [sekarang Drunken Road kompatibel]

Test case saya berfungsi, tetapi karena kesalahpahaman di pihak saya, itu tidak akan berfungsi dengan baik dengan contoh awal. Saya sedang berusaha memperbaikinya.

Sekarang bekerja untuk contoh asli dan jalan mabuk

Beberapa kode yang BENAR-BENAR kurang jelek :

=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

Uji di Sini

Saya mengujinya di jalan 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 byte

Jelas tidak akan memenangkan penghargaan apa pun, menjadi Java dan semuanya, tapi saya suka masalah ini dan ingin memasukkan entri saya sendiri.

Fitur dan batas:

• Dapat mendukung jalan yang tidak teratur (super mabuk!) Termasuk lebar variabel, garis kompleks, dll.
• Diharapkan jalan menjadi input sebagai parameter pada pelaksanaan; versi ungolfed juga mendukung pembacaan dari stdin, tetapi karena metode input tidak ditentukan, versi golf mengharapkan terkecil!
• Menggunakan beberapa teknik pemrograman dinamis yang belum saya gunakan dalam, oh, 6 tahun atau lebih untuk menyelesaikan secara efisien dalam waktu O (n * m), di mana n adalah baris dan m adalah kolom.
  • Menyelesaikan dari kanan ke kiri, menandai arah terbaik untuk mengambil dari indeks saat ini ke indeks berikutnya.
  • "garis" ditangani dengan menyelesaikan kolom mereka, lalu mengatasinya jika dapat dijangkau pada kolom berikutnya. Mereka menyelesaikan dengan menyimpan arah ke atas atau ke bawah, dengan biaya non-line yang akhirnya dapat dicapai.
• Melacak, tetapi tidak mencetak (dalam versi golf) indeks awal dari solusi terbaik.

Ok, cukup jibba jabba. Versi golf:

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

Sesuai kebiasaan saya, github dengan kode tidak disunat .

Solusi untuk jalan "pertama":

$ 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

Contoh kedua:

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

Sampel Brian Tuck:

$ 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

"Mabuk" Contoh Brian:

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

Solusi divisualisasikan:

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

Nikmati!

Sunting: Sekarang saya hanya pamer (dua jalan raya bergabung! Bisakah dia berhasil?)

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

Larutan:

$ 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: jalur dari ungolfed):

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

Detail tentang Algoritma

Penjelasan lebih lengkap tentang teknik Pemrograman Dinamis yang saya gunakan diminta, jadi begini:

Saya menggunakan metode mark-and-precompute dari solusi. Itu memiliki nama yang tepat, tetapi saya sudah lama melupakannya; mungkin orang lain bisa menawarkannya?

Algoritma:

• Mulai dari kolom paling kanan dan berlanjut ke kiri, hitung yang berikut tentang setiap sel dalam kolom:
  • Penjumlahan dari pergerakan biaya terendah, didefinisikan sebagai biaya sel saat ini + sel biaya terendah yang dapat dicapai di kolom berikutnya
  • Tindakan gerakan yang harus diambil untuk mencapai biaya terendah ini, hanya sebagai langkah yang valid dari sel ini ke sel tunggal lainnya.
• Pipa ditangguhkan. Untuk menyelesaikan pipa, Anda perlu membuat kolom lengkap dihitung, jadi kami tidak menghitung pipa sampai kolom berikutnya.
  • Saat menentukan biaya terendah sel di sebelah kiri pipa, pertama-tama kita menghitung arah terbaik untuk melakukan perjalanan di sepanjang pipa - itu akan selalu memutuskan untuk naik, atau turun, jadi kami menghitungnya sekali.
  • Kami kemudian menyimpan, seperti semua sel lainnya, biaya terbaik (didefinisikan sebagai biaya sel yang kami raih dengan melakukan perjalanan naik atau turun di pipa) dan arah untuk melakukan perjalanan untuk mencapainya.

Catatan:

Itu dia. Kami memindai dari atas ke bawah, dari kanan ke kiri, satu kali; satu-satunya sel yang tersentuh (berpotensi) lebih dari satu kali adalah pipa, namun, setiap pipa hanya "terpecahkan" satu kali, membuat kita tetap berada dalam jendela O (m * n) kita.

Untuk menangani ukuran peta "ganjil", saya memilih untuk melakukan pra-pemindaian dan menormalkan panjang baris dengan menambahkan karakter nol. Karakter kosong dihitung sebagai "biaya nol" bergerak sama dengan pipa dan spasi. Kemudian, dalam mencetak solusinya, saya berhenti mencetak biaya atau bergerak ketika salah satu tepi jalan dinormalisasi tercapai, atau karakter nol tercapai.

Keindahan algoritma ini sangat sederhana, menerapkan aturan yang sama untuk setiap sel, menghasilkan solusi lengkap dengan menyelesaikan sub-masalah O (m * n), dan dalam hal kecepatan agak cepat. Itu menukar memori, membuat dua salinan dalam memori peta jalan secara efektif, yang pertama untuk menyimpan data "biaya terbaik" dan yang kedua untuk menyimpan data "bergerak terbaik" per sel; ini tipikal untuk pemrograman dinamis.