Problem 349: Langton's Ant
View on Project EulerProject Euler Problem 349 Solution
EulerSolve provides an optimized solution for Project Euler Problem 349, Langton's Ant, with C++, Python, Java, and a step-by-step mathematical explanation.
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....
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
- Problem page: https://projecteuler.net/problem=349
- Langton's ant: Wikipedia — Langton's ant
- Turmites and moving automata: Wikipedia — Turmite
- Hash tables and expected constant-time lookup: Wikipedia — Hash table
Problem 349 source code
C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <unordered_set>
#include <vector>
namespace {
using u64 = std::uint64_t;
using i64 = std::int64_t;
struct Options {
u64 target_steps = 1'000'000'000'000'000'000ULL;
u64 detect_steps = 200'000ULL;
u64 max_period = 500ULL;
u64 verify_window = 50'000ULL;
bool run_checkpoints = true;
};
struct Pattern {
bool found = false;
u64 start = 0ULL;
u64 period = 0ULL;
i64 delta = 0;
};
bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
if (arg.rfind(prefix, 0U) != 0U) {
return false;
}
const std::string tail = arg.substr(prefix.size());
if (tail.empty()) {
return false;
}
u64 parsed = 0ULL;
for (char c : tail) {
if (c < '0' || c > '9') {
return false;
}
parsed = parsed * 10ULL + static_cast<u64>(c - '0');
}
value = parsed;
return true;
}
bool parse_arguments(int argc, char** argv, Options& options) {
for (int i = 1; i < argc; ++i) {
const std::string arg(argv[i]);
if (arg == "--skip-checkpoints") {
options.run_checkpoints = false;
continue;
}
if (parse_u64_after_prefix(arg, "--target-steps=", options.target_steps) ||
parse_u64_after_prefix(arg, "--detect-steps=", options.detect_steps) ||
parse_u64_after_prefix(arg, "--max-period=", options.max_period) ||
parse_u64_after_prefix(arg, "--verify-window=", options.verify_window)) {
continue;
}
std::cerr << "Unknown argument: " << arg << '\n';
return false;
}
return options.detect_steps >= 1ULL && options.max_period >= 1ULL;
}
u64 encode_cell(const std::int32_t x, const std::int32_t y) {
return (static_cast<u64>(static_cast<std::uint32_t>(x)) << 32U) |
static_cast<u64>(static_cast<std::uint32_t>(y));
}
std::vector<i64> simulate_black_counts(const u64 steps) {
std::vector<i64> counts(static_cast<std::size_t>(steps + 1ULL), 0);
std::unordered_set<u64> black;
black.reserve(static_cast<std::size_t>(steps / 2ULL + 1024ULL));
std::int32_t x = 0;
std::int32_t y = 0;
int direction = 0; // 0=up, 1=right, 2=down, 3=left
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
i64 black_count = 0;
for (u64 step = 1ULL; step <= steps; ++step) {
const u64 key = encode_cell(x, y);
const auto it = black.find(key);
if (it != black.end()) {
black.erase(it);
--black_count;
direction = (direction + 3) & 3;
} else {
black.insert(key);
++black_count;
direction = (direction + 1) & 3;
}
x += static_cast<std::int32_t>(dx[direction]);
y += static_cast<std::int32_t>(dy[direction]);
counts[static_cast<std::size_t>(step)] = black_count;
}
return counts;
}
Pattern detect_linear_pattern(const std::vector<i64>& counts, const u64 max_period, const u64 verify_window) {
const u64 total_steps = static_cast<u64>(counts.size() - 1U);
if (total_steps < 2ULL) {
return {};
}
const u64 window_start = (total_steps > verify_window) ? (total_steps - verify_window) : 0ULL;
for (u64 period = 1ULL; period <= max_period && period <= total_steps; ++period) {
const i64 delta = counts[static_cast<std::size_t>(total_steps)] -
counts[static_cast<std::size_t>(total_steps - period)];
bool tail_ok = true;
for (u64 t = window_start; t + period <= total_steps; ++t) {
if (counts[static_cast<std::size_t>(t + period)] -
counts[static_cast<std::size_t>(t)] !=
delta) {
tail_ok = false;
break;
}
}
if (!tail_ok) {
continue;
}
const u64 upto = total_steps - period;
std::vector<unsigned char> good(static_cast<std::size_t>(upto + 1ULL), 0U);
for (u64 t = 0ULL; t <= upto; ++t) {
good[static_cast<std::size_t>(t)] =
(counts[static_cast<std::size_t>(t + period)] -
counts[static_cast<std::size_t>(t)] == delta)
? 1U
: 0U;
}
std::vector<unsigned char> suffix_ok(static_cast<std::size_t>(upto + 2ULL), 1U);
for (i64 t = static_cast<i64>(upto); t >= 0; --t) {
suffix_ok[static_cast<std::size_t>(t)] =
static_cast<unsigned char>(good[static_cast<std::size_t>(t)] &&
suffix_ok[static_cast<std::size_t>(t + 1)]);
}
for (u64 start = 0ULL; start <= upto; ++start) {
if (suffix_ok[static_cast<std::size_t>(start)] != 0U) {
return Pattern{true, start, period, delta};
}
}
}
return {};
}
i64 extrapolate_black_count(const std::vector<i64>& counts, const Pattern& pattern, const u64 target_step) {
if (target_step < counts.size()) {
return counts[static_cast<std::size_t>(target_step)];
}
const u64 offset = target_step - pattern.start;
const u64 cycles = offset / pattern.period;
const u64 rem = offset % pattern.period;
const i64 base = counts[static_cast<std::size_t>(pattern.start + rem)];
const __int128 extra = static_cast<__int128>(cycles) * static_cast<__int128>(pattern.delta);
return static_cast<i64>(static_cast<__int128>(base) + extra);
}
i64 solve(const Options& options) {
const std::vector<i64> counts = simulate_black_counts(options.detect_steps);
if (options.target_steps <= options.detect_steps) {
return counts[static_cast<std::size_t>(options.target_steps)];
}
const Pattern pattern = detect_linear_pattern(counts, options.max_period, options.verify_window);
if (!pattern.found) {
throw std::runtime_error("Could not detect linear periodic tail");
}
return extrapolate_black_count(counts, pattern, options.target_steps);
}
bool run_checkpoints() {
const std::vector<i64> small = simulate_black_counts(200ULL);
if (small[10] != 6) {
std::cerr << "Checkpoint failed for first 10 moves" << '\n';
return false;
}
const std::vector<i64> large = simulate_black_counts(200'000ULL);
const Pattern pattern = detect_linear_pattern(large, 500ULL, 50'000ULL);
if (!pattern.found || pattern.period != 104ULL || pattern.delta != 12LL) {
std::cerr << "Checkpoint failed for detected highway period/delta" << '\n';
return false;
}
const i64 predicted = extrapolate_black_count(large, pattern, 150'000ULL);
if (predicted != large[150'000]) {
std::cerr << "Checkpoint failed for extrapolation consistency at step 150000" << '\n';
return false;
}
return true;
}
} // namespace
int main(int argc, char** argv) {
Options options;
if (!parse_arguments(argc, argv, options)) {
return 1;
}
if (options.run_checkpoints && !run_checkpoints()) {
return 2;
}
try {
std::cout << solve(options) << '\n';
} catch (const std::exception& ex) {
std::cerr << ex.what() << '\n';
return 3;
}
return 0;
}
Python
def solve():
target_steps = 10**18
detect_steps = 200_000
# Simulate Langton's ant
black = set()
x, y = 0, 0
direction = 0 # 0=up, 1=right, 2=down, 3=left
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
counts = [0] * (detect_steps + 1)
black_count = 0
for step in range(1, detect_steps + 1):
key = (x, y)
if key in black:
black.remove(key)
black_count -= 1
direction = (direction + 3) & 3
else:
black.add(key)
black_count += 1
direction = (direction + 1) & 3
x += dx[direction]
y += dy[direction]
counts[step] = black_count
# Detect linear periodic pattern
max_period = 500
verify_window = 50_000
total = detect_steps
window_start = total - verify_window if total > verify_window else 0
pattern = None
for period in range(1, max_period + 1):
if period > total:
break
delta = counts[total] - counts[total - period]
tail_ok = True
for t in range(window_start, total - period + 1):
if counts[t + period] - counts[t] != delta:
tail_ok = False
break
if not tail_ok:
continue
# Find earliest start
upto = total - period
for start in range(upto + 1):
all_ok = True
for s in range(start, upto + 1):
if counts[s + period] - counts[s] != delta:
all_ok = False
break
if all_ok:
pattern = (start, period, delta)
break
if pattern:
break
if target_steps <= detect_steps:
return str(counts[target_steps])
start, period, delta = pattern
offset = target_steps - start
cycles = offset // period
rem = offset % period
base = counts[start + rem]
return str(base + cycles * delta)
if __name__ == '__main__':
print(solve())
Java
import java.util.*;
public class Euler349 {
static long encodeCell(int x, int y) {
return ((long) x << 32) | (y & 0xFFFFFFFFL);
}
static long[] simulateBlackCounts(int steps) {
long[] counts = new long[steps + 1];
Set<Long> black = new HashSet<>(steps / 2 + 1024);
int x = 0;
int y = 0;
int direction = 0;
int[] dx = { 0, 1, 0, -1 };
int[] dy = { 1, 0, -1, 0 };
long blackCount = 0;
for (int step = 1; step <= steps; step++) {
long key = encodeCell(x, y);
if (black.contains(key)) {
black.remove(key);
blackCount--;
direction = (direction + 3) & 3;
} else {
black.add(key);
blackCount++;
direction = (direction + 1) & 3;
}
x += dx[direction];
y += dy[direction];
counts[step] = blackCount;
}
return counts;
}
static class Pattern {
boolean found;
int start;
int period;
long delta;
Pattern(boolean found, int start, int period, long delta) {
this.found = found;
this.start = start;
this.period = period;
this.delta = delta;
}
}
static Pattern detectLinearPattern(long[] counts, int maxPeriod, int verifyWindow) {
int totalSteps = counts.length - 1;
if (totalSteps < 2)
return new Pattern(false, 0, 0, 0);
int windowStart = (totalSteps > verifyWindow) ? (totalSteps - verifyWindow) : 0;
for (int period = 1; period <= maxPeriod && period <= totalSteps; period++) {
long delta = counts[totalSteps] - counts[totalSteps - period];
boolean tailOk = true;
for (int t = windowStart; t + period <= totalSteps; t++) {
if (counts[t + period] - counts[t] != delta) {
tailOk = false;
break;
}
}
if (!tailOk)
continue;
int upto = totalSteps - period;
byte[] good = new byte[upto + 1];
for (int t = 0; t <= upto; t++) {
good[t] = (counts[t + period] - counts[t] == delta) ? (byte) 1 : (byte) 0;
}
byte[] suffixOk = new byte[upto + 2];
suffixOk[upto + 1] = 1;
for (int t = upto; t >= 0; t--) {
suffixOk[t] = (byte) ((good[t] == 1 && suffixOk[t + 1] == 1) ? 1 : 0);
}
for (int start = 0; start <= upto; start++) {
if (suffixOk[start] == 1) {
return new Pattern(true, start, period, delta);
}
}
}
return new Pattern(false, 0, 0, 0);
}
static long extrapolateBlackCount(long[] counts, Pattern pattern, long targetStep) {
if (targetStep < counts.length) {
return counts[(int) targetStep];
}
long offset = targetStep - pattern.start;
long cycles = offset / pattern.period;
long rem = offset % pattern.period;
long base = counts[pattern.start + (int) rem];
return base + cycles * pattern.delta;
}
public static String solve() {
long targetSteps = 1000000000000000000L;
int detectSteps = 200000;
int maxPeriod = 500;
int verifyWindow = 50000;
long[] counts = simulateBlackCounts(detectSteps);
Pattern pattern = detectLinearPattern(counts, maxPeriod, verifyWindow);
if (!pattern.found) {
throw new RuntimeException("Could not detect linear periodic tail");
}
long ans = extrapolateBlackCount(counts, pattern, targetSteps);
return String.valueOf(ans);
}
public static void main(String[] args) {
System.out.println(solve());
}
}