Am I smarter than the fifth grader?

I thought I was, until my 10 year-old brought home a math homework from her school asking her to solve a few problems that look like this:

Replace letters with digits from this list [1, 2, 3, 4, 5, 7, 8, 9]
All letters to digit mapping is unique

   CAN
x  SAY
======
 BRAND

I thought such problem would have a quick-and-easy solution, like any others in a 5th grade math, but I was stumped. I tried several tricks to see if there was a shortcut to solving these, but found nothing. The only way to solve a problem like this was to iteratively try out various number combinations to see if the result would match the constraints of the problem.

Constraints

In a problem above the constraints are as follows:

  1. 2nd digit in the 2nd number must match 2nd digit in the 1st number
  2. 2nd and 3rd digit in the 1st number must match 3rd digit and 4th digits result
  3. Result must have 5 digits
  4. None of the digits of the result except for the 3rd and 4th can be present in the first two numbers

Solving such problem.

I learned that the type of these problems are called cryptarithms or verbal arithmetic. There’s a wikipedia page dedicated to these problems as well as a laundry list of sites hosting examples and explanations to these. There is no simple solution to such problem. The solution to them is defined as having NP-Complete in its difficulty, which according to Wikipedia is

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC. The abbreviation NP refers to “nondeterministic polynomial time”.

Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known.

My Solution

The only way to solve it was to write a program, which I did below. I figured that I have to start with a basic mapping of letters to digits and “increment” the mapping by “1” at every iteration. The difficult part was to implement the “increment” because no two letters can be mapped to the single digit, I could not completely mimic the way we increment regular numbers in base 10. Plus the universe of digits can also be constrained if the problem creator chooses to do so.

The code is written in C#, and is lazy-coded, where the inputs are hard-coded in the main method, because I own the code and can easily change the definitions. It supports multiplication and addition. It managed to solve all the problems that I found online, so I am fairly confident that it works.

Perhaps I am still smarter than the 5th grader, even if slightly.

namespace WordMultiplication
{
    class Program
    {
        static void Main(string[] args)
        {
            var digits = new int[] { 1, 2, 3, 4, 5,  7, 8, 9 }.OrderBy(n => n).ToArray();
            var word1 = "CAN";
            var word2 = "SAY";
            var result = "BRAND";

            var orderedInputLetters = word1.Union(word2).Distinct().ToArray();
            if (orderedInputLetters.Length > digits.Length)
            {
                Console.WriteLine("More letters than digits!");
                return;
            }

            var numbersToLetterMap = new SortedDictionary<int, char?>();
            var lettersToNumbersMap = new Dictionary<char, int>();

            InitialSetup(orderedInputLetters, digits, numbersToLetterMap, lettersToNumbersMap);

            bool found;
            bool couldIncrement;
            do
            {
                couldIncrement = false;
                int number1 = GetNumberForWord(word1, lettersToNumbersMap);
                int number2 = GetNumberForWord(word2, lettersToNumbersMap);

                var mathResult = number1 * number2;

                found = number1.ToString().Length == word1.Length &&
                        number2.ToString().Length == word2.Length &&
                        Verify(mathResult, result, word1, word2, new Dictionary<char, int>(lettersToNumbersMap), digits);
                if (found)
                    Console.WriteLine("{0} x {1} = {2}", number1, number2, mathResult);
                else
                    couldIncrement = TryIncrement(orderedInputLetters.Length - 1, orderedInputLetters, digits, numbersToLetterMap, lettersToNumbersMap);


            } while (!found && couldIncrement);

            if (!found)
                Console.WriteLine("Result not found");
        }

        private static bool TryIncrement(int index, char[] inputLetters, int[] digits,
            IDictionary<int, char?> numbersToLetterMap, IDictionary<char, int> lettersToNumbersMap)
        {
            if (index == -1)
                return false;

            var currLetter = inputLetters[index];
            var currDigit = lettersToNumbersMap[currLetter];

            int nextDigit;
            //If we reached the end
            if (!numbersToLetterMap.Any(kvp => kvp.Key > currDigit && !kvp.Value.HasValue))
            {
                //put current letter aside
                numbersToLetterMap[currDigit] = null;
                lettersToNumbersMap[currLetter] = -1;

                //Try to increment a digit of higher significance
                if (TryIncrement(index - 1, inputLetters, digits, numbersToLetterMap, lettersToNumbersMap))
                    //If succeeded, find the first available empty spot for the current letter
                    nextDigit = numbersToLetterMap.First(kvp => !kvp.Value.HasValue).Key;
                else
                    return false;
            }
            else
            {
                numbersToLetterMap[currDigit] = null;
                nextDigit = numbersToLetterMap.First(kvp => kvp.Key > currDigit && !kvp.Value.HasValue).Key;
            }

            numbersToLetterMap[nextDigit] = currLetter;
            lettersToNumbersMap[currLetter] = nextDigit;

            return true;
        }


        private static void InitialSetup(char[] inputLetters, int[] digits, IDictionary<int, char?> numbersToLetterMap, IDictionary<char, int> lettersToNumbersMap)
        {
            foreach (var digit in digits)
                numbersToLetterMap[digit] = null;

            foreach (var c in inputLetters)
                lettersToNumbersMap[c] = -1;

            //Place letters in the beginning of the digit line
            for (int i = 0; i < inputLetters.Length; i++)
            {
                lettersToNumbersMap[inputLetters[i]] = digits[i];
                numbersToLetterMap[digits[i]] = inputLetters[i];
            }
        }

        private static bool Verify(int mathResult, string result, string word1, string word2, IDictionary<char, int> allletters, int[] digits)
        {
            if (mathResult.ToString().Length != result.Length)
                return false;

            for (int i = 0; i < result.Length; i++)
            {
                var resultChar = result[i];
                var digitForChar = (mathResult / (int)Math.Pow(10, result.Length - i - 1) % 10);
                
                //Can result be even used?
                if (Array.IndexOf(digits, digitForChar) == -1)
                    return false;

                if (allletters.Keys.Contains(resultChar))
                {
                    if (allletters[resultChar] != digitForChar)
                        return false;
                }
                else if (allletters.Values.Contains(digitForChar))
                {
                    if (allletters.First(kvp => kvp.Value == digitForChar).Key != resultChar)
                        return false;
                }
                else
                {
                    allletters[resultChar] = digitForChar;
                }
            }

            return true;

        }

        private static int GetNumberForWord(string word, IDictionary<char, int> allletters)
        {
            var number = 0;
            for (int i = 0; i < word.Length; i++)
            {
                number += allletters[word[i]] * (int)Math.Pow(10, (word.Length) - i - 1);
            }

            return number;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s