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:

A colleague brought my attention to this brain-teaser, from Project Euler:

Having a Unix background, my first instinct was to fire up bc which I know can deal with integers of any size you like—such a calculator is known as an arbitrary precision calculator.

Here’s the one-liner, together with execution time:

Now, if you’re a Java programmer, you’ll know about java.math.BigInteger which is the implementation of an arbitrary precision integer.  Sadly, in the .NET world there is no built-in equivalent (soon to change in .NET 4.0).

What I did find interesting though was that the default (and only) implementation of integer in a lot of languages, including Python and Ruby is of the arbitrary precision variety (this also applies to Scheme and Lisp).  Since I have two implementations of python installed on my PC, namely cpython and IronPython, I could benchmark them from the command line.

First, cpython: And … IronPython:

Unfortunately the initialisation of the python runtime puts a nasty skew on our comparison in the case of IronPython.

Somehow, that just feels like cheating though, and even though there aren’t any set rules on Project Euler about how you come to the answer, of course, you just feel like you should be doing it a clever way; read: no use of a big integer library, built-in or otherwise.

The solution is simple, but deceptively so—why would we need to keep track of all those “more significant digits” if we never need them?  As long as we keep our eight byte integer from overflowing, we should be fine.  Hence our BigInteger-free C# version:

class Program
{
    static void Main(string[] args)
    {
        var largest = 10L*10*10*10*10*10*10*10*10*10;
        var tot = 0L;
        for (int i = 1; i < 1001; i++)
        {
            var exp = 1L;
            for (int j = 0; j < i; j++)
                exp = (exp * i) % largest;
            tot = (tot + exp) % largest;
        }
        Console.WriteLine(tot);
    }
}

And the result:

Continuing my “Sharpen Up” Series, herewith the next episode.

The problem is to find digits that:

1. For an integer n, divide exactly into n;
2. Also divide exactly into the sum of the digits of n.

For example, 3 divides exactly into 81 and also divides exactly into 8+1 = 9.  Except that the problem gets harder–there’s a requirement to count the digits for a particular base numbering system for which this property holds.  Using base 10, only 3 and 9 satisfy this property.  The problem statement indicates that if a digit appears to be a candidate for all possible numbers with less than 4 digits of the relevant base, then it is deemed true for all numbers.  The trivial cases of 0 and 1 should not be included in the count.

This problem took me 36 minutes to complete–here’s my solution:

using System.Collections.Generic;

// 4:30
// 5:06
// SRM150DIV1_250
public class InterestingDigits
{
    private int[] num = new int[3];

    public int[] digits(int Base)
    {
        List<int> interesting = new List<int>();
        for (int d = 2; d < Base; d++)
        {
            for (int i = 0; i < 3; i++)
                num[i] = 0;
            num[0] = d;
            bool exception = false;
            while (true)
            {
                if (((num[0] + num[1] + num[2]) % d == 0 &&
                     (num[0] + num[1]*Base + num[2]*Base*Base) % d != 0) ||
                    ((num[0] + num[1] + num[2]) % d != 0 &&
                     (num[0] + num[1]*Base + num[2]*Base*Base) % d == 0))
                {
                    exception = true;
                    break;
                }
                if (++num[0] == Base)
                {
                    num[0] = 0;
                    if (++num[1] == Base)
                    {
                        num[1] = 0;
                        if (++num[2] == Base)
                        {
                            break;
                        }
                    }
                }
            }
            if (!exception)
            {
                interesting.Add(d);
            }
        }
        return interesting.ToArray();
    }
}

Lesson learned–there’s a way of approaching TopCoder problems, and speeding through the problem description (missing some important, sometimes subtle hints as you go) is not the way.  Give yourself some time, maybe pull out a pencil and paper, doodle a bit, let your mind free.  Only then do you avail yourself of that light-bulb moment.

So, it turns out that the fast-food joint problem really isn’t that hard at all.  In a nutshell the time that a customer waits can be summed up as follows:

Wait_n = Arrival₀ – Arrival_n + Wait_n-1 + Service_n-1

… but only if Arrival₀ + (Wait_n-1 + Service_n-1) is later than (greater than) Arrival_n, otherwise Wait_n = 0

… and of course, Wait₀ = 0

That’s it–here’s the source:

public class BigBurger
{
    private int _MaxWait = 0;

    public int maxWait(int[] arrival, int[] service)
    {
        _MaxWait = 0;
        WaitFor(arrival, service, arrival.Length-1);
        return _MaxWait;
    }

    private int WaitFor(int[] arrival, int[] service, int ix)
    {
        if (ix == 0)
            return 0;
        int w = WaitFor(arrival, service, ix - 1) + service[ix - 1];
        w = (arrival[0] + w) > arrival[ix] ? arrival[0] + w - arrival[ix] : 0;
        _MaxWait = _MaxWait < w ? w : _MaxWait;
        return w;
    }
}

This is officially horribly embarrassing: 86 out of 250 points, and 1.5 hours later.  I simply could not get my mind around this one and out of sheer frustration ended up simulating the scenario (no doubt the most suboptimal solution) in painstaking detail.

This fast food joint has a queue (as they do), and a bunch of people arrive at integer value times provided in an array.  Congruent to this array is an array of integer durations of the same units indicating the time taken to serve the customer.  So if we have arrival = [1, 2, 3] and service = [10, 2, 10] then there are three customers, each arriving at time 1, 2 and 3 respectively; customer 1 has to wait 10 minutes for his order, customer 2, 2 minutes and customer 3, 10 minutes.  If consecutive customers arrive at the same time, they should be dealt with in the order in which they are encountered in the array.  The arrivals values will always be in non-descending order, and there won’t ever be a (fictitious) service of 0 minutes.  So, find the maximum time any one customer needs to wait to get to order.

It occurred to me that all of this isn’t very much help for anyone who chooses to try these problems themselves without benchmark input values and corresponding answers.  Here are the ones I worked against: {3, 3, 9} {2, 15, 14} = 11, {182} {11} = 0, {2,10,11} {3, 4, 3} = 3, {2,10,12} {15,1,15} = 7.

… and here’s my solution:

using System.Collections.Generic;

public class BigBurger
{
    public int maxWait(int[] arrival, int[] service)
    {
        int[] waitingTime = new int[arrival.Length];
        Queue<int> queue = new Queue<int>();
        int maxwait = 0;
        int index = 0;
        int time = 0;
        int lastStart = 0;
        bool started = false;
        while (queue.Count > 0 | !started | index < arrival.Length)
        {
            time++;
            foreach (int v in queue)
            {
                waitingTime[v]++;
            }
            if (queue.Count > 0 && (time - lastStart) >= service[queue.Peek()])
            {
                queue.Dequeue();
                lastStart = time;
                if (queue.Count == 0 && index < arrival.Length)
                {
                    started = false;
                }
            }
            while (index < arrival.Length && arrival[index] == time)
            {
                if (!started)
                {
                    lastStart = time;
                    started = true;
                }
                queue.Enqueue(index);
                index++;
            }
        }
        for (int i = 0; i < waitingTime.Length; i++)
        {
            maxwait = maxwait < (waitingTime[i]-service[i])
                ? (waitingTime[i]-service[i]) : maxwait;
        }
        return maxwait;
    }
}