Problem 297
completed March 13, 2021Comments
This was another fun dynamic programming problem. I recognized this right away then set about trying to find the best way to recurse. I found an image from the Wikipedia page on Zeckendorf’s theorem incredibly helpful:
It shows how Zeckendorf numbers can be uniquely created for all numbers. Each box has length and width of a Fibonacci number.
I studied this image for a while to look for patterns in how it’s constructed. The answer we are searching for in this problem is the length of all the vertical lines on the right hand side of each rectangle. Knowing this was what I needed to solve for, I was pretty easily able to come up with the solution.
Runs in about 47 milliseconds on Pypy3.
Code
def memoize(fn):
_cache = {}
def wrap(n):
if n in _cache:
return _cache[n]
ret = fn(n)
_cache[n] = ret
return ret
return wrap
def solve(n):
_fibs = [1, 1]
a = b = 1
while b < n:
a, b = b, a + b
_fibs.insert(0, b)
def fib_extra(n):
for f in _fibs:
if f <= n:
return n - f
return 0
def fibs(n):
start = False
for f in _fibs:
if f > n:
continue
if f < n:
if start:
yield f
start = True
@memoize
def search(f):
total = f
for n in fibs(f):
total += search(n)
return total
extra = fib_extra(n)
total = 0
if extra:
total = solve(extra) + extra
for f in fibs(n - extra):
total += search(f)
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
Tests
import pytest
from problem import solve
_test_solve = (
(1, 0),
(2, 1),
(3, 2),
(5, 5),
(8, 10),
(13, 20),
(21, 38),
(34, 71),
(55, 130),
(89, 235),
(144, 420),
(233, 744),
(377, 1308),
(610, 2285),
(987, 3970),
(1597, 6865),
(2584, 11822),
(4181, 20284),
(10**1, 13),
(10**2, 261),
(10**3, 4003),
(10**4, 52810),
(10**5, 658203),
(10**6, 7894453),
(10**7, 92359637),
(10**8, 1061261095),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)