Skip to content

Instantly share code, notes, and snippets.

@felipegtx
Last active December 20, 2015 09:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save felipegtx/6106974 to your computer and use it in GitHub Desktop.
Save felipegtx/6106974 to your computer and use it in GitHub Desktop.
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace YCombinatorCSharp
{
class Program
{
static void Main(string[] args)
{
var stp = new Stopwatch();
stp.Start();
////Simple recursion
//Console.WriteLine(Use.FibonacciSimples(40));
////Y w/ cache
//Console.WriteLine(Use.YCache(Use.FibonaccY)(40));
////Y w/t cache
//Console.WriteLine(Use.Y(Use.FibonaccY)(40));
stp.Stop();
Console.WriteLine(stp.ElapsedMilliseconds);
Console.ReadLine();
}
}
public class Use
{
public static Func<decimal, decimal> YCache(Func<Func<decimal, decimal>, Func<decimal, decimal>> f, Dictionary<decimal, decimal> cache = null)
{
if (cache == null) { cache = new Dictionary<decimal, decimal>(); }
return i =>
{
decimal result;
if (!cache.TryGetValue(i, out result))
{
var r = f(n => YCache(f, cache)(n))(i);
cache.Add(i, result = r);
}
return result;
};
}
public static Func<decimal, decimal> Y(Func<Func<decimal, decimal>, Func<decimal, decimal>> f)
{
Func<Func<dynamic, Func<decimal, decimal>>, Func<decimal, decimal>> _ = x => f(x1 => x(x)(x1));
return _(x => f(y => x(x)(y)));
}
public static Func<decimal, decimal> FibonaccY(Func<decimal, decimal> f)
{
return n =>
{
return n < 2 ? n : (f(n - 1) + f(n - 2));
};
}
public static long FibonacciSimples(long n)
{
return n < 2 ? n : (FibonacciSimples(n - 1) + FibonacciSimples(n - 2));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment