I initially got the wrong answer for this problem. That doesn’t happen all too
often for me, so it was definitely a new and interesting challenge! What I was
doing wrong initially was that I was attepting to memoize my _m closure.
This wouldn’t work since a later search with the same inputs could yield a
smaller result. It’s not guaranteed that each input has a single value for its
output. I was able to uncover my mistake by writing tests for ever number
between 1 and 200 that pass when memoized. I then ran the tests again without
memoization (very slowly) and saw some fail. This is how I knew I was wrong.
Instead, the solution still searches everything in a depth first manner,
however, it stops and returns early if the answer would be larger than one
already found. That saved enough time for the program to run in a reasonable
amount of time: 45 seconds with Pypy3.
The search algorithm I used is one very similar to the ones I’ve written when doing integer partitions.
def m(n):
arr = [1] + [0] * (n - 1)
minimal = [float('inf')]
def _m(last, index):
if index == minimal[0]:
return
elif last == n:
minimal[0] = index
return
index += 1
for val in arr[:index]:
this = last + val
if this > n:
return
arr[index] = this
_m(this, index)
_m(1, 0)
return minimal[0]
def solve(n):
total = 0
for k in range(1, n + 1):
total += m(k)
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve, m
_test_m = (
(1, 0),
(2, 1),
(3, 2),
(4, 2),
(5, 3),
(6, 3),
(7, 4),
(8, 3),
(9, 4),
(10, 4),
(11, 5),
(12, 4),
(13, 5),
(14, 5),
(15, 5),
(16, 4),
(17, 5),
(18, 5),
(19, 6),
(20, 5),
(21, 6),
(22, 6),
(23, 6),
(24, 5),
(25, 6),
(26, 6),
(27, 6),
(28, 6),
(29, 7),
(30, 6),
(31, 7),
(32, 5),
(33, 6),
(34, 6),
(35, 7),
(36, 6),
(37, 7),
(38, 7),
(39, 7),
(40, 6),
(41, 7),
(42, 7),
(43, 7),
(44, 7),
(45, 7),
(46, 7),
(47, 8),
(48, 6),
(49, 7),
(50, 7),
(51, 7),
(52, 7),
(53, 8),
(54, 7),
(55, 8),
(56, 7),
(57, 8),
(58, 8),
(59, 8),
(60, 7),
(61, 8),
(62, 8),
(63, 8),
(64, 6),
(65, 7),
(66, 7),
(67, 8),
(68, 7),
(69, 8),
(70, 8),
(71, 9),
(72, 7),
(73, 8),
(74, 8),
(75, 8),
(76, 8),
(77, 8),
(78, 8),
(79, 9),
(80, 7),
(81, 8),
(82, 8),
(83, 8),
(84, 8),
(85, 8),
(86, 8),
(87, 9),
(88, 8),
(89, 9),
)
@pytest.mark.parametrize('n,expect', _test_m)
def test_m(n, expect):
assert expect == m(n)
_test_solve = (
(1, 0),
(2, 1),
(3, 3),
(4, 5),
(5, 8),
(6, 11),
(7, 15),
(8, 18),
(9, 22),
(10, 26),
(11, 31),
(12, 35),
(13, 40),
(14, 45),
(15, 50),
(20, 75),
(25, 104),
(30, 135),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)