project euler problem 115 https projecteuler netproblem115 note this is a more difficult version of problem 114 https projecteuler netproblem114 a row measuring n units in length has red blocks with a minimum length of m units placed on it such that any two red blocks which are allowed to be different lengths are separated by at least one black square let the fillcount function fm n represent the number of ways that a row can be filled for example f3 29 673135 and f3 30 1089155 that is for m 3 it can be seen that n 30 is the smallest value for which the fillcount function first exceeds one million in the same way for m 10 it can be verified that f10 56 880711 and f10 57 1148904 so n 57 is the least value for which the fillcount function first exceeds one million for m 50 find the least value of n for which the fillcount function first exceeds one million returns for given minimum block length the least value of n for which the fillcount function first exceeds one million solution3 30 solution10 57 returns for given minimum block length the least value of n for which the fill count function first exceeds one million solution 3 30 solution 10 57
from itertools import count


def solution(min_block_length: int = 50) -> int:
    

    fill_count_functions = [1] * min_block_length

    for n in count(min_block_length):
        fill_count_functions.append(1)

        for block_length in range(min_block_length, n + 1):
            for block_start in range(n - block_length):
                fill_count_functions[n] += fill_count_functions[
                    n - block_start - block_length - 1
                ]

            fill_count_functions[n] += 1

        if fill_count_functions[n] > 1_000_000:
            break

    return n


if __name__ == "__main__":
    print(f"{solution() = }")