Detailed mathematical approach

Problem Summary

Langton's ant starts on an all-white infinite square grid. At each step it looks at the current cell, turns right if the cell is white and left if the cell is black, flips the color of that cell, and then moves forward by one unit. Project Euler 349 asks for the number of black cells after \(10^{18}\) steps, so a direct step-by-step simulation all the way to the target is impossible.

Mathematical Approach

Let \(c_t(x,y)\in\{0,1\}\) denote the color of cell \((x,y)\) after \(t\) steps, with \(1\) meaning black, and let \(a_t=(x_t,y_t)\) be the ant's position just before step \(t+1\). Define the black-cell count by

$B(t)=\sum_{(x,y)\in\mathbb{Z}^2} c_t(x,y).$

After any finite number of steps only finitely many cells have been visited, so this sum is finite. The problem is therefore to compute \(B(10^{18})\).

Local Update Rule

If the current cell is white, the ant turns right, paints that cell black, and moves forward. If the current cell is black, it turns left, paints that cell white, and moves forward. Writing the direction modulo 4 gives

$d_{t+1}=\begin{cases} d_t+1 \pmod 4,& c_t(a_t)=0,\\ d_t-1 \pmod 4,& c_t(a_t)=1, \end{cases}\qquad c_{t+1}(a_t)=1-c_t(a_t).$

Therefore the total number of black cells changes by exactly one at every step:

$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$

This is why the code can record the full history \(B(0),B(1),\dots,B(T_0)\) during simulation with very little extra work.

Why a Sparse Representation Works

The board is infinite, but almost every cell is white at any finite time. The implementations therefore store only the black cells. Toggling a cell means inserting it into the set if it was white, or removing it if it was black. The current black-cell count is simply the size of that set.

In C++ and Java, the pair \((x,y)\) is packed into a 64-bit integer key; in Python, it is stored directly as a tuple. This keeps the cost of one update essentially constant on average.

Highway Phase and Affine Periodicity

Langton's ant is famous for eventually leaving its chaotic transient and building a repeating diagonal "highway". The entire configuration is not strictly periodic in place, because the pattern drifts across the lattice, but it becomes periodic up to translation.

The quantity \(B(t)\) is translation-invariant, so during the highway phase there exist integers \(p>0\) and \(\Delta\) such that on a tail interval

$B(t+p)=B(t)+\Delta.$

With the parameters used in these programs, the detected tail has period \(p=104\) and gain \(\Delta=12\). In other words, every additional block of 104 moves creates a net increase of 12 black cells.

Detecting the Tail from Simulated Data

The code does not hard-code the highway constants. Instead it simulates exactly up to a moderate horizon \(T_0=200000\) and stores the count sequence.

For each candidate period \(1\le p\le 500\), it sets

$\Delta_p=B(T_0)-B(T_0-p)$

and tests whether

$B(t+p)-B(t)=\Delta_p$

holds throughout a long suffix window of length \(W=50000\). If a candidate survives that check, the algorithm then searches for the earliest start \(s\) from which the same relation remains valid until the end of the simulated range.

The C++ and Java versions make this "earliest start" search linear by precomputing a suffix-validity array. The Python version keeps the same logic in a simpler nested-loop form, which is still perfectly practical with the fixed thresholds used here.

Extrapolation Formula

Once a valid triple \((s,p,\Delta)\) has been found, any target \(T\ge s\) can be written as

$T=s+qp+r,\qquad 0\le r<p,$

where

$q=\left\lfloor\frac{T-s}{p}\right\rfloor,\qquad r=(T-s)\bmod p.$

Each full period contributes \(\Delta\) additional black cells, so

$\boxed{B(T)=B(s+r)+q\Delta.}$

This is the crucial reduction: after one finite simulation, the enormous target \(10^{18}\) is handled by ordinary integer arithmetic.

Worked Example: The First 10 Steps

The checkpoint used by the C++ solution verifies the initial black-cell sequence

$B(0..10)=0,1,2,3,4,3,4,5,6,7,6,$

so in particular \(B(10)=6\). This is a small but useful sanity check that the turn, flip, and move rules have been implemented correctly before any tail detection begins.

How the Code Works

All three implementations follow the same pipeline. First, simulateBlackCounts (or its Python equivalent) produces the history array counts. Next, detectLinearPattern scans candidate periods and returns a tail descriptor \((s,p,\Delta)\). Finally, extrapolateBlackCount evaluates the formula above at the target step.

The C++ version also includes checkpoints: it confirms \(B(10)=6\), verifies that the detected highway parameters are \(p=104\) and \(\Delta=12\), and checks that the extrapolation formula reproduces the directly simulated value at step \(150000\).

Complexity Analysis

The exact simulation takes \(O(T_0)\) expected time and \(O(M)\) memory for the black-cell set, where \(M\le T_0\). The history array for the values \(B(t)\) adds \(O(T_0)\) space.

The suffix verification across candidate periods costs about \(O(p_{\max}W)\), followed by a search for the earliest valid start. In C++ and Java that search is linear per surviving candidate; Python uses a simpler loop structure but the thresholds are fixed and small compared with \(10^{18}\). Once \((s,p,\Delta)\) is known, the final evaluation is \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=349
2. Langton's ant: Wikipedia — Langton's ant
3. Turmites and moving automata: Wikipedia — Turmite
4. Hash tables and expected constant-time lookup: Wikipedia — Hash table