A certain school rewards students for superior attendance and punctuality. The prize is received if there is no more than one lateness and no absence has lasted more than two consecutive days. If a student is late more than once in the specified duration of the award period or is absent three or more days in a row, the student is not eligible for a prize.
Note that multiple latenesses need not be on consecutive days to disentitle an award, but the three disqualifying absences need to be successive to cancel the award.
To keep track of attendance and punctuality for one student, a string of letters is used. For example:
PPPAAPAPPPAALAPPPPAP represents a sequence of Punctual days, Absence days and Lateness days that does qualify for the award, as none of the A's come in a group of three and there is only one lateness.
PPPAAPAPPPAAAPPPPAPL disqualifies the student because of the three absences in a row.
PPPAAPAPPPAALAPPPPAL disqualifies based on two latenesses.
A recent such prize period lasted 12 days. How many strings of 12 are there that would qualify for an award? There are obviously 3^12 possible strings altogether, many of which would not qualify; but how many do qualify?
Adapted from a Project Euler puzzle on-line.
When I saw this was adapted from a Project Euler puzzle, I knew there has to be a more elegant solution than a search (think smarter, not harder).
There is a classic puzzle that asks "How many ways can a 2xN rectangle be tiled (reflections and rotations being distinct) with 1x2 dominos?" The answer to that is the Fibonacci sequence, specifically the answer for a 2xN rectangle is F(N+1).
Ignore the Ls for now. A qualifying string of P and A can be built from blocks of 'P', 'AP', and 'AAP'. Then this is a variant of the classic puzzle mentioned earlier, just using a three term recursion: P(N+1) = P(N) + P(N-1) + P(N-2), with initial conditions P(-2)=0, P(-1)=0, P(0)=1. Then the number of qualifying strings using only A and P of length 12 is P(13)=1705. (Just lop off the extra P at the end of the 13 charater string generated by this method)
Now to add the L. A string with an L can be made from a shorter L string by adding 'P', 'AP', or 'AAP'; alternatively an L string can be formed from a P string by adding 'L', 'AL', or 'AAL'. The L(N+1) = L(N) + L(N-1) + L(N-2) + P(N) + P(N-1) + P(N-2), with initial conditions L(-2)=0, L(-1)=0, L(0)=1, P(-2)=0, P(-1)=0, P(0)=1. Then the number of qualifying strings of length 12 is L(13)=15776. (Again, just lop off the extra P or L from the end of the 13 charater string).
Daniel posted a computer search result of 14071. I think his program assumed exactly one L must be present since his result is the difference between 15776 and 1705.
Solution
