Skip to content

Instantly share code, notes, and snippets.

@BrianMacIntosh
Last active February 14, 2019 19:34
Show Gist options
  • Save BrianMacIntosh/f2b95ddbd2dffbd71080 to your computer and use it in GitHub Desktop.
Save BrianMacIntosh/f2b95ddbd2dffbd71080 to your computer and use it in GitHub Desktop.
Demo implementation of the Ackermann Function in C# using dynamic programming.
using System;
using System.Threading;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class Program
{
private static int answer;
private static int iterations = 0;
private static int maxdepth = 0;
private struct Key
{
public int m;
public int n;
public Key(int m, int n)
{
this.m = m;
this.n = n;
}
public override bool Equals(object obj)
{
if (obj is Key)
return m == ((Key)obj).m && n == ((Key)obj).n;
else
return false;
}
}
private static Dictionary<Key, int> dynamiclist = new Dictionary<Key, int>();
static void Main(string[] args)
{
Thread t = new Thread(AckermannMain, 512 * 1024 * 1024);
t.Start();
t.Join();
Console.Out.WriteLine("Answer: " + answer);
Console.Out.WriteLine("Iterations: " + iterations);
Console.Out.WriteLine("Max Depth: " + maxdepth);
Console.In.ReadLine();
}
static void AckermannMain()
{
answer = Ackermann(4, 2, 0);
}
static int Ackermann(int m, int n, int depth)
{
Console.Out.WriteLine(depth + "," + m + "," + n);
var key = new Key(m, n);
if (dynamiclist.ContainsKey(key))
return dynamiclist[key];
depth++;
maxdepth = Math.Max(depth, maxdepth);
iterations++;
int retval;
if (m == 0)
retval = n + 1;
else if (m > 0 && n == 0)
retval = Ackermann(m - 1, 1, depth);
else
{
int rec = Ackermann(m, n - 1, depth);
dynamiclist[new Key(m, n - 1)] = rec;
retval = Ackermann(m - 1, rec, depth);
}
dynamiclist[key] = retval;
return retval;
}
}
}
@theejhay
Copy link

cool

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment