This problem is labeled with 65% difficulty rating. This is now the “hardest” problem I’ve solved! Working on these more challenging problems gives me a lot of confidence and joy.
I first implemented this using brute force. Getting the horizontal rectangles was easy. The diagonals were certainly the hardest. Figuring out the algorithm was the toughest part. It was one of those situations where it is easy for a human to do it, but teaching a computer becomes very complex. I decided that the best way to structure the data was by rotating the grid 45 degrees. I noticed that this always lead to a square with varying numbers of missing squares in the corners. Once I figured out the pattern to it, it was a lot easier. The tests passed soon thereafter.
From here it’s a matter of speeding it up. Ends up my brute force implementation did get the correct answer in about 14-15 minutes. But this time I wanted to do it right and get it down to under a minute. I did this (it actually runs in about 70ms) by finding the patterns in the numbers of diagonals found in each grid. I threw some numbers into oeis and found https://oeis.org/A000447 and https://oeis.org/A330805 which fit the bill. I used these to replace my brute force algorithm for the diagonals.
def horizontals(width, height):
count = 0
for w in range(1, width + 1):
for h in range(1, height + 1):
count += (height - h + 1) * (width - w + 1)
return count
def adder(n):
return n * (4 * n**2 - 1) // 3
def equals(n):
return n * (n + 1) * (4 * n**2 + 12*n + 11) // 6
def diagonals(width, height):
if width == height:
return equals(width - 1)
return diagonals(width - 1, height) + adder(height)
def solve(width, height):
total = 0
for w in range(1, width + 1):
for h in range(1, height + 1):
total += horizontals(w, h)
if w < h:
total += diagonals(h, w)
else:
total += diagonals(w, h)
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
m = eval(sys.argv[2])
print(solve(n, m))
import pytest
from problem import solve, horizontals, diagonals
_test_horizontals = (
(1, 1, 1),
(2, 1, 3),
(2, 2, 9),
(3, 1, 6),
(3, 2, 18),
(3, 3, 36),
(4, 1, 10),
(4, 2, 30),
(4, 3, 60),
(4, 4, 100),
(5, 1, 15),
(5, 2, 45),
(5, 3, 90),
(5, 4, 150),
(5, 5, 225),
)
@pytest.mark.parametrize('n,m,expect', _test_horizontals)
def test_horizontals(n, m, expect):
assert expect == horizontals(n, m)
_test_diagonals = (
(1, 1, 0),
(2, 1, 1),
(2, 2, 9),
(3, 1, 2),
(3, 2, 19),
(3, 3, 51),
(4, 1, 3),
(4, 2, 29),
(4, 3, 86),
(4, 4, 166),
(5, 1, 4),
(5, 2, 39),
(5, 3, 121),
(5, 4, 250),
(5, 5, 410),
(6, 1, 5),
(6, 2, 49),
(6, 3, 156),
(6, 4, 334),
(6, 5, 575),
(6, 6, 855),
)
@pytest.mark.parametrize('n,m,expect', _test_diagonals)
def test_diagonals(n, m, expect):
assert expect == diagonals(n, m)
_test_solve = (
(3, 2, 72),
(4, 3, 422),
(5, 3, 736),
(6, 4, 2584),
(6, 8, 17248),
)
@pytest.mark.parametrize('n,m,expect', _test_solve)
def test_solve(n, m, expect):
assert expect == solve(n, m)