Wednesday, March 14, 2007

Nine number puzzle

One of my collegues at work asked me a 9 number puzzle question that he heard on the radio show "Car Talk" The puzzle is given the numbers 1 to 9, how do you insert 2 minuses and 1 addition so that they add up to 100. So I wrote up a programming solution for this problem: (This is not the best way to do it - one could use memoization for speed up, as well as implement it as a recursive solution. I would also like to make it so that it can take an arbitary number of operators and see if a solution exists). For now here is the solution in C#. The answer to the problem is : 123 - 45 - 67 + 89 = 100 The valid combination was found in 125 tries.
using System;
using System.Collections;

public class Find9NumberSolution
{
    public const string numbers = "123456789";
    public enum Operator
    {
        Add,
        Sub
    }
   
    public static string OperatorToString(Operator op)
    {
        switch(op)
        {
            case Operator.Add:
                return " + ";
            case Operator.Sub:
                return " - ";
        }
        return "";
    }
   
    public static int Operate(Operator op, int v1, int v2)
    {
        int val = 0;
        switch(op)
        {
            case Operator.Add:
                val = v1 + v2;
                break;
            case Operator.Sub:
                val = v1 - v2;
                break;
        }
        return val;
    }
   
    public static bool Calc(Operator first,int l1,
                                Operator second,int l2,
                                    Operator third, int l3,
                                        int targetValue)
    {
        int num1 = int.Parse(numbers.Substring(0,l1+1));
        int num2 = int.Parse(numbers.Substring(l1+1, (l2-l1)));
        int num3 = int.Parse(numbers.Substring(l2+1, (l3-l2)));
        int num4 = int.Parse(numbers.Substring(l3+1));
       
        int val = Operate(first,num1, num2);
        val = Operate(second, val, num3);
        val = Operate(third, val, num4);
       
        if (val == targetValue)
        {
            WL(num1 + OperatorToString(first) + num2 + OperatorToString(second) + num3 + OperatorToString(third) + num4 + " = " + val);
            return true;
        }
        return false;
    }
   
    public static void Main()
    {
        Operator op1 = Operator.Add;
        Operator op2 = Operator.Sub;
        Operator op3 = Operator.Sub;
       
        bool targetValFnd = false;
        int targetVal = 100;
        int len = numbers.Length;
       
        int i,j,k;
        i=j=k=0;
        int count = 0;
        for (i = 0; i < len - 3; i++)
        {
            for (j = i+1; j < len - 2; j++)
            {
                for (k = j+1;k < len-1; k++)
                {
                    count++;
                    if (targetValFnd = Calc(op1,i,op2,j,op3,k,targetVal))
                        break;
                    count++;
                    if (targetValFnd = Calc(op2,i,op3,j,op1,k,targetVal))
                        break;
                    count++;
                    if (targetValFnd = Calc(op2,i,op1,j,op3,k,targetVal))
                        break;
                }
                if (targetValFnd)
                    break;
            }
            if (targetValFnd)
                break;
        }
        WL("Valid combination was found in " + count + " tries.");
        RL();
    }
   
    #region Helper methods

    private static void WL(object text, params object[] args)
    {
        Console.WriteLine(text.ToString(), args);   
    }
   
    private static void RL()
    {
        Console.ReadLine();   
    }
   
    #endregion
}

No comments: