Calculating solutions for the game "24"

Question

I was bored this evening and decided to create a program which calculates all the solutions for a given scenario of the game "24".

The goal of this game is that you try to be the first one to find the answer to a certain card. On the card are four numbers ranging from 1 to 9. The player is allowed to use subtract, add, multiply and divide to reach the number 24 and must use each number only once.

Example: 8,8,5,1 could result in 8-5 = 3, 3*1 = 3, 3 * 8 = 24.

I have put the operators into an enum and the selected numbers are put in a list in the beginning of the method. The following code calculates the solution correctly and in the end selects the unique solutions and puts that into a public property which is displayed.

The method to rule them all:

    private void CalculateSolutions()
    {
        Solutions.Clear();
        var numbers = new List<int>(4) { NumberOne, NumberTwo, NumberThree, NumberFour };
        var solutions = new List<OperatorResult>();

        foreach (Operator operatorOne in Enum.GetValues(typeof (Operator)))
        {
            foreach (Operator operatorTwo in Enum.GetValues(typeof (Operator)))
            {
                foreach (Operator operatorThree in Enum.GetValues(typeof (Operator)))
                {
                    for (var numberOneCounter = 0; numberOneCounter < numbers.Count; numberOneCounter++)
                    {
                        var numberOne = numbers[numberOneCounter];
                        for (var numberTwoCounter = 0; numberTwoCounter < numbers.Count; numberTwoCounter++)
                        {
                            if (numberTwoCounter == numberOneCounter)
                                continue;

                            var numberTwo = numbers[numberTwoCounter];
                            for (var numberThreeCounter = 0;
                                numberThreeCounter < numbers.Count;
                                numberThreeCounter++)
                            {
                                if (numberThreeCounter == numberOneCounter || numberThreeCounter == numberTwoCounter)
                                    continue;

                                var numberThree = numbers[numberThreeCounter];
                                for (var numberFourCounter = 0;
                                    numberFourCounter < numbers.Count;
                                    numberFourCounter++)
                                {
                                    if (numberFourCounter == numberOneCounter ||
                                        numberFourCounter == numberTwoCounter ||
                                        numberFourCounter == numberThreeCounter)
                                        continue;

                                    var numberFour = numbers[numberFourCounter];
                                    var sum = GetTotalSum(numberOne, numberTwo, numberThree, numberFour, operatorOne,
                                        operatorTwo, operatorThree);
                                    if (sum != 24)
                                        continue;

                                    var result = new OperatorResult
                                    {
                                        OperatorOne = operatorOne,
                                        OperatorTwo = operatorTwo,
                                        OperatorThree = operatorThree,
                                        NumberOne = numberOne,
                                        NumberTwo = numberTwo,
                                        NumberThree = numberThree,
                                        NumberFour = numberFour
                                    };
                                    solutions.Add(result);
                                }
                            }
                        }
                    }
                }
            }
        }

        // Select only the unique solutions
        foreach (var solution in OperatorResult.GetUniqueSolutions(solutions))
            Solutions.Add(solution);
    }

The enum:

    public enum Operator
    {
        Multiply = '*',
        Subtract = '-',
        Add = '+',
        Divide = '/'
    }

Solutions property:

    public static DependencyProperty SolutionsProperty = DependencyProperty.Register("Solutions",
        typeof (ObservableCollection<OperatorResult>), typeof (MainWindow));

    public ObservableCollection<OperatorResult> Solutions
    {
        get { return GetValue(SolutionsProperty) as ObservableCollection<OperatorResult>; }
        set { SetValue(SolutionsProperty, value); }
    }

OperatorResult class:

public class OperatorResult
{
    public Operator OperatorOne { get; set; }
    public Operator OperatorTwo { get; set; }
    public Operator OperatorThree { get; set; }
    public int NumberOne { get; set; }
    public int NumberTwo { get; set; }
    public int NumberThree { get; set; }
    public int NumberFour { get; set; }

    /// <summary>
    /// Gets the unique solutions.
    /// </summary>
    /// <param name="solutions">The solutions.</param>
    public static IEnumerable<OperatorResult> GetUniqueSolutions(List<OperatorResult> solutions)
    {
        var uniqueSolutions = new List<OperatorResult>();
        foreach (var solution in solutions.Where(solution => uniqueSolutions.Count(p => p.Equals(solution)) == 0))
            uniqueSolutions.Add(solution);
        return uniqueSolutions;
    }

/* Resharper's generated Equals and GetHashCode functions are also present here.
   And the equals method does more than just a pure compare.
   This equals method should also filter: 6*8/4*2 is duplicate of 6*8*2/4 */
}

As you can see, this isn't the prettiest code and is seven levels deep when it comes to loops. The cyclomatic complexity is 16 and I can't find ways to bring it below ten.

Is there any thing I could do to reduce the number of loops? Other hints of improvement are very welcome too!

Answer 1

First of all implement Equals in your OperatorResult

public override bool Equals(object obj)
{
    return Equals(obj as OperatorResult);
}

public bool Equals(OperatorResult operatorResult)
{
    return operatorResult != null && 
           operatorResult.OperatorOne == this.OperatorOne && 
           operatorResult.OperatorTwo == this.OperatorTwo && 
           operatorResult.OperatorThree == this.OperatorThree && 
           operatorResult.NumberOne == this.NumberOne && 
           operatorResult.NumberTwo == this.NumberTwo && 
           operatorResult.NumberThree == this.NumberThree && 
           operatorResult.NumberFour == this.NumberFour;
}

public override int GetHashCode()
{
    var result = 0;
    result = (result * 397) ^ (int)OperatorOne;
    result = (result * 397) ^ (int)OperatorTwo;
    result = (result * 397) ^ (int)OperatorThree;
    result = (result * 397) ^ NumberOne;
    result = (result * 397) ^ NumberTwo;
    result = (result * 397) ^ NumberThree;
    result = (result * 397) ^ NumberFour;
    return result;
}

With it, you don't need the GetUniqueSolutions, you can just use Distinct.

Now, your code can be represented as this linq query:

void CalculateSolutions()
{
    var numbers = new List<int>(4) { 8, 8, 5, 1 };

    var solutions = 
       (from operatorOne in (IEnumerable<Operator>)Enum.GetValues(typeof(Operator))
        from operatorTwo in (IEnumerable<Operator>)Enum.GetValues(typeof(Operator))
        from operatorThree in (IEnumerable<Operator>)Enum.GetValues(typeof(Operator))
        from numberOne in numbers
        from numberTwo in GetRemainingNumbers(numbers, numberOne)
        from numberThree in GetRemainingNumbers(numbers, numberOne, numberTwo)
        from numberFour in GetRemainingNumbers(numbers, numberOne, numberTwo, numberThree)
        where GetTotalSum(numberOne, numberTwo, numberThree, numberFour, 
                          operatorOne, operatorTwo, operatorThree) == 24
        select new OperatorResult
        { 
            OperatorOne = operatorOne,
            OperatorTwo = operatorTwo,
            OperatorThree = operatorThree,
            NumberOne = numberOne,
            NumberTwo = numberTwo,
            NumberThree = numberThree,
            NumberFour = numberFour,
        }).Distinct();
}

IEnumerable<int> GetRemainingNumbers(IEnumerable<int> numbers, params int[] usedNumbers)
{
    var result = numbers.ToList();
    foreach (var number in usedNumbers)
    {
        result.Remove(number);
    }
    return result;
}