|
| 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() = }") |
0 commit comments