aboutsummaryrefslogtreecommitdiff
path: root/tools
diff options
context:
space:
mode:
Diffstat (limited to 'tools')
-rw-r--r--tools/ackermann.c38
-rwxr-xr-xtools/ackermann.py34
-rwxr-xr-xtools/orb_maze.py (renamed from tools/maze.py)0
3 files changed, 38 insertions, 34 deletions
diff --git a/tools/ackermann.c b/tools/ackermann.c
new file mode 100644
index 0000000..5ab25f7
--- /dev/null
+++ b/tools/ackermann.c
@@ -0,0 +1,38 @@
+// synacor challenge (@waffle87)
+#include <stdio.h>
+#include <stdlib.h>
+
+int ackermann(int m, int n, int k, int **memo) {
+ if (memo[m][n] != -1)
+ return memo[m][n];
+ int res;
+ if (!m)
+ res = (n + 1) % 32768;
+ else if (!n)
+ res = ackermann(m - 1, k, k, memo);
+ else
+ res = ackermann(m - 1, ackermann(m, n - 1, k, memo), k, memo);
+ memo[m][n] = res;
+ return memo[m][n];
+}
+
+int main() {
+ int **memo = malloc(sizeof(int *) * 5);
+ for (int i = 0; i < 5; i++)
+ memo[i] = malloc(sizeof(int) * 32768);
+ for (int i = 1; i < 32768; i++) {
+ for (int j = 0; j < 5; j++)
+ for (int k = 0; k < 32768; k++)
+ memo[j][k] = -1;
+ int res = ackermann(4, 1, i, memo);
+ printf("checking %d -> %d\n", i, res);
+ if (res == 6) {
+ printf("\nregister value: %d\n", i);
+ break;
+ }
+ }
+ for (int i = 0; i < 5; i++)
+ free(memo[i]);
+ free(memo);
+ return 0;
+}
diff --git a/tools/ackermann.py b/tools/ackermann.py
deleted file mode 100755
index 01c90fa..0000000
--- a/tools/ackermann.py
+++ /dev/null
@@ -1,34 +0,0 @@
-#!/usr/bin/env python
-
-
-def ackermann(a, b, c):
- stack = [(a, b)]
- res = 0
- while stack:
- a, b = stack.pop()
- if a == 0:
- res = b + 1
- elif a == 1:
- res = b + c + 1
- elif a == 2:
- res = (b + 2) * c + (b + 1)
- elif b == 0:
- stack.append((a - 1, c))
- else:
- stack.append((a, b - 1))
- stack.append((a - 1, b))
- return res
-
-
-def check_ack():
- for i in range(32768):
- print("checking:", i)
- res = ackermann(4, 1, i) % 32768
- if res == 6:
- return i
- return -1
-
-
-if __name__ == "__main__":
- res = check_ack()
- print("magic number:", res)
diff --git a/tools/maze.py b/tools/orb_maze.py
index fa2ab2f..fa2ab2f 100755
--- a/tools/maze.py
+++ b/tools/orb_maze.py