Friday 8 June 2012

Countdown - solver in C#

Countdown: presented with six integers they should be combined using the four arithmetic operators +, -, * and / to approach the target as closely as possible. Example code:
using System;
using System.Linq;
using System.Collections.Generic;
using NUnit.Framework;

namespace Test.Unit.Utils
{
    class NonIntegralDivisionResult:Exception {}

    [TestFixture]
    class Countdown
    {
        [Test]
        public static void CountdownTest1()
        {
            var operators = new Dictionary<string, Func<int, int, int>>
                            {
                                {"+", (a, b) => a + b},
                                {"-", (a, b) => a - b},
                                {"*", (a, b) => a*b},
                                {"/", (a, b) =>
                                         {
                                             var resAsDouble = a/(double) b;
                                             var dbl = (double) (a/b);
                                             if (resAsDouble != dbl) throw new NonIntegralDivisionResult();
                                             return a/b;
                                         }
                                    }
                            };
            var startNos = new[] {1, 5, 6, 7, 9, 10};
            var target = 127;

            var result = new Dictionary<int,List<string>>();

            foreach (var num1 in startNos)
                foreach (var op1 in operators)
                    foreach (var num2 in startNos.Except(new[] { num1 }))
                        foreach (var op2 in operators)
                            foreach (var num3 in startNos.Except(new[] { num1, num2 }))
                                foreach (var op3 in operators)
                                    foreach (var num4 in startNos.Except(new[] { num1, num2, num3 }))
                                        foreach (var op4 in operators)
                                            foreach (var num5 in startNos.Except(new[] { num1, num2, num3, num4 }))
                                                foreach (var op5 in operators)
                                                    foreach (var num6 in startNos.Except(new[] { num1, num2, num3, num4, num5 }))
                                                    {
                                                        try
                                                        {
                                                            var value = op5.Value(op4.Value(op3.Value(op2.Value(op1.Value(num1, num2), num3), num4), num5), num6);
                                                            var name = String.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}", num1, op1.Key, num2, op2.Key, num3, op3.Key, num4, op4.Key, num5, op5.Key, num6);
                                                            var key = Math.Abs(value - target);
                                                            if(result.ContainsKey(key)) result[key].Add(name);
                                                            else result.Add(key, new List{name});
                                                        }
                                                        catch(DivideByZeroException) {}
                                                        catch(NonIntegralDivisionResult) {}
                                                    }

            var output = result.OrderBy(kvp => kvp.Key).Take(25);
            foreach(var line in output)
                foreach(var value in line.Value)
                    Console.WriteLine("Key: {0} Value: {1}", line.Key, value);
        }
    }
}