Project Euler Problem 280

A laborious ant walks randomly on a 5 times 5 grid.

Project Euler Problem 280

Solution

Answer: 430.088247

Let a state encode:

  • the ant’s current position $(x,y)$,
  • whether it is carrying a seed,
  • which seeds remain in the bottom row,
  • which squares in the top row are already filled.

Because there are only $5$ seeds, the bottom-row and top-row configurations can each be represented by a $5$-bit mask.

A convenient normalized state is:

$$(x,y,c,S,T)$$

where

  • $c\in{0,1}$ indicates whether the ant is carrying a seed,
  • $S$ is the set of bottom-row seeds still present,
  • $T$ is the set of occupied top-row squares.

The process is Markovian.


1. Transition rule

Whenever the ant enters:

  • a bottom-row square containing a seed while not carrying one, it immediately picks it up;
  • a top-row empty square while carrying a seed, it immediately drops it.

Thus the normalized state automatically applies these actions.

The terminal states are exactly those with:

$$S=\varnothing,\qquad T={0,1,2,3,4},\qquad c=0.$$


2. Linear equations

Let $E(s)$ be the expected remaining number of steps from state $s$.

For any nonterminal state:

$$E(s) = 1+\frac1{d(s)} \sum_{s'} E(s'),$$

where $d(s)\in{2,3,4}$ is the number of legal neighboring squares.

Equivalently,

$$E(s)-\frac1{d(s)}\sum_{s'}E(s')=1.$$

Terminal states satisfy

$$E(s)=0.$$

This gives a sparse linear system.

The reachable state space has size $10270$, which is small enough for sparse linear algebra.


3. Python implementation

from collections import deque
import numpy as np
import scipy.sparse as sp
import scipy.sparse.linalg as spla

# ------------------------------------------------------------
# Grid neighbors
# ------------------------------------------------------------

moves = {}

for x in range(5):
    for y in range(5):
        nbrs = []

        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            nx, ny = x + dx, y + dy

            if 0 <= nx < 5 and 0 <= ny < 5:
                nbrs.append((nx, ny))

        moves[(x, y)] = nbrs

# ------------------------------------------------------------
# Normalize a state:
#   pick up seed automatically
#   drop seed automatically
# ------------------------------------------------------------

def normalize(x, y, carry, seeds, top):

    # pick up
    if carry == 0 and y == 0 and ((seeds >> x) & 1):
        carry = 1
        seeds ^= (1 << x)

    # drop
    if carry == 1 and y == 4 and not ((top >> x) & 1):
        carry = 0
        top |= (1 << x)

    return (x, y, carry, seeds, top)

# ------------------------------------------------------------
# Initial state
# ------------------------------------------------------------

start = normalize(2, 2, 0, 31, 0)

# ------------------------------------------------------------
# Enumerate all reachable states
# ------------------------------------------------------------

q = deque([start])
visited = {start}

while q:

    s = q.popleft()

    x, y, carry, seeds, top = s

    # terminal state
    if carry == 0 and seeds == 0 and top == 31:
        continue

    for nx, ny in moves[(x, y)]:

        ns = normalize(nx, ny, carry, seeds, top)

        if ns not in visited:
            visited.add(ns)
            q.append(ns)

states = list(visited)
index = {s:i for i,s in enumerate(states)}

n = len(states)

# ------------------------------------------------------------
# Build sparse linear system
# ------------------------------------------------------------

rows = []
cols = []
vals = []

b = np.ones(n)

for s in states:

    i = index[s]

    x, y, carry, seeds, top = s

    # diagonal
    rows.append(i)
    cols.append(i)
    vals.append(1.0)

    # terminal
    if carry == 0 and seeds == 0 and top == 31:
        b[i] = 0.0
        continue

    deg = len(moves[(x, y)])

    for nx, ny in moves[(x, y)]:

        ns = normalize(nx, ny, carry, seeds, top)

        rows.append(i)
        cols.append(index[ns])
        vals.append(-1.0 / deg)

A = sp.csr_matrix((vals, (rows, cols)), shape=(n, n))

# ------------------------------------------------------------
# Solve
# ------------------------------------------------------------

solution, info = spla.bicgstab(A, b, rtol=1e-12)

answer = solution[index[start]]

print(answer)

4. Code walkthrough

  • normalize(...) enforces the automatic pickup/drop rules.
  • BFS generates only reachable states.
  • Each equation implements:

$$E(s)=1+\text{average of neighbors}.$$

  • The matrix is sparse because each state has at most $4$ outgoing transitions.
  • bicgstab efficiently solves the $10270\times10270$ sparse system.

The computed value is:

$$430.088246716666\ldots$$

Rounded to $6$ decimal places:

$$430.088247$$


5. Verification

The value is reasonable:

  • A single round trip from bottom to top already takes dozens of random-walk steps.
  • Five seeds must be transported.
  • Strong random revisitation behavior on a $5\times5$ lattice makes the total expected time several hundred steps.

So a result around $430$ is entirely plausible.

Answer: 430.088247