notes.html

problem 54 · 27 lines

<article>
<h3>Problem Analysis</h3>
<p>
At its core, this problem asks me to impose a <a class="reference-source" href="https://en.wikipedia.org/wiki/Total_order" rel="noopener noreferrer" target="_blank">total order</a> on poker hands - a rule that, given any two hands, decides unambiguously which one is greater. A <a class="reference-source" href="https://en.wikipedia.org/wiki/Total_order" rel="noopener noreferrer" target="_blank">total order</a> is a comparison relation under which every pair of elements can be ranked relative to each other with no ties (the problem guarantees a clear winner). The technique is to map each hand to a comparison key that captures both its category (pair, flush, full house, and so on) and the cascading tie-breaker data (which pair first, then which kicker, then the next). Once each hand is reduced to such a key, choosing the winner is a single comparison.
</p>
<p>
The key observation is that every poker category can be detected with two cheap pieces of derived data: a <a class="reference-source" href="https://en.wikipedia.org/wiki/Frequency_(statistics)" rel="noopener noreferrer" target="_blank">frequency count</a> of how often each card value appears, plus two boolean flags - whether all five suits match (a flush) and whether the five distinct values form a consecutive run (a straight). Four-of-a-kind, full house, three-of-a-kind, two pairs, and one pair are distinguished purely by the shape of the frequency counts; flush and straight come from the two flags; straight flush and royal flush are their combination. Because a hand is always exactly five cards, every per-hand operation - counting, sorting, flag checks - is <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(1)</a>. Processing N lines from the file is therefore <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(N)</a> overall, and here N is just 1000.
</p>
<h3>Solution Approach</h3>
<h4>Canonical Hand Evaluation with a Sorted Frequency Table</h4>
<p>
Both the Python (<code>p0054_s0.py</code>) and C (<code>p0054_s0.c</code>) solutions implement the same algorithm and differ only in language idioms. For each line, the ten whitespace-separated tokens are split into Player 1's first five cards and Player 2's last five. Each hand is evaluated independently into a (rank, tie-breakers) structure, and the two structures are then compared.
</p>
<p>
My first design decision is how to turn a card character into a number. I encode the value ordering as the string <code>"23456789TJQKA"</code> and take each card's integer rank from its position in that string, so '2' maps to 0, 'T' to 8, and 'A' to 12. In Python this is <code>VALUES.index(c)</code>; in C it is pointer arithmetic via <code>strchr</code>. I prefer this over a dictionary or a switch because the ordering is implicit in the string and the data stays collocated and readable.
</p>
<p>
Next I compute the two flags. <code>is_flush</code> is true when all five suits are identical. <code>is_straight</code> is true when the five values are all distinct and <code>max - min == 4</code> - a compact test for "five consecutive values" that avoids explicitly sorting and walking the run. If both flags hold, the hand is a straight flush; if additionally the lowest value is 8 (the run T-J-Q-K-A), it is a royal flush. Settling these top categories first keeps the high-end cases short.
</p>
<p>
For everything else, I build a frequency table of (count, value) pairs and sort it by count descending, then value descending. This single sort into <a class="reference-source" href="https://en.wikipedia.org/wiki/Canonical_form" rel="noopener noreferrer" target="_blank">canonical form</a> is the heart of the classification: the dominant group always lands first, so I only need to inspect the first one or two entries. A leading count of 4 is four-of-a-kind; 3 followed by 2 is a full house; a lone 3 is three-of-a-kind; two consecutive 2s is two pairs; a single 2 is one pair; otherwise high card. Crucially, I build the tie-breaker sequence in priority order at the same time - the dominant value first, then kickers in descending order - so that comparing two hands of equal rank becomes a plain <a class="reference-source" href="https://en.wikipedia.org/wiki/Lexicographic_order" rel="noopener noreferrer" target="_blank">lexicographic comparison</a> of the tie-breaker tuples with no extra branching.
</p>
<p>
In Python the result is a <code>HandRank</code> dataclass with a custom <code>__gt__</code>; the hand itself is a <code>PokerHand</code> dataclass whose <code>hand_rank</code> is a <a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.cached_property" rel="noopener noreferrer" target="_blank">functools.cached_property</a>, and the categories are an <a class="reference-source" href="https://docs.python.org/3/library/enum.html#enum.IntEnum" rel="noopener noreferrer" target="_blank">IntEnum</a> so they compare as integers. The C version mirrors this with a <code>HandRank</code> struct holding the rank enum plus a fixed five-element tie-breaker array and a count, and a <code>hand_rank_gt</code> function that returns on the first differing element. The C code also defends against blank and short lines, using <a class="reference-source" href="https://en.cppreference.com/w/c/string/byte/strtok" rel="noopener noreferrer" target="_blank">strtok_r</a> for reentrant tokenisation.
</p>
</article>