52 lines
1.3 KiB
Python
52 lines
1.3 KiB
Python
from functools import lru_cache
|
|
|
|
|
|
@lru_cache()
|
|
def block_combinations(row_length: int):
|
|
|
|
if row_length == 0:
|
|
return 1
|
|
|
|
min_block_length = 3
|
|
result = 0
|
|
|
|
# Moving from left to right. Let's say we have four spaces (____), then
|
|
# there are three options
|
|
|
|
# Use a blank:
|
|
# -___
|
|
result = block_combinations(row_length - 1)
|
|
|
|
# Or add 3:
|
|
# ooo_
|
|
# For this case, the issue is that if we call block_combinations again with
|
|
# _, then it could happen that we will up with further o and double count.
|
|
# Therefore, for all cases where the spaces are not all filled, we will add
|
|
# a space.
|
|
for new_block in range(min_block_length, row_length):
|
|
result += block_combinations(row_length - new_block - 1)
|
|
|
|
# Or add 4:
|
|
# oooo
|
|
if row_length >= min_block_length:
|
|
result += 1
|
|
|
|
return result
|
|
|
|
|
|
def euler_114():
|
|
assert block_combinations(0) == 1
|
|
assert block_combinations(1) == 1
|
|
assert block_combinations(2) == 1
|
|
assert block_combinations(3) == 2
|
|
assert block_combinations(4) == 4
|
|
assert block_combinations(7) == 17
|
|
return block_combinations(50)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_114()
|
|
print("e114.py: " + str(solution))
|
|
# assert(solution == 0)
|
|
|