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.
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.
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\).
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?
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.
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.
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.
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.
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.
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.
Der Roboter startet im Ursprung, blickt nach Norden und macht \(70\) Bewegungen. Jede Bewegung ist ein Kreisbogen mit Winkel \(72^\circ\): In jedem Schritt wird entweder im Uhrzeigersinn oder gegen den Uhrzeigersinn gedreht, also ändert sich die Orientierung um \(\pm72^\circ\), und der Endpunkt verschiebt sich um die zugehörige Sehne. Gesucht ist die Anzahl der Drehfolgen, die einen geschlossenen Weg erzeugen. Ein vollständiger Durchlauf über alle \(2^{70}\) Befehlsfolgen ist unmöglich; man braucht daher eine exakte mathematische Zustandsbeschreibung.
Die Implementierungen ersetzen Gleitkomma-Geometrie vollständig durch exakte Algebra in einem ganzzahligen 5-dimensionalen Zustand. Anschließend zählt eine geschichtete dynamische Programmierung die erreichbaren Zustände.
Setze
$$\lambda=e^{i\pi/5}.$$
Dann gilt \(\lambda^{10}=1\) und \(\lambda^5=-1\). Die Endpunktverschiebung eines einzelnen \(72^\circ\)-Bogens hat immer dieselbe Länge \(2\sin(\pi/5)\). Für die Frage, ob der Weg schließt, ist dieser gemeinsame Faktor irrelevant, also kann man ihn herausdividieren. Danach entspricht ein Linksbogen dem Beitrag \(\lambda\) im aktuellen Bezugsrahmen, ein Rechtsbogen dem Beitrag \(\lambda^{-1}\). Die Drehung des Blickwinkels um \(\pm72^\circ\) multipliziert alle zukünftigen Richtungen mit \(\lambda^{\pm2}\).
Sei \(z_t\) die normierte Verschiebung nach \(t\) Schritten, gemessen im gerade aktuellen Orientierungsrahmen des Roboters. Dann gilt für den nächsten Schritt
$$z_{t+1}=\lambda^2 z_t+\lambda \qquad \text{bei einer Linksdrehung},$$
$$z_{t+1}=\lambda^{-2} z_t+\lambda^{-1} \qquad \text{bei einer Rechtsdrehung}.$$
Die Orientierung steckt also schon in der Transformation selbst; der Algorithmus muss sie nicht als zusätzliche Variable speichern.
Jeder Zustand wird in der Basis \(1,\lambda,\lambda^2,\lambda^3,\lambda^4\) geschrieben:
$$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}.$$
Wegen \(\lambda^5=-1\) bedeutet Multiplikation mit \(\lambda^{\pm2}\) nur ein Vorzeichen-behaftetes Verschieben der Koeffizienten:
$$\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).$$
Außerdem entspricht \(\lambda\) dem Tupel \((0,1,0,0,0)\), und \(\lambda^{-1}=-\lambda^4\) entspricht \((0,0,0,0,-1)\). Damit entstehen exakt die beiden Übergänge aus dem Code:
$$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).$$
Jeder Schritt bleibt also vollständig ganzzahlig.
Für \(\lambda=e^{i\pi/5}\) gilt die Relation
$$1-\lambda+\lambda^2-\lambda^3+\lambda^4=0.$$
Daher beschreiben zwei Koeffizientenvektoren genau dann dieselbe Verschiebung, wenn sie sich um ein Vielfaches von
$$(-1,1,-1,1,-1)$$
unterscheiden. Insbesondere ist \(z_t=0\) genau dann, wenn
$$s=k(-1,1,-1,1,-1)$$
für ein ganzzahliges \(k\) gilt. Das ist äquivalent zu den vier linearen Prüfungen aus den Implementierungen:
$$s_1+s_4=0,\qquad s_2+s_3=0,\qquad s_1+s_2=0,\qquad s_0+s_1=0.$$
Die Geometrie des Schließens wird also auf eine einfache lineare Bedingung in \(\mathbb{Z}^5\) reduziert.
Starte mit \(z_0=0\) und führe fünf Rechtsdrehungen aus. Durch wiederholtes Anwenden von \(z_{t+1}=\lambda^{-2}z_t+\lambda^{-1}\) erhält man
$$z_5=\lambda^{-1}\left(1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}\right).$$
Weil \(\lambda^2\) eine primitive fünfte Einheitswurzel ist, gilt
$$1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}=0,$$
also \(z_5=0\). In Koeffizientenform landet man bei
$$(-1,1,-1,1,-1),$$
und genau dieses Tupel erfüllt die vier Schließungsgleichungen. Geometrisch ist das der offensichtliche volle Fünfeck-Kreis.
Sei \(C_t(s)\) die Anzahl der Folgen der Länge \(t\), die im Zustand \(s\) enden. Mit dem Startwert
$$C_0(0,0,0,0,0)=1$$
liefert jeder Zustand genau zwei Folgezustände:
$$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).$$
Nach \(70\) Runden wird über alle Endzustände summiert, die die lineare Schließungsbedingung erfüllen.
Die C++-, Python- und Java-Implementierungen arbeiten alle schichtweise. Sie halten jeweils eine Map von komprimierten 5-Tupeln auf die Anzahl der Wege, die nach der aktuellen Schrittzahl genau dort enden, und beginnen mit dem Nullzustand mit Zählwert \(1\).
In jeder Runde wird eine neue Map für die nächste Schicht aufgebaut. Für jedes gespeicherte Tupel werden die beiden exakten affinen Übergänge für Rechts- und Linksdrehung berechnet und die vorhandene Anzahl auf beide Zielzustände addiert. Mehr Geometrie gibt es algorithmisch nicht: Alle Informationen stecken in diesen beiden Formeln.
Am Ende durchläuft die Implementierung die letzte Schicht und addiert die Zählwerte der Zustände, die die vier linearen Schließungsgleichungen erfüllen. Die Java-Version kodiert das 5-Tupel in einen einzelnen Ganzzahlschlüssel, weil jede Koordinate zwischen \(-70\) und \(70\) bleibt; C++ und Python verwenden das Tupel selbst als Schlüssel. Die Datenstruktur variiert, das Verfahren nicht.
Ist \(S_t\) die Anzahl der nach \(t\) Schritten erreichbaren komprimierten Zustände, dann verarbeitet die \(t\)-te Schicht genau \(S_t\) Zustände und erzeugt je Zustand zwei Übergänge. Der mathematische Aufwand ist daher
$$O\!\left(\sum_{t=0}^{69} S_t\right).$$
Der Speicherbedarf beträgt
$$O\!\left(\max_{0\le t\le 70} S_t\right),$$
da immer nur aktuelle und nächste Schicht gehalten werden müssen. Gegenüber einem rohen Durchprobieren aller \(2^{70}\) Folgen ist das die entscheidende Reduktion. In C++ kommt durch die geordnete Map noch ein logarithmischer Updatefaktor hinzu; Python und Java liegen mit Hash-Maps praktisch nahe an der linearen Zahl der erzeugten Übergänge.
Robot orijinde başlar, kuzeye bakar ve \(70\) hareket yapar. Her hareket \(72^\circ\)'lik bir dairesel yaydır: robot her adımda ya sağa ya sola döner, dolayısıyla yönü \(\pm72^\circ\) değişir ve uç nokta o yay parçasının kirişi kadar yer değiştirir. İstenen şey, kapalı bir yürüyüş oluşturan dönüş dizilerinin sayısıdır. Tüm \(2^{70}\) olasılığı kaba kuvvetle saymak imkansız olduğundan, çözüm geometriyi tam sayılarla çalışan kesin bir duruma indirger.
Uygulamalar kayan noktalı trigonometriden tamamen kaçınır. Yürüyüş, beş boyutlu bir tamsayı durumunda tam olarak ifade edilir; ardından katmanlı dinamik programlama erişilebilen durumları sayar.
$$\lambda=e^{i\pi/5}$$
olsun. Böylece \(\lambda^{10}=1\) ve \(\lambda^5=-1\) elde edilir. Tek bir \(72^\circ\)'lik yayın uç nokta yer değiştirmesinin uzunluğu sabit olarak \(2\sin(\pi/5)\)'tir. Kapanma sayımı için bu ortak ve sıfır olmayan çarpanı bölebiliriz. Bu normalizasyondan sonra saat yönünün tersine bir yay güncel referans çerçevesinde \(\lambda\), saat yönünde bir yay ise \(\lambda^{-1}\) katkısı yapar. Yönün \(\pm72^\circ\) değişmesi de gelecekteki doğrultuları \(\lambda^{\pm2}\) ile çarpmaya karşılık gelir.
\(z_t\), \(t\) adım sonundaki normalize edilmiş yer değiştirme olsun; bu değer robotun o andaki yönüne göre yazılsın. O zaman bir sonraki adım için
$$z_{t+1}=\lambda^2 z_t+\lambda \qquad \text{saat yönünün tersine dönüşte},$$
$$z_{t+1}=\lambda^{-2} z_t+\lambda^{-1} \qquad \text{saat yönünde dönüşte}$$
olur. Yani yön bilgisinin değişimi zaten dönüşümün içine gömülüdür; ayrıca bir baş-yön değişkeni tutmaya gerek yoktur.
Her durumu \(1,\lambda,\lambda^2,\lambda^3,\lambda^4\) tabanında yazalım:
$$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}.$$
\(\lambda^5=-1\) olduğu için \(\lambda^{\pm2}\) ile çarpma yalnızca işaretli bir kaydırmadır:
$$\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).$$
Ayrıca \(\lambda\) sayısı \((0,1,0,0,0)\), \(\lambda^{-1}=-\lambda^4\) ise \((0,0,0,0,-1)\) ile temsil edilir. Böylece kodda görülen iki geçiş doğrudan elde edilir:
$$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).$$
Bütün hesap tamamen kesin tamsayı aritmetiğiyle yürür.
\(\lambda=e^{i\pi/5}\) sayısı
$$1-\lambda+\lambda^2-\lambda^3+\lambda^4=0$$
ilişkisini sağlar. Bu yüzden iki katsayı vektörü ancak ve ancak
$$(-1,1,-1,1,-1)$$
vektörünün bir katı kadar farklıysa aynı yer değiştirmeyi temsil eder. Özellikle \(z_t=0\) olması için ve ancak bunun için
$$s=k(-1,1,-1,1,-1)$$
şeklinde bir \(k\in\mathbb{Z}\) bulunmalıdır. Bu da uygulamaların kullandığı dört lineer eşitliğe denktir:
$$s_1+s_4=0,\qquad s_2+s_3=0,\qquad s_1+s_2=0,\qquad s_0+s_1=0.$$
Yani kapalı yürüyüş testi, Öklid koordinatları yerine \(\mathbb{Z}^5\) içindeki tam bir lineer altuzay testine dönüşür.
\(z_0=0\) noktasından başlayıp art arda beş saat yönlü yay alalım. \(z_{t+1}=\lambda^{-2}z_t+\lambda^{-1}\) yinelemesini açınca
$$z_5=\lambda^{-1}\left(1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}\right)$$
elde edilir. \(\lambda^2\) ilkel bir beşinci birim kök olduğu için
$$1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}=0,$$
dolayısıyla \(z_5=0\) olur. Katsayı vektörü olarak son durum
$$(-1,1,-1,1,-1)$$
şeklindedir ve bu vektör yukarıdaki dört kapanış eşitliğini sağlar. Geometrik olarak bu, robotun tam bir beşgen çevrimi çizmesidir.
\(C_t(s)\), uzunluğu \(t\) olan ve \(s\) durumunda biten komut dizilerinin sayısı olsun. Başlangıç koşulu
$$C_0(0,0,0,0,0)=1$$
olduğunda iki olası dönüş şu yinelemeyi verir:
$$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).$$
\(70\) turun sonunda kapanış koşulunu sağlayan bütün durumların sayıları toplanır ve cevap elde edilir.
C++, Python ve Java uygulamaları aynı omurgayı kullanır. O ana kadarki adım sayısından sonra hangi sıkıştırılmış 5-tuple durumuna kaç farklı yoldan gelinebildiğini tutan bir harita yapısı kullanılır ve başlangıçta yalnızca sıfır durumu \(1\) kez mümkündür.
Her turda yeni bir sonraki-katman haritası oluşturulur. Saklanan her durum için yukarıdaki saat yönlü ve saat yönünün tersine geçişler uygulanır, sonra mevcut yol sayısı her iki hedef duruma eklenir. Ayrı bir geometrik işleme veya kayan nokta hesabına ihtiyaç yoktur; tüm yapı bu iki affine dönüşümden gelir.
Son katmanda uygulama bütün durumları tarar ve dört lineer kapanış eşitliğini sağlayanların sayısını toplar. Java sürümü, her koordinat \(-70\) ile \(70\) arasında kaldığı için 5'liyi tek bir tamsayı anahtara paketler; C++ ve Python sürümleri ise tuple/array anahtarı kullanır. Veri temsili değişse de algoritma aynıdır.
\(S_t\), \(t\) adım sonrasında erişilebilen sıkıştırılmış durum sayısı olsun. Her katman tam olarak \(S_t\) durumu işler ve her durumdan iki geçiş çıkar. Dolayısıyla matematiksel iş yükü
$$O\!\left(\sum_{t=0}^{69} S_t\right)$$
olur. Bellek kullanımı ise yalnızca mevcut ve sonraki katmanlar saklandığı için
$$O\!\left(\max_{0\le t\le 70} S_t\right)$$
düzeyindedir. Bu, \(2^{70}\) ham dönüş dizisinin tamamını denemekten kat kat küçüktür. C++ sürümünde sıralı map yüzünden güncelleme başına logaritmik bir çarpan vardır; Python ve Java sürümleri hash tabanlı yapılarda pratik olarak üretilen geçiş sayısına yakın maliyetle çalışır.
El robot comienza en el origen, mirando hacia el norte, y realiza \(70\) movimientos. Cada movimiento es un arco circular de \(72^\circ\): en cada paso gira en sentido horario o antihorario, de modo que la orientación cambia en \(\pm72^\circ\) y el extremo se desplaza por la cuerda correspondiente a ese arco. Hay que contar cuántas secuencias de giros producen un recorrido cerrado. Recorrer directamente las \(2^{70}\) secuencias posibles es inviable, así que la clave es convertir la geometría en un estado exacto que se pueda contar.
Las implementaciones eliminan por completo la trigonometría en coma flotante. El paseo se reescribe como aritmética exacta en un estado entero de dimensión cinco, y luego una programación dinámica por capas cuenta las secuencias que llegan a cada estado.
Definimos
$$\lambda=e^{i\pi/5}.$$
Entonces \(\lambda^{10}=1\) y \(\lambda^5=-1\). El desplazamiento del extremo tras un solo arco de \(72^\circ\) tiene longitud fija \(2\sin(\pi/5)\). Como solo importa si el camino se cierra o no, podemos dividir por ese factor común no nulo. Tras esa normalización, un arco antihorario aporta \(\lambda\) en el marco actual, mientras que un arco horario aporta \(\lambda^{-1}\). Cambiar la orientación en \(\pm72^\circ\) equivale a multiplicar las direcciones futuras por \(\lambda^{\pm2}\).
Sea \(z_t\) el desplazamiento normalizado después de \(t\) movimientos, expresado en el marco de la orientación actual del robot. Entonces un paso adicional transforma el estado como
$$z_{t+1}=\lambda^2 z_t+\lambda \qquad \text{para un giro antihorario},$$
$$z_{t+1}=\lambda^{-2} z_t+\lambda^{-1} \qquad \text{para un giro horario}.$$
La orientación variable ya está absorbida en esta fórmula, así que el algoritmo no necesita guardar por separado hacia dónde mira el robot.
Escribimos cada estado en la base \(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}.$$
Como \(\lambda^5=-1\), multiplicar por \(\lambda^{\pm2}\) solo produce desplazamientos exactos de coeficientes con algunos cambios de signo:
$$\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).$$
Además, \(\lambda\) corresponde a \((0,1,0,0,0)\), y \(\lambda^{-1}=-\lambda^4\) corresponde a \((0,0,0,0,-1)\). Por eso las dos transiciones exactas que usa la implementación son
$$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).$$
Todo el problema queda así convertido en transformaciones afines de 5-tuplas enteras.
El número \(\lambda=e^{i\pi/5}\) satisface
$$1-\lambda+\lambda^2-\lambda^3+\lambda^4=0.$$
Por tanto, dos vectores de coeficientes representan exactamente el mismo desplazamiento cuando difieren en un múltiplo de
$$(-1,1,-1,1,-1).$$
En particular, \(z_t=0\) si y solo si
$$s=k(-1,1,-1,1,-1)$$
para algún entero \(k\). Eso equivale a las cuatro ecuaciones lineales que se comprueban al final:
$$s_1+s_4=0,\qquad s_2+s_3=0,\qquad s_1+s_2=0,\qquad s_0+s_1=0.$$
La prueba de cierre ya no se hace en coordenadas cartesianas, sino dentro de un subespacio lineal exacto de \(\mathbb{Z}^5\).
Partimos de \(z_0=0\) y hacemos cinco giros horarios. Al iterar \(z_{t+1}=\lambda^{-2}z_t+\lambda^{-1}\) se obtiene
$$z_5=\lambda^{-1}\left(1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}\right).$$
Como \(\lambda^2\) es una raíz quinta primitiva de la unidad,
$$1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}=0,$$
y por tanto \(z_5=0\). En forma de coeficientes, el mismo estado final aparece como
$$(-1,1,-1,1,-1),$$
que satisface las cuatro ecuaciones de cierre. Geométricamente es la vuelta pentagonal completa.
Sea \(C_t(s)\) el número de secuencias de longitud \(t\) que terminan en el estado \(s\). Con la condición inicial
$$C_0(0,0,0,0,0)=1,$$
las dos opciones de giro producen la recurrencia
$$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).$$
Tras \(70\) rondas, la respuesta es la suma de \(C_{70}(s)\) sobre todos los estados que cumplen las ecuaciones de cierre.
Las implementaciones en C++, Python y Java siguen la misma idea. Mantienen un diccionario o mapa desde la 5-tupla comprimida hasta el número de maneras de alcanzarla después del número actual de movimientos, empezando con el estado cero y conteo \(1\).
En cada ronda se construye una estructura nueva para la capa siguiente. Para cada estado almacenado se calculan exactamente los dos sucesores, horario y antihorario, mediante las fórmulas afines anteriores, y el conteo del estado actual se suma en ambos destinos. No hay aproximación geométrica ni cálculo en coma flotante en ningún punto.
Al final, la implementación recorre la última capa y suma los conteos de los estados que satisfacen las cuatro ecuaciones lineales de cierre. La versión Java empaqueta la 5-tupla en una sola clave entera porque cada coordenada queda entre \(-70\) y \(70\); C++ y Python usan la tupla explícita como clave. La representación cambia, pero el algoritmo es el mismo.
Si \(S_t\) es el número de estados comprimidos alcanzables tras \(t\) movimientos, entonces la capa \(t\) procesa exactamente \(S_t\) estados y genera dos transiciones por cada uno. El trabajo matemático total es
$$O\!\left(\sum_{t=0}^{69} S_t\right).$$
La memoria necesaria es
$$O\!\left(\max_{0\le t\le 70} S_t\right),$$
porque solo se guardan la capa actual y la siguiente. Esto es muchísimo menor que enumerar directamente las \(2^{70}\) secuencias de giros. En la versión de C++ aparece además un factor logarítmico por el mapa ordenado; en Python y Java, con tablas hash, el coste práctico queda cerca del número total de transiciones generadas.
机器人从原点出发，初始朝北，一共走 \(70\) 步。每一步都是一个转角为 \(72^\circ\) 的圆弧：要么顺时针转，要么逆时针转，所以朝向每次改变 \(\pm72^\circ\)，终点相对起点的位移则是该圆弧所对应的弦。题目要求统计有多少条左右转指令序列会形成闭合路径。直接枚举全部 \(2^{70}\) 条序列完全不可行，因此必须把几何过程压缩成一个可以精确计数的代数状态。
实现并不做浮点三角计算，而是把整条路径写成一个五维整数状态上的精确递推，再用分层动态规划统计可达状态数。
设
$$\lambda=e^{i\pi/5}.$$
于是 \(\lambda^{10}=1\)，并且 \(\lambda^5=-1\)。单个 \(72^\circ\) 圆弧的端点位移长度恒为 \(2\sin(\pi/5)\)。我们只关心路径是否闭合，所以这个公共且非零的比例因子可以整体除掉。归一化以后，在当前参考系中，逆时针一步的位移可记为 \(\lambda\)，顺时针一步的位移可记为 \(\lambda^{-1}\)。而朝向每改变 \(\pm72^\circ\)，后续所有方向就相当于再乘上 \(\lambda^{\pm2}\)，因为 \(72^\circ=2\cdot36^\circ\)。
记 \(z_t\) 为走完 \(t\) 步后的归一化位移，并把它写在机器人当前朝向对应的参考系中。那么再走一步时，状态更新为
$$z_{t+1}=\lambda^2 z_t+\lambda \qquad \text{对应逆时针转},$$
$$z_{t+1}=\lambda^{-2} z_t+\lambda^{-1} \qquad \text{对应顺时针转}.$$
这两个式子已经把“当前朝向如何变化”吸收进去了，所以代码里不需要再单独保存一个朝向变量。只要知道这个随动参考系中的位移，就足以继续递推。
把每个状态都写成基底 \(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}.$$
由于 \(\lambda^5=-1\)，乘以 \(\lambda^{\pm2}\) 只会把系数做符号变化后的循环平移：
$$\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).$$
另外，\(\lambda\) 对应的系数向量是 \((0,1,0,0,0)\)，而 \(\lambda^{-1}=-\lambda^4\) 对应 \((0,0,0,0,-1)\)。因此实现中真正使用的两个一步转移正是
$$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).$$
这样一来，整个问题完全变成了整数 5 元组上的仿射变换，不再涉及任何数值误差。
\(\lambda=e^{i\pi/5}\) 满足
$$1-\lambda+\lambda^2-\lambda^3+\lambda^4=0.$$
这说明两个系数向量表示同一个复位移，当且仅当它们相差某个
$$(-1,1,-1,1,-1)$$
的整数倍。特别地，\(z_t=0\) 当且仅当
$$s=k(-1,1,-1,1,-1)$$
对某个整数 \(k\) 成立。把它改写成坐标条件，就是代码结尾所检查的四个线性方程：
$$s_1+s_4=0,\qquad s_2+s_3=0,\qquad s_1+s_2=0,\qquad s_0+s_1=0.$$
因此“路径是否闭合”被严格地转化成了 \(\mathbb{Z}^5\) 中的线性判定问题。
从 \(z_0=0\) 开始，连续执行五次顺时针转弯。把递推式 \(z_{t+1}=\lambda^{-2}z_t+\lambda^{-1}\) 展开后得到
$$z_5=\lambda^{-1}\left(1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}\right).$$
因为 \(\lambda^2\) 是本原五次单位根，所以
$$1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}=0,$$
从而 \(z_5=0\)。如果看整数系数形式，终点对应的 5 元组是
$$(-1,1,-1,1,-1),$$
它恰好满足前面的四个闭合方程。几何上，这正对应机器人沿着完整的五边形方向绕一圈回到起点。
设 \(C_t(s)\) 表示长度为 \(t\) 的转向序列中，最终落在状态 \(s\) 的方案数。初值为
$$C_0(0,0,0,0,0)=1.$$
由于每个状态下一步只有顺时针和逆时针两种选择，所以递推为
$$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).$$
做完 \(70\) 轮后，把所有满足闭合方程的终态计数相加，就是题目所求。
C++、Python 和 Java 三个实现的核心结构完全一致。它们都维护一个映射，记录“当前走了若干步以后，每个压缩后的 5 元组状态有多少条路径可以到达”，并以零状态计数为 \(1\) 作为起点。
每一轮都会新建下一层的映射。对于当前层中的每个状态，程序按照上面的两个精确仿射公式计算顺时针与逆时针的后继状态，再把当前状态的方案数分别累加到这两个后继中。整个过程中没有浮点误差，也不需要显式模拟平面中的坐标轨迹。
最后一轮结束后，程序遍历最终映射，把满足四个线性闭合条件的状态计数全部加起来。Java 实现利用“每个坐标都不会超出 \(-70\) 到 \(70\)”这一事实，把五个坐标打包成一个整数键；C++ 和 Python 则直接把 5 元组本身当作映射键。存储方式不同，但算法完全相同。
设 \(S_t\) 为走完 \(t\) 步后可达的压缩状态数。那么第 \(t\) 层恰好处理 \(S_t\) 个状态，并从每个状态生成两条转移，所以总的数学工作量是
$$O\!\left(\sum_{t=0}^{69} S_t\right).$$
空间复杂度为
$$O\!\left(\max_{0\le t\le 70} S_t\right),$$
因为任意时刻只需要保留当前层和下一层。与直接枚举 \(2^{70}\) 条原始转向序列相比，这个压缩状态空间已经小了非常多。具体实现上，C++ 的有序映射会带来额外的对数更新代价；Python 和 Java 的哈希映射则更接近按转移条数线性增长的实际运行时间。
Робот стартует в начале координат, смотрит на север и делает \(70\) ходов. Каждый ход представляет собой дугу окружности с углом \(72^\circ\): на каждом шаге робот поворачивает либо по часовой стрелке, либо против, поэтому ориентация меняется на \(\pm72^\circ\), а конечная точка смещается на хорду этой дуги. Нужно посчитать, сколько последовательностей поворотов образуют замкнутый путь. Перебирать все \(2^{70}\) вариантов бессмысленно, поэтому геометрию надо переписать в точной алгебраической форме.
Во всех реализациях вместо вещественной тригонометрии используется точная арифметика в пятикомпонентном целочисленном состоянии. Затем по слоям считается, сколько инструкций приводит в каждое достижимое состояние.
Положим
$$\lambda=e^{i\pi/5}.$$
Тогда \(\lambda^{10}=1\), а \(\lambda^5=-1\). Смещение конца одного дугового шага имеет фиксированную длину \(2\sin(\pi/5)\). Для проверки замкнутости этот общий ненулевой множитель не важен, поэтому его можно отбросить. После нормировки шаг против часовой стрелки дает вклад \(\lambda\) в текущем локальном базисе, а шаг по часовой стрелке дает вклад \(\lambda^{-1}\). Изменение ориентации на \(\pm72^\circ\) означает, что все будущие направления надо домножать на \(\lambda^{\pm2}\).
Пусть \(z_t\) обозначает нормированное смещение после \(t\) шагов, записанное в системе координат, связанной с текущим направлением робота. Тогда следующий шаг преобразует состояние по формулам
$$z_{t+1}=\lambda^2 z_t+\lambda \qquad \text{для поворота против часовой стрелки},$$
$$z_{t+1}=\lambda^{-2} z_t+\lambda^{-1} \qquad \text{для поворота по часовой стрелке}.$$
Тем самым изменение ориентации уже встроено в сам переход, и отдельная переменная для направления не нужна.
Каждое состояние записывается в базисе \(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}.$$
Так как \(\lambda^5=-1\), умножение на \(\lambda^{\pm2}\) превращается просто в перестановку коэффициентов со сменой знаков:
$$\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).$$
Кроме того, \(\lambda\) соответствует вектору \((0,1,0,0,0)\), а \(\lambda^{-1}=-\lambda^4\) соответствует \((0,0,0,0,-1)\). Поэтому используемые в программах точные переходы имеют вид
$$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).$$
Никаких погрешностей округления здесь нет: каждый ход есть аффинное преобразование целочисленной пятерки.
Число \(\lambda=e^{i\pi/5}\) удовлетворяет соотношению
$$1-\lambda+\lambda^2-\lambda^3+\lambda^4=0.$$
Значит, два вектора коэффициентов задают одно и то же смещение тогда и только тогда, когда они отличаются на целое кратное
$$(-1,1,-1,1,-1).$$
В частности, \(z_t=0\) эквивалентно условию
$$s=k(-1,1,-1,1,-1)$$
для некоторого целого \(k\). Это равносильно четырем линейным равенствам, которые и проверяются в конце:
$$s_1+s_4=0,\qquad s_2+s_3=0,\qquad s_1+s_2=0,\qquad s_0+s_1=0.$$
Именно так условие геометрической замкнутости превращается в точный линейный тест в пространстве \(\mathbb{Z}^5\).
Пусть \(z_0=0\), и робот делает пять поворотов по часовой стрелке подряд. Тогда из рекурсии \(z_{t+1}=\lambda^{-2}z_t+\lambda^{-1}\) получается
$$z_5=\lambda^{-1}\left(1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}\right).$$
Поскольку \(\lambda^2\) является примитивным корнем пятой степени из единицы, имеем
$$1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}=0,$$
значит, \(z_5=0\). В координатной форме этот же конечный пункт записывается как
$$(-1,1,-1,1,-1),$$
и он действительно удовлетворяет всем четырем линейным условиям замыкания. Геометрически это полный обход пятиугольного контура.
Обозначим через \(C_t(s)\) количество последовательностей длины \(t\), оканчивающихся в состоянии \(s\). Начальное условие
$$C_0(0,0,0,0,0)=1.$$
Из каждого состояния есть ровно два перехода, поэтому
$$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).$$
После \(70\) шагов остается просуммировать \(C_{70}(s)\) по всем состояниям, удовлетворяющим условиям замыкания.
Реализации на C++, Python и Java устроены одинаково. Они хранят отображение из сжатой 5-компонентной записи состояния в число способов прийти в него после текущего количества шагов, начиная с нулевого состояния с весом \(1\).
На каждом шаге строится новая таблица следующего слоя. Для каждого сохраненного состояния программа вычисляет двух потомков, соответствующих повороту по часовой стрелке и против, с помощью точных аффинных формул выше, а затем прибавляет счетчик текущего состояния к обоим потомкам. Никакой отдельной геометрической симуляции или вещественной арифметики не требуется.
В конце просматривается последний слой, и суммируются значения тех состояний, которые проходят четыре линейные проверки на замыкание. В Java пятерка координат упаковывается в один целочисленный ключ, так как каждая координата остается в пределах \(-70\) и \(70\); в C++ и Python ключом служит сама пятерка. Это разница в представлении данных, а не в алгоритме.
Если \(S_t\) обозначает число достижимых сжатых состояний после \(t\) шагов, то слой \(t\) обрабатывает ровно \(S_t\) состояний и порождает по два перехода из каждого. Следовательно, математическая трудоемкость равна
$$O\!\left(\sum_{t=0}^{69} S_t\right).$$
Память составляет
$$O\!\left(\max_{0\le t\le 70} S_t\right),$$
потому что одновременно нужно хранить только текущий и следующий слой. Это на порядки меньше, чем прямой перебор всех \(2^{70}\) исходных последовательностей. В версии на C++ появляется дополнительный логарифмический множитель из-за упорядоченного контейнера; в Python и Java с хеш-таблицами практическая стоимость близка к линейной по числу сгенерированных переходов.
يبدأ الروبوت من الأصل وهو متجه إلى الشمال، ثم ينفذ \(70\) حركة. كل حركة عبارة عن قوس دائري زاويته \(72^\circ\): في كل خطوة ينعطف إما مع عقارب الساعة أو عكسها، ولذلك يتغير اتجاهه بمقدار \(\pm72^\circ\) وتتحرك نقطة النهاية بمقدار وتر ذلك القوس. المطلوب هو عدّ عدد سلاسل الانعطاف التي تعطي مسارًا مغلقًا. استعراض جميع السلاسل وعددها \(2^{70}\) غير عملي تمامًا، لذا يجب تحويل الهندسة إلى حالة جبرية دقيقة يمكن عدّها.
التنفيذات لا تستخدم حسابات مثلثية عائمة، بل تعيد صياغة المسار كله على هيئة حالة صحيحة من خمسة مركبات، ثم تستعمل برمجة ديناميكية طبقية لعدّ الحالات الممكنة.
لنضع
$$\lambda=e^{i\pi/5}.$$
عندئذٍ \(\lambda^{10}=1\) و \(\lambda^5=-1\). إزاحة نقطة النهاية الناتجة عن قوس واحد بطول زاوي \(72^\circ\) لها طول ثابت هو \(2\sin(\pi/5)\). وبما أن ما يهمنا هو الانغلاق فقط، فيمكن قسمة جميع الإزاحات على هذا العامل الثابت غير الصفري. بعد هذا التطبيع، تساهم الخطوة عكس عقارب الساعة بالمتجه \(\lambda\) في الإطار الحالي، بينما تساهم الخطوة مع عقارب الساعة بالمتجه \(\lambda^{-1}\). أما تغير الاتجاه بمقدار \(\pm72^\circ\) فيكافئ ضرب الاتجاهات اللاحقة كلها في \(\lambda^{\pm2}\).
ليكن \(z_t\) هو الإزاحة المطَبَّعة بعد \(t\) خطوات، لكن مكتوبة في الإطار الموافق لاتجاه الروبوت الحالي. عندئذٍ تعطى الخطوة التالية بالعلاقتين
$$z_{t+1}=\lambda^2 z_t+\lambda$$
للخطوة عكس عقارب الساعة، و
$$z_{t+1}=\lambda^{-2} z_t+\lambda^{-1}$$
للخطوة مع عقارب الساعة.
بهذا تكون معلومات الاتجاه مدمجة أصلًا داخل التحويل نفسه، ولذلك لا حاجة إلى تخزين اتجاه مستقل في الخوارزمية.
نكتب كل حالة على الأساس \(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}.$$
وبما أن \(\lambda^5=-1\)، فإن الضرب في \(\lambda^{\pm2}\) يتحول إلى إزاحة دورية دقيقة للمعاملات مع بعض تغييرات الإشارة:
$$\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).$$
كذلك فإن \(\lambda\) يقابل المتجه \((0,1,0,0,0)\)، و \(\lambda^{-1}=-\lambda^4\) يقابل \((0,0,0,0,-1)\). ومن هنا نحصل مباشرة على تحولي الخطوة المستخدمين في التنفيذ:
$$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).$$
إذن الحساب كله يتم داخل تحويلات affine صحيحة على خماسيات عددية، من دون أي تقريب عددي.
العدد \(\lambda=e^{i\pi/5}\) يحقق العلاقة
$$1-\lambda+\lambda^2-\lambda^3+\lambda^4=0.$$
ولذلك فإن متجهي معاملات يمثلان الإزاحة نفسها إذا وفقط إذا اختلفا بمضاعف صحيح للمتجه
$$(-1,1,-1,1,-1).$$
وبوجه خاص يكون \(z_t=0\) إذا وفقط إذا أمكن كتابة الحالة على الصورة
$$s=k(-1,1,-1,1,-1)$$
لبعض \(k\in\mathbb{Z}\). وهذا مكافئ تمامًا للمعادلات الخطية الأربع التي تُفحَص في نهاية الحل:
$$s_1+s_4=0,\qquad s_2+s_3=0,\qquad s_1+s_2=0,\qquad s_0+s_1=0.$$
هكذا يصبح شرط إغلاق المسار اختبارًا خطيًا دقيقًا داخل \(\mathbb{Z}^5\) بدلًا من فحص إحداثيات هندسية عائمة.
نبدأ من \(z_0=0\) ونأخذ خمس خطوات متتالية مع عقارب الساعة. من العلاقة \(z_{t+1}=\lambda^{-2}z_t+\lambda^{-1}\) نحصل على
$$z_5=\lambda^{-1}\left(1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}\right).$$
ولأن \(\lambda^2\) جذر خامس أولي للوحدة، فإن
$$1+\lambda^{-2}+\lambda^{-4}+\lambda^{-6}+\lambda^{-8}=0,$$
ومن ثم \(z_5=0\). وفي صورة معاملات صحيحة تمثل نقطة النهاية نفسها بالمتجه
$$(-1,1,-1,1,-1),$$
وهو بالفعل يحقق معادلات الانغلاق الأربع. هندسيًا هذا هو الدوران الكامل حول المسار الخماسي الواضح.
لتكن \(C_t(s)\) عدد سلاسل الانعطاف ذات الطول \(t\) التي تنتهي في الحالة \(s\). نقطة البداية هي
$$C_0(0,0,0,0,0)=1.$$
ومن كل حالة توجد خطوتان ممكنتان فقط، لذا تكون العودية
$$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).$$
وبعد \(70\) طبقة نجمع قيم \(C_{70}(s)\) على جميع الحالات التي تحقق شروط الانغلاق لنحصل على العدد المطلوب.
تنفيذات C++ وPython وJava تعتمد البنية نفسها. فهي تحتفظ بخريطة من الحالة المضغوطة ذات الخمس مركبات إلى عدد المسارات التي تصل إليها بعد عدد الخطوات الحالي، وتبدأ من الحالة الصفرية بعدد يساوي \(1\).
في كل جولة تُبنى خريطة جديدة للطبقة التالية. ولكل حالة محفوظة يحسب التنفيذ الحالتين التاليتين، مع عقارب الساعة وعكسها، باستخدام التحويلين affine الدقيقين السابقين، ثم يضيف عدد المسارات الحالي إلى كلتا الوجهتين. لا توجد محاكاة هندسية خام ولا أي حساب عائم أثناء هذا العمل.
في النهاية تُفحَص جميع حالات الطبقة الأخيرة، وتُجمع أعداد الحالات التي تحقق المعادلات الخطية الأربع الخاصة بالانغلاق. نسخة Java تضغط الخماسية في مفتاح عددي واحد لأن كل مركبة تبقى بين \(-70\) و\(70\)، بينما تحتفظ نسختا C++ وPython بالخماسية نفسها كمفتاح. هذه فروق تمثيل فقط، أما الخوارزمية الرياضية فواحدة.
إذا رمزنا بـ \(S_t\) إلى عدد الحالات المضغوطة القابلة للوصول بعد \(t\) خطوة، فإن الطبقة \(t\) تعالج بالضبط \(S_t\) حالة وتولد انتقالين من كل حالة. لذلك يكون العبء الرياضي الكلي
$$O\!\left(\sum_{t=0}^{69} S_t\right).$$
أما الذاكرة فهي
$$O\!\left(\max_{0\le t\le 70} S_t\right),$$
لأن المطلوب تخزين الطبقة الحالية والطبقة التالية فقط. وهذا أصغر بكثير من تعداد جميع السلاسل الخام وعددها \(2^{70}\). في نسخة C++ يوجد عامل لوغاريتمي إضافي بسبب البنية المرتبة، بينما تعمل نسختا Python وJava عمليًا قريبًا من خطية عدد الانتقالات المولدة بفضل الخرائط المعتمدة على التجزئة.