notes.html
problem 28 · 24 lines
<article>
<h3>Problem Analysis</h3>
<p>
The spiral writes the integers <code>1, 2, 3, ...</code> outward from the centre in a clockwise direction, and we are asked only for the sum of the numbers lying on the two diagonals of the final square. The naive route is to construct the entire grid and add up the diagonal cells - but building an <code>N</code> by <code>N</code> grid is an <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time" rel="noopener noreferrer" target="_blank">O(N^2)</a> operation (quadratic in the side length, since the grid has <code>N^2</code> cells). A little arithmetic on the structure of the spiral collapses the problem to a single formula evaluated in <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity#Constant_time" rel="noopener noreferrer" target="_blank">O(1)</a> - constant time, independent of <code>N</code>.
</p>
<p>
The key observation is that the diagonal entries form a regular pattern, ring by ring. The centre holds <code>1</code>. Each subsequent "ring" is a square frame whose side length <code>s</code> grows by 2 each step: <code>s = 3, 5, 7, ...</code> up to <code>N</code>. A ring of side <code>s</code> ends exactly at the perfect square <code>s^2</code>, because the spiral fills outward and that ring's last and largest value sits at its bottom-right corner. The four corners of a ring are its only contributions to the diagonals, and travelling counter-clockwise from the bottom-right corner each step decreases the value by <code>s - 1</code> (the number of cells along one side minus the shared corner). So the four corners are <code>s^2</code>, <code>s^2 - (s-1)</code>, <code>s^2 - 2(s-1)</code>, and <code>s^2 - 3(s-1)</code>, summing to <code>4s^2 - 6(s-1)</code>. Summing this over every odd <code>s</code> from 3 to <code>N</code> and adding the central 1 reduces, via standard <a class="reference-source" href="https://en.wikipedia.org/wiki/Summation" rel="noopener noreferrer" target="_blank">summation</a> identities, to the single <a class="reference-source" href="https://en.wikipedia.org/wiki/Closed-form_expression" rel="noopener noreferrer" target="_blank">closed-form expression</a> <code>(N * (N * (4*N + 3) + 8) - 9) / 6</code>. The numerator is always divisible by 6 for odd <code>N</code>, so integer arithmetic is exact throughout - no floating point, no rounding concerns.
</p>
<h3>Solution Approach</h3>
<h4>Closed-Form Formula with Optional Spiral Simulation</h4>
<p>
Both <code>p0028_s0.py</code> and <code>p0028_s0.c</code> implement one design with two paths. The production path is a single <a class="reference-source" href="https://en.wikipedia.org/wiki/Closed-form_expression" rel="noopener noreferrer" target="_blank">closed-form</a> evaluation; the diagnostic path is an O(N^2) spiral simulation that runs only when <code>--show</code> is passed and the grid is small (<code>size <= 10</code>). The simulation exists purely as an independent correctness check and a way to visualise the spiral - it never runs in normal use.
</p>
<p>
The fast path evaluates the polynomial using nested multiplication: compute <code>4*N + 3</code>, then <code>N * (...) + 8</code>, then <code>N * (...) - 9</code>, then divide by 6. This is <a class="reference-source" href="https://en.wikipedia.org/wiki/Horner%27s_method" rel="noopener noreferrer" target="_blank">Horner's method</a> - it evaluates a degree-3 polynomial with exactly three multiplications and never forms large intermediate powers like <code>N**3</code>. Before returning, both solutions also validate that the formula equals the value the simulation produced, printing a coloured pass/fail marker.
</p>
<p>
The simulation reproduces the spiral without tracking a heading or turn rules. Starting at the origin with value 1, for each successive number it inspects the four neighbours (right, down, left, up), discards any already occupied, and moves to the unoccupied neighbour with the smallest squared distance from the origin (<code>x*x + y*y</code>). This "nearest free neighbour" rule reproduces the clockwise outward walk because the spiral's geometry guarantees the next correct cell is always the nearest empty one. After filling the grid, the diagonal sum is the total over every cell where <code>col == row</code> (main diagonal) or <code>col == -row</code> (anti-diagonal).
</p>
<p>
The two languages differ only in storage. Python uses a <a class="reference-source" href="https://docs.python.org/3/library/stdtypes.html#dict" rel="noopener noreferrer" target="_blank">dict</a> keyed by <code>(col, row)</code> tuples, so occupancy is a simple <code>in</code> test and the origin-centred coordinate system needs no offset. C uses a flat 1-D array of <code>dim * dim</code> ints allocated with <a class="reference-source" href="https://en.cppreference.com/w/c/memory/calloc" rel="noopener noreferrer" target="_blank">calloc</a> (so every cell starts at 0, meaning "empty"), mapping signed coordinate <code>(col, row)</code> to index <code>(row + half) * dim + (col + half)</code>. The C layout is compact and cache-friendly; the Python dict is more convenient but heavier per cell - an acceptable trade, since the simulation only ever runs on tiny grids.
</p>
</article>