notes.html

problem 84 · 30 lines

<article>
<h3>Problem Analysis</h3>
<p>
At its core this is a question about a <a class="reference-source" href="https://en.wikipedia.org/wiki/Markov_chain" rel="noopener noreferrer" target="_blank">Markov chain</a>: a stochastic process whose next state depends only on the current state and a fixed set of transition probabilities, never on the full path taken to reach it. The board's 40 squares are the states, and one turn - a dice roll followed by any card or "Go To Jail" redirection - defines the transition rule. What the problem asks for is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Stationary_distribution" rel="noopener noreferrer" target="_blank">stationary distribution</a>: the long-run fraction of turns that finish on each square, which an ergodic chain converges to regardless of where it started. From that distribution I need only the three squares with the highest probability, concatenated as zero-padded indices.
</p>
<p>
The distribution is non-uniform because several mechanics redirect the player after the roll. G2J sends you straight to Jail; Community Chest (CC) and Chance (CH) draw cards that may move you elsewhere - Chance is the most disruptive, with 10 of its 16 cards commanding a move, several of them relative ("next railway", "next utility", "go back 3"). On top of that, rolling three consecutive doubles sends the player directly to Jail regardless of the roll. These coupled rules make the transition probabilities intricate, but they are all <em>exactly</em> computable - there is no need to approximate.
</p>
<p>
The natural temptation is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Monte_Carlo_method" rel="noopener noreferrer" target="_blank">Monte Carlo simulation</a>: roll a million dice and tally. The fatal flaw is that simulation is <em>non-deterministic</em> - the harness runs <code>solve()</code> several times and requires an identical result each time, but a random walk yields a slightly different modal string on every run, and with the leading squares often statistically close the ranking itself can flip. The exact approach has no such weakness: it computes the steady state directly, so the answer is reproducible to the last digit.
</p>
<h3>Solution Approach</h3>
<h4>Exact Stationary Distribution (Python and C)</h4>
<p>
Both files implement the same algorithm in three stages: build the transition matrix, power-iterate it to the stationary distribution, then marginalise and rank. The board is kept as an ordered list of 40 name strings rather than bare integers, so the rules read almost as a direct transcription: identifying a CC square is a <code>"CC"</code> prefix test, and "go to next railway" is "scan clockwise to the next name starting with R". Nothing depends on magic indices.
</p>
<h4>Resolving a Landing Square into Finishing Probabilities</h4>
<p>
The helper <code>resolve(landing)</code> returns the probability distribution over the squares a player can <em>finish</em> on, given the roll dropped them on <code>landing</code>. A plain square maps to itself with probability 1; G2J maps wholly to Jail. A CC square splits 2/16 onto its two movement cards (Advance to GO, Go to Jail) and 14/16 staying put. A CH square splits across its ten movement cards - the absolute targets (GO, Jail, C1, E3, H2, R1), the relative "next R" (which appears twice, giving 2/16) and "next U" found by a forward scan, and "go back 3" - with 6/16 staying put. One subtlety the simulation got wrong by omission: "go back 3" from CH3 (square 36) lands on CC3, which then triggers a Community Chest draw. <code>resolve</code> handles this by recursing on the back-3 destination and folding its distribution in, so the chained card is modelled exactly.
</p>
<h4>The Augmented State and the Three-Doubles Rule</h4>
<p>
A chain over the 40 squares alone cannot express "three consecutive doubles", because that depends on history. The fix is to <em>augment</em> the state with the number of consecutive doubles carried into the turn (0, 1 or 2), giving 120 states indexed <code>square * 3 + doubles</code>. The transition then enumerates every ordered dice pair: a third successive double routes straight to Jail and resets the streak; otherwise the player moves, the landing square is resolved into finishing probabilities, and the streak advances (or resets on a non-double). Any move that finishes in Jail also resets the streak. This captures the rule faithfully rather than waving it away as negligible.
</p>
<h4>Power Iteration and Ranking</h4>
<p>
The stationary distribution is found by <a class="reference-source" href="https://en.wikipedia.org/wiki/Power_iteration" rel="noopener noreferrer" target="_blank">power iteration</a>: start from the uniform vector and repeatedly multiply by the transition matrix until the change between successive iterates falls below 1e-15. Because the chain is ergodic this converges quickly to the dominant eigenvector (eigenvalue 1). The 120-state distribution is then marginalised back to 40 per-square probabilities by summing over the doubles dimension, and the three largest are taken - with index as a deterministic tie-break - and formatted as the six-digit modal string. Both solutions reproduce the known 6-sided answer (102400) and yield 101524 for the 4-sided case.
</p>
</article>