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.
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})\).
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.
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.
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.
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.
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.
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.
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\).
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)\).
Langtons Ameise startet auf einem vollständig weißen unendlichen Quadratraster. In jedem Schritt betrachtet sie das aktuelle Feld, dreht bei Weiß nach rechts und bei Schwarz nach links, invertiert die Farbe des Feldes und geht dann ein Feld vorwärts. Project Euler 349 fragt nach der Anzahl schwarzer Felder nach \(10^{18}\) Schritten; eine vollständige Direktsimulation bis dorthin ist daher unmöglich.
Sei \(c_t(x,y)\in\{0,1\}\) die Farbe des Feldes \((x,y)\) nach \(t\) Schritten, wobei \(1\) für schwarz steht, und sei \(a_t=(x_t,y_t)\) die Position der Ameise unmittelbar vor Schritt \(t+1\). Definiere die Anzahl schwarzer Felder durch
$$B(t)=\sum_{(x,y)\in\mathbb{Z}^2} c_t(x,y).$$
Nach endlich vielen Schritten wurden nur endlich viele Felder besucht, also ist diese Summe endlich. Gesucht ist somit \(B(10^{18})\).
Ist das aktuelle Feld weiß, so dreht die Ameise nach rechts, färbt das Feld schwarz und geht vorwärts. Ist das Feld schwarz, so dreht sie nach links, färbt es weiß und geht vorwärts. Mit Richtungen modulo 4 gilt
$$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).$$
Damit ändert sich die Zahl schwarzer Felder in jedem Schritt genau um eins:
$$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$$
Genau deshalb kann der Code die komplette Folge \(B(0),B(1),\dots,B(T_0)\) während der Simulation praktisch kostenlos mitschreiben.
Das Gitter ist unendlich, aber zu jedem endlichen Zeitpunkt sind fast alle Felder weiß. Die Programme speichern daher nur die schwarzen Felder. Ein Umschalten bedeutet: War das Feld weiß, wird es in die Menge eingefügt; war es schwarz, wird es entfernt. Die aktuelle Zahl schwarzer Felder ist einfach die Größe dieser Menge.
In C++ und Java wird das Koordinatenpaar \((x,y)\) in einen 64-Bit-Schlüssel gepackt; in Python wird direkt das Tupel \((x,y)\) verwendet. Damit bleibt ein einzelnes Update im Erwartungswert konstant schnell.
Langtons Ameise ist dafür bekannt, nach einer chaotischen Übergangsphase einen sich wiederholenden diagonalen "Highway" zu erzeugen. Die gesamte Konfiguration ist dabei nicht ortsfest periodisch, weil das Muster über das Gitter wandert, wohl aber periodisch bis auf eine Translation.
Die Größe \(B(t)\) ist translationsinvariant. Deshalb existieren in der Highway-Phase ganze Zahlen \(p>0\) und \(\Delta\) mit
$$B(t+p)=B(t)+\Delta$$
auf einem Endintervall. Für die hier verwendeten Parameter findet das Programm \(p=104\) und \(\Delta=12\). Alle 104 weiteren Schritte entstehen also netto 12 zusätzliche schwarze Felder.
Die Highway-Konstanten sind im Code nicht fest einprogrammiert. Stattdessen wird bis zu einem moderaten Horizont \(T_0=200000\) exakt simuliert und die gesamte Zählfolge gespeichert.
Für jede Kandidatenperiode \(1\le p\le 500\) setzt der Algorithmus
$$\Delta_p=B(T_0)-B(T_0-p)$$
und prüft, ob
$$B(t+p)-B(t)=\Delta_p$$
auf einem langen Suffixfenster der Länge \(W=50000\) gilt. Überlebt ein Kandidat diesen Test, so wird anschließend der früheste Start \(s\) gesucht, ab dem dieselbe Beziehung bis zum Ende des simulierten Bereichs gültig bleibt.
Die C++- und Java-Versionen beschleunigen diese Suche durch ein Suffix-Array für Wahrheitswerte; Python verwendet dieselbe Logik in einer direkteren verschachtelten Schleife, was bei den hier festen Schranken ebenfalls problemlos praktikabel ist.
Sobald ein gültiges Tripel \((s,p,\Delta)\) gefunden ist, schreibt man jedes Ziel \(T\ge s\) als
$$T=s+qp+r,\qquad 0\le r<p,$$
wobei
$$q=\left\lfloor\frac{T-s}{p}\right\rfloor,\qquad r=(T-s)\bmod p.$$
Jede volle Periode trägt \(\Delta\) zusätzliche schwarze Felder bei, also
$$\boxed{B(T)=B(s+r)+q\Delta.}$$
Genau das macht aus dem gigantischen Ziel \(10^{18}\) nach einer endlichen Simulation nur noch eine gewöhnliche Ganzzahlarithmetik-Rechnung.
Der im C++-Programm eingebaute Checkpoint überprüft die Anfangsfolge
$$B(0..10)=0,1,2,3,4,3,4,5,6,7,6,$$
also insbesondere \(B(10)=6\). Das ist ein kleiner, aber hilfreicher Konsistenztest dafür, dass Drehen, Färben und Vorwärtsbewegung korrekt implementiert sind, bevor überhaupt nach einem Schwanzmuster gesucht wird.
Alle drei Implementierungen folgen derselben Pipeline. Zuerst erzeugt simulateBlackCounts (bzw. das Python-Pendant) das Verlaufsarray counts. Danach durchsucht detectLinearPattern die Kandidatenperioden und liefert einen Schwanzparameter \((s,p,\Delta)\). Schließlich wertet extrapolateBlackCount die obige Formel am Zielschritt aus.
Die C++-Version enthält zusätzlich Checkpoints: Sie bestätigt \(B(10)=6\), prüft die gefundenen Highway-Parameter \(p=104\) und \(\Delta=12\) und verifiziert, dass die Extrapolation den direkt simulierten Wert bei Schritt \(150000\) reproduziert.
Die exakte Simulation benötigt \(O(T_0)\) erwartete Zeit und \(O(M)\) Speicher für die Menge schwarzer Felder, wobei \(M\le T_0\). Das Verlaufsarray für die Werte \(B(t)\) braucht zusätzlich \(O(T_0)\) Speicher.
Die Prüfung der Suffixbedingung über alle Kandidatenperioden kostet ungefähr \(O(p_{\max}W)\), gefolgt von einer Suche nach dem frühesten gültigen Start. In C++ und Java ist diese Suche pro erfolgreichem Kandidaten linear; Python benutzt eine einfachere Schleifenstruktur, aber mit festen Grenzen, die im Vergleich zu \(10^{18}\) winzig sind. Ist \((s,p,\Delta)\) einmal bekannt, kostet die Endauswertung nur \(O(1)\).
Langton karıncası, tamamı beyaz olan sonsuz kareli bir ızgarada başlar. Her adımda bulunduğu hücrenin rengine bakar; hücre beyazsa sağa, siyahsa sola döner, o hücrenin rengini tersine çevirir ve sonra bir kare ilerler. Project Euler 349, \(10^{18}\) adım sonundaki siyah kare sayısını sorar; dolayısıyla hedefe kadar doğrudan adım adım simülasyon yapmak imkansızdır.
\(c_t(x,y)\in\{0,1\}\), \((x,y)\) hücresinin \(t\) adım sonundaki rengini göstersin; burada \(1\) siyah anlamına gelsin. \(a_t=(x_t,y_t)\) ise karıncanın \(t+1\). adımdan hemen önceki konumu olsun. Siyah kare sayısını
$$B(t)=\sum_{(x,y)\in\mathbb{Z}^2} c_t(x,y)$$
şeklinde tanımlayalım. Sonlu sayıda adımda yalnızca sonlu sayıda hücre ziyaret edildiği için bu toplam sonludur. İstenen değer de \(B(10^{18})\)'dir.
Karınca beyaz bir hücre üzerindeyse sağa döner, o hücreyi siyaha boyar ve ileri gider. Siyah bir hücre üzerindeyse sola döner, hücreyi beyaza boyar ve ileri gider. Yönü mod 4 ile yazarsak
$$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).$$
Böylece toplam siyah kare sayısı her adımda tam olarak bir artar ya da bir azalır:
$$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$$
Bu yüzden kod, simülasyon sırasında \(B(0),B(1),\dots,B(T_0)\) geçmişini neredeyse ek maliyet olmadan tutabilir.
Tahta sonsuzdur ama sonlu bir anda hücrelerin neredeyse tamamı beyazdır. Bu nedenle implementasyonlar yalnızca siyah hücreleri saklar. Bir hücreyi ters çevirmek, hücre beyazsa kümeye eklemek; siyahsa kümeden çıkarmak demektir. O andaki siyah hücre sayısı da doğrudan kümenin boyudur.
C++ ve Java sürümlerinde \((x,y)\) koordinat çifti 64 bitlik tek bir anahtara kodlanır; Python sürümünde ise doğrudan \((x,y)\) demeti kullanılır. Böylece tek adımlık güncellemenin ortalama maliyeti sabit kalır.
Langton karıncasının klasik davranışı şudur: karmaşık bir geçiş döneminden sonra tekrarlayan diyagonal bir "otoyol" üretmeye başlar. Tüm konfigürasyon bulunduğu yerde tam periyodik olmaz; çünkü desen ızgara üzerinde kayar. Fakat öteleme altında periyodiktir.
\(B(t)\) ötelemeye göre değişmeyen bir büyüklüktür. Bu nedenle otoyol fazında bazı \(p>0\) ve \(\Delta\) tamsayıları için kuyruğun bir noktasından sonra
$$B(t+p)=B(t)+\Delta$$
ilişkisi geçerlidir. Bu programlarda kullanılan parametrelerle tespit edilen kuyruk \(p=104\) ve \(\Delta=12\) verir. Yani her 104 ilave adımda siyah kare sayısı net 12 artar.
Kod, otoyol sabitlerini doğrudan gömmez. Bunun yerine önce \(T_0=200000\) adımına kadar tam simülasyon yapar ve tüm sayım dizisini saklar.
Her \(1\le p\le 500\) aday periyodu için
$$\Delta_p=B(T_0)-B(T_0-p)$$
tanımlanır ve
$$B(t+p)-B(t)=\Delta_p$$
eşitliğinin uzunluğu \(W=50000\) olan son bir pencere boyunca geçerli olup olmadığı test edilir. Bir aday bu testi geçerse, algoritma daha sonra aynı ilişkinin simülasyonun sonuna kadar ilk kez hangi başlangıç noktası \(s\)'den itibaren sürekli doğru kaldığını arar.
C++ ve Java sürümleri bu "en erken başlangıç" aramasını bir suffix-doğruluk dizisi ile doğrusal hale getirir. Python sürümü aynı mantığı daha doğrudan iç içe döngülerle yazar; burada kullanılan sabit sınırlar için bu da tamamen yeterlidir.
Geçerli bir \((s,p,\Delta)\) üçlüsü bulunduğunda her \(T\ge s\) hedefi
$$T=s+qp+r,\qquad 0\le r<p,$$
şeklinde yazılır; burada
$$q=\left\lfloor\frac{T-s}{p}\right\rfloor,\qquad r=(T-s)\bmod p.$$
Her tam periyot \(\Delta\) kadar ek siyah hücre ürettiği için
$$\boxed{B(T)=B(s+r)+q\Delta.}$$
Asıl kırılma noktası budur: tek bir sonlu simülasyondan sonra devasa \(10^{18}\) hedefi sıradan tamsayı aritmetiğiyle hesaplanır.
C++ çözümündeki checkpoint, başlangıç sayım dizisinin
$$B(0..10)=0,1,2,3,4,3,4,5,6,7,6$$
olduğunu doğrular; özellikle \(B(10)=6\). Bu küçük örnek, kuyruk tespiti yapılmadan önce dönme, boyama ve ilerleme kurallarının doğru uygulandığını göstermesi açısından önemlidir.
Üç dilde de akış aynıdır. Önce simulateBlackCounts fonksiyonu (veya Python eşdeğeri) counts geçmiş dizisini üretir. Ardından detectLinearPattern aday periyotları tarar ve bir kuyruk tanımı \((s,p,\Delta)\) döndürür. Son aşamada extrapolateBlackCount yukarıdaki formülü hedef adıma uygular.
C++ sürümünde ek doğrulamalar da vardır: \(B(10)=6\) kontrol edilir, tespit edilen otoyol parametrelerinin \(p=104\) ve \(\Delta=12\) olduğu doğrulanır ve ekstrapolasyonun \(150000\). adımda doğrudan simülasyonla aynı sonucu verdiği sınanır.
Tam simülasyon beklenen \(O(T_0)\) zaman alır ve siyah hücre kümesi için \(O(M)\) bellek kullanır; burada \(M\le T_0\). \(B(t)\) geçmişini tutan dizi ayrıca \(O(T_0)\) alan gerektirir.
Aday periyotlar üzerindeki son pencere doğrulaması yaklaşık \(O(p_{\max}W)\) maliyetlidir; bunun ardından en erken geçerli başlangıç aranır. C++ ve Java'da bu arama aday başına doğrusaldır. Python daha basit bir döngü yapısı kullanır, ancak kullanılan eşikler \(10^{18}\) ile kıyaslandığında çok küçüktür. \((s,p,\Delta)\) bulunduktan sonra nihai hesap \(O(1)\)'dir.
La hormiga de Langton empieza en una cuadrícula infinita completamente blanca. En cada paso mira la celda actual: si es blanca gira a la derecha, si es negra gira a la izquierda, invierte el color de esa celda y luego avanza una unidad. Project Euler 349 pide el número de celdas negras después de \(10^{18}\) pasos, así que una simulación directa hasta el objetivo es inviable.
Sea \(c_t(x,y)\in\{0,1\}\) el color de la celda \((x,y)\) tras \(t\) pasos, donde \(1\) significa negra, y sea \(a_t=(x_t,y_t)\) la posición de la hormiga justo antes del paso \(t+1\). Definimos
$$B(t)=\sum_{(x,y)\in\mathbb{Z}^2} c_t(x,y).$$
Tras un número finito de pasos solo se han visitado finitas celdas, de modo que la suma es finita. El objetivo es calcular \(B(10^{18})\).
Si la celda actual es blanca, la hormiga gira a la derecha, la pinta de negro y avanza. Si la celda actual es negra, gira a la izquierda, la pinta de blanco y avanza. Escribiendo la dirección módulo 4, tenemos
$$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).$$
Por tanto, el número total de celdas negras cambia exactamente en una unidad en cada paso:
$$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$$
Esto explica por qué el programa puede registrar toda la historia \(B(0),B(1),\dots,B(T_0)\) durante la simulación con muy poco trabajo adicional.
La cuadrícula es infinita, pero en cualquier instante finito casi todas las celdas siguen siendo blancas. Por eso las implementaciones guardan solo las celdas negras. Cambiar el color de una celda equivale a insertarla en el conjunto si era blanca o eliminarla si era negra. El valor actual de \(B(t)\) es simplemente el tamaño de ese conjunto.
En C++ y Java, el par \((x,y)\) se empaqueta en una clave de 64 bits; en Python se usa directamente la tupla \((x,y)\). Así, cada actualización tiene coste esperado constante.
La hormiga de Langton es famosa porque, después de una fase caótica inicial, construye una "autopista" diagonal repetitiva. La configuración completa no es estrictamente periódica en el mismo lugar, porque el dibujo se desplaza por la cuadrícula, pero sí es periódica salvo por una traslación.
La cantidad \(B(t)\) es invariante por traslación. Por eso, en la fase de autopista existen enteros \(p>0\) y \(\Delta\) tales que en una cola de la secuencia se cumple
$$B(t+p)=B(t)+\Delta.$$
Con los parámetros usados aquí, la cola detectada tiene periodo \(p=104\) y ganancia \(\Delta=12\). Es decir, cada bloque adicional de 104 pasos añade 12 celdas negras netas.
El código no fija de antemano esas constantes. En lugar de eso, simula exactamente hasta un horizonte moderado \(T_0=200000\) y guarda toda la secuencia de conteos.
Para cada periodo candidato \(1\le p\le 500\), define
$$\Delta_p=B(T_0)-B(T_0-p)$$
y comprueba si
$$B(t+p)-B(t)=\Delta_p$$
se mantiene en una ventana final larga de longitud \(W=50000\). Si un candidato supera esa prueba, el algoritmo busca después el punto inicial más temprano \(s\) a partir del cual la misma relación sigue siendo válida hasta el final de la simulación.
Las versiones en C++ y Java aceleran esta búsqueda con un arreglo de sufijos booleanos. La versión en Python usa la misma idea con bucles anidados más directos, suficiente con los umbrales fijos de este problema.
Una vez hallado un triple válido \((s,p,\Delta)\), cualquier objetivo \(T\ge s\) puede escribirse como
$$T=s+qp+r,\qquad 0\le r<p,$$
donde
$$q=\left\lfloor\frac{T-s}{p}\right\rfloor,\qquad r=(T-s)\bmod p.$$
Cada periodo completo aporta \(\Delta\) celdas negras adicionales, luego
$$\boxed{B(T)=B(s+r)+q\Delta.}$$
Esta es la reducción clave: después de una simulación finita, el objetivo gigantesco \(10^{18}\) se resuelve con aritmética entera ordinaria.
La comprobación incluida en la versión C++ verifica la sucesión inicial
$$B(0..10)=0,1,2,3,4,3,4,5,6,7,6,$$
de modo que \(B(10)=6\). Es una verificación pequeña, pero útil, de que las reglas de giro, cambio de color y avance están implementadas correctamente antes de detectar la cola lineal-periódica.
Las tres implementaciones siguen el mismo esquema. Primero, simulateBlackCounts (o su equivalente en Python) construye el arreglo counts. Después, detectLinearPattern recorre los periodos candidatos y devuelve un descriptor de cola \((s,p,\Delta)\). Por último, extrapolateBlackCount evalúa la fórmula anterior en el paso objetivo.
La versión en C++ añade comprobaciones explícitas: confirma \(B(10)=6\), verifica que los parámetros detectados de la autopista son \(p=104\) y \(\Delta=12\), y comprueba que la extrapolación reproduce el valor simulado directamente en el paso \(150000\).
La simulación exacta cuesta \(O(T_0)\) tiempo esperado y \(O(M)\) memoria para el conjunto de celdas negras, con \(M\le T_0\). El historial de valores \(B(t)\) requiere además \(O(T_0)\) espacio.
La verificación de la cola sobre los periodos candidatos cuesta aproximadamente \(O(p_{\max}W)\), seguida de la búsqueda del inicio válido más temprano. En C++ y Java esa búsqueda es lineal por candidato superviviente; Python usa una estructura de bucles más simple, pero con límites fijos muy pequeños frente a \(10^{18}\). Una vez conocido \((s,p,\Delta)\), la evaluación final es \(O(1)\).
Langton 蚂蚁从一张全白的无限方格纸开始。每一步它先看当前格子的颜色：若是白色就右转，若是黑色就左转；随后把该格子颜色翻转，再向前走一格。Project Euler 349 要求的是 \(10^{18}\) 步之后黑格子的数量，因此不可能一直直接模拟到目标步数。
记 \(c_t(x,y)\in\{0,1\}\) 为第 \(t\) 步后格子 \((x,y)\) 的颜色，其中 \(1\) 表示黑色；记 \(a_t=(x_t,y_t)\) 为第 \(t+1\) 步开始前蚂蚁所在的位置。定义黑格数量
$$B(t)=\sum_{(x,y)\in\mathbb{Z}^2} c_t(x,y).$$
因为有限步之后只会访问有限多个格子，所以这个和是有限的。题目要求的就是 \(B(10^{18})\)。
如果当前格子是白色，蚂蚁右转，把该格翻成黑色，然后前进一步；如果当前格子是黑色，蚂蚁左转，把该格翻成白色，然后前进一步。把方向按模 4 表示，则有
$$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).$$
因此黑格总数每一步只会变化 \(\pm1\)：
$$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$$
这就是为什么程序可以在模拟过程中顺便记录完整的计数历史 \(B(0),B(1),\dots,B(T_0)\)。
棋盘虽然无限，但任意有限时刻几乎所有格子仍然是白色，所以实现里只保存黑格坐标。某个格子翻转时，如果原来是白色就插入集合，如果原来是黑色就从集合删除。当前的黑格数就是集合大小。
在 C++ 和 Java 中，\((x,y)\) 会被编码成一个 64 位整数键；在 Python 中，直接使用 \((x,y)\) 元组。这样每一步的更新在平均意义下都接近常数时间。
Langton 蚂蚁最著名的现象之一，是在经历一段混乱过渡后会形成重复的对角“高速公路”。整个图案并不是在原地严格周期，因为它会沿着平面平移；但它在“平移意义下”是周期的。
黑格数量 \(B(t)\) 对平移不敏感，因此在高速公路阶段，存在整数 \(p>0\) 和 \(\Delta\)，使得在尾部区间上满足
$$B(t+p)=B(t)+\Delta.$$
在这里使用的参数下，程序检测到的尾部参数是 \(p=104\)、\(\Delta=12\)。也就是说，每再走 104 步，黑格总数净增加 12 个。
代码并没有把这些常数写死，而是先精确模拟到中等规模的步数 \(T_0=200000\)，并保存整段计数序列。
对每个候选周期 \(1\le p\le 500\)，先定义
$$\Delta_p=B(T_0)-B(T_0-p),$$
再检查
$$B(t+p)-B(t)=\Delta_p$$
是否在长度为 \(W=50000\) 的后缀窗口内始终成立。如果某个候选周期通过了这个测试，算法还会继续寻找最早的起点 \(s\)，使得从 \(s\) 开始到模拟结束，这个关系一直成立。
C++ 和 Java 用一个布尔后缀数组把“最早起点”搜索优化成线性过程；Python 保留了相同逻辑，但用更直接的双重循环实现，在这里的固定阈值下也完全足够。
一旦得到有效三元组 \((s,p,\Delta)\)，任何 \(T\ge s\) 都可写成
$$T=s+qp+r,\qquad 0\le r<p,$$
其中
$$q=\left\lfloor\frac{T-s}{p}\right\rfloor,\qquad r=(T-s)\bmod p.$$
每个完整周期都会额外贡献 \(\Delta\) 个黑格，因此
$$\boxed{B(T)=B(s+r)+q\Delta.}$$
这一步就是核心简化：先做一次有限模拟，再用普通整数运算处理巨大的 \(10^{18}\) 步目标。
C++ 版本里的检查点验证了最开始的黑格计数序列
$$B(0..10)=0,1,2,3,4,3,4,5,6,7,6,$$
因此 \(B(10)=6\)。这个小例子可以确认转向、翻色和前进规则在开始阶段就已经实现正确。
三个版本都遵循同一条流水线。首先，simulateBlackCounts（或 Python 中对应的函数）构造历史数组 counts。接着，detectLinearPattern 扫描候选周期并返回尾部描述 \((s,p,\Delta)\)。最后，extrapolateBlackCount 用上面的公式计算目标步数对应的黑格数量。
C++ 版本还带有额外检查：先确认 \(B(10)=6\)，再验证检测出的高速公路参数确实是 \(p=104\)、\(\Delta=12\)，并检查外推结果在第 \(150000\) 步与直接模拟完全一致。
精确模拟需要 \(O(T_0)\) 的期望时间，以及 \(O(M)\) 的黑格集合空间，其中 \(M\le T_0\)。计数历史数组还需要额外的 \(O(T_0)\) 空间。
对候选周期进行后缀验证的代价大约是 \(O(p_{\max}W)\)，之后还要寻找最早有效起点。C++ 和 Java 中，这一步对每个通过的候选周期都是线性的；Python 的写法更直接，但这里的阈值与 \(10^{18}\) 相比非常小。模式一旦确定，最终求值就是 \(O(1)\)。
Муравей Лэнгтона стартует на бесконечной квадратной решетке, где все клетки изначально белые. На каждом шаге он смотрит на текущую клетку: если она белая, поворачивает направо, если черная, поворачивает налево, затем меняет цвет клетки и делает шаг вперед. В задаче Project Euler 349 требуется число черных клеток после \(10^{18}\) шагов, поэтому прямое моделирование до цели нереально.
Пусть \(c_t(x,y)\in\{0,1\}\) обозначает цвет клетки \((x,y)\) после \(t\) шагов, где \(1\) означает черный цвет, а \(a_t=(x_t,y_t)\) — положение муравья непосредственно перед шагом \(t+1\). Определим число черных клеток как
$$B(t)=\sum_{(x,y)\in\mathbb{Z}^2} c_t(x,y).$$
После конечного числа шагов посещено лишь конечное число клеток, поэтому эта сумма конечна. Требуется вычислить \(B(10^{18})\).
Если текущая клетка белая, муравей поворачивает направо, красит клетку в черный цвет и идет вперед. Если клетка черная, он поворачивает налево, красит ее в белый цвет и идет вперед. Если считать направления по модулю 4, то
$$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).$$
Отсюда следует, что число черных клеток на каждом шаге меняется ровно на единицу:
$$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$$
Именно поэтому программа может почти бесплатно записывать всю историю значений \(B(0),B(1),\dots,B(T_0)\) во время моделирования.
Поле бесконечно, но в любой конечный момент почти все клетки все равно белые. Поэтому реализации хранят только координаты черных клеток. Перекрасить клетку означает добавить ее в множество, если она была белой, или удалить из множества, если она была черной. Текущее значение \(B(t)\) — это просто размер этого множества.
В версиях на C++ и Java пара \((x,y)\) кодируется в один 64-битный ключ; в Python используется кортеж \((x,y)\). Это дает в среднем постоянную стоимость одного обновления.
Классическое свойство муравья Лэнгтона состоит в том, что после хаотического переходного периода он строит повторяющееся диагональное "шоссе". Вся конфигурация не является строго периодической на месте, потому что рисунок сдвигается по решетке, но она становится периодической с точностью до переноса.
Величина \(B(t)\) инвариантна относительно переноса. Поэтому в режиме шоссе существуют целые \(p>0\) и \(\Delta\), для которых на хвосте последовательности выполняется
$$B(t+p)=B(t)+\Delta.$$
При параметрах, используемых в этих программах, обнаруживается хвост с \(p=104\) и \(\Delta=12\): каждые дополнительные 104 шага дают чистый прирост в 12 черных клеток.
Код не зашивает эти константы вручную. Вместо этого сначала выполняется точное моделирование до умеренного горизонта \(T_0=200000\), и сохраняется вся последовательность значений.
Для каждого кандидата на период \(1\le p\le 500\) вычисляется
$$\Delta_p=B(T_0)-B(T_0-p),$$
после чего проверяется, выполняется ли
$$B(t+p)-B(t)=\Delta_p$$
на длинном хвостовом окне длины \(W=50000\). Если кандидат проходит эту проверку, алгоритм затем ищет самый ранний момент \(s\), начиная с которого это соотношение остается верным до конца смоделированного диапазона.
В C++ и Java этот поиск ускоряется булевым суффиксным массивом; в Python используется та же логика в более прямой форме с вложенными циклами, чего вполне достаточно при фиксированных ограничениях задачи.
После нахождения корректной тройки \((s,p,\Delta)\) любой момент \(T\ge s\) записывается в виде
$$T=s+qp+r,\qquad 0\le r<p,$$
где
$$q=\left\lfloor\frac{T-s}{p}\right\rfloor,\qquad r=(T-s)\bmod p.$$
Каждый полный период добавляет \(\Delta\) черных клеток, поэтому
$$\boxed{B(T)=B(s+r)+q\Delta.}$$
Это и есть ключевая редукция: после конечной симуляции гигантское значение \(10^{18}\) обрабатывается обычной целочисленной арифметикой.
Проверка в версии на C++ подтверждает начальную последовательность
$$B(0..10)=0,1,2,3,4,3,4,5,6,7,6,$$
то есть \(B(10)=6\). Это небольшой, но полезный тест того, что поворот, перекраска и движение реализованы верно еще до поиска линейно-периодического хвоста.
Во всех трех реализациях используется одна и та же схема. Сначала simulateBlackCounts (или ее эквивалент в Python) строит массив истории counts. Затем detectLinearPattern перебирает кандидаты на период и возвращает параметры хвоста \((s,p,\Delta)\). Наконец, extrapolateBlackCount подставляет целевой шаг в приведенную выше формулу.
Версия на C++ содержит и дополнительные проверки: она подтверждает \(B(10)=6\), проверяет, что найденные параметры шоссе равны \(p=104\) и \(\Delta=12\), а также сверяет экстраполяцию с прямой симуляцией на шаге \(150000\).
Точная симуляция требует \(O(T_0)\) ожидаемого времени и \(O(M)\) памяти для множества черных клеток, где \(M\le T_0\). Массив истории значений \(B(t)\) добавляет еще \(O(T_0)\) памяти.
Проверка хвоста по кандидатам на период стоит примерно \(O(p_{\max}W)\), после чего выполняется поиск самого раннего допустимого начала. В C++ и Java этот поиск линейный для каждого выжившего кандидата; Python использует более простой цикл, но фиксированные пороги по-прежнему ничтожны по сравнению с \(10^{18}\). После нахождения \((s,p,\Delta)\) итоговое вычисление занимает \(O(1)\).
تبدأ نملة لانغتون على شبكة مربعة لا نهائية تكون جميع خلاياها بيضاء في البداية. في كل خطوة تنظر إلى الخلية الحالية: إذا كانت بيضاء تدور يمينًا، وإذا كانت سوداء تدور يسارًا، ثم تعكس لون الخلية وتتحرك خطوة واحدة إلى الأمام. في مسألة Project Euler 349 نريد عدد الخلايا السوداء بعد \(10^{18}\) خطوة، ولذلك فالمحاكاة المباشرة حتى الهدف غير عملية.
لتكن \(c_t(x,y)\in\{0,1\}\) لون الخلية \((x,y)\) بعد \(t\) خطوة، بحيث تمثل \(1\) اللون الأسود، وليكن \(a_t=(x_t,y_t)\) موضع النملة مباشرة قبل الخطوة \(t+1\). نعرّف عدد الخلايا السوداء بالصيغة
$$B(t)=\sum_{(x,y)\in\mathbb{Z}^2} c_t(x,y).$$
بعد عدد منتهٍ من الخطوات لا تكون قد زارت النملة إلا عددًا منتهيًا من الخلايا، لذلك يكون هذا المجموع منتهيًا. والمطلوب هو حساب \(B(10^{18})\).
إذا كانت الخلية الحالية بيضاء، تدور النملة إلى اليمين، وتلوّن الخلية بالأسود، ثم تتحرك إلى الأمام. وإذا كانت الخلية الحالية سوداء، تدور إلى اليسار، وتلوّن الخلية بالأبيض، ثم تتحرك إلى الأمام. وإذا رمزنا للاتجاهات بتوافقية modulo 4 فإن
$$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).$$
إذن يتغير عدد الخلايا السوداء بمقدار واحد فقط في كل خطوة:
$$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$$
وهذا يفسر لماذا يستطيع البرنامج تسجيل التاريخ الكامل للقيم \(B(0),B(1),\dots,B(T_0)\) أثناء المحاكاة بكلفة إضافية صغيرة جدًا.
الشبكة لا نهائية، لكن معظم الخلايا تبقى بيضاء عند أي زمن منتهٍ. لذلك تخزن البرامج الخلايا السوداء فقط. قلب لون خلية يعني إضافتها إلى المجموعة إذا كانت بيضاء، أو حذفها إذا كانت سوداء. وبالتالي فإن القيمة الحالية لـ \(B(t)\) هي ببساطة حجم تلك المجموعة.
في C++ وJava يُحوَّل الزوج \((x,y)\) إلى مفتاح وحيد بطول 64 بت، أما في Python فيُستخدم الزوج نفسه على هيئة tuple. وبهذا تبقى كلفة التحديث في المتوسط ثابتة تقريبًا.
من أشهر خصائص نملة لانغتون أنها، بعد مرحلة انتقالية فوضوية، تبدأ في بناء "طريق سريع" قطري متكرر. التشكيل الكامل لا يصبح دوريًا في موضعه نفسه لأن النمط ينساب عبر الشبكة، لكنه يصبح دوريًا حتى مع وجود إزاحة مكانية.
أما العدد \(B(t)\) فهو ثابت تحت الإزاحة، ولذلك توجد أعداد صحيحة \(p>0\) و\(\Delta\) بحيث يتحقق على ذيل السلسلة
$$B(t+p)=B(t)+\Delta.$$
وبالمعاملات المستخدمة هنا يكتشف البرنامج أن \(p=104\) و\(\Delta=12\). أي إن كل 104 خطوة إضافية تزيد عدد الخلايا السوداء الصافي بمقدار 12.
لا يضع الكود ثوابت الطريق السريع بشكل صريح. بل يحاكي أولًا حتى أفق متوسط \(T_0=200000\) خطوة ويخزن سلسلة العد كاملة.
لكل فترة مرشحة \(1\le p\le 500\) يعرّف
$$\Delta_p=B(T_0)-B(T_0-p)$$
ثم يختبر هل
$$B(t+p)-B(t)=\Delta_p$$
صحيحة على نافذة لاحقة طويلة طولها \(W=50000\). وإذا اجتاز المرشح هذا الاختبار، يبحث البرنامج بعد ذلك عن أقدم بداية \(s\) تبقى عندها العلاقة نفسها صحيحة حتى نهاية المدى المحاكى.
نسختا C++ وJava تسرعان هذا البحث بمصفوفة suffix منطقية، بينما تكتب Python المنطق نفسه بحلقات متداخلة أبسط، وهو كاف تمامًا مع الحدود الثابتة المستخدمة هنا.
بمجرد العثور على ثلاثية صالحة \((s,p,\Delta)\)، يمكن كتابة أي هدف \(T\ge s\) على الصورة
$$T=s+qp+r,\qquad 0\le r<p,$$
حيث
$$q=\left\lfloor\frac{T-s}{p}\right\rfloor,\qquad r=(T-s)\bmod p.$$
كل دورة كاملة تضيف \(\Delta\) خلية سوداء، لذلك
$$\boxed{B(T)=B(s+r)+q\Delta.}$$
وهذه هي الفكرة الحاسمة: بعد محاكاة منتهية يصبح الهدف الهائل \(10^{18}\) مجرد حساب صحيح بسيط.
تتحقق نقطة الفحص في نسخة C++ من أن متتالية البداية هي
$$B(0..10)=0,1,2,3,4,3,4,5,6,7,6,$$
ومن ثم \(B(10)=6\). هذا مثال صغير لكنه مفيد للتأكد من صحة قواعد الدوران والتلوين والحركة قبل البدء في اكتشاف الذيل الدوري.
تتبع التطبيقات الثلاثة المسار نفسه. أولًا تبني الدالة simulateBlackCounts أو ما يقابلها في Python مصفوفة التاريخ counts. بعد ذلك تفحص detectLinearPattern الفترات المرشحة وتعيد وصف الذيل \((s,p,\Delta)\). وأخيرًا تطبق extrapolateBlackCount الصيغة السابقة على الخطوة الهدف.
وتتضمن نسخة C++ اختبارات إضافية: فهي تتحقق من \(B(10)=6\)، وتؤكد أن معاملي الطريق السريع المكتشفين هما \(p=104\) و\(\Delta=12\)، كما تتحقق من أن الاستقراء يعطي القيمة نفسها التي تنتجها المحاكاة المباشرة عند الخطوة \(150000\).
تستغرق المحاكاة الدقيقة زمنًا متوقعًا قدره \(O(T_0)\)، وتستخدم \(O(M)\) من الذاكرة لمجموعة الخلايا السوداء، حيث \(M\le T_0\). كما تحتاج مصفوفة تاريخ القيم \(B(t)\) إلى مساحة إضافية قدرها \(O(T_0)\).
أما فحص الذيل عبر الفترات المرشحة فيكلف تقريبًا \(O(p_{\max}W)\)، ثم يتبعه بحث عن أقدم بداية صحيحة. يكون هذا البحث خطيًا لكل مرشح ناجح في C++ وJava، بينما تستخدم Python بنية حلقات أبسط، لكن الحدود الثابتة هنا صغيرة جدًا مقارنةً بـ \(10^{18}\). وبعد معرفة \((s,p,\Delta)\) تصبح عملية الحساب النهائية \(O(1)\).