TheAlgorithms-Python

1
"""
2
Prize Strings
3
Problem 191
4

5
A particular school offers cash rewards to children with good attendance and
6
punctuality. If they are absent for three consecutive days or late on more
7
than one occasion then they forfeit their prize.
8

9
During an n-day period a trinary string is formed for each child consisting
10
of L's (late), O's (on time), and A's (absent).
11

12
Although there are eighty-one trinary strings for a 4-day period that can be
13
formed, exactly forty-three strings would lead to a prize:
14

15
OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
16
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
17
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
18
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
19
LAOO LAOA LAAO
20

21
How many "prize" strings exist over a 30-day period?
22

23
References:
24
    - The original Project Euler project page:
25
      https://projecteuler.net/problem=191
26
"""
27

28
cache: dict[tuple[int, int, int], int] = {}
29

30

31
def _calculate(days: int, absent: int, late: int) -> int:
32
    """
33
    A small helper function for the recursion, mainly to have
34
    a clean interface for the solution() function below.
35

36
    It should get called with the number of days (corresponding
37
    to the desired length of the 'prize strings'), and the
38
    initial values for the number of consecutive absent days and
39
    number of total late days.
40

41
    >>> _calculate(days=4, absent=0, late=0)
42
    43
43
    >>> _calculate(days=30, absent=2, late=0)
44
    0
45
    >>> _calculate(days=30, absent=1, late=0)
46
    98950096
47
    """
48

49
    # if we are absent twice, or late 3 consecutive days,
50
    # no further prize strings are possible
51
    if late == 3 or absent == 2:
52
        return 0
53

54
    # if we have no days left, and have not failed any other rules,
55
    # we have a prize string
56
    if days == 0:
57
        return 1
58

59
    # No easy solution, so now we need to do the recursive calculation
60

61
    # First, check if the combination is already in the cache, and
62
    # if yes, return the stored value from there since we already
63
    # know the number of possible prize strings from this point on
64
    key = (days, absent, late)
65
    if key in cache:
66
        return cache[key]
67

68
    # now we calculate the three possible ways that can unfold from
69
    # this point on, depending on our attendance today
70

71
    # 1) if we are late (but not absent), the "absent" counter stays as
72
    # it is, but the "late" counter increases by one
73
    state_late = _calculate(days - 1, absent, late + 1)
74

75
    # 2) if we are absent, the "absent" counter increases by 1, and the
76
    # "late" counter resets to 0
77
    state_absent = _calculate(days - 1, absent + 1, 0)
78

79
    # 3) if we are on time, this resets the "late" counter and keeps the
80
    # absent counter
81
    state_ontime = _calculate(days - 1, absent, 0)
82

83
    prizestrings = state_late + state_absent + state_ontime
84

85
    cache[key] = prizestrings
86
    return prizestrings
87

88

89
def solution(days: int = 30) -> int:
90
    """
91
    Returns the number of possible prize strings for a particular number
92
    of days, using a simple recursive function with caching to speed it up.
93

94
    >>> solution()
95
    1918080160
96
    >>> solution(4)
97
    43
98
    """
99

100
    return _calculate(days, absent=0, late=0)
101

102

103
if __name__ == "__main__":
104
    print(solution())
105