FilesExpand file tree

Factorial

/

sol1.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (42 loc) · 1.99 KB

Factorial

/

sol1.py

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (42 loc) · 1.99 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

"""

Project Euler Problem 116: https://projecteuler.net/problem=116

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,red|grey|grey|grey| |grey|red,red|grey|grey|

|grey|grey|red,red|grey| |grey|grey|grey|red,red|

|red,red|red,red|grey| |red,red|grey|red,red|

|grey|red,red|red,red|

If green tiles are chosen there are three ways.

|green,green,green|grey|grey| |grey|green,green,green|grey|

|grey|grey|green,green,green|

And if blue tiles are chosen there are two ways.

|blue,blue,blue,blue|grey| |grey|blue,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.net/problem=117).

"""

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

"""

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

"""

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