Stand Terakhir - Kalahkan Zombie Horde

25

pengantar

Anda sendirian di sebuah pulau. Sisa umat manusia sudah mati ( mungkin karena bug dalam kode user12345 ). Zombie Pirate Horde telah mencapai pulau Anda, dan mereka tidak ada habisnya. Saatnya untuk menendang pantat atau mengunyah permen karet, dan Anda semua keluar dari permen karet.

Masalah

Skenario kiamat kami dijelaskan oleh 2 bilangan bulat pada satu baris, mdan n. Di pulau Anda ada pos-pos unik yang diberi nomor mulai dari 1 hingga m. Berikut ini ngaris masing-masing berisi tiga bilangan bulat, x, y, dan z, dipisahkan oleh spasi. xdan ymerupakan ID unik dari dua pos terdepan, dan zmerupakan jumlah zombie yang akan ditemui di jalur di antara mereka.

Ketika Anda menempuh jalan, Anda kehilangan zamunisi dan Anda membunuh zzombie. Jika Anda menempuh jalan yang sama lagi, sayangnya, Anda akan menemukan jumlah zombie yang sama. Semua pos menghasilkan amunisi +1 setiap kali Anda menempuh jalur. Anda mulai dengan 100 amunisi di pos 1. Semua pos dimulai dengan 0 amunisi. Anda langsung mati jika tidak ada jalur yang amunisi Anda lebih besar dari jumlah zombie di jalur itu, dan sisa amunisi Anda dikonversi menjadi kill. Itulah pendirian terakhir Anda.

Tulis program yang menghasilkan jumlah zombie maksimum yang dapat Anda bunuh untuk skenario yang diberikan. Jika Anda dapat membunuh zombie dalam jumlah tak terbatas, cukup output x.

Contoh Input

5 6
1 2 4
2 3 4
3 1 4
2 4 10
2 5 10
1 1 50

Contoh Output

x

Asumsi

  • Jalur akan berada di antara dua pos yang valid. Artinya 1 <= x/ y<=m
  • Jika jalur antara xdan ytidak terdaftar, itu tidak dapat dilalui
  • Jalan adalah dua arah
  • 1 m<<= 100
  • 1 n<<= 500
  • Input harus diberikan melalui stdin, membaca dari file, atau diterima sebagai argumen tunggal untuk program, dan harus persis mengikuti format contoh
  • Runtime dari program Anda mungkin besar sembarang tetapi harus terbatas

Kode dengan karakter paling sedikit menang!

code-golf Rainbolt
sumber
Apakah setiap pos selain 1mulai dengan 0 amunisi? Apakah grafiknya tidak langsung?
Peter Taylor
2
Mungkin juga akan berguna untuk mencegah kelas bug tertentu dengan memiliki test case di mana ada siklus yang tidak menurunkan amunisi Anda tetapi tidak dapat dicapai dalam waktu. (Saya harus menambahkan bahwa saya tidak yakin bahwa test case saat ini benar: bagi saya sepertinya siklus itu 1->1membutuhkan amunisi 49, dan siklus itu 1->2->3->1memakan amunisi 3 dalam jangka panjang.
Peter Taylor
@PeterTaylor Saya harus menarik kembali kedua komentar saya karena tampaknya saya membuat contoh dua arah . Jadi izinkan saya untuk memulai kembali - semua jalur dua arah dan semua pos mulai dengan 0. Contohnya sekarang harus berfungsi.
Rainbolt
@Rusher: Contoh yang bagus! Butuh saya 45 langkah untuk menunjukkan diri saya bahwa itu memang berkelanjutan tanpa batas. Bisakah kita berasumsi bahwa semua pos akan dapat dijangkau atau Anda ingin kami menangani kasus di mana ada pos yang terputus dari grafik utama?
Claudiu
1
Ahhh ... Jadi untuk setiap langkah dari A ke B, setiap pos "menghasilkan" amunisi dan menyimpannya di sana sampai Anda mengunjunginya.
Tobia

Jawaban:

14

Jawa ( kurang aneh: 8415 5291 3301)

Baik. Pada dasarnya, saya malu tidak ada yang mengajukan solusi. Jadi beberapa hari yang lalu saya mulai mencoba untuk menyelesaikan masalah ini, itu bagus. . Ikuti tautan itu untuk menyaksikan kemajuan saya di sana melalui GitHub.

Edit

Versi pemecah baru, lebih banyak "golf", dengan pemeriksa siklus yang diperbaiki sebagaimana diidentifikasi oleh MT0. Ini juga mendukung rute penerusan cepat, yang dapat disesuaikan dengan mengubah berapa banyak memori yang tersedia untuk VM. Sunting BIG terbaru : menyadari bahwa saya memiliki beberapa kesalahan indeks kecil dan optimasi prematur, yang mengakibatkan kegagalan untuk mempertimbangkan sejumlah besar jenis kemenangan. Jadi itu diperbaiki, hati-hati. Versi baru lebih kecil dan di bawah. Untuk rute referensi kami, java -Xmx2GB ZombieHordeMinlakukan triknya dengan cukup baik (diperingatkan, ini akan memakan waktu cukup lama).

Factoid keren

Dalam twist yang menarik, ada solusi BANYAK panjangnya 24, dan pemecah saya menemukan satu berbeda dari MT0, tetapi pada prinsipnya identik, kecuali bahwa itu dimulai dengan mengunjungi pos-pos lain yang terhubung 1. Menarik! Benar-benar melawan intuisi manusia, tetapi sangat valid.

Sorotan Solusi

Jadi ini milikku. Ini (sebagian) golf, b / c itu pemecah eksponensial, hampir kasar. Saya menggunakan algoritma IDDFS (iterative deepening depth first search), jadi ini adalah pemecah umum yang hebat yang tidak melewatkan, sehingga memecahkan kedua bagian dari pertanyaan OP, yaitu:

  • Jika rute kemenangan ditemukan (zombie tanpa batas), hasilkan 'x'.
  • Jika semua rute berakhir dengan kematian (zombie terbatas), hasilkan jumlah zombie terbanyak yang terbunuh.

Berikan kekuatan, ingatan, dan waktu yang cukup, dan itu akan melakukan hal itu, bahkan peta kematian lambat. Saya menghabiskan lebih banyak waktu untuk memperbaiki solver ini, dan sementara lebih banyak yang dapat dilakukan, itu sedikit lebih baik sekarang. Saya juga mengintegrasikan saran MT0 tentang solusi zombie tak terbatas terbaik, dan menghapus beberapa optimasi prematur dari win-checker saya yang mencegah versi sebelumnya menemukannya, dan sekarang saya sebenarnya menemukan solusi yang sangat mirip dengan yang dijelaskan oleh MT0.

Beberapa highlight lainnya:

  • Seperti disebutkan, menggunakan IDDFS untuk menemukan rute kemenangan sesingkat mungkin.
  • Karena itu adalah inti sebuah DFS, itu juga akan menemukan jika setiap rute berakhir dengan kematian pahlawan kita, dan melacak rute "terbaik" dalam hal sebagian besar zombie terbunuh. Mati pahlawan!
  • Saya telah memasukkan algoritme untuk membuatnya lebih menarik untuk ditonton Dihapus untuk tujuan bermain golf. Ikuti salah satu tautan ke github untuk melihat versi yang tidak diserang.
  • Ada sejumlah komentar juga, jadi jangan ragu untuk menerapkan kembali untuk solusi Anda sendiri berdasarkan pendekatan saya, atau tunjukkan padaku bagaimana itu harus dilakukan!
  • Rute fast-forwarding memori-adaptif
    • Hingga memori sistem yang tersedia, akan melacak "rute akhir" yang tidak mengakibatkan kematian.
    • Dengan menggunakan rutin rute kompresi dan dekompresi, kemajuan dari iterasi IDDFS sebelumnya dipulihkan untuk mencegah penemuan kembali semua rute yang dikunjungi sebelumnya.
    • Sebagai bonus sampingan yang disengaja, bertindak sebagai penyisihan rute jalan buntu. Rute jalan buntu tidak disimpan, dan tidak akan pernah dikunjungi lagi di kedalaman IDDFS mendatang.

Sejarah pemecah masalah

  • Saya mencoba sekelompok algoritma satu langkah melihat-depan, dan sementara untuk skenario yang sangat sederhana mereka akan bekerja, akhirnya mereka gagal.
  • Kemudian saya mencoba algoritma dua langkah melihat ke depan, yang .. tidak memuaskan.
  • Saya kemudian mulai membangun lookahead n-step, ketika saya menyadari bahwa pendekatan ini dapat direduksi ke DFS, namun DFS jauh ... lebih elegan.
  • Saat membangun DFS, terpikir oleh saya bahwa IDDFS akan memastikan (a) menemukan rute HERO (kematian) terbaik atau (b) siklus kemenangan pertama.
  • Ternyata membangun win-cycle checker itu mudah, tetapi saya harus melalui beberapa iterasi yang sangat salah sebelum saya sampai ke checker yang terbukti berhasil.
  • Dipertimbangkan dalam win-path MT0 untuk menghapus tiga baris optimasi prematur yang membuat algoritma saya buta untuk itu.
  • Menambahkan algoritma caching rute adaptif yang akan menggunakan semua memori yang Anda berikan untuk mencegah pengerjaan ulang yang tidak perlu antara panggilan IDDFS, dan juga memilah rute buntu hingga batas memori.

Kode (golf)

Aktif ke kode (dapatkan versi yang tidak di -serigala di sini atau di sini ):

import java.util.*;public class ZombieHordeMin{int a=100,b,m,n,i,j,z,y,D=0,R,Z,N;int p[][][];Scanner in;Runtime rt;int[][]r;int pp;int dd;int[][]bdr;int ww;int[][]bwr;int[][]faf;int ff;boolean ffOn;public static void main(String[]a){(new ZombieHordeMin()).pR();}ZombieHordeMin(){in=new Scanner(System.in);rt=Runtime.getRuntime();m=in.nextInt();N=in.nextInt();p=new int[m+1][m+1][N+1];int[]o=new int[m+1];for(b=0;b<N;b++){i=in.nextInt();j=in.nextInt();z=in.nextInt();o[i]++;o[j]++;D=(o[i]>D?o[i]:D);p[i][j][++p[i][j][0]]=z;if(i!=j)p[j][i][++p[j][i][0]]=z;D=(o[j]>D?o[j]:D);}m++;}void pR(){r=new int[5000][m+3];r[0][0]=a;Arrays.fill(r[0],1,m,1);r[0][m]=1;r[0][m+1]=0;r[0][m+2]=0;ww=-1;pp=dd=0;pR(5000);}void pR(int aMD){faf=new int[D][];ff=0;ffOn=true;for(int mD=1;mD<=aMD;mD++){System.out.printf("Checking len %d\n",mD);int k=ffR(0,mD);if(ww>-1){System.out.printf("%d x\n",ww+1);for(int win=0;win<=ww;win++)System.out.printf(" %d:%d,%d-%d",win,bwr[win][0],bwr[win][1],bwr[win][2]);System.out.println();break;}if(k>0){System.out.printf("dead max %d kills, %d steps\n",pp,dd+1);for(int die=0;die<=dd;die++)System.out.printf(" %d:%d,%d-%d",die,bdr[die][0],bdr[die][1],bdr[die][2]);System.out.println();break;}}}int ffR(int dP,int mD){if(ff==0)return pR(dP,mD);int kk=0;int fm=ff;if(ffOn&&D*fm>rt.maxMemory()/(faf[0][0]*8+12))ffOn=false;int[][]fmv=faf;if(ffOn){faf=new int[D*fm][];ff=0;}for(int df=0;df<fm;df++){dS(fmv[df]);kk+=pR(fmv[df][0],mD);}fmv=null;rt.gc();return kk==fm?1:0;}int pR(int dP,int mD){if(dP==mD)return 0;int rT=0;int dC=0;int src=r[dP][m];int sa=r[dP][0];for(int dt=1;dt<m;dt++){for(int rut=1;rut<=p[src][dt][0];rut++){rT++;r[dP+1][0]=sa-p[src][dt][rut]+r[dP][dt];for(int cp=1;cp<m;cp++)r[dP+1][cp]=(dt==cp?1:r[dP][cp]+1);r[dP+1][m]=dt;r[dP+1][m+1]=rut;r[dP+1][m+2]=r[dP][m+2]+p[src][dt][rut];if(sa-p[src][dt][rut]<1){dC++;if(pp<r[dP][m+2]+sa){pp=r[dP][m+2]+sa;dd=dP+1;bdr=new int[dP+2][3];for(int cp=0;cp<=dP+1;cp++){bdr[cp][0]=r[cp][m];bdr[cp][1]=r[cp][m+1];bdr[cp][2]=r[cp][0];}}}else{for(int chk=0;chk<=dP;chk++){if(r[chk][m]==dt){int fR=chk+1;for(int cM=0;cM<m+3;cM++)r[dP+2][cM]=r[dP+1][cM];for(;fR<=dP+1;fR++){r[dP+2][0]=r[dP+2][0]-p[r[dP+2][m]][r[fR][m]][r[fR][m+1]]+r[dP+2][r[fR][m]];for(int cp=1;cp<m;cp++)r[dP+2][cp]=(r[fR][m]==cp?1:r[dP+2][cp]+1);r[dP+2][m+2]=r[dP+2][m+2]+p[r[dP+2][m]][r[fR][m]][r[fR][m+1]];r[dP+2][m]=r[fR][m];r[dP+2][m+1]=r[fR][m+1];}if(fR==dP+2&&r[dP+2][0]>=r[dP+1][0]){ww=dP+1;bwr=new int[dP+2][3];for(int cp=0;cp<dP+2;cp++){bwr[cp][0]=r[cp][m];bwr[cp][1]=r[cp][m+1];bwr[cp][2]=r[cp][0];}return 0;}}}dC+=pR(dP+1,mD);if(ww>-1)return 0;}for(int cp=0;cp<m+3;cp++)r[dP+1][cp]=0;}}if(rT==dC)return 1;else{if(ffOn&&dP==mD-1)faf[ff++]=cP(dP);return 0;}}int[]cP(int dP){int[]cmp=new int[dP*2+3];cmp[0]=dP;cmp[dP*2+1]=r[dP][0];cmp[dP*2+2]=r[dP][m+2];for(int zip=1;zip<=dP;zip++){cmp[zip]=r[zip][m];cmp[dP+zip]=r[zip][m+1];}return cmp;}void dS(int[]cmp){int[]lv=new int[m];int dP=cmp[0];r[dP][0]=cmp[dP*2+1];r[dP][m+2]=cmp[dP*2+2];r[0][0]=100;r[0][m]=1;for(int dp=1;dp<=dP;dp++){r[dp][m]=cmp[dp];r[dp][m+1]=cmp[dP+dp];r[dp-1][cmp[dp]]=dp-lv[cmp[dp]];r[dp][m+2]=r[dp-1][m+2]+p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];r[dp][0]=r[dp-1][0]+r[dp-1][cmp[dp]]-p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];lv[cmp[dp]]=dp;}for(int am=1;am<m;am++)r[dP][am]=(am==cmp[dP]?1:dP-lv[am]+1);}}

