synacor_challenge

OSCON Synacor Challenge
git clone https://git.pngu.org/synacor_challenge
Log | Files | Refs | README

ackermann.c (899B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// synacor challenge (jack@pngu.org)
#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;
}