LeetCode 552: Student Attendance Record II

I'm posting my code for a LeetCode problem copied here. If you have time and would like to golf for a short solution, please do so.

Requirement

• It has to only pass the LeetCode's Online Judge, if the language would be available.

• If the language is not available, simply we should possibly keep the class Solution as well as the function name.

Languages and Version Notes

Available languages are:

• C++ clang 9 Uses the C++17 standard.
• Java 13.0.1
• Python 2.7.12
• Python3 3.8
• C gcc 8.2
• C# 8.0
• JavaScript 14.3.0
• Ruby 2.4.5
• Bash 4.3.30
• Swift 5.0.1
• Go 1.13
• Scala 2.13
• Kotlin 1.3.10
• Rust 1.40.0
• PHP 7.2

Thank you!

Problem

Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 10 ^ 9 + 7.

A student attendance record is a string that only contains the following three characters:

• 'A' : Absent.
• 'L' : Late.
• 'P' : Present.

A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

• Input: n = 2
• Output: 8

Explanation:

There are 8 records with length 2 will be regarded as rewardable:

• "PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"

• Only "AA" won't be regarded as rewardable owing to more than one absent times.

• Note: The value of n won't exceed 100,000.

Accepted Code

class Solution:
def checkRecord(self, n):
MOD = 1000000007
a = b = d = 1
c = e = f = 0
for _ in range(n - 1):
a, b, c, d, e, f = (a + b + c) % MOD, a, b, (a + b + c + d + e + f) % MOD, d, e

return (a + b + c + d + e + f) % MOD


Accepted Golf Attempt in Python 3 - 185 bytes - I

class Solution:
def checkRecord(self,n):
M=1000000007;a=b=d=1;c=e=f=0
for _ in range(n-1):a,b,c,d,e,f=(a+b+c)%M,a,b,(a+b+c+d+e+f)%M,d,e
return(a+b+c+d+e+f)%M


Accepted Golf Attempt in Python 3 - 185 bytes - II

class Solution:
def checkRecord(self,n):
M=int(1e9+7);a=b=d=1;c=e=f=0
for _ in range(n-1):a,b,c,d,e,f=(a+b+c)%M,a,b,(a+b+c+d+e+f)%M,d,e
return(a+b+c+d+e+f)%M


Reference

In LeetCode's answer template, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

• I appreciate you being open with crediting the problem LeetCode and providing a link to it. But I still wonder if the site or challenge author would be OK with having the problem here. It also makes a lot of answers be easy to Google. – xnor Jun 24 at 11:52
• As a code golf challenge, this has lots of things we consider Things to Avoid on the site, with the lengthy boilerplate names and the programming chestnut of 10^7+9. It's also not ideal that to know if a solution is fast enough to pass I have to run it on another site. As a tips question, this all of course all makes sense to help you with a challenge from elsewhere. I think though that we'd do better to help if you explain how your code works and what you've tried, and limit to your one language. – xnor Jun 24 at 12:02
• This surely won't scale to inputs like n=10^6 within the needed runtime, but here's a short and nifty purely integer-arithmetic expression based on generating functions: Try it online!. This is only partly golfed and doesn't have the mod 1e9+7. For larger input n, you'll need L to at least n, and B to at least the output. – xnor Jun 24 at 13:49
• If anyone wants it, the generating function (formal power series) is pretty nice: $(1+x+x^2)/(1-x-x^2-x^3)^2$. – xnor Jun 24 at 14:53

Tips:

1. The first argument self can be renamed to something shorter.
2. Use while n:n-=1 to loop n times
3. (Python 2 specific) You can use a single tab for the second level of indentation, instead of 2 spaces.
4. For this problem, it's sufficiently fast to just mod b every loop, instead of having to mod both a and d.
5. The part a,b,c,d,e,f=... can be broken into a,b,c=...;d,e,f=..., which allows reusing the updated value a=a+b+c
6. c,e,f can be initialized to 10**9+7 instead of 0 (found by @xnor).

Python 2, 136 134 131 127 125 bytes

class Solution:
def checkRecord(_,n):
a=b=d=1;c=e=f=M=10**9+7
while n:n-=1;a,b,c=a+b+c,a%M,b;d,e,f=a+d+e+f,d,e
return d%M


Try it online!

• exec('a,b,c=a+b+c,a%M,b;d,e,f=a+d+e+f,d,e;'*n) saves 2 over the while loop. EDIT, actually 6 as it allows inlining too: def checkRecord(_,n):M=10**9+7;a=b=d=1;c=e=f=0;exec('a,b,c=a+b+c,a%M,b;d,e,f=a+d+e+f,d,e;'*n);return d%M. – Jonathan Allan Jun 24 at 11:11
• @JonathanAllan thanks, I did consider using exec, but it's too slow for large n due to the construction of really long string. – Surculose Sputum Jun 24 at 11:55
• Haven't check this on Leetcode, but it looks like you can initialize c=e=f=M=10**9+7 since we're working mod M anyway. – xnor Jun 24 at 12:47
• @xnor That works, thanks! – Surculose Sputum Jun 24 at 12:54
1. You don't need more than one space per level of indentation.
2. Observe that you have (a+b+c+d+e+f) used twice. This code duplication can be avoided by running the loop one more time and using d of the extra iteration
3. [0]*n is 3 bytes shorter than range(n)
4. It's not necessary to modulo by 1000000007 each time; you can remove it from the loop and only do it at the end (This takes about 1 second for n=100000 on TIO, which appears to be too slow). After this, M will only be used once, so you can inline it into the one place it was used

Python 3, 136 bytes

class Solution:
def checkRecord(self,n):
a=b=d=1;c=e=f=0
for _ in [0]*n:a,b,c,d,e,f=a+b+c,a,b,a+b+c+d+e+f,d,e
return d%int(1e9+7)


Try it online!

Or, if the last tip is too slow:

Python 3, 148 bytes

class Solution:
def checkRecord(self,n):
M=int(1e9+7);a=b=d=1;c=e=f=0
for _ in [0]*n:a,b,c,d,e,f=(a+b+c)%M,a,b,(a+b+c+d+e+f)%M,d,e
return d%M


Try it online!

• @pppery you can rename self to something with 1 character, and remove the space after in: for _ in[0]*n. If you switch to Python 2, you can use a single tab instead of 2 spaces for the second level of indent. – Surculose Sputum Jun 23 at 18:08
• @SurculoseSputum This is a tips question, so I think that would be better as a separate answer. – pppery Jun 23 at 18:09
• @pppery gotcha, I'll post a separate answer. – Surculose Sputum Jun 23 at 18:30
• You can remove the space at in[0] in both your functions. – Kevin Cruijssen Jun 24 at 12:46
• @KevinCruijssen This is a tips question, so that tip should be a separate answer. I will not be editing any other users' golfing suggestions into this answer, because I feel that defeats the point of tips. – pppery Jun 24 at 13:45

C (gcc), 121 bytes

checkRecord(n){long a=1,b=1,d=1,c=0,e=0,f=0,x,y,m=7+1e9;for(;n--;d=y%m)x=a+b+c,y=x+d+e+f,f=e,e=d,c=b,b=a,a=x%m;return d;}


Try it online!

Slightly golfed less

checkRecord(n){
long a=1,b=1,d=1,c=0,e=0,f=0,x,y,m=7+1e9;
for(;n--;d=y%m)
x=a+b+c,
y=x+d+e+f,
f=e,
e=d,
c=b,
b=a,
a=x%m;
return d;
}


Python 2, 127126 119 bytes

class Solution:
def checkRecord(s,n):
a=[1,0,0]
while~n:n-=1;a=[sum(a[:3])]+a;b=a[3]=sum(a[1:7])%(10**9+7)
return b


Try it online! Somewhat slower than @SurculoseSputum's answer. Edit: Saved 1 byte thanks to @KevinCruijssen. Saved a further 7 bytes thanks to @xnor.

Out of interest, I also wrote a 34-byte solution in Charcoal:

≔Ｅ⁶¬ιηＦＮＵＭη⎇﹪λ³§η⊖λΣ…η⁺³λＩ﹪Ση⁺⁷Ｘφ³


Try it online! Link is to verbose version of code. Explanation:

≔Ｅ⁶¬ιη


Create an array of six elements where only the first element is 1 and the others are all 0.

ＦＮ


Loop over the given number of times.

ＵＭη


Modify the array in-place according to the result of the mapping (the mapping is calculated first, then the array modified).

⎇﹪λ³


For positions 1, 2, 4 and 5:

§η⊖λ


Take the previous element of the previous array.

Σ…η⁺³λ


Otherwise take the sum of the array so far plus the next three elements.

This results in h = [sum(h[0:3]), h[0], h[1], sum(h), h[3], h[4]].

Ｉ﹪Ση⁺⁷Ｘφ³


Take the final sum and reduce modulo 7+1000**3.

• You can remove the space at in[0] for -1 in the Python function. – Kevin Cruijssen Jun 24 at 12:45
• @KevinCruijssen ... I was just pasting that in, but I'll be generous and credit you anyway. – Neil Jun 24 at 12:47
• Nice solution, here's a couple more saves: Try it online! (fixed) – xnor Jun 24 at 12:51
• 119: Try it online! – xnor Jun 24 at 12:57
• @Emma You can make it much faster at a cost of 4 bytes by adding [:5]: after the +a. – Neil Jun 24 at 15:03

Java, 137 bytes

long checkRecord(int n){long a=1,b=1,c=0,d=1,e=0,f=0,x,y,m=7+(int)1e9;for(;n-->0;y=x+d+e+f,f=e,e=d,c=b,b=a,a=x%m,d=y%m)x=a+b+c;return d;}


Figured I'd add a Java answer, since it was missing. It's a straightforward port of @ceilingcat's C answer, since I couldn't find anything shorter.

Try it online.

05AB1E, 24 23 bytes

6LΘIFÐÁr3£‚O30Sǝ}O9°7+%


Try it online.

Explanation:

6L                # Push the list [1,2,3,4,5,6]
Θ               # Check == 1 for each (1 if truthy; 0 if falsey): [1,0,0,0,0,0]
IF             # Loop the input amount of times:
Ð            #  Triplicate the list at the top of the stack
Á           #  Rotate the top list once towards the right: [f,a,b,c,d,e]
r          #  Reverse the stack so this rotated list is at the bottom
3£        #  Pop and push the first three items of the top list: [a,b,c]
‚       #  Pair it with the full list: [[a,b,c,d,e,f],[a,b,c]]
O      #  Sum both inner lists: [a+b+c+d+e+f,a+b+c]
30S   #  Push [3,0]
ǝ  #  Insert the a+b+c+d+e+f and a+b+c at indices 3 and 0 respectively in
#  the rotated list: [a+b+c,a,b,a+b+c+d+e+f,d,e]
}O            # After the loop, sum the resulting list
9°          # Push 10 to the power 9: 1000000000
7+        # Add 7: 1000000007
%       # Modulo
# (after which the result is output implicitly)


x86_64 machine language for Linux, 83 bytes

0x00:  55                push rbp
0x01:  45 31 C0          xor  r8d, r8d
0x04:  31 C9             xor  ecx, ecx
0x06:  53                push rbx
0x07:  6A 01             push 1
0x09:  41 5A             pop  r10
0x0b:  31 DB             xor  ebx, ebx         ; a=b=d=0
0x0d:  4D 89 D1          mov  r9, r10
0x10:  4D 89 D3          mov  r11, r10         ; c=e=f=1
0x13:  BE 07 CA 9A 3B    mov  esi, 0x3b9aca07  ; m=1000000007
0x18:  4B 8D 04 0B       lea  rax, [r11 + r9]
0x1c:  48 01 C8          add  rax, rcx         ; x=a+b+c
0x1f:  48 99             cqo
0x21:  49 8D 0C 02       lea  rcx, [r10 + rax]
0x25:  48 F7 FE          idiv rsi              ; x%=m
0x28:  4C 01 C1          add  rcx, r8
0x2b:  48 01 D9          add  rcx, rbx         ; y=x+d+e+f
0x2e:  4C 89 C3          mov  rbx, r8          ; f=e
0x31:  48 89 C8          mov  rax, rcx         ; e=d
0x34:  4C 89 C9          mov  rcx, r9          ; c=b
0x37:  48 89 D5          mov  rbp, rdx         ; b=a
0x3a:  48 99             cqo
0x3c:  48 F7 FE          idiv rsi              ; y%=m
0x3f:  4D 89 D0          mov  r8, r10
0x42:  4D 89 D9          mov  r9, r11
0x45:  49 89 D2          mov  r10, rdx         ; d=y
0x48:  49 89 EB          mov  r11, rbp         ; a=x
0x4b:  FF CF             dec  edi
0x4d:  75 C9             jne  0x18             ; if( --n ) goto 0x18
0x4f:  92                xchg eax, edx
0x50:  5B                pop  rbx
0x51:  5D                pop  rbp
0x52:  C3                ret                   ; return d


To Try it online!, call the following c code as if it were a function (you may also be able to paste it into one or more 'interview preparation websites' and run it as if it were a c program)

(*checkRecord)()=L"\xc0314555\x6a53c931\x315a4101\xd1894ddb\xbed3894d\x3b9aca07\x0b048d4b\x48c80148\x0c8d4999\xfef74802\x48c1014c\x894cd901\xc88948c3\x48c9894c\x9948d589\x4dfef748\x894dd089\xd28949d9\xffeb8949\x92c975cf\xc35d5b";