Student Attendance Record III.md

There is student attendance information that has 3 state.

O: attendance
L: late
A: absent

If student is "absent two days in total" OR "late three days in a row", student get penalty.

There are 8 ways that student get penalty in 3 days.

LLL   AAO   AOA   OAA   AAL
ALA   LAA   AAA

Thete are 38 ways that student get penalty in 4 days

AAOO   AAOL   AALO   AALL   AOAO
AOAL   ALAO   ALAL   AOOA   AOLA
ALOA   ALLA   OAAO   OAAL   LAAO
LAAL   OAOA   OALA   LAOA   LALA
OOAA   OLAA   LOAA   LLAA   AAAO
AAAL   AAOA   AALA   AOAA   ALAA
OAAA   LAAA   AAAA   LLLO LLLA
OLLL   ALLL   LLLL

Qustion.
One semester is N days. Given an integer N, generate the number of ways that student get penalty.

Example 1.
Input : 3
Output : 8

Example 2.
Input : 4
Output : 38

(If there is error in example , feel free to comment! I will fix it :) Thanks)

My code:

#import numpy as np
def call_zPen(N,i):
    #Define zPen(i, j) := the number of ways to attend i days with A = 0 without penalty, while the last j days are L. Thus 0 <= j < 3.
    if N<0:
        return 0
    if N>overN:
        return 0
    #print(N)
    #print(i)
    if record[N][i]!=-1:
        return record[N][i]
    if i==0:
        record[N][i]=call_zPen(N-1,i)+call_zPen(N-1,i+1)+call_zPen(N-1,i+2)
    elif i==1:
        record[N][i]=call_zPen(N-1,i-1)
    elif i==2:
        record[N][i]=call_zPen(N-1,i-1)
    return record[N][i]
def zPen(i):
    if i<=0:
        return 1
    return call_zPen(i-1,0)+call_zPen(i-1,1)+call_zPen(i-1,2)
def noPen(N):
    retval = 0
    for i in range(1, N+1): # calculate the partitions for when the kid misses exactly one day
        retval += zPen(i-1) * zPen(N - i)
        print('i %d retval %d'%(i,retval))
    retval += zPen(N)    # For when the kid misses zero days
    return retval
global record
global overN
N=5
record=[[-1]*3 for i in range(N)]#Init
overN=N
record[0][0]=1
record[0][1]=1
record[0][2]=0
record[1][0]=2
record[1][1]=1
record[1][2]=1

print(3**N-noPen(N))
print(record)

Their code:

    public static int waysToGetPenalty(int days){
        return getPenaltyWays(days, 1, '#', '#', 0, false);
    }

    private static int getPenaltyWays(int days, int currDay, char prev, char prev2, 
            int aCount, boolean penalty) {
        if(currDay > days){
            if(penalty){
                return 1;
            }
            return 0;
        }

        int count = 0;
        // add L
        count += getPenaltyWays(days, currDay + 1, 'L', prev, aCount, 
        penalty || (prev == 'L' && prev2 == 'L'));

        // add O
        count += getPenaltyWays(days, currDay + 1, 'O', prev, aCount, 
        penalty);

        // add A
        count += getPenaltyWays(days, currDay + 1, 'A', prev, aCount + 1, 
        penalty || (aCount + 1 >= 2));

        return count;
    }

Solution: https://leetcode.com/discuss/interview-question/130159/Google-onsite-interview-question