A while ago I wrote this blog post on this problem. The previous code was able to produce the answer in about 20 minutes, using several gigabytes of RAM.

You may want to read the previous blog post first.

There is a simpler and more efficient solution (used by *inamori*, *zwuupeape*, and many others).

### The new approach

We do not need to know the exact value of the solution, only an approximate. This approximation has to be accurate only to six digits.

Any any step, there is a certain probability that the ant will reach the final state *in that step*.

Let’s call this function : the probability that the ant will reach the final state on step *s*:

At very small values of *s*, the probability is zero because it takes a certain number of steps to get to the final position. 44 is the smallest number of steps to get from the initial to the final position, and the probability increases from there.

But it only increases until a certain point. After that point, the probability decreases. After all, if we run this for thousands of steps, how likely is the ant to *still* not have reached the final position?

However, the graph continues forever to the right. Even after thousands of steps, there is still a chance, however small, that the final position hasn’t been reached.

Let’s define as the *weighted average* of the probabilities of each value of from 0 to *s*:

The expected value and the answer for this problem would simply be the weighted average for the entire graph.

Since *s* must be an integer greater than zero, we don’t have to do any integration with curves. A bit misleading because I’ve drawn and as curves, when they are not.

But because cannot be expressed algebraically, we cannot evaluate it as it approaches infinity. Instead, we pick a point that gives us enough precision:

Either that, or we keep calculating the weighted average while increasing *s* until we have enough precision.

### Calculating the probabilities

In order to calculate a weighted average , we need to be able to calculate ; while is the probability function for the *final state*, we’ll need to know the probabilities for the in-between states as well.

The probabilities of the states on step *s* depend most upon the probabilities of the previous step, *s-1*.

So if on step *s-1* there’s a 0.6 probability that we’re on state *X*, then on step *s* we should have a 0.3 probability of being on either *Y* or *Z* as there’s an equal chance of moving to either state.

And if multiple states can go to our state, we can get the probability by adding up the probabilities:

### Coding a solution

At first we start on the initial state, with a probability of 1 (certain chance) of being on it.

On each step we generate a new set of probabilities using rules I described above, and so on.

A lot of code is stolen from my previous work on this problem. The `State`

class is essentially unchanged in this version.

Here’s the code:

import java.util.*; public class Main{ public static void main(String[] args){ final int ITERATIONS = 2501; // Initialize probability map. // The initial step is 0, containing the initial position with a probability of 1. Map<State,Double> prevProbs = new LinkedHashMap<State,Double>(); prevProbs.put(State.INIT_STATE, 1.0); // Distributions for the final state. double[] finalValues = new double[ITERATIONS+1]; Arrays.fill(finalValues, 0); // Keep the time. long startTime = System.currentTimeMillis(); // Loop counter is actually the step number of the next step. for(int step=1; step<ITERATIONS; step++){ // Make new probabilities. Map<State,Double> nextProbs = new LinkedHashMap<State,Double>(); // Loop through old probabilities and add Set<State> stateSet = prevProbs.keySet(); for(State state : stateSet){ // Probability of being on this state right now double stateProb = prevProbs.get(state); // List of next states List<State> nextStates = nextStates(state); // Probability factor for each of the next states double multiplier = 1.0 / nextStates.size(); // Added value to each of the next states double added = stateProb * multiplier; // Now go and update all the state probabilities. for(State nextState : nextStates){ // If we've got the final state, handle it separately. if(nextState.equals(State.FINAL_STATE)){ finalValues[step] += added; continue; } // Could be the first time. if(!nextProbs.containsKey(nextState)) nextProbs.put(nextState, added); // Might not be the first time. else { // Old value, we need to add to it instead of replacing it. double previous = nextProbs.get(nextState); nextProbs.put(nextState, previous + added); } } } // Our new probabilities are the old probabilities for the next loop. prevProbs = nextProbs; System.out.println(step + " " + weightedAverage(finalValues)); } System.out.println((System.currentTimeMillis() - startTime) + "ms"); } // Calculates a weighted average of a double array with the indices as // values and the values in the array as weights. static double weightedAverage(double[] array){ double sumValues = 0; for(int i=0; i<array.length; i++) sumValues += i * array[i]; return sumValues; } // Returns a list of possible continuation states from the current one. static List<State> nextStates(State state){ // Current and changing position of the ant int antX = state.ant % 5; int antY = state.ant / 5; // Whether it can go into each of the four directions (N,S,E,W respectively). boolean[] possibleDirs = new boolean[4]; Arrays.fill(possibleDirs, true); // Take out some directions if it's in the corner. if(antY == 0) possibleDirs[0] = false; // Can't go north if(antY == 4) possibleDirs[1] = false; // Can't go south if(antX == 4) possibleDirs[2] = false; // Can't go east if(antX == 0) possibleDirs[3] = false; // Can't go west // Construct a list of continuations. List<State> nextStates = new ArrayList<State>(); // Loop through the four directions. for(int i=0; i<4; i++){ // Cannot go this direction. if( !(possibleDirs[i])) continue; int newAntX = antX; int newAntY = antY; // Modify direction. switch(i){ case 0: newAntY--; break; case 1: newAntY++; break; case 2: newAntX++; break; case 3: newAntX--; break; } // Start constructing new state object. int oldAnt = state.ant; // old ant position int newAnt = 5*newAntY + newAntX; int[] board = state.board.clone(); boolean carrying = state.carrying; // Carrying a seed. Notice that a square can contain // two seeds at once (but not more); seeds are indistinguishable // so we just need to keep track of the number of seeds // on each square. if(carrying){ board[oldAnt] --; board[newAnt] ++; } // Drop off the seed. if(newAntY == 0 && board[newAnt] == 1 && carrying) carrying = false; // Pick up a new seed. if(newAntY == 4 && board[newAnt] == 1 && !carrying) carrying = true; // Treat the five done positions the same. if(donePosition(board)) nextStates.add(State.FINAL_STATE); // Add it normally. else nextStates.add(new State(board, newAnt, carrying)); } return nextStates; } // Is the board in the done position? static boolean donePosition(int[] b){ return b[0]==1 && b[1]==1 && b[2]==1 && b[3]==1 && b[4]==1; } } class State{ static final State INIT_STATE = new State( new int[]{ 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 1,1,1,1,1 }, 12, false); // Consider all final states the same; there is // no ant position. static final State FINAL_STATE = new State( new int[]{ 1,1,1,1,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0 }, -1, true); // 25 board. int[] board; int ant; boolean carrying; State(int[] board, int ant, boolean carrying){ this.board = board; this.ant = ant; this.carrying = carrying; } State(State s){ this(s.board, s.ant, s.carrying); } public boolean equals(Object o){ State s = (State) o; return Arrays.equals(s.board, board) && s.ant == ant && s.carrying == carrying; } public int hashCode(){ return Arrays.hashCode(board) + ant; } // For debugging mostly. public String toString(){ StringBuilder ret = new StringBuilder("\n"); for(int i=0; i<5; i++){ for(int j=0; j<5; j++){ int pos = 5*i + j; if(ant == pos) ret.append("#"); else ret.append(board[pos] >= 1? "+" : "-"); } ret.append("\n"); } return ret.toString(); } }

As we run this program, the answer becomes more and more accurate. We only need 2300 or 2500 steps to get the six digits of accuracy we need.

Running the program:

This takes just over a minute to run — not bad at all.

After reading someone else’s solution, just how dishonored of a dog would I be to redo it and score the point on Project Euler?

I have been a fool to have looked for spoilers. I shall never forgive myself.

Thanks for the articles; good reads!

LikeLike

I haven’t had enough time to fully understand your approach but I thought, if we want the max of P(s) would it not be simpler to calculate values of P(s) until P(s) > P(s+1)? and then answer = s?

cheers

LikeLike

Yes; but I don’t think we’re trying to calculate the maximum of P(s), rather to approximate the integral of it from 0 to infinity.

LikeLike