7.11

The problem that I read this week, and to spare you from the context behind it, is very easy to understand: in essence, you have 4 numbers that correspond to prices of products, where the price has a precision of two decimal points (i.e., the format is $NN.nn). Call these numbers p1, p2, p3 and p4. The products are sold in a 7/11 store, and the coincidence at the heart of this problem is that these four numbers when multiplied altogether or when added up, the result is always 7.11. Mathematically speaking:

p1+p2+p3+p4 = 7.11

p1*p2*p3*p4 = 7.11

Question becomes: what are the prices p1, p2, p3 and p4?

Now, we have 2 equations and 4 variables which becomes extremely hard to solve. The book that I read this question at actually describes a 4-pages convoluted mathematical process to solve the problem, without any computers or algorithms. It is based on a number of very clever mathematical observations, but… I’d rather let the computer do the brute-force for me. The code to solve this particular problem is backtracking since we have a very small universe of possibilities: each variable can have only 712 possibilities (from 0.00 to 7.11, varying by 0.01), hence the total number of possibilities that we need to try out is 712^4, or 257 billion, which frankly is a very small number. Besides, remember that with any backtracking you can cut the search space considerably by using some rules specific to the problem in question: for instance, in this particular problem the moment that we have an assignment of values to p1, p2, p3 and p4 whose sum is greater than 7.11 (or whose multiplication is greater than 7.11) there is no need to continue the search any further. Hence in reality that 257 billion is an upper-limit, the real search space is much smaller. The code below actually tries to find solutions to a slightly more general version of this problem: instead of trying only 4 variables, it tries [1..5] variables. Interesting enough there are only solutions if the number of variables is either 1 (in which case the solution is trivial: p1 = 7.11) or 4 (I won’t tell you the solution to the problem with four variables (the original problem up above), but I’ll tell you that there is one and only one solution!). 2, 3 and 5 variables have no solution with only two decimal places of precision (the problem with 2 variables does have a solution with 3 decimal places of precision, but not with 2). And here it is the code (C#):

 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NumbersAddAndMul
{
    class Program
    {
        static double ZERO = 0.00001;
        static double QUASIZERO = 0.0001;
        static Random rd = new Random();
        static void Main(string[] args)
        {
            double initVal = 0.00;
            double endVal = 7.11;
            double increment = 0.01;
            double targetAddition = 7.11;
            double targetMultiplication = 7.11;
            for (int n = 1; n <= 5; n++)
            {
                int max = n;
                double[] currentNumbers = new double[n];
                long combinationsTried = 0;
                Console.WriteLine("Processing n = {0}", n);
                if (SearchSolution(initVal,
                                   endVal,
                                   increment,
                                   targetAddition,
                                   targetMultiplication,
                                   max,
                                   0.0,
                                   1.0,
                                   ref currentNumbers,
                                   0,
                                   ref combinationsTried))
                {
                    Console.Write("Found Solution (after {0} combinations)! Numbers: ", combinationsTried);
                    foreach (double d in currentNumbers)
                    {
                        Console.Write("{0} ", d.ToString("F"));
                    }
                    Console.WriteLine();
                }
                else
                {
                    Console.WriteLine("No Solution after {0} combinations!", combinationsTried);
                }
                Console.WriteLine();
            }
        }
        static bool SearchSolution(double initVal,
                                   double endVal,
                                   double increment,
                                   double targetAddition,
                                   double targetMultiplication,
                                   int max,
                                   double currentAddition,
                                   double currentMultiplication,
                                   ref double[] currentNumbers,
                                   int current,
                                   ref long combinationsTried)
        {
            if (current >= max)
            {
                if (Math.Abs(currentAddition - targetAddition) < ZERO &&
                    Math.Abs(currentMultiplication - targetMultiplication) < ZERO)
                {
                    return true;
                }
                else if (Math.Abs(currentAddition - targetAddition) < QUASIZERO &&
                    Math.Abs(currentMultiplication - targetMultiplication) < QUASIZERO)
                {
                    Console.Write("Found a very close quasi-solution: ");
                    foreach (double d in currentNumbers)
                    {
                        Console.Write("{0} ", d.ToString("F"));
                    }
                    Console.WriteLine();
                }
                return false;
            }
            for (double d = initVal; d <= endVal; d += increment)
            {
                currentNumbers[current] = d;
                combinationsTried++;
                if (currentAddition + currentNumbers[current] > targetAddition ||
                    currentMultiplication * currentNumbers[current] > targetMultiplication)
                {
                    break;
                }
                if (SearchSolution(currentNumbers[current],
                                   endVal,
                                   increment,
                                   targetAddition,
                                   targetMultiplication,
                                   max,
                                   currentAddition + currentNumbers[current],
                                   currentMultiplication * currentNumbers[current],
                                   ref currentNumbers,
                                   current + 1,
                                   ref combinationsTried))
                {
                    return true;
                }
            }
            return false;
        }
    }
}