We consider a random \(W\times H\) binary grid, with the Project Euler instance using \(W=H=7\). Each cell is occupied independently with probability \(1/2\), and occupied cells are connected by 4-neighbor adjacency. If \(L(B)\) denotes the size of the largest occupied connected component of a board \(B\), the task is to compute the exact expectation \(\mathbb E[L(B)]\).
A brute-force search would inspect all \(2^{WH}\) boards, which is impossible for \(7\times 7\). The successful idea is to scan the grid one column at a time and keep only the information that can still influence future growth.
Let
$$\Omega_{W,H}=\{0,1\}^{W\times H}.$$
For each board \(B\in\Omega_{W,H}\), let \(\mathcal C(B)\) be the set of occupied 4-connected components of \(B\), and define
$$L(B)=\max_{C\in\mathcal C(B)} \lvert C\rvert,$$
with the convention \(L(B)=0\) when the board has no occupied cells. Since every board is equally likely,
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{B\in\Omega_{W,H}} L(B).$$
So the whole problem is to sum the largest-component size over all boards exactly, then divide by \(2^{WH}\).
Suppose the first \(c\) columns have already been processed. Any connected component that does not touch column \(c\) can never grow again, because all future cells lie strictly to the right. Therefore closed components only matter through a single number: the largest closed size seen so far.
Now look at column \(c\). Its occupied cells form vertical runs such as \(11100 11\mapsto (111)\) and \((11)\). Let these runs be \(R_1,\dots,R_t\). Two different runs in the same column may already belong to the same global component because earlier columns can connect them around the gaps. Hence the frontier is not described only by the mask of occupied cells; we must also know which runs belong together.
The state can therefore be written as
$$\sigma=(b,\Pi,a_1,\dots,a_r),$$
where:
Here \(b\) denotes the largest closed component size seen so far.
\(\Pi\) is a partition of the runs \(R_1,\dots,R_t\), and each block of \(\Pi\) corresponds to one open component touching the frontier,
For \(1\le j\le r\), \(a_j\) denotes the total size of the \(j\)-th open component.
This is sufficient because future columns can interact with the processed region only through those open components.
Let the next column be the bitmask \(m\in\{0,1\}^W\). Its occupied cells also decompose into vertical runs, say \(S_1,\dots,S_u\).
An old open component touches the new column exactly at rows where both adjacent columns contain an occupied cell. Once one cell of a run \(S_k\) is touched, the whole run belongs to the same new connected piece, because cells inside one vertical run are already connected within the new column.
This produces three possibilities:
First, an old open component may touch nothing in the new column. Then it becomes closed forever and can only update the best closed value.
Second, one old component may touch one or more runs in the new column. Then it survives and its size grows by the number of newly occupied cells attached to it.
Third, several old components may touch the same run, or runs that become linked inside the new column. Then those components merge into one new open component.
If \(\mathcal D\) is the set of old open components that disappear, then
$$b'=\max\!\Bigl(b,\max_{j\in\mathcal D} a_j\Bigr).$$
For each new open component \(T\), let \(\mathcal A(T)\) be the set of old components that feed into it. Its new size is
$$a'(T)=\lvert T\rvert+\sum_{j\in\mathcal A(T)} a_j,$$
where \(\lvert T\rvert\) counts only the occupied cells in the newly appended column.
Inside a single column, connectivity is completely determined by vertical runs. Cells in the same run are automatically connected, while cells in different runs are separated inside that column. The only missing information is whether two distinct runs are already linked through earlier columns. That is exactly what the partition \(\Pi\) records.
This compression is powerful because a width-7 column has at most four occupied runs, for example \(1010101\). So for each column mask there are only finitely many possible partitions of those runs, and all of them can be precomputed once. The dynamic program then works with canonical frontier patterns instead of full partial boards.
Take width \(W=3\). Suppose the first processed column is \(101\). Then there are two runs:
$$R_1=\{1\},\qquad R_2=\{3\}.$$
No earlier column exists, so they are separate open components of sizes \(1\) and \(1\). The state is
$$\sigma=\bigl(0,\{\{R_1\},\{R_2\}\},1,1\bigr).$$
Now append the next column \(111\). In the new column there is one run
$$S_1=\{1,2,3\}.$$
The old component at row \(1\) touches \(S_1\), and the old component at row \(3\) also touches \(S_1\). Because those contacts lie in the same vertical run, the whole run becomes one connected bridge, so the two old components merge. The new open component has size
$$1+1+3=5.$$
The new state is therefore
$$\sigma'=\bigl(0,\{\{S_1\}\},5\bigr).$$
If the following column were \(000\), that size-5 component would lose frontier contact, close permanently, and update the best closed value to \(5\).
Let \(w_c(\sigma)\) be the number of \(c\)-column prefixes that produce state \(\sigma\). The transition defined above gives
$$w_{c+1}(\sigma')=\sum_{\sigma}\sum_{\substack{m\in\{0,1\}^W\\ T_m(\sigma)=\sigma'}} w_c(\sigma),$$
where \(T_m\) is the deterministic update induced by the next column mask \(m\). The dynamic program stores these weights as exact integers, not floating-point probabilities.
After all \(H\) columns have been processed, every terminal state \(\sigma=(b,\Pi,a_1,\dots,a_r)\) contributes
$$\operatorname{score}(\sigma)=\max(b,a_1,\dots,a_r)$$
to the largest connected area of each board counted by that state. Hence
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{\sigma\in\mathcal T} w_H(\sigma)\operatorname{score}(\sigma),$$
where \(\mathcal T\) is the set of terminal states. This is exactly the quantity evaluated by the implementation.
The implementation first enumerates every possible column mask, decomposes each mask into vertical runs, and precomputes the canonical partitions of those runs. It also precomputes how an old frontier pattern interacts with a new column: which old components survive, which ones merge, which ones disappear, and how many new occupied cells are absorbed into each surviving component.
The dynamic program then advances one column at a time. A state is keyed by the frontier partition together with the accumulated open-component sizes and the current best closed size. When a new column is appended, the implementation applies the precomputed connectivity rule, creates the resulting state, and merges identical target states by adding their integer multiplicities.
Because every column mask is equally likely, the C++, Python, and Java implementations count boards rather than carrying fractions at each step. Only at the very end do they divide by \(2^{WH}\). The Python and Java implementations use the same exact underlying solver as the C++ implementation, so all three languages follow identical transitions and produce the same final value.
The implementation also uses horizontal reflection on the penultimate layer: mirror-image masks contribute equally to the final expectation, so non-symmetric representatives can be counted once with multiplicity \(2\). This reduces the amount of final work without changing the exact result.
Let \(P\) be the total number of canonical frontier partitions across all column masks, and let \(S_c\) be the number of reachable compressed states after \(c\) columns. Precomputing mask-to-mask contact information costs \(O(4^W\cdot W)\), and building the partition-transition tables costs \(O(P\cdot 2^W)\).
The main dynamic program processes each reachable state against each possible next-column mask, so its time complexity is
$$O\!\left(\sum_{c=0}^{H-1} 2^W S_c\right).$$
The memory usage is
$$O(S_c+P\cdot 2^W)$$
for the active DP layers and the precomputed transition data. For the \(7\times 7\) instance this is practical, while direct enumeration of all \(2^{49}\) boards is not.
Wir betrachten ein zufälliges binäres \(W\times H\)-Gitter; im Project-Euler-Fall ist \(W=H=7\). Jede Zelle ist unabhängig mit Wahrscheinlichkeit \(1/2\) besetzt, und besetzte Zellen sind über 4-Nachbarschaft verbunden. Bezeichnet \(L(B)\) die Größe der größten zusammenhängenden besetzten Komponente eines Gitters \(B\), so ist die gesuchte Größe der exakte Erwartungswert \(\mathbb E[L(B)]\).
Eine Brute-Force-Suche müsste alle \(2^{WH}\) Gitter prüfen und ist für \(7\times 7\) unbrauchbar. Die Lösung verarbeitet daher die Spalten nacheinander und speichert nur die Informationen, die zukünftiges Wachstum noch beeinflussen können.
Sei
$$\Omega_{W,H}=\{0,1\}^{W\times H}.$$
Für jedes Gitter \(B\in\Omega_{W,H}\) sei \(\mathcal C(B)\) die Menge seiner besetzten 4-zusammenhängenden Komponenten, und wir definieren
$$L(B)=\max_{C\in\mathcal C(B)} \lvert C\rvert,$$
wobei im leeren Fall \(L(B)=0\) gesetzt wird. Da alle Gitter gleich wahrscheinlich sind, gilt
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{B\in\Omega_{W,H}} L(B).$$
Die Aufgabe besteht also darin, die größte Komponente über alle Gitter exakt aufzusummieren und erst am Ende durch \(2^{WH}\) zu teilen.
Angenommen, die ersten \(c\) Spalten sind bereits verarbeitet. Jede zusammenhängende Komponente, die Spalte \(c\) nicht berührt, kann nie wieder wachsen, denn alle späteren Zellen liegen strikt rechts davon. Für abgeschlossene Komponenten genügt deshalb eine einzige Zahl: die bisher größte abgeschlossene Größe.
Betrachte nun Spalte \(c\). Ihre besetzten Zellen zerfallen in vertikale Läufe, etwa \(11100 11\mapsto (111)\) und \((11)\). Diese Läufe seien \(R_1,\dots,R_t\). Zwei verschiedene Läufe derselben Spalte können bereits zur gleichen globalen Komponente gehören, weil frühere Spalten sie um eine Lücke herum verbinden können. Deshalb reicht die Besetzungsmaske allein nicht aus; wir müssen zusätzlich wissen, welche Läufe zusammengehören.
Der Zustand lässt sich also schreiben als
$$\sigma=(b,\Pi,a_1,\dots,a_r),$$
wobei:
Dabei bezeichnet \(b\) die Größe der bisher größten abgeschlossenen Komponente.
\(\Pi\) eine Partition der Läufe \(R_1,\dots,R_t\) ist, deren Blöcke genau die offenen Frontier-Komponenten darstellen,
Für \(1\le j\le r\) bezeichnet \(a_j\) die Gesamtgröße der \(j\)-ten offenen Komponente.
Mehr Information ist nicht nötig, denn zukünftige Spalten können mit dem bereits verarbeiteten Bereich nur über diese offenen Komponenten interagieren.
Sei die nächste Spalte die Bitmaske \(m\in\{0,1\}^W\). Ihre besetzten Zellen zerfallen ebenfalls in vertikale Läufe \(S_1,\dots,S_u\).
Eine alte offene Komponente berührt die neue Spalte genau in den Zeilen, in denen beide benachbarten Spalten besetzt sind. Sobald eine Zelle eines Laufs \(S_k\) berührt wird, gehört der ganze Lauf zum gleichen neuen Zusammenhang, weil die Zellen innerhalb eines vertikalen Laufs bereits in der neuen Spalte verbunden sind.
Daraus folgen drei Fälle:
Erstens kann eine alte offene Komponente überhaupt keinen Kontakt zur neuen Spalte haben. Dann ist sie endgültig abgeschlossen und kann nur noch den besten abgeschlossenen Wert aktualisieren.
Zweitens kann eine alte Komponente einen oder mehrere neue Läufe berühren. Dann bleibt sie offen und ihre Größe wächst um die Zahl der neu angefügten besetzten Zellen.
Drittens können mehrere alte Komponenten denselben Lauf berühren oder Läufe, die innerhalb der neuen Spalte miteinander verbunden werden. Dann verschmelzen diese alten Komponenten zu einer einzigen neuen offenen Komponente.
Ist \(\mathcal D\) die Menge der alten offenen Komponenten ohne Kontakt, so gilt
$$b'=\max\!\Bigl(b,\max_{j\in\mathcal D} a_j\Bigr).$$
Für jede neue offene Komponente \(T\) sei \(\mathcal A(T)\) die Menge der alten Komponenten, die in \(T\) aufgehen. Dann ist ihre neue Größe
$$a'(T)=\lvert T\rvert+\sum_{j\in\mathcal A(T)} a_j,$$
wobei \(\lvert T\rvert\) nur die in der neu angehängten Spalte hinzugekommenen besetzten Zellen zählt.
Innerhalb einer einzelnen Spalte ist die Konnektivität vollständig durch die vertikalen Läufe beschrieben. Zellen im selben Lauf sind automatisch verbunden, Zellen in verschiedenen Läufen sind innerhalb dieser Spalte getrennt. Die einzige fehlende Information ist also, ob zwei verschiedene Läufe über frühere Spalten bereits miteinander verbunden wurden. Genau das speichert die Partition \(\Pi\).
Diese Kompression ist stark, weil eine Breite von \(7\) höchstens vier besetzte Läufe in einer Spalte erlaubt, etwa bei \(1010101\). Zu jeder Spaltenmaske gibt es daher nur endlich viele mögliche Partitionen dieser Läufe, und alle können einmalig vorab erzeugt werden. Das dynamische Programm arbeitet dann mit kanonischen Frontier-Mustern statt mit vollständigen Teilgittern.
Nehmen wir die Breite \(W=3\). Sei die erste verarbeitete Spalte \(101\). Dann gibt es zwei Läufe:
$$R_1=\{1\},\qquad R_2=\{3\}.$$
Da es keine frühere Spalte gibt, sind das zwei getrennte offene Komponenten der Größen \(1\) und \(1\). Der Zustand lautet
$$\sigma=\bigl(0,\{\{R_1\},\{R_2\}\},1,1\bigr).$$
Hängen wir nun die Spalte \(111\) an. In ihr gibt es genau einen Lauf
$$S_1=\{1,2,3\}.$$
Die alte Komponente in Zeile \(1\) berührt \(S_1\), und die alte Komponente in Zeile \(3\) berührt \(S_1\) ebenfalls. Weil beide Kontakte im selben vertikalen Lauf liegen, wird der ganze Lauf zu einer zusammenhängenden Brücke, also verschmelzen die beiden alten Komponenten. Die neue offene Komponente hat Größe
$$1+1+3=5.$$
Damit ist der neue Zustand
$$\sigma'=\bigl(0,\{\{S_1\}\},5\bigr).$$
Wäre die folgende Spalte \(000\), dann verlöre diese Komponente ihren Frontier-Kontakt, würde dauerhaft abgeschlossen und den abgeschlossenen Maximalwert auf \(5\) setzen.
Sei \(w_c(\sigma)\) die Anzahl der \(c\)-spaltigen Präfixe, die den Zustand \(\sigma\) erzeugen. Dann liefert die oben definierte Übergangsregel
$$w_{c+1}(\sigma')=\sum_{\sigma}\sum_{\substack{m\in\{0,1\}^W\\ T_m(\sigma)=\sigma'}} w_c(\sigma),$$
wobei \(T_m\) das durch die nächste Spaltenmaske \(m\) induzierte deterministische Update bezeichnet. Das dynamische Programm speichert diese Gewichte als exakte ganze Zahlen und nicht als Fließkommazahlen.
Nach allen \(H\) Spalten trägt jeder Endzustand \(\sigma=(b,\Pi,a_1,\dots,a_r)\) den Wert
$$\operatorname{score}(\sigma)=\max(b,a_1,\dots,a_r)$$
zur größten zusammenhängenden Fläche aller durch diesen Zustand repräsentierten Gitter bei. Also gilt
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{\sigma\in\mathcal T} w_H(\sigma)\operatorname{score}(\sigma),$$
wobei \(\mathcal T\) die Menge aller Endzustände ist. Genau diese Größe berechnet die Implementierung.
Die Implementierung enumeriert zuerst alle möglichen Spaltenmasken, zerlegt jede Maske in ihre vertikalen Läufe und erzeugt alle kanonischen Partitionen dieser Läufe. Zusätzlich wird vorab berechnet, wie ein altes Frontier-Muster mit einer neuen Spalte interagiert: welche alten Komponenten überleben, welche verschmelzen, welche verschwinden und wie viele neue besetzte Zellen in jede überlebende Komponente aufgenommen werden.
Danach läuft das dynamische Programm spaltenweise vorwärts. Ein Zustand wird durch die Frontier-Partition, die akkumulierten Größen der offenen Komponenten und den besten bisher abgeschlossenen Wert beschrieben. Beim Anhängen einer neuen Spalte wendet die Implementierung die vorbereitete Konnektivitätsregel an, erzeugt den Folgezustand und verschmilzt identische Zielzustände durch Addition ihrer ganzzahligen Multiplizitäten.
Weil jede Spaltenmaske gleich wahrscheinlich ist, zählen die C++-, Python- und Java-Implementierungen konkrete Gitter statt unterwegs mit Brüchen zu rechnen. Erst ganz am Ende wird durch \(2^{WH}\) geteilt. Die Python- und Java-Implementierungen verwenden dabei denselben exakten Solver wie die C++-Implementierung, sodass alle drei Sprachen identische Übergänge, Zählungen und Ergebnisse haben.
Zusätzlich nutzt die Implementierung auf der vorletzten Schicht die horizontale Spiegelung: Spiegelbildliche Masken tragen gleich viel zum Enderwartungswert bei, daher kann man nichtsymmetrische Repräsentanten einmal mit Multiplizität \(2\) zählen. Das reduziert die Endarbeit, ohne das exakte Resultat zu verändern.
Sei \(P\) die Gesamtzahl der kanonischen Frontier-Partitionen über alle Spaltenmasken und \(S_c\) die Anzahl erreichbarer komprimierter Zustände nach \(c\) Spalten. Die Vorberechnung der Masken-Kontakte kostet \(O(4^W\cdot W)\), und der Aufbau der Partitions-Übergangstabellen kostet \(O(P\cdot 2^W)\).
Das eigentliche dynamische Programm verarbeitet jeden erreichbaren Zustand gegen jede mögliche nächste Spaltenmaske, also
$$O\!\left(\sum_{c=0}^{H-1} 2^W S_c\right).$$
Der Speicherbedarf beträgt
$$O(S_c+P\cdot 2^W)$$
für die aktiven DP-Schichten und die vorberechneten Übergangsdaten. Für den \(7\times 7\)-Fall ist das praktikabel, während die direkte Enumeration aller \(2^{49}\) Gitter unpraktikabel wäre.
Rastgele bir \(W\times H\) ikili ızgara düşünülür; Project Euler örneğinde \(W=H=7\). Her hücre bağımsız olarak \(1/2\) olasılıkla doludur ve dolu hücreler 4-komşuluk ile bağlı kabul edilir. Bir tahtanın en büyük dolu bağlı bileşeninin büyüklüğü \(L(B)\) ile gösterilirse, istenen şey \(\mathbb E[L(B)]\) değerinin tam olarak hesaplanmasıdır.
Doğrudan yaklaşım tüm \(2^{WH}\) tahtayı dolaşmayı gerektirir; bu da \(7\times 7\) için mümkün değildir. Çözüm bunun yerine ızgarayı sütun sütun işler ve gelecekte büyümeyi etkileyebilecek bilgiyi sıkıştırılmış bir sınır durumunda tutar.
Şöyle tanımlayalım:
$$\Omega_{W,H}=\{0,1\}^{W\times H}.$$
Her \(B\in\Omega_{W,H}\) tahtası için \(\mathcal C(B)\) dolu 4-bağlı bileşenlerin kümesi olsun ve
$$L(B)=\max_{C\in\mathcal C(B)} \lvert C\rvert$$
olsun; tahta tamamen boşsa \(L(B)=0\) alınır. Tüm tahtalar eşit olasılıkla geldiği için
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{B\in\Omega_{W,H}} L(B).$$
Dolayısıyla asıl amaç, bütün tahtalar üzerindeki en büyük bağlı alan büyüklüklerini tam olarak toplayıp sonucu \(2^{WH}\)'ye bölmektir.
İlk \(c\) sütunun işlendiğini varsayalım. Eğer bir bağlı bileşen \(c\). sütuna değmiyorsa artık bir daha büyüyemez; çünkü ileride eklenecek tüm hücreler bunun sağında kalacaktır. Bu yüzden kapanmış bileşenler için tek gereken bilgi, şimdiye kadarki en büyük kapanmış bileşen boyutudur.
Şimdi \(c\). sütuna bakalım. Bu sütundaki dolu hücreler, örneğin \(11100 11\mapsto (111)\) ve \((11)\) gibi dikey koşulara ayrılır. Bunları \(R_1,\dots,R_t\) ile gösterelim. Aynı sütundaki iki farklı koşu, önceki sütunlar üzerinden dolanarak aynı küresel bileşene bağlı olabilir. Bu nedenle yalnızca doluluk maskesini bilmek yetmez; hangi koşuların aynı açık bileşene ait olduğunu da bilmek gerekir.
Bu yüzden durum şu biçimde yazılır:
$$\sigma=(b,\Pi,a_1,\dots,a_r),$$
burada:
Burada \(b\), şimdiye kadar kapanmış en büyük bileşen boyutunu gösterir.
\(\Pi\), \(R_1,\dots,R_t\) koşularının bir bölümlemesidir; her blok sınırda hâlâ açık olan tek bir bileşeni temsil eder,
\(1\le j\le r\) için \(a_j\), \(j\). açık bileşenin toplam alanını gösterir.
Bu bilgi yeterlidir; çünkü gelecekte eklenecek sütunlar işlenmiş bölgeyle sadece bu açık bileşenler üzerinden etkileşebilir.
Sıradaki sütun maskesi \(m\in\{0,1\}^W\) olsun. Bu sütunun dolu hücreleri de \(S_1,\dots,S_u\) dikey koşularına ayrılır.
Eski bir açık bileşen, yeni sütuna ancak iki komşu sütunda aynı satırda dolu hücre varsa temas eder. Yeni sütundaki bir koşunun herhangi bir hücresine temas edilirse, o koşunun tamamı aynı yeni bağlı parçanın içine girer; çünkü aynı dikey koşudaki hücreler zaten birbirine bağlıdır.
Böylece üç olasılık ortaya çıkar:
Birincisi, eski açık bileşen yeni sütunda hiçbir hücreye temas etmeyebilir. Bu durumda kalıcı olarak kapanır ve yalnızca kapanmış maksimumu güncelleyebilir.
İkincisi, eski bir bileşen yeni sütunda bir veya birkaç koşuya temas edebilir. O zaman açık kalır ve boyutu yeni eklenen dolu hücre sayısı kadar artar.
Üçüncüsü, birkaç eski bileşen aynı koşuya ya da yeni sütun içinde birbirine bağlanan koşulara temas edebilir. Bu durumda bu eski bileşenler tek bir yeni açık bileşende birleşir.
Teması kesilen eski açık bileşenlerin kümesi \(\mathcal D\) ise
$$b'=\max\!\Bigl(b,\max_{j\in\mathcal D} a_j\Bigr)$$
olur. Her yeni açık bileşen \(T\) için, ona taşınan eski bileşenlerin kümesi \(\mathcal A(T)\) ile gösterilsin. O zaman yeni boyut
$$a'(T)=\lvert T\rvert+\sum_{j\in\mathcal A(T)} a_j$$
şeklindedir; burada \(\lvert T\rvert\) sadece yeni eklenen sütundaki dolu hücreleri sayar.
Tek bir sütun içinde bağlantı yapısı tamamen dikey koşular tarafından belirlenir. Aynı koşudaki hücreler zaten bağlıdır; farklı koşulardaki hücreler ise o sütunun içinde ayrıdır. Eksik olan tek bilgi, farklı koşuların önceki sütunlar üzerinden zaten bağlanıp bağlanmadığıdır. Bunu da tam olarak \(\Pi\) bölümlemesi taşır.
Bu sıkıştırma çok etkilidir; çünkü genişliği \(7\) olan bir sütunda en fazla dört dolu koşu olabilir, örneğin \(1010101\). Dolayısıyla her sütun maskesi için olası koşu bölümlemelerinin sayısı sonludur ve bunların tamamı önceden üretilebilir. Dinamik program böylece tüm kısmi tahtalar yerine kanonik sınır desenleri üzerinde çalışır.
Genişlik \(W=3\) olsun. İlk işlenen sütun \(101\) ise iki koşu vardır:
$$R_1=\{1\},\qquad R_2=\{3\}.$$
Öncesinde sütun olmadığı için bunlar büyüklükleri \(1\) ve \(1\) olan iki ayrı açık bileşendir. Durum
$$\sigma=\bigl(0,\{\{R_1\},\{R_2\}\},1,1\bigr)$$
şeklindedir. Şimdi yanına \(111\) sütununu ekleyelim. Yeni sütunda tek bir koşu vardır:
$$S_1=\{1,2,3\}.$$
Eski bileşenlerden biri \(1\). satırda, diğeri \(3\). satırda bu koşuya temas eder. Bu temaslar aynı dikey koşu içinde olduğu için ortadaki hücre de köprü görevi görür ve iki eski bileşen birleşir. Yeni açık bileşenin boyutu
$$1+1+3=5$$
olur. Dolayısıyla yeni durum
$$\sigma'=\bigl(0,\{\{S_1\}\},5\bigr)$$
şeklindedir. Bir sonraki sütun \(000\) olsaydı bu boyutu \(5\) olan bileşen kapanacak ve kapanmış maksimum değer \(5\)'e çıkacaktı.
\(w_c(\sigma)\), \(\sigma\) durumunu üreten \(c\) sütunlu ön-ek sayısı olsun. Yukarıdaki geçiş kuralı
$$w_{c+1}(\sigma')=\sum_{\sigma}\sum_{\substack{m\in\{0,1\}^W\\ T_m(\sigma)=\sigma'}} w_c(\sigma)$$
eşitliğini verir; burada \(T_m\), sonraki sütun maskesi \(m\) ile oluşan deterministik güncellemedir. Dinamik program bu ağırlıkları kayan noktalı sayı değil, tam sayı olarak tutar.
Tüm \(H\) sütun işlendiğinde, \(\sigma=(b,\Pi,a_1,\dots,a_r)\) biçimindeki her terminal durum
$$\operatorname{score}(\sigma)=\max(b,a_1,\dots,a_r)$$
katkısını yapar. Böylece
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{\sigma\in\mathcal T} w_H(\sigma)\operatorname{score}(\sigma)$$
elde edilir; burada \(\mathcal T\) terminal durumlar kümesidir. Uygulamanın hesapladığı nicelik tam olarak budur.
Uygulama önce tüm olası sütun maskelerini çıkarır, her maskeyi dikey koşularına ayırır ve bu koşuların tüm kanonik bölümlemelerini önceden oluşturur. Ayrıca eski bir sınır deseninin yeni bir sütunla nasıl etkileşeceği de önceden hesaplanır: hangi eski bileşenlerin yaşayacağı, hangilerinin birleşeceği, hangilerinin kapanacağı ve her yaşayan bileşene yeni sütundan kaç dolu hücre ekleneceği belirlenir.
Dinamik program daha sonra sütunları soldan sağa işler. Her durum, sınır bölümlemesi, açık bileşenlerin birikmiş alanları ve şimdiye kadarki en büyük kapanmış bileşen değeri ile anahtarlanır. Yeni bir sütun eklendiğinde uygulama önceden hesaplanmış bağlantı kuralını uygular, hedef durumu üretir ve aynı hedefe giden durumların tam sayı ağırlıklarını toplayarak birleştirir.
Her sütun maskesi eşit olasılıkla geldiği için C++, Python ve Java implementasyonları ara adımlarda kesir taşımak yerine tahta sayılarını tutar. Sadece en sonda \(2^{WH}\)'ye bölünür. Python ve Java implementasyonları da C++ implementasyonuyla aynı tam çözücüyü kullandığından üç dilin geçişleri, sayımları ve son değeri aynıdır.
Uygulama ayrıca sondan bir önceki katmanda yatay ayna simetrisini kullanır: Aynadaki sütun maskeleri beklenen değere eşit katkı verdiği için simetrik olmayan temsilci bir kez hesaplanıp ağırlığı \(2\) ile çarpılabilir. Bu, sonucu değiştirmeden son aşamadaki işi azaltır.
\(P\), tüm sütun maskeleri üzerindeki kanonik sınır bölümleme sayısı; \(S_c\) ise \(c\) sütun sonunda ulaşılabilen sıkıştırılmış durum sayısı olsun. Maske-maske temas bilgisinin ön hesaplaması \(O(4^W\cdot W)\), bölümleme-geçiş tablolarının kurulması ise \(O(P\cdot 2^W)\) zaman alır.
Ana dinamik program, erişilebilir her durumu her olası sonraki sütun maskesiyle eşleştirir; dolayısıyla zaman maliyeti
$$O\!\left(\sum_{c=0}^{H-1} 2^W S_c\right)$$
olur. Bellek kullanımı ise etkin DP katmanları ve önceden hesaplanmış geçiş verileri için
$$O(S_c+P\cdot 2^W)$$
seviyesindedir. \(7\times 7\) örneği için bu yöntem uygulanabilirken, tüm \(2^{49}\) tahtanın doğrudan taranması uygulanabilir değildir.
Se considera una rejilla binaria aleatoria de tamaño \(W\times H\); en la instancia de Project Euler se usa \(W=H=7\). Cada celda está ocupada de manera independiente con probabilidad \(1/2\), y las celdas ocupadas se conectan mediante vecindad de 4 direcciones. Si \(L(B)\) denota el tamaño de la mayor componente conectada ocupada del tablero \(B\), el objetivo es calcular exactamente \(\mathbb E[L(B)]\).
Un recorrido exhaustivo tendría que inspeccionar los \(2^{WH}\) tableros posibles, algo inviable para \(7\times 7\). La solución correcta procesa las columnas una por una y conserva solamente la información que todavía puede afectar al crecimiento futuro.
Definimos
$$\Omega_{W,H}=\{0,1\}^{W\times H}.$$
Para cada tablero \(B\in\Omega_{W,H}\), sea \(\mathcal C(B)\) el conjunto de sus componentes ocupadas 4-conectadas, y definimos
$$L(B)=\max_{C\in\mathcal C(B)} \lvert C\rvert,$$
tomando \(L(B)=0\) cuando no hay celdas ocupadas. Como todos los tableros tienen la misma probabilidad,
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{B\in\Omega_{W,H}} L(B).$$
Por tanto, el problema consiste en sumar exactamente el tamaño de la mayor componente sobre todos los tableros y dividir al final por \(2^{WH}\).
Supongamos que ya se han procesado las primeras \(c\) columnas. Cualquier componente conectada que no toque la columna \(c\) ya no podrá crecer, porque todas las celdas futuras estarán estrictamente a su derecha. Por eso, de las componentes cerradas solo hace falta conservar un número: el mayor tamaño cerrado visto hasta ese momento.
Ahora miremos la columna \(c\). Sus celdas ocupadas se descomponen en tramos verticales, por ejemplo \(11100 11\mapsto (111)\) y \((11)\). Llamemos \(R_1,\dots,R_t\) a esos tramos. Dos tramos distintos de la misma columna pueden pertenecer ya a la misma componente global, porque columnas anteriores pueden conectarlos rodeando un hueco. Por eso no basta con la máscara de ocupación; también hay que saber qué tramos están agrupados.
El estado se puede escribir como
$$\sigma=(b,\Pi,a_1,\dots,a_r),$$
donde:
Aquí \(b\) representa el mayor tamaño entre las componentes ya cerradas.
\(\Pi\) es una partición de los tramos \(R_1,\dots,R_t\), y cada bloque de \(\Pi\) representa una componente abierta que toca la frontera,
Para \(1\le j\le r\), \(a_j\) representa el tamaño total de la \(j\)-ésima componente abierta.
Esto es suficiente, porque las columnas futuras solo pueden interactuar con la parte ya procesada a través de esas componentes abiertas.
Sea \(m\in\{0,1\}^W\) la máscara de la columna siguiente. Sus celdas ocupadas también se descomponen en tramos verticales \(S_1,\dots,S_u\).
Una componente abierta antigua toca la columna nueva exactamente en las filas en las que ambas columnas adyacentes tienen una celda ocupada. En cuanto una celda de un tramo \(S_k\) queda tocada, todo el tramo pasa a formar parte de la misma pieza conectada nueva, porque las celdas dentro de un mismo tramo vertical ya están unidas dentro de la columna nueva.
Eso produce tres situaciones:
Primero, una componente abierta antigua puede no tocar nada en la columna nueva. Entonces queda cerrada para siempre y solo puede actualizar el mejor valor cerrado.
Segundo, una componente antigua puede tocar uno o varios tramos nuevos. Entonces sobrevive y su tamaño crece con el número de nuevas celdas ocupadas que se le adhieren.
Tercero, varias componentes antiguas pueden tocar el mismo tramo, o tramos que quedan unidos dentro de la columna nueva. Entonces esas componentes antiguas se fusionan en una sola componente abierta nueva.
Si \(\mathcal D\) es el conjunto de componentes abiertas antiguas que desaparecen, entonces
$$b'=\max\!\Bigl(b,\max_{j\in\mathcal D} a_j\Bigr).$$
Para cada nueva componente abierta \(T\), sea \(\mathcal A(T)\) el conjunto de componentes antiguas que desembocan en ella. Su nuevo tamaño es
$$a'(T)=\lvert T\rvert+\sum_{j\in\mathcal A(T)} a_j,$$
donde \(\lvert T\rvert\) cuenta únicamente las celdas ocupadas de la columna recién añadida.
Dentro de una sola columna, la conectividad queda determinada por los tramos verticales. Las celdas del mismo tramo están conectadas automáticamente, mientras que las celdas de tramos distintos están separadas dentro de esa columna. La única información que falta es si dos tramos distintos ya habían quedado unidos mediante columnas anteriores. Eso es exactamente lo que almacena la partición \(\Pi\).
Esta compresión es muy efectiva porque una columna de anchura \(7\) tiene como máximo cuatro tramos ocupados, por ejemplo \(1010101\). Así, para cada máscara de columna solo hay un número finito de particiones posibles, y todas pueden precomputarse. El programa dinámico trabaja entonces con patrones de frontera canónicos, no con tableros parciales completos.
Tomemos \(W=3\). Si la primera columna procesada es \(101\), aparecen dos tramos:
$$R_1=\{1\},\qquad R_2=\{3\}.$$
Como no existe una columna anterior, son dos componentes abiertas separadas de tamaños \(1\) y \(1\). El estado es
$$\sigma=\bigl(0,\{\{R_1\},\{R_2\}\},1,1\bigr).$$
Ahora añadimos la columna \(111\). En la columna nueva hay un único tramo
$$S_1=\{1,2,3\}.$$
La componente antigua de la fila \(1\) toca \(S_1\), y la de la fila \(3\) también toca \(S_1\). Como ambos contactos están dentro del mismo tramo vertical, ese tramo completo actúa como puente y las dos componentes antiguas se fusionan. La nueva componente abierta tiene tamaño
$$1+1+3=5.$$
Por tanto, el nuevo estado es
$$\sigma'=\bigl(0,\{\{S_1\}\},5\bigr).$$
Si la columna siguiente fuera \(000\), esa componente de tamaño \(5\) perdería el contacto con la frontera, se cerraría definitivamente y haría que el máximo cerrado pasara a ser \(5\).
Sea \(w_c(\sigma)\) el número de prefijos de \(c\) columnas que producen el estado \(\sigma\). La regla de transición anterior da
$$w_{c+1}(\sigma')=\sum_{\sigma}\sum_{\substack{m\in\{0,1\}^W\\ T_m(\sigma)=\sigma'}} w_c(\sigma),$$
donde \(T_m\) es la actualización determinista inducida por la máscara \(m\) de la siguiente columna. El programa dinámico almacena estos pesos como enteros exactos y no como probabilidades en coma flotante.
Tras procesar todas las \(H\) columnas, cada estado terminal \(\sigma=(b,\Pi,a_1,\dots,a_r)\) aporta
$$\operatorname{score}(\sigma)=\max(b,a_1,\dots,a_r)$$
al tamaño de la mayor área conectada de cada tablero representado por ese estado. En consecuencia,
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{\sigma\in\mathcal T} w_H(\sigma)\operatorname{score}(\sigma),$$
donde \(\mathcal T\) es el conjunto de estados terminales. Esa es exactamente la magnitud que evalúa la implementación.
La implementación enumera primero todas las máscaras de columna posibles, descompone cada una en tramos verticales y precomputa las particiones canónicas de esos tramos. También precomputa cómo interactúa un patrón de frontera antiguo con una columna nueva: qué componentes antiguas sobreviven, cuáles se fusionan, cuáles desaparecen y cuántas celdas ocupadas nuevas se absorben en cada componente superviviente.
Después, el programa dinámico avanza columna a columna. Un estado queda determinado por la partición de frontera, los tamaños acumulados de las componentes abiertas y el mejor tamaño cerrado visto hasta ese momento. Al añadir una nueva columna, la implementación aplica la regla de conectividad precomputada, genera el estado de salida y fusiona estados destino idénticos sumando sus multiplicidades enteras.
Como cada máscara de columna es equiprobable, las implementaciones en C++, Python y Java cuentan tableros en lugar de propagar fracciones en cada paso. Solo al final dividen por \(2^{WH}\). Las versiones en Python y Java usan exactamente el mismo solucionador subyacente que la implementación en C++, de modo que las tres lenguas comparten las mismas transiciones, los mismos conteos y el mismo resultado final.
La implementación también aprovecha la reflexión horizontal en la penúltima capa: las máscaras espejo aportan la misma contribución a la esperanza final, así que un representante no simétrico puede contarse una sola vez con multiplicidad \(2\). Eso reduce el trabajo final sin cambiar el resultado exacto.
Sea \(P\) el número total de particiones canónicas de frontera sobre todas las máscaras de columna, y sea \(S_c\) el número de estados comprimidos alcanzables después de \(c\) columnas. La precomputación del contacto máscara-a-máscara cuesta \(O(4^W\cdot W)\), y construir las tablas de transición por partición cuesta \(O(P\cdot 2^W)\).
El programa dinámico principal procesa cada estado alcanzable frente a cada máscara posible de la siguiente columna, así que el tiempo total es
$$O\!\left(\sum_{c=0}^{H-1} 2^W S_c\right).$$
La memoria necesaria es
$$O(S_c+P\cdot 2^W)$$
para las capas activas del DP y los datos de transición precomputados. Para el caso \(7\times 7\) esto es manejable, mientras que enumerar directamente los \(2^{49}\) tableros no lo es.
我们考虑一个随机的 \(W\times H\) 二值网格；在 Project Euler 的题目实例中，\(W=H=7\)。每个格子独立地以概率 \(1/2\) 被占据，连通关系采用上下左右四联通。若 \(L(B)\) 表示棋盘 \(B\) 上最大占据连通块的大小，那么题目要求的是 \(\mathbb E[L(B)]\) 的精确值。
直接暴力需要检查全部 \(2^{WH}\) 个棋盘，对 \(7\times 7\) 来说完全不可行。可行方法是按列扫描整个网格，并且只保留那些仍然可能影响未来扩展的信息。
定义
$$\Omega_{W,H}=\{0,1\}^{W\times H}.$$
对每个棋盘 \(B\in\Omega_{W,H}\)，记 \(\mathcal C(B)\) 为其中所有占据的四联通分量的集合，并定义
$$L(B)=\max_{C\in\mathcal C(B)} \lvert C\rvert,$$
若棋盘完全为空，则约定 \(L(B)=0\)。由于每个棋盘出现的概率都相同，因此
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{B\in\Omega_{W,H}} L(B).$$
这说明问题本质上是：把所有棋盘上的“最大连通块大小”精确求和，然后再除以 \(2^{WH}\)。
设前 \(c\) 列已经处理完。若某个连通块不再接触第 \(c\) 列，那么它以后不可能继续增长，因为之后新增的格子全部位于它的右侧。因此，对已经封闭的连通块，我们只需要保留一个数：到目前为止封闭连通块中的最大大小。
接着观察第 \(c\) 列。该列中的占据格子会分解成若干个竖直连续段，例如 \(11100 11\mapsto (111)\) 和 \((11)\)。把这些连续段记为 \(R_1,\dots,R_t\)。同一列中的两个不同连续段，虽然在当前列内彼此分开，但它们仍然可能通过更早的列绕过空隙而属于同一个全局连通块。因此，只记录这一列的占据掩码还不够，还必须知道这些连续段之间如何分组。
于是一个状态可以写成
$$\sigma=(b,\Pi,a_1,\dots,a_r),$$
其中：
这里的 \(b\) 表示到目前为止所有已封闭连通块中的最大大小。
\(\Pi\) 是连续段 \(R_1,\dots,R_t\) 的一个划分；划分中的每个块对应一个仍然接触边界的开放连通块，
当 \(1\le j\le r\) 时，\(a_j\) 表示第 \(j\) 个开放连通块的总大小。
这样的信息已经足够，因为未来各列与已处理区域的交互只能通过这些仍然开放的连通块发生。
设下一列的掩码为 \(m\in\{0,1\}^W\)。新列中的占据格子也会分解为若干竖直连续段 \(S_1,\dots,S_u\)。
旧的某个开放连通块与新列接触，当且仅当相邻两列在某一行上同时有占据格子。一旦新列中某个连续段 \(S_k\) 的任意一个格子被接触到，那么这个连续段中的全部格子都属于同一个新的连通部分，因为它们在该列内部已经通过竖直方向连通。
因此会出现三种情况：
第一，某个旧的开放连通块在新列中完全没有接触点。这样它就永久封闭，只可能拿来更新“已封闭最大值”。
第二，某个旧连通块接触到新列中的一个或多个连续段。这样它仍保持开放，并且它的大小会增加与之相连的新占据格子数。
第三，若多个旧连通块接触到同一个连续段，或者接触到在新列内部又彼此连通的连续段，那么这些旧连通块会合并成一个新的开放连通块。
若 \(\mathcal D\) 表示所有失去接触而关闭的旧开放连通块，则
$$b'=\max\!\Bigl(b,\max_{j\in\mathcal D} a_j\Bigr).$$
对每个新的开放连通块 \(T\)，设 \(\mathcal A(T)\) 为流入它的旧连通块集合，则它的新大小为
$$a'(T)=\lvert T\rvert+\sum_{j\in\mathcal A(T)} a_j,$$
其中 \(\lvert T\rvert\) 只计算刚刚附加的这一列中的占据格子数量。
在单独一列内部，连通性完全由竖直连续段决定。同一连续段里的格子天然连通，不同连续段里的格子在该列内天然分离。唯一额外需要知道的信息，是不同连续段是否已经通过更早的列连接到了一起。这正是划分 \(\Pi\) 所表达的内容。
这种压缩之所以有效，是因为宽度为 \(7\) 的一列最多只会出现四个占据连续段，例如 \(1010101\)。因此，对每种列掩码来说，连续段的可能划分数量都是有限且不大的，可以预先全部列举出来。动态规划于是处理的是规范化的边界模式，而不是完整的部分棋盘。
取 \(W=3\)。假设第一列是 \(101\)，那么会出现两个连续段：
$$R_1=\{1\},\qquad R_2=\{3\}.$$
由于没有更早的列，这两个连续段就是两个彼此独立的开放连通块，大小分别为 \(1\) 和 \(1\)。此时状态为
$$\sigma=\bigl(0,\{\{R_1\},\{R_2\}\},1,1\bigr).$$
现在附加第二列 \(111\)。新列只有一个连续段
$$S_1=\{1,2,3\}.$$
原来位于第 \(1\) 行的连通块会接触到 \(S_1\)，位于第 \(3\) 行的连通块也会接触到 \(S_1\)。由于这些接触都发生在同一个竖直连续段里，所以整个连续段都会成为一座桥梁，从而把两个旧连通块合并起来。新的开放连通块大小就是
$$1+1+3=5.$$
因此新状态变成
$$\sigma'=\bigl(0,\{\{S_1\}\},5\bigr).$$
如果下一列是 \(000\)，那么这个大小为 \(5\) 的连通块会失去与边界的接触，从而永久封闭，并把“已封闭最大值”更新为 \(5\)。
记 \(w_c(\sigma)\) 为能够产生状态 \(\sigma\) 的 \(c\) 列前缀个数。由上面的转移规则可得
$$w_{c+1}(\sigma')=\sum_{\sigma}\sum_{\substack{m\in\{0,1\}^W\\ T_m(\sigma)=\sigma'}} w_c(\sigma),$$
其中 \(T_m\) 表示由下一列掩码 \(m\) 诱导出的确定性更新。动态规划内部保存的是这些精确整数计数，而不是浮点概率。
在处理完全部 \(H\) 列之后，每个终止状态 \(\sigma=(b,\Pi,a_1,\dots,a_r)\) 对应的最大连通块大小是
$$\operatorname{score}(\sigma)=\max(b,a_1,\dots,a_r).$$
因此
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{\sigma\in\mathcal T} w_H(\sigma)\operatorname{score}(\sigma),$$
其中 \(\mathcal T\) 表示全部终止状态集合。这正是实现最终求出的量。
实现首先枚举所有可能的列掩码，把每种掩码分解成竖直连续段，并预先生成这些连续段的全部规范划分。同时，它还预计算旧边界模式与新列之间的交互方式：哪些旧连通块会继续存在，哪些会合并，哪些会消失，以及每个继续存在的连通块会吸收多少个新占据格子。
随后动态规划按列推进。每个状态由边界划分、开放连通块的累计大小以及目前为止最大的已封闭连通块大小共同决定。每加入一列，实现就应用对应的预计算连通规则，得到目标状态，并把所有相同目标状态的整数计数累加到一起。
由于每种列掩码的概率都相同，C++、Python 和 Java 实现都使用“棋盘个数”而不是逐步传播分数概率。只有在最后才除以 \(2^{WH}\)。Python 和 Java 版本使用与 C++ 实现完全相同的底层精确求解器，因此三种语言对应的是同一组转移、同一组计数和同一个最终结果。
实现还在倒数第二层利用了水平镜像对称：互为镜像的列掩码对最终期望的贡献相同，所以非自对称代表可以只计算一次，再乘上权重 \(2\)。这样可以减少最后阶段的工作量，同时不改变精确答案。
记 \(P\) 为所有列掩码对应的规范边界划分总数，记 \(S_c\) 为处理完 \(c\) 列后可达的压缩状态数。预计算掩码之间的接触闭包需要 \(O(4^W\cdot W)\) 时间，构造划分转移表需要 \(O(P\cdot 2^W)\) 时间。
主动态规划会把每个可达状态与每个可能的下一列掩码配对，因此总时间复杂度为
$$O\!\left(\sum_{c=0}^{H-1} 2^W S_c\right).$$
内存复杂度为
$$O(S_c+P\cdot 2^W),$$
其中包括当前活动的 DP 层以及预计算的转移数据。对于 \(7\times 7\) 的题目实例，这个规模是可处理的，而直接枚举全部 \(2^{49}\) 个棋盘则完全不可行。
Рассматривается случайная бинарная решётка размера \(W\times H\); в задаче Project Euler используется случай \(W=H=7\). Каждая клетка независимо занята с вероятностью \(1/2\), а связность определяется по 4-соседям. Если \(L(B)\) обозначает размер наибольшей занятой связной компоненты на доске \(B\), то требуется точно вычислить \(\mathbb E[L(B)]\).
Прямой перебор должен был бы проверить все \(2^{WH}\) досок, что для \(7\times 7\) нереально. Поэтому решение идёт по столбцам и хранит только ту информацию, которая ещё может повлиять на дальнейшее разрастание компонент.
Положим
$$\Omega_{W,H}=\{0,1\}^{W\times H}.$$
Для каждой доски \(B\in\Omega_{W,H}\) обозначим через \(\mathcal C(B)\) множество её занятых 4-связных компонент и определим
$$L(B)=\max_{C\in\mathcal C(B)} \lvert C\rvert,$$
причём для пустой доски считаем \(L(B)=0\). Поскольку все доски равновероятны, имеем
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{B\in\Omega_{W,H}} L(B).$$
Значит, задача сводится к точному суммированию размера наибольшей компоненты по всем доскам с последующим делением на \(2^{WH}\).
Предположим, что уже обработаны первые \(c\) столбцов. Любая связная компонента, которая не касается столбца \(c\), больше никогда не вырастет, потому что все будущие клетки лежат строго правее. Следовательно, от закрытых компонент нужно помнить только одно число: максимальный размер среди уже закрытых.
Теперь посмотрим на столбец \(c\). Его занятые клетки распадаются на вертикальные пробеги, например \(11100 11\mapsto (111)\) и \((11)\). Обозначим эти пробеги через \(R_1,\dots,R_t\). Два разных пробега в одном и том же столбце могут уже принадлежать одной глобальной компоненте, если более ранние столбцы связывают их в обход промежутка. Поэтому одной лишь маски занятости недостаточно: нужно знать, какие пробеги объединены между собой.
Состояние можно записать так:
$$\sigma=(b,\Pi,a_1,\dots,a_r),$$
где:
Здесь \(b\) обозначает максимальный размер среди уже закрытых компонент.
\(\Pi\) — разбиение пробегов \(R_1,\dots,R_t\), причём каждый блок этого разбиения соответствует одной открытой компоненте, касающейся фронтира,
Для \(1\le j\le r\) величина \(a_j\) обозначает полный размер \(j\)-й открытой компоненты.
Этого достаточно, потому что будущие столбцы могут взаимодействовать с уже обработанной частью только через эти открытые компоненты.
Пусть следующему столбцу соответствует маска \(m\in\{0,1\}^W\). Его занятые клетки также распадаются на вертикальные пробеги \(S_1,\dots,S_u\).
Старая открытая компонента касается нового столбца ровно в тех строках, где в обоих соседних столбцах стоят занятые клетки. Как только хотя бы одна клетка пробега \(S_k\) оказалась в контакте, весь этот пробег относится к одной и той же новой связной части, поскольку клетки внутри одного вертикального пробега уже соединены внутри нового столбца.
Отсюда возникают три сценария:
Во-первых, старая открытая компонента может вообще не соприкоснуться с новым столбцом. Тогда она навсегда закрывается и может только обновить лучший закрытый размер.
Во-вторых, одна старая компонента может коснуться одного или нескольких новых пробегов. Тогда она остаётся открытой, а её размер увеличивается на число присоединённых новых занятых клеток.
В-третьих, несколько старых компонент могут коснуться одного и того же пробега или пробегов, которые оказываются связанными внутри нового столбца. Тогда эти старые компоненты сливаются в одну новую открытую компоненту.
Если \(\mathcal D\) — множество старых открытых компонент, потерявших контакт, то
$$b'=\max\!\Bigl(b,\max_{j\in\mathcal D} a_j\Bigr).$$
Для каждой новой открытой компоненты \(T\) обозначим через \(\mathcal A(T)\) множество старых компонент, переходящих в неё. Тогда её новый размер равен
$$a'(T)=\lvert T\rvert+\sum_{j\in\mathcal A(T)} a_j,$$
где \(\lvert T\rvert\) считает только занятые клетки в только что добавленном столбце.
Внутри одного столбца связность полностью задаётся вертикальными пробегами. Клетки одного пробега автоматически связаны, а клетки разных пробегов в рамках этого столбца разделены. Единственная недостающая информация состоит в том, были ли разные пробеги уже соединены через предыдущие столбцы. Именно это и кодирует разбиение \(\Pi\).
Такое сжатие эффективно, потому что в столбце ширины \(7\) может быть не более четырёх занятых пробегов, например при маске \(1010101\). Поэтому для каждой маски столбца число возможных разбиений конечно и невелико; все они могут быть заранее перечислены. Динамика работает с каноническими граничными шаблонами, а не с полными частичными досками.
Возьмём \(W=3\). Пусть первый обработанный столбец равен \(101\). Тогда имеются два пробега:
$$R_1=\{1\},\qquad R_2=\{3\}.$$
Поскольку более раннего столбца нет, это две разные открытые компоненты размеров \(1\) и \(1\). Состояние имеет вид
$$\sigma=\bigl(0,\{\{R_1\},\{R_2\}\},1,1\bigr).$$
Теперь добавим столбец \(111\). В новом столбце есть один пробег
$$S_1=\{1,2,3\}.$$
Старая компонента в строке \(1\) касается \(S_1\), и старая компонента в строке \(3\) тоже касается \(S_1\). Поскольку оба контакта лежат в одном вертикальном пробеге, весь пробег становится мостом, и две старые компоненты сливаются. Размер новой открытой компоненты равен
$$1+1+3=5.$$
Следовательно, новое состояние равно
$$\sigma'=\bigl(0,\{\{S_1\}\},5\bigr).$$
Если бы следующий столбец был \(000\), эта компонента размера \(5\) потеряла бы контакт с фронтиром, закрылась бы окончательно и обновила бы максимальный закрытый размер до \(5\).
Пусть \(w_c(\sigma)\) — число префиксов из \(c\) столбцов, приводящих к состоянию \(\sigma\). Тогда из описанного перехода следует
$$w_{c+1}(\sigma')=\sum_{\sigma}\sum_{\substack{m\in\{0,1\}^W\\ T_m(\sigma)=\sigma'}} w_c(\sigma),$$
где \(T_m\) — детерминированное обновление, задаваемое следующей маской столбца \(m\). Динамическая программа хранит эти веса как точные целые числа, а не как вещественные вероятности.
После обработки всех \(H\) столбцов каждый терминальный статус \(\sigma=(b,\Pi,a_1,\dots,a_r)\) даёт вклад
$$\operatorname{score}(\sigma)=\max(b,a_1,\dots,a_r)$$
в размер наибольшей связной области для всех досок, представляемых этим состоянием. Поэтому
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{\sigma\in\mathcal T} w_H(\sigma)\operatorname{score}(\sigma),$$
где \(\mathcal T\) — множество терминальных состояний. Именно эту величину вычисляет реализация.
Сначала реализация перебирает все возможные маски столбца, разбивает каждую маску на вертикальные пробеги и заранее строит канонические разбиения этих пробегов. Также заранее вычисляется взаимодействие старого фронтирного шаблона с новым столбцом: какие старые компоненты продолжаются, какие сливаются, какие исчезают и сколько новых занятых клеток добавляется к каждой выжившей компоненте.
Далее динамическая программа движется столбец за столбцом. Состояние определяется разбиением фронтира, накопленными размерами открытых компонент и текущим лучшим значением среди закрытых компонент. При добавлении нового столбца реализация применяет подготовленное правило связности, создаёт целевое состояние и объединяет одинаковые целевые состояния, суммируя их целочисленные кратности.
Поскольку каждая маска столбца равновероятна, реализации на C++, Python и Java считают количество досок, а не переносят дробные вероятности на каждом шаге. Деление на \(2^{WH}\) происходит только в самом конце. Python- и Java-версии используют тот же самый точный базовый решатель, что и реализация на C++, поэтому все три языка работают с одними и теми же переходами, одними и теми же подсчётами и одним и тем же итогом.
Кроме того, реализация использует горизонтальное отражение на предпоследнем слое: зеркальные маски дают одинаковый вклад в финальное ожидание, поэтому несимметричный представитель можно посчитать один раз с кратностью \(2\). Это уменьшает объём финальной работы без какого-либо изменения точного результата.
Пусть \(P\) — общее число канонических разбиений фронтира по всем маскам столбца, а \(S_c\) — число достижимых сжатых состояний после \(c\) столбцов. Предварительное вычисление контактов между масками требует \(O(4^W\cdot W)\) времени, а построение таблиц переходов по разбиениям требует \(O(P\cdot 2^W)\).
Основная динамика сопоставляет каждое достижимое состояние с каждой возможной маской следующего столбца, поэтому её временная сложность равна
$$O\!\left(\sum_{c=0}^{H-1} 2^W S_c\right).$$
Память имеет порядок
$$O(S_c+P\cdot 2^W)$$
для активных слоёв DP и предварительно вычисленных переходов. Для случая \(7\times 7\) это выполнимо, тогда как прямой перебор всех \(2^{49}\) досок невыполним.
ننظر إلى شبكة ثنائية عشوائية بحجم \(W\times H\)، وفي مسألة Project Euler تكون \(W=H=7\). كل خلية مشغولة بصورة مستقلة باحتمال \(1/2\)، ويُعرَّف الاتصال بواسطة الجيران الأربعة فقط. إذا رمزنا بـ \(L(B)\) إلى حجم أكبر مكوّن متصل من الخلايا المشغولة في اللوحة \(B\)، فالمطلوب هو حساب \(\mathbb E[L(B)]\) حسابًا دقيقًا.
العدّ المباشر يقتضي المرور على جميع اللوحات وعددها \(2^{WH}\)، وهذا غير عملي عند \(7\times 7\). لذلك تعتمد الفكرة الصحيحة على معالجة الأعمدة واحدًا بعد آخر والاحتفاظ فقط بالمعلومات التي يمكن أن تؤثر في النمو المستقبلي.
لنعرّف
$$\Omega_{W,H}=\{0,1\}^{W\times H}.$$
ولكل لوحة \(B\in\Omega_{W,H}\)، لتكن \(\mathcal C(B)\) مجموعة المكوّنات المشغولة المتصلة وفق جوار الأربع اتجاهات، ونعرّف
$$L(B)=\max_{C\in\mathcal C(B)} \lvert C\rvert,$$
مع الاتفاق على أن \(L(B)=0\) إذا كانت اللوحة خالية تمامًا. وبما أنّ جميع اللوحات متساوية الاحتمال، فإن
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{B\in\Omega_{W,H}} L(B).$$
إذن جوهر المسألة هو جمع حجم أكبر مكوّن متصل على جميع اللوحات جمعًا تامًا، ثم القسمة في النهاية على \(2^{WH}\).
افترض أنّ أول \(c\) أعمدة قد عولجت بالفعل. أي مكوّن متصل لا يلامس العمود \(c\) لن يتمكن من النمو لاحقًا، لأن جميع الخلايا المستقبلية تقع إلى يمينه فقط. لذلك يكفي بالنسبة إلى المكوّنات المغلقة أن نحتفظ بعدد واحد: أكبر حجم لمكوّن أُغلق حتى الآن.
انظر الآن إلى العمود \(c\). الخلايا المشغولة فيه تنقسم إلى مقاطع رأسية متصلة، مثل \(11100 11\mapsto (111)\) و\((11)\). لنرمز إلى هذه المقاطع بـ \(R_1,\dots,R_t\). قد ينتمي مقطعان مختلفان في العمود نفسه إلى المكوّن العالمي نفسه إذا كانت الأعمدة السابقة قد ربطتهما بالالتفاف حول الفجوة. لذلك لا تكفي معرفة قناع الإشغال وحده، بل يجب أيضًا معرفة أي المقاطع تنتمي معًا إلى المكوّن المفتوح نفسه.
ومن ثم يمكن كتابة الحالة على الصورة
$$\sigma=(b,\Pi,a_1,\dots,a_r),$$
حيث:
ويمثل \(b\) أكبر حجم بين المكوّنات التي أُغلقت حتى الآن.
\(\Pi\) تقسيم لمقاطع العمود \(R_1,\dots,R_t\)، وكل كتلة في هذا التقسيم تمثل مكوّنًا مفتوحًا واحدًا ما زال يلامس الحدّ الفاصل،
ولكل \(1\le j\le r\)، فإن \(a_j\) يمثل الحجم الكلي للمكوّن المفتوح رقم \(j\).
وهذه المعلومات كافية، لأن الأعمدة المستقبلية لا يمكنها التفاعل مع الجزء المعالَج إلا عبر هذه المكوّنات المفتوحة.
ليكن قناع العمود التالي هو \(m\in\{0,1\}^W\). الخلايا المشغولة في هذا العمود تنقسم كذلك إلى مقاطع رأسية \(S_1,\dots,S_u\).
يلامس مكوّن مفتوح قديم العمود الجديد بالضبط في الصفوف التي تكون فيها الخليتان المتجاورتان في العمودين مشغولتين معًا. وما إن يلامس أي خلية من مقطع \(S_k\)، حتى يصبح المقطع كله جزءًا من القطعة المتصلة الجديدة نفسها، لأن خلايا المقطع الرأسي الواحد متصلة أصلًا داخل العمود الجديد.
وهذا يؤدي إلى ثلاث حالات:
أولًا، قد لا يلامس مكوّن مفتوح قديم أي خلية في العمود الجديد. عندئذٍ يُغلق نهائيًا، ولا يبقى له إلا احتمال تحديث أفضل قيمة مغلقة.
ثانيًا، قد يلامس مكوّن قديم واحد مقطعًا جديدًا واحدًا أو عدة مقاطع. عندها يظل مفتوحًا ويزداد حجمه بعدد الخلايا المشغولة الجديدة التي انضمت إليه.
ثالثًا، قد تلامس عدة مكوّنات قديمة المقطع نفسه، أو تلامس مقاطع تصبح مرتبطة داخل العمود الجديد. عندئذٍ تندمج تلك المكوّنات القديمة في مكوّن مفتوح جديد واحد.
إذا كانت \(\mathcal D\) هي مجموعة المكوّنات المفتوحة القديمة التي فقدت الاتصال، فإن
$$b'=\max\!\Bigl(b,\max_{j\in\mathcal D} a_j\Bigr).$$
ولكل مكوّن مفتوح جديد \(T\)، لتكن \(\mathcal A(T)\) مجموعة المكوّنات القديمة التي تصب فيه. عندئذٍ يكون حجمه الجديد
$$a'(T)=\lvert T\rvert+\sum_{j\in\mathcal A(T)} a_j,$$
حيث إن \(\lvert T\rvert\) يعدّ فقط الخلايا المشغولة في العمود المضاف حديثًا.
داخل عمود واحد، تتحدد البنية الاتصالية بالكامل بواسطة المقاطع الرأسية. الخلايا الواقعة في المقطع نفسه متصلة تلقائيًا، والخلايا الواقعة في مقاطع مختلفة منفصلة داخل ذلك العمود. المعلومة الوحيدة الناقصة هي ما إذا كان مقطعان مختلفان قد اتصلا مسبقًا عبر أعمدة أقدم. وهذا بالضبط ما يحمله التقسيم \(\Pi\).
هذا الضغط فعّال جدًا، لأن العمود بعرض \(7\) لا يمكن أن يحتوي أكثر من أربعة مقاطع مشغولة، مثل \(1010101\). لذلك فإن عدد التقسيمات الممكنة لكل قناع عمود يبقى محدودًا وصغيرًا، ويمكن توليده مسبقًا بالكامل. وهكذا تعمل البرمجة الديناميكية على أنماط حدّية معيارية بدلًا من اللوحات الجزئية الكاملة.
لنأخذ \(W=3\). إذا كان أول عمود معالَج هو \(101\)، فلدينا مقطعان:
$$R_1=\{1\},\qquad R_2=\{3\}.$$
وبما أنه لا يوجد عمود سابق، فهما مكوّنان مفتوحان منفصلان حجماهما \(1\) و\(1\). إذن الحالة هي
$$\sigma=\bigl(0,\{\{R_1\},\{R_2\}\},1,1\bigr).$$
الآن نضيف العمود \(111\). في العمود الجديد يوجد مقطع واحد فقط:
$$S_1=\{1,2,3\}.$$
المكوّن القديم في الصف \(1\) يلامس \(S_1\)، وكذلك المكوّن القديم في الصف \(3\). ولأن هذين التلامسين يقعان داخل المقطع الرأسي نفسه، فإن المقطع كله يصبح جسرًا يوحّد المكوّنين القديمين. لذا يصبح حجم المكوّن المفتوح الجديد
$$1+1+3=5.$$
ومن ثم تكون الحالة الجديدة
$$\sigma'=\bigl(0,\{\{S_1\}\},5\bigr).$$
ولو كان العمود التالي هو \(000\)، لفقد هذا المكوّن ذو الحجم \(5\) اتصاله بالحدّ الفاصل، وأُغلق نهائيًا، ولرفع أفضل قيمة مغلقة إلى \(5\).
ليكن \(w_c(\sigma)\) عدد البوادئ المؤلفة من \(c\) أعمدة والتي تنتج الحالة \(\sigma\). عندئذٍ تعطي قاعدة الانتقال السابقة
$$w_{c+1}(\sigma')=\sum_{\sigma}\sum_{\substack{m\in\{0,1\}^W\\ T_m(\sigma)=\sigma'}} w_c(\sigma),$$
حيث يرمز \(T_m\) إلى التحديث الحتمي الذي يسببه قناع العمود التالي \(m\). وتحفظ البرمجة الديناميكية هذه الأوزان على هيئة أعداد صحيحة دقيقة، لا احتمالات عشرية.
بعد معالجة جميع الأعمدة \(H\)، تسهم كل حالة نهائية \(\sigma=(b,\Pi,a_1,\dots,a_r)\) بالقيمة
$$\operatorname{score}(\sigma)=\max(b,a_1,\dots,a_r)$$
في حجم أكبر مساحة متصلة لكل لوحة تمثلها تلك الحالة. ولذلك
$$\mathbb E[L]=\frac{1}{2^{WH}}\sum_{\sigma\in\mathcal T} w_H(\sigma)\operatorname{score}(\sigma),$$
حيث \(\mathcal T\) مجموعة الحالات النهائية. وهذه هي الكمية التي تحسبها الشيفرة فعليًا.
تبدأ الشيفرة بتعداد جميع أقنعة الأعمدة الممكنة، ثم تفكيك كل قناع إلى مقاطعه الرأسية، ثم توليد جميع التقسيمات المعيارية الممكنة لهذه المقاطع. كذلك تُحسب مسبقًا طريقة تفاعل نمط حدّي قديم مع عمود جديد: أي المكوّنات القديمة ستبقى، وأيها ستندمج، وأيها ستختفي، وكم خلية مشغولة جديدة ستُضاف إلى كل مكوّن باقٍ.
بعد ذلك تتقدم البرمجة الديناميكية عمودًا بعد عمود. تُفهرس الحالة بواسطة تقسيم الحدّ الفاصل، والأحجام المتراكمة للمكوّنات المفتوحة، وأكبر قيمة مغلقة حتى تلك اللحظة. وعند إضافة عمود جديد، تطبق الشيفرة قاعدة الاتصال المحسوبة مسبقًا، وتنتج الحالة التالية، ثم تدمج الحالات المتطابقة بجمع تعداداتها الصحيحة.
وبما أن كل قناع عمود متساوي الاحتمال، فإن تطبيقات C++ وPython وJava تعدّ عدد اللوحات بدلًا من نقل الكسور في كل خطوة. ولا تتم القسمة على \(2^{WH}\) إلا في النهاية. كما أن نسختي Python وJava تستخدمان الحل الدقيق الأساسي نفسه الذي تستخدمه نسخة C++، ولذلك فالقواعد الانتقالية والعدّ والنتيجة النهائية متماثلة في اللغات الثلاث.
وتستفيد الشيفرة أيضًا من التناظر بالانعكاس الأفقي في الطبقة قبل الأخيرة: فأقنعة الأعمدة المتناظرة مرآتيًا تعطي الإسهام نفسه في القيمة المتوقعة النهائية، ولذلك يمكن حساب ممثل غير متناظر مرة واحدة فقط مع مضاعفة وزنه إلى \(2\). وهذا يقلل العمل في المرحلة الأخيرة من دون أي تغيير في النتيجة الدقيقة.
ليكن \(P\) هو العدد الكلي لتقسيمات الحدّ الفاصل المعيارية عبر جميع أقنعة الأعمدة، وليكن \(S_c\) عدد الحالات المضغوطة القابلة للوصول بعد \(c\) أعمدة. إن حساب معلومات التماس بين الأقنعة مسبقًا يكلف \(O(4^W\cdot W)\)، وبناء جداول انتقالات التقسيمات يكلف \(O(P\cdot 2^W)\).
أما البرمجة الديناميكية الأساسية فتعالج كل حالة قابلة للوصول مع كل قناع ممكن للعمود التالي، ومن ثم فإن زمنها الكلي هو
$$O\!\left(\sum_{c=0}^{H-1} 2^W S_c\right).$$
واستهلاك الذاكرة هو
$$O(S_c+P\cdot 2^W)$$
للطبقات الفعالة من DP ولبيانات الانتقال المحسوبة مسبقًا. وفي حالة \(7\times 7\) يكون هذا عمليًا، بينما يبقى التعداد المباشر لجميع اللوحات وعددها \(2^{49}\) غير عملي.