The Limber Lambda

Do you know what a pandigital number is?  Following is the definition from Wikipedia:

Project Euler problem number 32 modifies the definition a little for the sake of convenience:

1. 1 to 9 instead of 0 to 9
2. Each digit occurs only once, instead of at least once.

Now if the definition is extended to a multiplicand/multiplier/product identity, that is, like this:

39 × 186 = 7254

Then the problem becomes:

A “hint” is provided, although I think that this is less of a hint and more of “additional instructions”. As it turns out, the set of answers has multiple identities that result in the same product (and these are not the obvious transpositions of multiplicand and multiplier as one might think), so where there are duplicates, only one instance of the product should be added to the total. As an example:

18 x 297 = 5346

27 x 198 = 5346

In this case, the second identity is ignored.

This isn’t a hugely challenging problem – I would say the only interesting bit is finding the possible 9 digit permutations. We know that the number of permutations is 9! = 9 x 8 x 7 x 6 x 5 x 4 x 2 = 36288o.  Given the sort of computing power we have these days, churning through that list should be an absolute doddle.

Finding Permutations

I generally try not to defer to “official algorithms” when trying to solve problems like these, and as a result end up implementing something that may work but probably is not the most efficient.  There are various algorithms for calculating permutations, but the one that I came up with is of the recursive variety (recursion is fun).  It goes something like this:

1. mySwapper = { Given a set of n digits (numbered 1 … n), swap digit i with the remaining digits where i goes from 1 … n.  For each iteration of i, return mySwapper(<remaining digits>) }
2. mySwapper(<all the digits>)

Note that we obviously don’t need to swap digit k with digit k, but to keep the algorithm neat (read: exception-free) we’ll sacrifice a little performance.

Producing the Sum

Once we have all the possible permutations of 9 digits, what remains is to split them up into multiplicand/multiplier/product parts and test that the product is correct.  Now, since we only have 9 digits, we can make use of some common sense rules re products, that is, a product will always have at least as many digits as the sum of multiplicand and multiplier digits minus 1. The only multiplicand/multiplier/product combinations that satisfy this condition are 2/3/4 and 1/4/4 (well … 3/2/4 and 4/1/4 as well, but these provide duplicate answers).

What remains is to check that we don’t add duplicate products (like the one shown above), and to calculate the sum.  I’ve included the source code in C# below–I’m not claiming that this is particularly efficient at all though, I’m quite sure there are much faster ways of doing this using System.Int32‘s only:

using System;
using System.Collections.Generic;

class ProjectEuler32
{
    static void Main(string[] args)
    {
        var permutations = GetDigitPermutations();
        var alreadyHave = new HashSet<string>();
        Console.WriteLine(
            "Total: " +
            (GetMultiplicationComboSum(1, 4, permutations, alreadyHave) +
            GetMultiplicationComboSum(2, 3, permutations, alreadyHave)));
        Console.ReadLine();
    }

    static int GetMultiplicationComboSum(int multiplicandLen, int multiplierLen, char[][] permutationSet,
        HashSet<string> alreadyHave)
    {
        int sum = 0;
        for (int i = 0; i < permutationSet.Length; i++)
        {
			var productString = new String(permutationSet[i], multiplicandLen + multiplierLen,
				9 - multiplicandLen - multiplierLen);
			var multiplicandString = new String(permutationSet[i], 1, multiplicandLen);
			var multiplierString = new String(permutationSet[i], multiplicandLen, multiplierLen);
			var product = Convert.ToInt32(productString);
            if (Convert.ToInt32(multiplicandString) * Convert.ToInt32(multiplierString) == product)
            {
                if (alreadyHave.Contains(productString))
                {
                    Console.Write("Already have: ");
                }
                else
                {
                    alreadyHave.Add(productString);
                    sum += product;
                }
                Console.WriteLine(multiplicandString + " x " + multiplierString + " = " + productString);
            }
        }
        return sum;
    }

    static char[][] GetDigitPermutations()
    {
        var toFill = new char[9 * 8 * 7 * 6 * 5 * 4 * 3 * 2][];
        var toFillIndex = 0;
        Action<char[], int> permutationFinder = null;
        permutationFinder =
            (ca, ix) =>
            {
                if (ix == 9)
                    toFill[toFillIndex++] = ca;
                else
                {
                    var myca = new char[9];
                    ca.CopyTo(myca, 0);
                    for (var i = ix; i < 9; i++)
                    {
                        var c1 = myca[ix]; myca[ix] = myca[i]; myca[i] = c1;
                        permutationFinder(myca, ix + 1);
                        c1 = myca[ix]; myca[ix] = myca[i]; myca[i] = c1;
                    }
                }
            };
        permutationFinder(new char[] { '1', '2', '3', '4', '5', '6', '7', '8', '9' }, 0);
        return toFill;
    }
}

And here’s the output: