## 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
{
Sub
}

public static string OperatorToString(Operator op)
{
switch(op)
{
return " + ";
case Operator.Sub:
return " - ";
}
return "";
}

public static int Operate(Operator op, int v1, int v2)
{
int val = 0;
switch(op)
{
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 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()
{