TheAlgorithms-Python

1
"""
2
Project Euler Problem 114: https://projecteuler.net/problem=114
3

4
A row measuring seven units in length has red blocks with a minimum length
5
of three units placed on it, such that any two red blocks
6
(which are allowed to be different lengths) are separated by at least one grey square.
7
There are exactly seventeen ways of doing this.
8

9
    |g|g|g|g|g|g|g|    |r,r,r|g|g|g|g|
10

11
    |g|r,r,r|g|g|g|    |g|g|r,r,r|g|g|
12

13
    |g|g|g|r,r,r|g|    |g|g|g|g|r,r,r|
14

15
    |r,r,r|g|r,r,r|    |r,r,r,r|g|g|g|
16

17
    |g|r,r,r,r|g|g|    |g|g|r,r,r,r|g|
18

19
    |g|g|g|r,r,r,r|    |r,r,r,r,r|g|g|
20

21
    |g|r,r,r,r,r|g|    |g|g|r,r,r,r,r|
22

23
    |r,r,r,r,r,r|g|    |g|r,r,r,r,r,r|
24

25
    |r,r,r,r,r,r,r|
26

27
How many ways can a row measuring fifty units in length be filled?
28

29
NOTE: Although the example above does not lend itself to the possibility,
30
in general it is permitted to mix block sizes. For example,
31
on a row measuring eight units in length you could use red (3), grey (1), and red (4).
32
"""
33

34

35
def solution(length: int = 50) -> int:
36
    """
37
    Returns the number of ways a row of the given length can be filled
38

39
    >>> solution(7)
40
    17
41
    """
42

43
    ways_number = [1] * (length + 1)
44

45
    for row_length in range(3, length + 1):
46
        for block_length in range(3, row_length + 1):
47
            for block_start in range(row_length - block_length):
48
                ways_number[row_length] += ways_number[
49
                    row_length - block_start - block_length - 1
50
                ]
51

52
            ways_number[row_length] += 1
53

54
    return ways_number[length]
55

56

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