Detailed mathematical approach

Problem Summary

Compress a hand from a standard 52-card deck into a rank-count vector \(c=(c_1,\dots,c_{13})\), where \(0\le c_r\le 4\) and the ranks are \(A,2,\dots,10,J,Q,K\). The card values used by the problem are

\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \]

A count vector does not distinguish suits, so it stands for

\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]

different physical hands: for each rank we choose \(c_r\) suits out of the four available. The goal is to count, with that multiplicity and excluding the empty hand, all vectors for which the face-value total

\[ H(c)=\sum_{r=1}^{13} v_r c_r \]

is exactly equal to the cribbage score used in the problem, namely

\[ C(c)=P(c)+R(c)+2F_{15}(c). \]

Here \(P(c)\) is the score from equal-rank pairs, \(R(c)\) is the score from runs, and \(F_{15}(c)\) counts card subsets whose values add up to 15. So the whole problem is an exact weighted count of the nonempty hands satisfying \(H(c)=C(c)\).

Mathematical Approach

Rank-count vectors are the natural state space

Since suits matter only through multiplicity, the real combinatorial object is the 13-dimensional vector \(c\). Every legal hand corresponds to exactly one such vector, and every vector represents \(W(c)\) suit assignments. That compression is what makes the problem finite: there are only \(5^{13}\) possible count vectors, because each rank may appear 0, 1, 2, 3, or 4 times.

Pair score and run score come directly from the counts

The pair contribution is immediate. If rank \(r\) appears \(c_r\) times, then it contains \(\binom{c_r}{2}\) equal-rank pairs, each worth 2 points, so

\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1). \]

The run contribution is slightly subtler. Break the rank line into maximal consecutive blocks of positive counts. For one such block \(a,a+1,\dots,b\), let

\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r. \]

Each choice of one card from every rank in that block produces a distinct run, so the block contributes \(L\cdot M\) if \(L\ge 3\), and 0 otherwise. Therefore

\[ R(c)=\sum_{\text{maximal positive blocks}} \mathbf{1}_{L\ge 3}\,L\,M. \]

This matches the usual cribbage behavior: a block such as \(A,A,2,3,4,5\) gives two runs of length 5, not a pile of shorter subruns, because the whole maximal block is scored at once.

Fifteens are a subset-sum coefficient

For each rank \(r\), we may select \(d\) of its \(c_r\) copies into a subset, where \(0\le d\le c_r\). There are \(\binom{c_r}{d}\) ways to do that, and it contributes value \(d\,v_r\). Hence the generating function

\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]

has the property that

\[ F_{15}(c)=[x^{15}]\,G_c(x). \]

The implementations evaluate that coefficient by a short dynamic program on sums \(0,1,\dots,15\): after processing rank \(r\), the array entry for sum \(s\) stores how many subsets of the processed ranks have total \(s\). Because we only care about 15, the polynomial is truncated immediately.

Worked example

Take the hand with two aces and one each of 2, 3, 4, and 5. In count-vector form, that means

\[ c_A=2,\quad c_2=c_3=c_4=c_5=1, \]

and all other entries are 0. Then

\[ H(c)=2\cdot 1+2+3+4+5=16. \]

The pair score is \(P(c)=2\), coming from the two aces. The ranks \(A,2,3,4,5\) form one maximal positive block of length 5, with multiplicity product \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\), so

\[ R(c)=5\cdot 2=10. \]

For fifteens, the subset \(A+2+3+4+5\) sums to 15, and either ace may be chosen, so \(F_{15}(c)=2\). Therefore

\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]

This is exactly the kind of hand the program counts.

Split the ranks into two reusable half-states

The main implementation trick is a meet-in-the-middle split after the sixth rank. A full count vector is written as

\[ c=(c^{L},c^{R}), \]

where the left half contains the first 6 ranks and the right half contains the remaining 7. For each half, the implementation precomputes a compact summary consisting of:

\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]

together with:

\[ f(s)=\#\{\text{subsets in this half with total } s\}\qquad (0\le s\le 15), \]

and the length, multiplicity product, and score of the prefix and suffix positive blocks. The point is that the expensive work for a half-hand is done once and then reused for every compatible half on the other side.

The only cross-boundary interaction is one merged run

The left half and the right half are independent except at the split point. If the left half ends with a positive block and the right half begins with a positive block, those two pieces actually form one longer run block in the full hand. Let the left suffix have length and multiplicity \((\ell_L,m_L)\), and the right prefix have \((\ell_R,m_R)\). Define

\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]

Then the correction needed at the boundary is

\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R). \]

This quantity may add a new run that was too short in both halves, or it may replace two separate partial scores by one merged score. After this correction, the full run score is

\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust}. \]

The fifteen count becomes a short dot product

The generating function also factors over the split:

\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]

If \(f_L(s)\) and \(f_R(s)\) are the subset-count arrays for the two halves, then

\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s). \]

The implementations store a reversed copy of the right array, so this becomes a 16-term dot product rather than a fresh subset-sum computation for every full hand.

Final merge condition

For a merged hand, write

\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}). \]

Since the full run score differs from \(R(c^{L})+R(c^{R})\) by exactly \(\operatorname{adjust}\), the target identity becomes

\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c). \]

So a left state and a right state form a valid hand precisely when the corrected left-right base value equals twice the dot-product count of fifteens. Whenever that happens, the contribution to the answer is \(W(c^{L})W(c^{R})\). The all-zero vector satisfies the identity trivially, so it is removed at the end by subtracting 1.

How the Code Works

Half-state enumeration

The C++, Python, and Java implementations first enumerate every possible count pattern in each half: \(5^6\) states on the left and \(5^7\) on the right. For every half-state they compute the hand total, pair score, internal run score, multiplicity, the truncated subset-sum polynomial up to 15, and the prefix/suffix block data needed for a later merge.

Merging two halves

Each left half-state is paired with each right half-state. The implementation computes the boundary correction for a run that crosses the split, then forms

\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust}. \]

If this value is negative, odd, or larger than 340, the pair is impossible and is skipped immediately. The upper bound 340 comes from the largest possible face-value sum of a full deck count vector. Otherwise the code evaluates the 16-term dot product for \(F_{15}\), stopping early if the partial sum has already exceeded the target.

Accumulation and exactness

When the equality test succeeds, the product of the two multiplicities is added to the total. This counts all suit assignments represented by the merged rank-count vector. The empty hand is excluded at the very end. The C++ and Java implementations parallelize the outer scan over left states; the Python entry point uses the same mathematical computation path rather than a different scoring rule.

Complexity Analysis

Enumerating the half-states costs \(O(5^6)\) and \(O(5^7)\) summaries, each with only a constant-size dynamic program on sums \(0\) through \(15\). The dominant phase is the cartesian product of the two state sets, so the merge work is

\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}). \]

That means the method does not reduce the exponent of the search space. Its advantage is that the expensive scoring data for a half-hand is computed once and reused many times, so each full-hand test becomes only a boundary correction plus a 16-term dot product. Memory usage is

\[ O\!\big((5^6+5^7)\cdot 16\big), \]

coming from the stored half-state tables and their short subset-sum arrays.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=928
2. Cribbage: Wikipedia - Cribbage
3. Binomial coefficient: Wikipedia - Binomial coefficient
4. Generating function: Wikipedia - Generating function
5. Subset sum problem: Wikipedia - Subset sum problem
6. Dynamic programming: Wikipedia - Dynamic programming