notes.html

problem 90 · 30 lines

<article>
<h3>Problem Analysis</h3>
<p>
At its core this is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Combinatorics" rel="noopener noreferrer" target="_blank">combinatorics</a> problem about counting subsets. A cube is fully described by the set of six distinct digits printed on its faces - the physical orientation of the faces is irrelevant, because any face can be rotated into view. So a cube is simply a 6-element <a class="reference-source" href="https://en.wikipedia.org/wiki/Combination" rel="noopener noreferrer" target="_blank">combination</a> (an unordered selection, with no element repeated) drawn from the ten digits {0, ..., 9}. The number of such combinations is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Binomial_coefficient" rel="noopener noreferrer" target="_blank">binomial coefficient</a> C(10, 6) = 210. Recognising this change of representation is the entire trick: a tangible object with rotatable faces becomes a plain set, and the problem dissolves into counting.
</p>
<p>
An "arrangement" is a pair of cubes, and the problem states the pair is unordered: cube A beside cube B is the same arrangement as cube B beside cube A. Counting unordered pairs with repetition allowed - two identical cubes are a legitimate physical arrangement - gives C(210 + 1, 2) = 22,155 candidate pairs. That is a tiny number, so a <a class="reference-source" href="https://en.wikipedia.org/wiki/Brute-force_search" rel="noopener noreferrer" target="_blank">brute-force search</a> over every pair is the natural and optimal strategy. For each pair I test the nine two-digit squares below 100 (01, 04, 09, 16, 25, 36, 49, 64, 81). Two observations make that test clean: each square can be formed with either cube supplying the tens digit, so the check considers both orientations; and the 6/9 flip rule means a face showing 6 can also serve as 9 and vice versa, so "can this cube show a 6 or 9?" reduces to "is 6 or 9 present?". The overall complexity is O(C(10,6)^2 * 9) - effectively constant for fixed input, completing in well under a millisecond in C.
</p>
<h3>Solution Approach</h3>
<h4>Brute-Force Combination Enumeration (Python and C)</h4>
<p>
Both files implement the identical algorithm; only the language idioms differ. I chose <a class="reference-source" href="https://en.wikipedia.org/wiki/Brute-force_search" rel="noopener noreferrer" target="_blank">brute force</a> deliberately because, as the analysis shows, the search space is minuscule. When a problem fits comfortably under roughly 10^7 operations, correctness and clarity matter far more than algorithmic cleverness.
</p>
<p>
Step 1 - enumerate the cubes. In Python I call <code>itertools.combinations(range(10), 6)</code>, which yields all 210 six-element subsets in lexicographic order. In C I reproduce the same enumeration with six nested loops whose index bounds enforce a strictly increasing sequence (<code>a &lt; b &lt; c &lt; d &lt; e &lt; f</code>), storing the digits in a fixed <code>all_cubes[210][6]</code> array. Both produce exactly the same 210 cubes.
</p>
<p>
Step 2 - encode the square targets. The Python solution computes the nine squares at runtime, formatting each as a two-character string and splitting it into tens and units digits. The C solution hard-codes the nine digit pairs as a static <code>int squares[9][2]</code>. Both are equally correct; the C version trades a little flexibility for directness.
</p>
<p>
Step 3 - the display predicate. The helper <code>can_display(cube, digit)</code> returns true if the digit is on the cube, or - when the target is 6 or 9 - if either 6 or 9 is present. This single function captures the only subtle rule in the problem, so I isolated it rather than scattering the condition through the pairing loop.
</p>
<p>
Step 4 - the pair check. <code>can_pair_display_all</code> loops over the nine square pairs (a, b) and requires that for each one, either (cube1 shows a and cube2 shows b) or (cube1 shows b and cube2 shows a). The disjunction covers both physical placements. If any square fails, the pair is rejected immediately - a short-circuit that prunes most pairs after only a few iterations.
</p>
<p>
Step 5 - count unordered pairs. The outer loops run <code>for i in range(n): for j in range(i, n)</code>. Starting <code>j</code> at <code>i</code> (not <code>i + 1</code>) counts each unordered pair once and crucially admits a cube paired with an identical copy of itself.
</p>
</article>