project euler problem 116 https projecteuler netproblem116 a row of five grey square tiles is to have a number of its tiles replaced with coloured oblong tiles chosen from red length two green length three or blue length four if red tiles are chosen there are exactly seven ways this can be done red redgreygreygrey greyred redgreygrey greygreyred redgrey greygreygreyred red red redred redgrey red redgreyred red greyred redred red if green tiles are chosen there are three ways green green greengreygrey greygreen green greengrey greygreygreen green green and if blue tiles are chosen there are two ways blue blue blue bluegrey greyblue blue blue blue assuming that colours cannot be mixed there are 7 3 2 12 ways of replacing the grey tiles in a row measuring five units in length how many different ways can the grey tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used note this is related to problem 117 https projecteuler netproblem117 returns the number of different ways can the grey tiles in a row of the given length be replaced if colours cannot be mixed and at least one coloured tile must be used solution5 12 returns the number of different ways can the grey tiles in a row of the given length be replaced if colours cannot be mixed and at least one coloured tile must be used solution 5 12
def solution(length: int = 50) -> int:
    

    different_colour_ways_number = [[0] * 3 for _ in range(length + 1)]

    for row_length in range(length + 1):
        for tile_length in range(2, 5):
            for tile_start in range(row_length - tile_length + 1):
                different_colour_ways_number[row_length][tile_length - 2] += (
                    different_colour_ways_number[row_length - tile_start - tile_length][
                        tile_length - 2
                    ]
                    + 1
                )

    return sum(different_colour_ways_number[length])


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