The Final Stand - Defeat the Zombie Horde

Question

Introduction

You are alone on an island. The remainder of humanity is dead (probably due to the bug in user12345's code). The Zombie Pirate Horde has reached your island, and they are endless. It's time to kick ass or chew bubble gum, and you're all outta bubble gum.

Problem

Our doomsday scenario is described by 2 integers on a single line, m and n. On your island are outposts uniquely numbered from 1 to m. The following n lines each contain three integers, x, y, and z, separated by a space. x and y are the unique IDs of two outposts, and z is the number of zombies that will be encountered on the path between them.

When you travel a path, you lose z ammunition and you kill z zombies. If you travel the same path again, you will encounter the same number of zombies, unfortunately. All outposts generate +1 ammunition each time you travel a path. You begin with 100 ammunition at outpost 1. All outposts begin with 0 ammunition. You die immediately if no path exists for which your ammunition is greater than the number of zombies on that path, and the remainder of your ammunition is converted to kills. Such is your final stand.

Write a program that outputs the maximum number of zombies you can kill for a given scenario. If you can kill an infinite number of zombies, simply output x.

Example Input

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

Example Output

x

Assumptions

• A path will be between two valid outposts. That is to say 1 <= x/y <= m
• If a path between x and y is not listed, it cannot be traveled
• A path is bidirectional
• 1 < m <= 100
• 1 < n <= 500
• Input must be provided through stdin, read from a file, or accepted as a sole argument to the program, and it must exactly follow the format of the example
• The runtime of your program may be arbitrarily large but must be determinably finite

The code with the fewest characters wins!

Answer 1

Java ( less grotesque: 8415 5291 3301)

Ok. Basically, I'm embarrassed no-one has submitted a solution. So a few days ago I began trying to solve this problem, b/c it's great.. Follow that link to watch my progress on it via GitHub.

Edit

New solver version, much more "golfed", with corrected cycle checker as identified by MT0. It also supports fast-forwarding routes, tuneable by changing how much memory is available to the VM. Latest BIG edit: realized that I had a few other small index errors and premature optimizations, that resulted in a failure to consider quite a large number of types of wins. So that's fixed, carefully. The new version is both smaller and below. For our reference route, java -Xmx2GB ZombieHordeMin does the trick quite nicely (be warned, it will take a while).

Cool factoid

In a fascinating twist, there are MANY solutions at length 24, and my solver finds one different from MT0's, but identical in principle, except that it starts by visiting the the other outposts connected to 1. Fascinating! Totally counter human intuition, but perfectly valid.

Solution Highlights

So here's mine. It's (partially) golfed, b/c it's an exponential, almost-brute-force solver. I use an IDDFS (iterative deepening depth first search) algorithm, so it's a great general solver that doesn't skip, so it solves both parts of the OP's question, namely:

• If a winning route is found (infinite zombies), output 'x'.
• If all routes end in death (finite zombies), output the largest number of zombies killed.

Give it enough power, memory, and time, and it will do just that, even slow-death maps. I spent some more time improving this solver, and while more can be done, it's a bit better now. I also integrated MT0's advice on the best infinite-zombies solution, and removed several premature optimizations from my win-checker that prevented the previous version from finding it, and now I do in fact find a very similar solution to the one MT0 described.

A few other highlights:

• As mentioned, uses an IDDFS to find the shortest possible winning route.
• Since it is at core a DFS, it will also discover if every route ends in the death of our hero, and keeps track of the "best" route in terms of most zombies killed. Die a hero!
• I've instrumented the algorithm to make it more interesting to watch Removed for golfing purposes. Follow one of the links to github to see the ungolfed version.
• There are a number of comments throughout as well, so feel free to re-implement for your own solution building on my approach, or show me how it should be done!
• Memory-adaptive route fast-forwarding
  • Up to available system memory, will keep track of "end routes" that did not result in death.
  • Using a fancy route compression and decompression routine, progress from a prior iteration of IDDFS is restored to prevent rediscovery all prior visited routes.
  • As an intentional side-bonus, acts as a dead-end route cull. Dead end routes aren't stored, and will never be visited again in future depths of IDDFS.

History of the solver

• I tried a bunch of one-step look-ahead algorithms, and while for very simple scenarios they would work, ultimately they fall flat.
• Then I tried a two-step look-ahead algorithm, which was.. unsatisfying.
• I then began building an n-step lookahead, when I recognized that this approach is reducible to DFS, yet DFS is far ... more elegant.
• While building the DFS, it occurred to me that IDDFS would ensure (a) find best HERO (death) route or (b) first winning cycle.
• Turns out building a win-cycle checker is easy, but I had to go through several very very wrong iterations before I got to a provably successful checker.
• Factored in MT0's win-path to remove three lines of premature optimization that made my algorithm blind to it.
• Added an adaptive route-caching algorithm that will use all the memory you give it to prevent unnecessary redoing of work between IDDFS calls, and also culls dead-end routes up to the limits of memory.

The (golfed) code

On to the code (get the ungolfed version here or here):

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

Get the code from github here, to track any changes I make. Here are some other maps I used.

Output example

Example output for reference solution:

    $ 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

Read the route output like this: step:source,route-to-get-here-ammo. So in the above solution, you would read it as:

• At step 0, at outpost 1 with ammo 100.
• At step 1, use route 1 to get to outpost 3 with ending ammo 97
• At step 2, use route 1 to get to outpost 1 with ending ammo 95
• ...

Closing notes

So, I hope I've made my solution harder to beat, but PLEASE TRY! Use it against me, add in some parallel processing, better graph theory, etc. A couple of things I figure could improve this approach:

• aggressively "reduce" loops to cut out needless retread as the algorithm progresses.
  • An example: in the example problem, consider the loops 1-2-3 and other permutations as "one step", so that we can make our way to end-cycle more quickly.
  • E.g. if you are at node 1, you can either (a) go to 2, (b) go to 1, (c) go through 1-2-3 as one step and so on. This would allow a solved to fold depth into breadth, increasing the number of routes at a particular depth but greatly speeding time-to-solution for long cycles.
• cull dead routes. My current solution doesn't "remember" that a particular route is dead-ended, and has to rediscover it every time. It would be better to keep track of the earliest moment in a route that death is certain, and never progress beyond it. did this...
• if careful, you could apply the dead route culling as a sub-route cull. By example, if 1-2-3-4 always results in death, and the solver is about to test the route 1-3-1-2-3-4, it should immediately stop descending that path as it is guaranteed to end in disappointment. It would still be possible to calculate # of kills, with some careful math.
• Any other solution that trades memory for time, or allows aggressive avoidance of following dead-end routes. did this too!

Answer 2

Some abstract notes on a solution

If I get time I'll convert this into an algorithm...

For a given graph G then there exists a connected sub-graph G' which contains town 1. If there is an infinite solution then there will exist a connected sub-graph G'' of G' which contains V towns and P paths.

The paths P of G'' can be partitioned such that {p} contains a path which has then minimal cost of all the paths in P and P/{p} is all the other paths (forming a spanning tree or possibly a cycle). If we assume that p is not a looping edge (connecting both ends to the same town) then it will connect two towns (v1 and v2) and has cost c ammunition then you (the survivor) can then traverse from v1 to v2 and back at a total cost of 2c ammunition and this will increase the ammunition in all the towns by 2 (for a total increase of 2|V| within G'' - some of which will have been collected from v1 and v2).

If you travel from v1 to v2 and back to v1 multiple (m) times and then take a trip from v1 along the edges P/{p} to visit all the towns other than v1 and v2 before returning to v1 and this takes n paths to achieve (where |P/{p}| ≤ n ≤ 2|P/{p}| since you should never need to traverse a path more than twice) with a cost of k and the towns will gain 2m|V| ammunition (again some of which will have been collected during traversal).

Given all this then you can tell if an infinite solution is potentially possible if then cost k + 2mc is equal or lower than the total reward 2(m+n)|V|.

There is a additional complexity to the problem in that:

• you may need to travel from the starting town 1 to {p} on the first iteration and need to factor in this cost; and
• you also need to ensure that the m and n are low enough that you don't run out of ammunition before you can make it through the first iteration since the first iteration will have a higher cost than the subsequent iterations).

This leads to a 24 path cost neutral solution to the example in the question (the numbers are the towns visited):

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 ...