Dapatkan kode dari github di sini, untuk melacak setiap perubahan yang saya buat. Berikut adalah beberapa peta lain yang saya gunakan.

Contoh keluaran

Contoh output untuk solusi referensi:

    $ java -d64 -Xmx3G ZombieHordeMin > reference_route_corrected_min.out
    5 6 1 2 4 2 3 4 3 1 4 2 4 10 2 5 10 1 1 50
    Checking len 1
    Checking len 2
    Checking len 3
    Checking len 4
    Checking len 5
    Checking len 6
    Checking len 7
    Checking len 8
    Checking len 9
    Checking len 10
    Checking len 11
    Checking len 12
    Checking len 13
    Checking len 14
    Checking len 15
    Checking len 16
    Checking len 17
    Checking len 18
    Checking len 19
    Checking len 20
    Checking len 21
    Checking len 22
    Checking len 23
    Checking len 24
    25 x
     0:1,0-100 1:3,1-97 2:1,1-95 3:2,1-94 4:5,1-88 5:2,1-80 6:4,1-76 7:2,1-68 8:1,1-70 9:2,1-68 10:1,1-66 11:2,1-64 12:1,1-62 13:2,1-60 14:1,1-58 15:2,1-56 16:1,1-54 17:2,1-52 18:1,1-50 19:2,1-48 20:1,1-46 21:2,1-44 22:1,1-42 23:2,1-40 24:1,1-38

Baca output rute seperti ini step:: source, route-to-get-here- ammo. Jadi dalam solusi di atas, Anda akan membacanya sebagai:

  • Pada langkah 0, di pos terdepan 1dengan amunisi 100.
  • Pada langkah 1, gunakan rute 1untuk mencapai pos 3dengan amunisi berakhir97
  • Pada langkah 2, gunakan rute 1untuk mencapai pos 1dengan amunisi berakhir95
  • ...

Catatan penutup

Jadi, saya harap saya membuat solusi saya lebih sulit untuk dikalahkan, tapi TOLONG MENCOBA! Gunakan untuk melawan saya, tambahkan beberapa pemrosesan paralel, teori grafik yang lebih baik, dll. Beberapa hal yang saya pikir dapat meningkatkan pendekatan ini :

  • "kurangi" secara agresif loop untuk memotong ulang yang tidak perlu saat algoritme berlangsung.
    • Contoh: dalam contoh masalah, pertimbangkan loop 1-2-3 dan permutasi lainnya sebagai "satu langkah", sehingga kita dapat membuat jalan kita untuk mengakhiri siklus lebih cepat.
    • Misalnya, jika Anda berada di simpul 1, Anda dapat (a) pergi ke 2, (b) pergi ke 1, (c) melewati 1-2-3 sebagai satu langkah dan seterusnya. Ini akan memungkinkan penyelesaian untuk melipat kedalaman menjadi lebar, meningkatkan jumlah rute pada kedalaman tertentu tetapi sangat mempercepat waktu-untuk-solusi untuk siklus panjang.
  • menyisihkan rute mati. Solusi saya saat ini tidak "ingat" bahwa rute tertentu buntu, dan harus menemukan kembali setiap waktu. Akan lebih baik untuk melacak momen paling awal dalam rute yang kematiannya pasti, dan tidak pernah maju setelahnya. melakukan ini ...
  • jika hati-hati, Anda bisa menerapkan culling rute mati sebagai cull sub-rute. Sebagai contoh, jika 1-2-3-4 selalu menghasilkan kematian, dan pemecah akan menguji rute 1-3-1-2-3-4, itu harus segera berhenti menuruni jalan itu karena dijamin akan berakhir dalam kekecewaan. Masih mungkin untuk menghitung jumlah pembunuhan, dengan perhitungan yang cermat.
  • Solusi lain yang memperdagangkan memori untuk waktu tertentu, atau memungkinkan penghindaran agresif mengikuti rute buntu. lakukan ini juga!
ProgrammerDan
sumber
Jawaban bagus! Siapa yang butuh kode golf ketika mereka adalah satu-satunya yang dapat memecahkan masalah? Saya termotivasi sekarang untuk menulis solusi saya sendiri, jadi saya akan mengerjakannya.
Rainbolt
Luar biasa, itulah yang saya harapkan akan dilakukan. Jangan ragu untuk meminjam / mencuri apa pun dari jawaban saya yang menurut Anda berguna! Meskipun tentu saja saya berharap orang lain selain saya sendiri dan OP akan mencoba menyelesaikannya: P
ProgrammerDan
Saya dialihkan dan mulai mengecilkan kode Anda. Jika Anda menganggap jawaban Anda aneh sebelumnya, lihat ini: tny.cz/17ef0b3a . Masih dalam proses.
Rainbolt
Haha, Anda benar-benar teralihkan. Terlihat bagus (cukup mengerikan untuk kode-golf? Anda tahu apa yang saya maksud) sejauh ini!
ProgrammerDan
@Rusher Keberuntungan sejauh ini? Saya punya beberapa ide untuk perbaikan yang telah saya buat, termasuk teknik kompresi representasi rute dan cara memajukan melalui rute yang sudah diproses (hingga titik tertentu).
ProgrammerDan
2

