NumberMania solver

Main points

NumberMania solver is an application I just finished creating, which helps you solve the NumberMania puzzles that the puzzles site Brain Teasers provides. The site also makes these puzzles available at its own community in Google plus named Brain Teasers and also at the Mathematics community in Google Plus.

In a previous post, I presented my MasterMind solver application, that solves the MasterMind puzzles that Brain Teasers provides. So, I thought I should also create an application that solves the NumberMania puzzles, as well.

This application is available at the following link: NumberMania solver. There you will find the executable NumberManiaSolver.exe, which is all you need to run the application. You will also find a zip file containing the source code of the application. I include the Windows form’s code in this blog post as well. I developed the application using Microsoft Visual Studio 2005 C#. The application needs the .NET Framework 2.0 in order to run. There is no need to install the application. Copy the executable somewhere in your computer, click it, and the application will run.

You input six numbers  in the application and also  a seventh number that you want to calculate as a goal. Click the button “Calculate” and the computation will start.  The lowest horizontal rectangle is a progress bar. When the calculation finishes, the progress bar will reset to no color. If you want to do another calculation, you can change any number (or leave them as they are, to get the same results). The button “Clear everything ans start anew” is for those times when you want to clear all input text boxes at once and you do not want to do it manually.

The calculation will take any one, two, three, four, five, or all six input numbers and compute all operations with any order. We begin with six input numbers which are integers greater than zero. Additions and multiplications are always performed. If a subtraction results in zero or in a negative number, the whole expression is no longer considered. The same goes for a division that leaves a remainder.

Here is what the program looks like:

NM1

The story behind this program

If someone tries to solve a NumberMania problem, she is alone. What do I mean by the word “alone”? Well, I mean that she has no one to help her. If she cannot come up with an answer, how does she know that its her fault? The Brain Teasers site provides no answers. Yes, you read that correctly. There are no answers in the site. So, how does a player know  if she should keep looking or she should stop? How can a player be sure she is not send in a wild goose chase, when there is no goose to be found?

Well, NumberMania solver answers this question. It calculates all expressions that lead to the goal number, so that the user can be sure she has all answers and that there are indeed answers.

Actually, when I was developing the program, at some point I thought that I had finished it. But there was a bug in my program. This bug prevented the program from discovering some expressions that leaded to the goal, so for some problems no answers were found. Before I discovered the bug in my program, I thought that the NumberMania puzzles, that my program could not solve, were incorrect. I thought that the site had sent players in a wild goose chase.

I tried to find a way to contact the Brain Teasers site, but there is no way to contact them. There is no contact information whatsoever anywhere on the site. And, as I also mentioned, there are no solutions posted there, either. So, a player is alone indeed.

Actually, Brain Teasers provides help in the following manner: when a user finds the solution, she can validate it on the puzzle and the puzzle displays the number of correct validations/solutions that have been found. It just so happened that the puzzles that my program could not solve due to the bug where also puzzles that no one had validate an answer, so they displayed the attribute “Correct Answers: 0”.

So, thinking that the site was sending players into a wild goose chase, I desperately tried to contact the site. Yes, there was no contact information, but I kept trying. Knowing that they are active on Google plus, I tried to reach them there. But it was still difficult to find anyone that would be the correct person to contact. At some point, I thought that I found someone who could be the correct person to contact, but the only way I could find in order to contact him was Google hangouts. Still, I left him the following message there:

Possibly incorrect puzzles

Dear Brain Teasers,

Two of your latest NumberMania puzzles,
“Calculate the number 2914 from 7,6,2,2,58,440” and
“Calculate the number 9783 from 1,5,6,5,86,893”
do not seem to have a solution.

If this is a mistake from your part,
please inform the visitors of your site,
as well as the Google+ communities where you post your puzzles.

If these two puzzles do have solutions,
I would be grateful if you could tell me the solutions
and I promise that I will not reveal them to anyone.

In any event, I would be grateful
if you could respond to this email message.

Kind regards,
Dimitrios Kalemis

I got no reply to my message. After a week, I discovered the bug in my program and I correct it. The puzzles I mention in my message and all other NumberMania puzzles are correct. They have solutions. Now, with my corrected program, you can be sure that these solutions exist. You are no longer “alone”. As far as the bug in my program, keep reading and you will find out about it later on in this blog post.

Just as I did with my MasterMind solver program, I was planning to include two examples, two puzzles that NumberMania solver solved from the Brain Teasers site. So, in order for us to see the program in action, I choose to solve the two puzzles that I so wrongfully accused of being incorrect.

The first puzzle is:

numbermania-1396227604

And after the calculation, my program displays:

NM2

The second puzzle is:

numbermania-1397610004

And after the calculation, my program displays:

NM3

The source code

Here is the source code of NumberMania solver:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace NumberManiaSolver
{
    public partial class Form1 : Form
    {
        int[] a = new int[6];
        String[] sa = new String[6];
        Char[] b = new Char[4];
        int goal;
        int counter;

        public Form1()
        {
            InitializeComponent();
            progressBar1.Minimum = 0;
            progressBar1.Maximum = 93039486;
        }

        private void btnCalculate_Click(object sender, EventArgs e)
        {   
            try
            {
                a[0] = Convert.ToInt32(textBox1.Text);
                a[1] = Convert.ToInt32(textBox2.Text);
                a[2] = Convert.ToInt32(textBox3.Text);
                a[3] = Convert.ToInt32(textBox4.Text);
                a[4] = Convert.ToInt32(textBox5.Text);
                a[5] = Convert.ToInt32(textBox6.Text);
            }
            catch (Exception e1)
            {
                MessageBox.Show("At least one of the input numbers is not given, has an incorrect format, or is too large." + "\n" + "System message: " + e1.Message);
                return;
            }

            sa[0] = Convert.ToString(a[0]);
            sa[1] = Convert.ToString(a[1]);
            sa[2] = Convert.ToString(a[2]);
            sa[3] = Convert.ToString(a[3]);
            sa[4] = Convert.ToString(a[4]);
            sa[5] = Convert.ToString(a[5]);

            b[0] = '+';
            b[1] = '-';
            b[2] = '*';
            b[3] = '/';

            try
            {
               goal = Convert.ToInt32(textBoxGoal.Text);
            }
            catch(Exception e2)
            {
                MessageBox.Show("The goal number is not given, has an incorrect format, or is too large." + "\n" + "System message: " + e2.Message);
                return;
            }

            try
            {
                int something = 0;
                something = a[0] * a[1] * a[2] * a[3] * a[4] * a[5];
            }
            catch (Exception e3)
            {
                MessageBox.Show("The input numbers (combined) are too large." + "\n" + "System message: " + e3.Message);
                return;
            }

            listBox1.Items.Clear();
            lblCount.Text = "Please wait...";
            btnCalculate.Enabled = false;
            btnClear.Enabled = false;

            Application.DoEvents();

            counter = 0;

            // Any one input number
            for (int i = 0; i <= 5; i++)
            {
                updateCounter();
                anyOneInputNumber(a[i], sa[i]);
            }

            // Any two input numbers
            for (int i = 0; i <= 5; i++)
            {
                for (int j = 0; j <= 5; j++)
                {
                    if (i != j)
                    {
                        for (int p1 = 0; p1 <= 3; p1++)
                        {
                            updateCounter();
                            anyTwoInputNumbers(a[i], a[j], p1, sa[i], sa[j]);
                        } //p1
                    } //endif
                } //j
            } //i

            // Any three input numbers
            for (int i = 0; i <= 5; i++)
            {
                for (int j = 0; j <= 5; j++)
                {
                    if (i != j)
                    {
                        for (int k = 0; k <= 5; k++)
                        {
                            if ((i != k) && (j != k))
                            {
                                for (int p1 = 0; p1 <= 3; p1++)
                                {
                                    for (int p2 = 0; p2 <= 3; p2++)
                                    {
                                        for (int o1 = 0; o1 <= 1; o1++)
                                        {
                                            for (int o2 = 0; o2 <= 1; o2++)
                                            {
                                                if (o1 != o2)
                                                {
                                                    updateCounter();
                                                    anyThreeInputNumbers(a[i], a[j], a[k], p1, p2, o1, o2, sa[i], sa[j], sa[k]);
                                                } //endif
                                            } //o2
                                        } //o1
                                    } //p2
                                } //p1
                            } // endif
                        } //k
                    } //endif
                } //j
            } //i

            // Any four input numbers
            for (int i = 0; i <= 5; i++)
            {
                for (int j = 0; j <= 5; j++)
                {
                    if (i != j)
                    {
                        for (int k = 0; k <= 5; k++)
                        {
                            if ((i != k) && (j != k))
                            {
                                for (int l = 0; l <= 5; l++)
                                {
                                    if ((i != l) && (j != l) && (k != l))
                                    {
                                        for (int p1 = 0; p1 <= 3; p1++)
                                        {
                                            for (int p2 = 0; p2 <= 3; p2++)
                                            {
                                                for (int p3 = 0; p3 <= 3; p3++)
                                                {
                                                    for (int o1 = 0; o1 <= 2; o1++)
                                                    {
                                                        for (int o2 = 0; o2 <= 2; o2++)
                                                        {
                                                            if (o1 != o2)
                                                            {
                                                                for (int o3 = 0; o3 <= 2; o3++)
                                                                {
                                                                    if ((o1 != o3) && (o2 != o3))
                                                                    {
                                                                        updateCounter();
                                                                        anyFourInputNumbers(a[i], a[j], a[k], a[l], p1, p2, p3, o1, o2, o3, sa[i], sa[j], sa[k], sa[l]);
                                                                    } //endif
                                                                } //o3
                                                            } //endif
                                                        } //o2
                                                    } //o1
                                                } //p3
                                            } //p2
                                        } //p1
                                    } //endif
                                } //l
                            } // endif
                        } //k
                    } //endif
                } //j
            } //i

            // Any five input numbers
            for (int i = 0; i <= 5; i++)
            {
                for (int j = 0; j <= 5; j++)
                {
                    if (i != j)
                    {
                        for (int k = 0; k <= 5; k++)
                        {
                            if ((i != k) && (j != k))
                            {
                                for (int l = 0; l <= 5; l++)
                                {
                                    if ((i != l) && (j != l) && (k != l))
                                    {
                                        for (int m = 0; m <= 5; m++)
                                        {
                                            if ((i != m) && (j != m) && (k != m) && (l != m))
                                            {
                                                for (int p1 = 0; p1 <= 3; p1++)
                                                {
                                                    for (int p2 = 0; p2 <= 3; p2++)
                                                    {
                                                        for (int p3 = 0; p3 <= 3; p3++)
                                                        {
                                                            for (int p4 = 0; p4 <= 3; p4++)
                                                            {
                                                                for (int o1 = 0; o1 <= 3; o1++)
                                                                {
                                                                    for (int o2 = 0; o2 <= 3; o2++)
                                                                    {
                                                                        if (o1 != o2)
                                                                        {
                                                                            for (int o3 = 0; o3 <= 3; o3++)
                                                                            {
                                                                                if ((o1 != o3) && (o2 != o3))
                                                                                {
                                                                                    for (int o4 = 0; o4 <= 3; o4++)
                                                                                    {
                                                                                        if ((o1 != o4) && (o2 != o4) && (o3 != o4))
                                                                                        {
                                                                                            updateCounter();
                                                                                            anyFiveInputNumbers(a[i], a[j], a[k], a[l], a[m], p1, p2, p3, p4, o1, o2, o3, o4, sa[i], sa[j], sa[k], sa[l], sa[m]);
                                                                                        } //endif
                                                                                    } //o4
                                                                                } //endif
                                                                            } //o3
                                                                        } //endif
                                                                    } //o2
                                                                } //o1
                                                            } //p4
                                                        } //p3
                                                    } //p2
                                                } //p1
                                            } //endif
                                        } //m
                                    } //endif
                                } //l
                            } // endif
                        } //k
                    } //endif
                } //j
            } //i

            // Any six input numbers
            for (int i = 0; i <= 5; i++)
            {
                for (int j = 0; j <= 5; j++)
                {
                    if (i != j)
                    {
                        for (int k = 0; k <= 5; k++)
                        {
                            if ((i != k) && (j != k))
                            {
                                for (int l = 0; l <= 5; l++)
                                {
                                    if ((i != l) && (j != l) && (k != l))
                                    {
                                        for (int m = 0; m <= 5; m++)
                                        {
                                            if ((i != m) && (j != m) && (k != m) && (l != m))
                                            {
                                                for (int n = 0; n <= 5; n++)
                                                {
                                                    if ((i != n) && (j != n) && (k != n) && (l != n) && (m != n))
                                                    {
                                                        for (int p1 = 0; p1 <= 3; p1++)
                                                        {
                                                            for (int p2 = 0; p2 <= 3; p2++)
                                                            {
                                                                for (int p3 = 0; p3 <= 3; p3++)
                                                                {
                                                                    for (int p4 = 0; p4 <= 3; p4++)
                                                                    {
                                                                        for (int p5 = 0; p5 <= 3; p5++)
                                                                        {
                                                                            for (int o1 = 0; o1 <= 4; o1++)
                                                                            {
                                                                                for (int o2 = 0; o2 <= 4; o2++)
                                                                                {
                                                                                    if (o1 != o2)
                                                                                    {
                                                                                        for (int o3 = 0; o3 <= 4; o3++)
                                                                                        {
                                                                                            if ((o1 != o3) && (o2 != o3))
                                                                                            {
                                                                                                for (int o4 = 0; o4 <= 4; o4++)
                                                                                                {
                                                                                                    if ((o1 != o4) && (o2 != o4) && (o3 != o4))
                                                                                                    {
                                                                                                        for (int o5 = 0; o5 <= 4; o5++)
                                                                                                        {
                                                                                                            if ((o1 != o5) && (o2 != o5) && (o3 != o5) && (o4 != o5))
                                                                                                            {
                                                                                                                updateCounter();
                                                                                                                anySixInputNumbers(a[i], a[j], a[k], a[l], a[m], a[n], p1, p2, p3, p4, p5, o1, o2, o3, o4, o5, sa[i], sa[j], sa[k], sa[l], sa[m], sa[n]);
                                                                                                            } //endif
                                                                                                        } //o5
                                                                                                    } //endif
                                                                                                } //o4
                                                                                            } //endif
                                                                                        } //o3
                                                                                    } //endif
                                                                                } //o2
                                                                            } //o1
                                                                        } //p5
                                                                    } //p4
                                                                } //p3
                                                            } //p2
                                                        } //p1
                                                    } //endif
                                                } //n
                                            } //endif
                                        } //m
                                    } //endif
                                } //l
                            } // endif
                        } //k
                    } //endif
                } //j
            } //i

            progressBar1.Value = counter;

            lblCount.Text = "Total number of expressions = " + Convert.ToString(listBox1.Items.Count);

            btnCalculate.Enabled = true;
            btnClear.Enabled = true;

            progressBar1.Value = 0;

        }

        private void anyOneInputNumber(int ai, String sai)
        {
            if (ai == goal)
            {
                if (!listBox1.Items.Contains(sai))
                {
                    listBox1.Items.Add(sai);
                }
            }
        }

        private void anyTwoInputNumbers(int ai, int aj, int p1, String sai, String saj)
        {
            int theResult = 0;
            String expression = "";

            theResult = doTheMath(ai, aj, p1);
            expression = sai + b[p1] + saj;

            if (theResult == 0)
            {
                return;
            }
            else
            {
                anyOneInputNumber(theResult, expression);
            }

        }

        private void anyThreeInputNumbers(int ai, int aj, int ak, int p1, int p2, int o1, int o2, String sai, String saj, String sak)
        {
            int theResult = 0;
            String expression = "";

            if (o1 == 0)
            {
                theResult = doTheMath(ai, aj, p1);
                expression = "(" + sai + b[p1] + saj + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyTwoInputNumbers(theResult, ak, p2, expression, sak);
                }
            }

            if (o2 == 0)
            {
                theResult = doTheMath(aj, ak, p2);
                expression = "(" + saj + b[p2] + sak + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyTwoInputNumbers(ai, theResult, p1, sai, expression);
                }
            }
        }

        private void anyFourInputNumbers(int ai, int aj, int ak, int al, int p1, int p2, int p3, int o1, int o2, int o3, String sai, String saj, String sak, String sal)
        {
            int theResult = 0;
            String expression = "";

            if (o1 == 0)
            {
                theResult = doTheMath(ai, aj, p1);
                expression = "(" + sai + b[p1] + saj + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyThreeInputNumbers(theResult, ak, al, p2, p3, o2 - 1, o3 - 1, expression, sak, sal);
                }
            }

            if (o2 == 0)
            {
                theResult = doTheMath(aj, ak, p2);
                expression = "(" + saj + b[p2] + sak + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyThreeInputNumbers(ai, theResult, al, p1, p3, o1 - 1, o3 - 1, sai, expression, sal);
                }
            }

            if (o3 == 0)
            {
                theResult = doTheMath(ak, al, p3);
                expression = "(" + sak + b[p3] + sal + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyThreeInputNumbers(ai, aj, theResult, p1, p2, o1 - 1, o2 - 1, sai, saj, expression);
                }
            }
        }

        private void anyFiveInputNumbers(int ai, int aj, int ak, int al, int am, int p1, int p2, int p3, int p4, int o1, int o2, int o3, int o4, String sai, String saj, String sak, String sal, String sam)
        {
            int theResult = 0;
            String expression = "";

            if (o1 == 0)
            {
                theResult = doTheMath(ai, aj, p1);
                expression = "(" + sai + b[p1] + saj + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFourInputNumbers(theResult, ak, al, am, p2, p3, p4, o2 - 1, o3 - 1, o4 - 1, expression, sak, sal, sam);
                }
            }

            if (o2 == 0)
            {
                theResult = doTheMath(aj, ak, p2);
                expression = "(" + saj + b[p2] + sak + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFourInputNumbers(ai, theResult, al, am, p1, p3, p4, o1 - 1, o3 - 1, o4 - 1, sai, expression, sal, sam);
                }
            }

            if (o3 == 0)
            {
                theResult = doTheMath(ak, al, p3);
                expression = "(" + sak + b[p3] + sal + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFourInputNumbers(ai, aj, theResult, am, p1, p2, p4, o1 - 1, o2 - 1, o4 - 1, sai, saj, expression, sam);
                }
            }

            if (o4 == 0)
            {
                theResult = doTheMath(al, am, p4);
                expression = "(" + sal + b[p4] + sam + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFourInputNumbers(ai, aj, ak, theResult, p1, p2, p3, o1 - 1, o2 - 1, o3 - 1, sai, saj, sak, expression);
                }
            }
        }

        private void anySixInputNumbers(int ai, int aj, int ak, int al, int am, int an, int p1, int p2, int p3, int p4, int p5, int o1, int o2, int o3, int o4, int o5, String sai, String saj, String sak, String sal, String sam, String san)
        {
            int theResult = 0;
            String expression = "";

            if (o1 == 0)
            {
                theResult = doTheMath(ai, aj, p1);
                expression = "(" + sai + b[p1] + saj + ")";
                
                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFiveInputNumbers(theResult, ak, al, am, an, p2, p3, p4, p5, o2 - 1, o3 - 1, o4 - 1, o5 - 1, expression, sak, sal, sam, san);
                }
            }

            if (o2 == 0)
            {
                theResult = doTheMath(aj, ak, p2);
                expression = "(" + saj + b[p2] + sak + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFiveInputNumbers(ai, theResult, al, am, an, p1, p3, p4, p5, o1 - 1, o3 - 1, o4 - 1, o5 - 1, sai, expression, sal, sam, san);
                }
            }

            if (o3 == 0)
            {
                theResult = doTheMath(ak, al, p3);
                expression = "(" + sak + b[p3] + sal + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFiveInputNumbers(ai, aj, theResult, am, an, p1, p2, p4, p5, o1 - 1, o2 - 1, o4 - 1, o5 - 1, sai, saj, expression, sam, san);
                }
            }

            if (o4 == 0)
            {
                theResult = doTheMath(al, am, p4);
                expression = "(" + sal + b[p4] + sam + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFiveInputNumbers(ai, aj, ak, theResult, an, p1, p2, p3, p5, o1 - 1, o2 - 1, o3 - 1, o5 - 1, sai, saj, sak, expression, san);
                }
            }
            if (o5 == 0)
            {
                theResult = doTheMath(am, an, p5);
                expression = "(" + sam + b[p5] + san + ")";

                if (theResult == 0)
                {
                    return;
                }
                else
                {
                    anyFiveInputNumbers(ai, aj, ak, al, theResult, p1, p2, p3, p4, o1 - 1, o2 - 1, o3 - 1, o4 - 1, sai, saj, sak, sal, expression);
                }
            }

        }

        private int doTheMath(int first, int second, int praxis)
        {

            int theResult;
            int theRemainder;

            theResult = 0;
            theRemainder = 0;

            if (praxis == 0)
            {
                return (first + second);
            }

            if (praxis == 1)
            {
                theResult = first - second;
                if (theResult <= 0)
                {
                    return 0;
                }
                else
                {
                    return (theResult);
                }
            }

            if (praxis == 2)
            {
                return(first * second);
            }

            if (praxis == 3)
            {
                theRemainder = first % second;
                if (theRemainder != 0)
                {
                    return 0;
                }
                else
                {
                    return (first / second);
                }
            }

            return 0;

        }

        private void updateCounter()
        {
            counter = counter + 1;
            if (counter % 1000000 == 0)
            {
                Application.DoEvents();
                progressBar1.Value = counter;
            }
        }

        private void btnClear_Click(object sender, EventArgs e)
        {
            textBox1.Text = "";
            textBox2.Text = "";
            textBox3.Text = "";
            textBox4.Text = "";
            textBox5.Text = "";
            textBox6.Text = "";

            textBoxGoal.Text = "";

            listBox1.Items.Clear();
            lblCount.Text = "Total number of expressions = 0";

            progressBar1.Value = 0;

            textBox1.Focus();
        }
    }
}

