3
\$\begingroup\$

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!

\$\endgroup\$
0

1 Answer 1

4
\$\begingroup\$

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;
}
\$\endgroup\$
4
  • \$\begingroup\$ I did implemented Equals, but I thought it would take too much space in the question. Moreover, equals does more than just check for an equal expression. It should also filter duplicates like: 6*8/4*2 duplicate of 6*8*2/4. So the equals is mandatory. I'm going to try this out. \$\endgroup\$
    – Mixxiphoid
    Mar 7, 2015 at 22:25
  • \$\begingroup\$ @Mixxiphoid and don't ever forget to implement a GetHashCode when you're implementing Equals. \$\endgroup\$
    – aush
    Mar 7, 2015 at 22:27
  • \$\begingroup\$ See my update in the question at OperatorResult. \$\endgroup\$
    – Mixxiphoid
    Mar 7, 2015 at 22:29
  • \$\begingroup\$ This is a much more beautiful and readable solution! Thanks. The (IEnumerable<Operator>) smells though. So I added a private static readonly List<Operator> with the four operators in it and used that instead. Making it even more readable, and faster. \$\endgroup\$
    – Mixxiphoid
    Mar 7, 2015 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.