From 4cb2aa155ce9618c265a0edcda30d2ba2132baac Mon Sep 17 00:00:00 2001 From: Jean-Pierre Appel Date: Mon, 23 Oct 2023 01:50:10 -0400 Subject: fixed import names, added startup script --- server/fast_p.py | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 server/fast_p.py (limited to 'server/fast_p.py') diff --git a/server/fast_p.py b/server/fast_p.py new file mode 100644 index 0000000..54902ad --- /dev/null +++ b/server/fast_p.py @@ -0,0 +1,35 @@ +hashStuff = {0: 0, 1: 1, 2: 1, 3: 1, 4: 2, 5: 2} + + +def MEX(S: set) -> int: + i = 0 + while True: + if i not in S: + return i + i += 1 + + +def P(n: int) -> int: + """ + Compute nimber for a path of a certain length + """ + if n in hashStuff: + return hashStuff[n] + res = Prec(n) + hashStuff[n] = res + return res + + +def Prec(n: int) -> int: + S = set() + # Works only for n >= 5 + S.add(P(n-2)) + S.add(P(n-3)) + S.add(P(n-4)) + for i in range(2, n-5+1): + S.add(nimAdd(P(i), P(n-3-i))) + return MEX(S) + + +def nimAdd(x: int, y: int) -> int: + return x ^ y -- cgit v1.2.3