Explanation of the source code

First of all, let us see what I am trying to accomplish. I have six input integers greater than zero and I want to find all mathematical expressions that lead to a seventh integer greater than zero, the goal number. The allowed mathematical operations are addition, subtraction, multiplication, and division. A subtraction that results in zero or in a negative integer is not allowed, so the corresponding mathematical expressions are discarded. All divisions have to be integer divisions, thus, a division that results in a remainder other than zero is not allowed and the corresponding mathematical expressions are discarded. So, only positive integers are in play here.

To find all the mathematical expressions that result in the goal number, I perform an exhaustive brute force search of all the permutation of the input integers with any and all operations in any any all orders. Let me explain how I do this.

First of all, I take each one of the six input numbers and check whether any of them is equal to the goal number. If any of them is, I consider the corresponding input number to be one of the solutions and I list it in the listbox on the right side of the form.

This listbox holds all valid expressions, but if an expression is listed I do not add it again. I think that this will play well with most end users, since most of us would not want to see the same expression more than once. But why should an expression be listed more than once? Well, first of all, there is the case that two of more of the six input numbers are the same. Since the program treats each of the six input numbers as a different entity and makes no effort in comparing them, duplications expression sare bound to arise from that fact alone. But, keep reading, and you will find that there are other cases that will also result in duplicate expressions.

So, even in the first case where we examine each number alone with the goal, there might be duplicate expressions (correct hits), if there is more than one input number that is equal to the goal. Again, the listbox will not show duplicate expressions, thus, if any of the input numbers matches the goal, one expression containing only this number will be shown.

Next, there is the case of expressions that are built using any two input numbers. If we use two numbers in the expression, then we will need one operation in order to produce a result. Thus, we need to take all permutations of any two numbers out of the six input numbers. And, for each permutation, we need to apply any of the four operations. We will compare each result to the goal number and insert any expression (that results in a hit) into the list box, avoiding duplicating entries.

Next, we have the case of expressions that are built using any three input numbers. Thus, we need to obtain all permutations of any three input numbers out of the six input numbers.For each permutation, we need to apply all permutations of two operators out of the four available (+,-,*,/). So, we might insert an addition between the first and second number and a multiplication between the second and third number. But this is not all. We also have to take these two operations in any order. Thus, we will need all permutations for the order of these two operations. In this case we only have two operations, so their order can only have two permutations: it can be either the first operation applied first and the second operation applied second, or the first operation applied second and the second operation applied first. This is not going to produce duplicate expressions. Imagine for example having he same operation in both the first and second pace. The order does not matter then, but the program inserts pairs of parentheses to denote the order, resulting in non-duplicate expressions that produce the same result.

