@@ -0,0 +1,1866 @@
+%22%22%22%0AA row of five black square tiles is to have a number of its tiles replaced with%0Acoloured oblong tiles chosen from red (length two), green (length three), or%0Ablue (length four).%0A%0AIf red tiles are chosen there are exactly seven ways this can be done. If%0Agreen tiles are chosen there are three ways. And if blue tiles are chosen%0Athere are two ways.%0A%0AAssuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of%0Areplacing the black tiles in a row measuring five units in length.%0A%0AHow many different ways can the black tiles in a row measuring fifty units in%0Alength be replaced if colours cannot be mixed and at least one coloured tile%0Amust be used?%0A%0ANOTE: This is related to Problem 117.%0A%0A%0ASolution comment: Very fast, ~1 ms. Very similar to 114, only now the blocks%0Ahave a fixed size, not a minimum size. This actually only makes things simpler,%0Aand faster. One important note is that at least one colour must be used, so the%0Atrivial solution should not be counted for the total length. It still needs to%0Abe counted in the subproblems though for the algo. to work. So this extra 1 is%0Asubtracted afterwards. Then we simply do the whole thing for the different%0Ablocks and sum it up.%0A%22%22%22%0A%0Afrom time import time%0Afrom functools import lru_cache%0Afrom itertools import count%0A%0A@lru_cache(maxsize=None)%0Adef ways(N, m):%0A    w = 1   # The trivial solution is always possible.%0A    if N %3E= m:%0A        for offset in range(N - m + 1):  # Start placing block at each offset.%0A            n = N - offset               # The remaining units after the offset.%0A            w += ways(n - m, m)          # Add number of ways to fill the rest.%0A    return w%0A%0Adef actual_ways(N):%0A    return sum(ways(N, m) - 1 for m in %5B2, 3, 4%5D)%0A%0Aif __name__ == %22__main__%22:%0A    t0 = time()%0A%0A    print('Answer:', actual_ways(50))%0A%0A    print('Execution time: %7B:.3f%7D ms'.format((time() - t0) * 1e3))%0A

Add solution to 116.