Beberapa catatan abstrak tentang suatu solusi

Jika saya punya waktu, saya akan mengonversinya menjadi sebuah algoritma ...

Untuk grafik yang diberikan Gmaka ada sub-grafik terhubung G'yang berisi kota 1. Jika ada solusi tak terbatas maka akan ada sub-graf terhubung G''dari G'yang berisi Vkota-kota dan Pjalan.

Jalur Pdari G''dapat dipartisi sehingga {p}mengandung jalur yang memiliki biaya maka minimal semua jalan di Pdan P/{p}semua jalan lain (membentuk spanning tree atau mungkin siklus). Jika kita berasumsi bahwa pitu bukan perulangan (menghubungkan kedua ujungnya ke kota yang sama) maka itu akan menghubungkan dua kota ( v1dan v2) dan memiliki camunisi biaya maka Anda (yang selamat) kemudian dapat melintasi dari dan v1ke v2belakang dengan total biaya 2camunisi dan ini akan menambah amunisi di semua kota sebesar 2 (untuk peningkatan total di 2|V|dalam G''- beberapa di antaranya akan dikumpulkan dari v1dan v2).

Jika Anda melakukan perjalanan dari v1untuk v2dan kembali ke v1beberapa ( m) kali dan kemudian melakukan perjalanan dari v1sepanjang tepi P/{p}untuk mengunjungi semua kota-kota selain v1dan v2sebelum kembali ke v1dan ini membutuhkan njalur untuk mencapai (di mana |P/{p}| ≤ n ≤ 2|P/{p}|karena Anda tidak pernah harus perlu melintasi jalur yang lebih dari dua kali) dengan biaya kdan kota-kota akan mendapatkan 2m|V|amunisi (lagi beberapa di antaranya akan dikumpulkan selama perjalanan).

Dengan semua ini maka Anda dapat mengetahui apakah solusi yang tak terbatas berpotensi terjadi jika biaya k + 2mcsama atau lebih rendah dari total hadiah 2(m+n)|V|.

Ada kompleksitas tambahan untuk masalah ini yaitu:

  • Anda mungkin perlu melakukan perjalanan dari kota awal 1ke {p}pada iterasi pertama dan perlu memperhitungkan biaya ini; dan
  • Anda juga perlu memastikan bahwa mdan ncukup rendah sehingga Anda tidak kehabisan amunisi sebelum Anda dapat membuatnya melalui iterasi pertama karena iterasi pertama akan memiliki biaya yang lebih tinggi daripada iterasi berikutnya).

Ini mengarah ke solusi netral biaya 24 jalur untuk contoh dalam pertanyaan (jumlahnya adalah kota-kota yang dikunjungi):

1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,2,4,2,5,2,3, ... and repeat ...
MT0
sumber
Satu hal kecil untuk ditambahkan - Anda mungkin harus mempertimbangkan perulangan tepi dengan biaya 1, karena tepi itu sendiri membentuk kondisi menang jika Anda dapat mencapainya tepat waktu.
Rainbolt