prize strings problem 191 a particular school offers cash rewards to children with good attendance and punctuality if they are absent for three consecutive days or late on more than one occasion then they forfeit their prize during an nday period a trinary string is formed for each child consisting of l s late o s on time and a s absent although there are eightyone trinary strings for a 4day period that can be formed exactly fortythree strings would lead to a prize oooo oooa oool ooao ooaa ooal oolo oola oaoo oaoa oaol oaao oaal oalo oala oloo oloa olao olaa aooo aooa aool aoao aoaa aoal aolo aola aaoo aaoa aaol aalo aala aloo aloa alao alaa looo looa loao loaa laoo laoa laao how many prize strings exist over a 30day period references the original project euler project page https projecteuler netproblem191 a small helper function for the recursion mainly to have a clean interface for the solution function below it should get called with the number of days corresponding to the desired length of the prize strings and the initial values for the number of consecutive absent days and number of total late days calculatedays4 absent0 late0 43 calculatedays30 absent2 late0 0 calculatedays30 absent1 late0 98950096 if we are absent twice or late 3 consecutive days no further prize strings are possible if we have no days left and have not failed any other rules we have a prize string no easy solution so now we need to do the recursive calculation first check if the combination is already in the cache and if yes return the stored value from there since we already know the number of possible prize strings from this point on now we calculate the three possible ways that can unfold from this point on depending on our attendance today 1 if we are late but not absent the absent counter stays as it is but the late counter increases by one 2 if we are absent the absent counter increases by 1 and the late counter resets to 0 3 if we are on time this resets the late counter and keeps the absent counter returns the number of possible prize strings for a particular number of days using a simple recursive function with caching to speed it up solution 1918080160 solution4 43 a small helper function for the recursion mainly to have a clean interface for the solution function below it should get called with the number of days corresponding to the desired length of the prize strings and the initial values for the number of consecutive absent days and number of total late days _calculate days 4 absent 0 late 0 43 _calculate days 30 absent 2 late 0 0 _calculate days 30 absent 1 late 0 98950096 if we are absent twice or late 3 consecutive days no further prize strings are possible if we have no days left and have not failed any other rules we have a prize string no easy solution so now we need to do the recursive calculation first check if the combination is already in the cache and if yes return the stored value from there since we already know the number of possible prize strings from this point on now we calculate the three possible ways that can unfold from this point on depending on our attendance today 1 if we are late but not absent the absent counter stays as it is but the late counter increases by one 2 if we are absent the absent counter increases by 1 and the late counter resets to 0 3 if we are on time this resets the late counter and keeps the absent counter returns the number of possible prize strings for a particular number of days using a simple recursive function with caching to speed it up solution 1918080160 solution 4 43
cache: dict[tuple[int, int, int], int] = {}


def _calculate(days: int, absent: int, late: int) -> int:
    

    
    
    if late == 3 or absent == 2:
        return 0

    
    
    if days == 0:
        return 1

    

    
    
    
    key = (days, absent, late)
    if key in cache:
        return cache[key]

    
    

    
    
    state_late = _calculate(days - 1, absent, late + 1)

    
    
    state_absent = _calculate(days - 1, absent + 1, 0)

    
    
    state_ontime = _calculate(days - 1, absent, 0)

    prizestrings = state_late + state_absent + state_ontime

    cache[key] = prizestrings
    return prizestrings


def solution(days: int = 30) -> int:
    

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


if __name__ == "__main__":
    print(solution())