Next we have expressions that are built using any four input numbers. Thus we will need all permutations of any four numbers out of the six input numbers. We also need all permutations of any three operations. And we need to apply these three operations in any order. From here onwards, there are cases where we can have duplicate expressions. Let us consider, for example, the following expression: (a[i] + a[j]) + (a[k] + a[l]). It is obvious that we have three additions. It is also obvious that the middle + is last in order. But this expression can either have the first + as first in order and the last + as second in order, or it can have the first + as second in order and the last + as first in order. Anyway, the expression will only be listed once in the listbox, because the insert operation eliminates the duplicate expressions.

Next we have expressions that are built using any five input numbers. Thus we will need all permutations of any five numbers out of the six input numbers. We also need all permutations of any four operations. And we need to apply these four operations in any order.

Finally we have expressions that are built using any six input numbers. Thus we will need all permutations of all six input numbers. We also need all permutations of any five operations. And we need to apply these five operations in any order.

We denote the integer positions in each expression using i,j,k,l,m,n. We denote the operations using p1,p2,p3,p4,p5. We denote the order of the operations with o1,o2,o3,o4,o5. The counting starts for all variables from zero.

In the integer positions, we have permutations where repetition is not allowed. Each number is unique.

In the operations, we have permutations where repetition is allowed. We can have any operation everywhere in some expressions. Or two additions and three subtractions if we have five numbers.

