1 files changed, 35 insertions, 0 deletions
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