Detailed mathematical approach

Problem Summary

The robot starts at the origin, facing north, and makes \(70\) moves. Each move is a circular arc of angle \(72^\circ\): at every step the robot turns either clockwise or anticlockwise, so the heading changes by \(\pm72^\circ\) and the endpoint shifts by the chord of that arc. The task is to count how many turn sequences produce a closed walk. A brute-force search would inspect all \(2^{70}\) instruction strings, so the real problem is to encode the geometry in a form that can be counted exactly.

Mathematical Approach

The implementations avoid floating-point trigonometry entirely. The walk is rewritten as exact arithmetic in a five-dimensional integer state, and then a layered dynamic program counts how many sequences reach each state.

Encoding a \(72^\circ\) arc as an algebraic step

Let

$\lambda=e^{i\pi/5}.$

Then \(\lambda^{10}=1\) and \(\lambda^5=-1\). The endpoint displacement of one \(72^\circ\) arc has a fixed length \(2\sin(\pi/5)\), so for closure counting we may divide every displacement by that common nonzero factor. After this normalization, an anticlockwise arc contributes \(\lambda\) in the current frame, while a clockwise arc contributes \(\lambda^{-1}\). Rotating the heading by \(\pm72^\circ\) multiplies future directions by \(\lambda^{\pm2}\), because \(72^\circ=2\cdot36^\circ\).

A moving-frame recurrence

If \(z_t\) denotes the normalized displacement after \(t\) moves, expressed in the robot's current orientation frame, then one more move transforms it by

$z_{t+1}=\lambda^2 z_t+\lambda \qquad \text{for an anticlockwise turn},$

$z_{t+1}=\lambda^{-2} z_t+\lambda^{-1} \qquad \text{for a clockwise turn}.$

This already absorbs the changing heading, so the algorithm never needs a separate orientation variable. The state always answers the only question that matters for counting: where is the endpoint relative to the start?

From complex arithmetic to an exact integer state

Write every state in the basis \(1,\lambda,\lambda^2,\lambda^3,\lambda^4\):

$z_t=s_0+s_1\lambda+s_2\lambda^2+s_3\lambda^3+s_4\lambda^4,\qquad s_i\in\mathbb{Z}.$

Because \(\lambda^5=-1\), multiplying by \(\lambda^{\pm2}\) is just a signed shift of coefficients:

$\lambda^2 z \leftrightarrow (-s_3,-s_4,s_0,s_1,s_2),$

$\lambda^{-2} z \leftrightarrow (s_2,s_3,s_4,-s_0,-s_1).$

Also, \(\lambda\) corresponds to \((0,1,0,0,0)\), and \(\lambda^{-1}=-\lambda^4\) corresponds to \((0,0,0,0,-1)\). Therefore the exact state updates used by the implementations are

$T_{\mathrm{ccw}}(s)=(-s_3,-s_4+1,s_0,s_1,s_2),$

$T_{\mathrm{cw}}(s)=(s_2,s_3,s_4,-s_0,-s_1-1).$

No rounding appears anywhere: every move is an affine transformation of a 5-tuple of integers.

Why the closure test is linear

The number \(\lambda=e^{i\pi/5}\) satisfies the degree-4 relation

$1-\lambda+\lambda^2-\lambda^3+\lambda^4=0.$

So two coefficient vectors represent the same complex displacement exactly when they differ by a multiple of

$(-1,1,-1,1,-1).$

In particular, \(z_t=0\) if and only if

$s=k(-1,1,-1,1,-1)$

for some integer \(k\). This is equivalent to the four linear equations used at the end of the code:

$s_1+s_4=0,\qquad s_2+s_3=0,\qquad s_1+s_2=0,\qquad s_0+s_1=0.$

That is why the test for a closed walk is exact even though the implementation never stores Euclidean coordinates.

Worked Example: five turns in the same direction

Start from \(z_0=0\) and take five clockwise moves. Repeatedly applying \(z_{t+1}=\lambda^{-2}z_t+\lambda^{-1}\) gives

$z_5=\lambda^{-1}\left(1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}\right).$

Since \(\lambda^2\) is a primitive fifth root of unity,

$1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}=0,$

so \(z_5=0\). In coefficient form, the same endpoint is represented by

$(-1,1,-1,1,-1),$

which satisfies the four closure equations above. Geometrically this is the obvious full pentagonal loop; algebraically it shows why the terminal state need not be the literal zero 5-tuple.

Dynamic programming over reachable states

Let \(C_t(s)\) be the number of length-\(t\) turn sequences ending in state \(s\). Starting from

$C_0(0,0,0,0,0)=1,$

the two possible turns give the recurrence

$C_{t+1}(T_{\mathrm{cw}}(s)) \leftarrow C_{t+1}(T_{\mathrm{cw}}(s)) + C_t(s),$

$C_{t+1}(T_{\mathrm{ccw}}(s)) \leftarrow C_{t+1}(T_{\mathrm{ccw}}(s)) + C_t(s).$

After \(70\) rounds, summing \(C_{70}(s)\) over all states satisfying the closure equations gives the number of closed robot walks.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They keep a map from compressed 5-tuples to the number of ways to reach them after the current number of moves, starting from the zero state with count \(1\).

Each round creates a fresh next-layer map. For every stored state, the implementation computes the clockwise and anticlockwise successor states using the exact affine formulas above and adds the current count to both destinations. This is the whole computation: there is no geometric branching beyond these two transitions, and there is no floating-point arithmetic at all.

At the end, the implementation scans the last layer and sums the counts of the states that satisfy the four linear closure equations. The Java version packs the 5-tuple into one integer key because every coordinate stays between \(-70\) and \(70\); the C++ and Python versions keep the tuple itself as the map key. Those storage choices differ, but the mathematics is identical.

Complexity Analysis

If \(S_t\) is the number of reachable compressed states after \(t\) moves, then each layer processes exactly \(S_t\) states and emits two transitions per state. The mathematical workload is therefore

$O\!\left(\sum_{t=0}^{69} S_t\right),$

which is exponentially smaller than checking all \(2^{70}\) raw turn strings. The memory usage is

$O\!\left(\max_{0\le t\le 70} S_t\right),$

because only the current and next layers need to be stored. In practice the C++ version's ordered map adds a logarithmic update cost, while the Python and Java implementations use hash-based maps and are close to linear in the number of generated transitions.

Footnotes and References

1. Project Euler problem page: Project Euler 208 - Robot Walks
2. Roots of unity: Wikipedia - Root of unity
3. Cyclotomic polynomials: Wikipedia - Cyclotomic polynomial
4. Dynamic programming: Wikipedia - Dynamic programming
5. Regular pentagon geometry: Wikipedia - Regular pentagon