In the operations order, we have permutations where repetition is not allowed. Each order is unique.

To get the permutations that we need, we use for loops. When we want permutations without repetition, such as in the case of the input numbers or the order of the operations, we use for loops with if statements. The if statements are there to eliminate the repetitions. When we want permutations with repetition, such as in the case of operations, we use for loops without any if statements.

The following table shows the number of permutations obtained and the number of loops that were used to obtain these permutations. It is obvious that using loops to obtain permutations is inefficient. But it is a very easy and obvious way to obtain permutations. Actually, in less than one hour, one person can read this program code and be sure that the program is correct. A program, that would use more advanced algorithms to produce the permutations or would use pre-calculated permutations, would be faster but would be more difficult to read and validate for correctness.

Info

Actually, the for loops are not what is mainly causing the slowness of the program. The program uses most of its time in order to provide beautified expressions. Each expression listed in the listbox has parentheses to denote the order of the operations. If I would just list the numbers a[i] to a[n], their operations p1 to p5, and their order o1 to o5, as plain numbers, the program would be much faster.

Anyway, the program does not try to be fast. It tries to do an exhaustive brute force search. It does not try to do a clever search of the available set of permutations. It tries do to a dumb search. It does not try to outperform humans or compete in a game with humans. It tries to provide a complete set of solutions to a human, so she does not fell alone when trying to solve a NumberMania puzzle. The program tries to answer the question: “Is there an answer to this NumberMania puzzle?” And to its fictitious proposition: “Would you please wait?”, it expects the answer: “Yes, I will.”

I still have not revealed the bug that my program had and kept it from calculating the answers to some (but not all) NumberMania puzzles. Well, the mistake I made was a logical one. I accounted for all permutations of the input numbers and I also accounted for all operations between them. But my original version of the program had no notion of order of operations. It would only perform the leftmost calculation first, the next leftmost calculation second, and so on, all the way to performing the rightmost operation last. And I would test the program as such. I would create mathematical expressions that only performed operations in this order. At some point, unfortunately after I sent my incorrect message to Google hangouts, I tested the program using a different order of operations, without realizing that this would reveal a bug. Thankfully, the numbers I used could not produce the goal I set using the order of operations that I had as default. Thus, I found my mistake and I corrected it, by adding to the program the notion of order of operations for each expression.

Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Development. Bookmark the permalink.