Project Euler Problem 280
A laborious ant walks randomly on a 5 times 5 grid.
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.
bicgstabefficiently 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