The Limber Lambda

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;
    }
}

This one is an example of “trivial”.  Problem description: find how many digits in a given number divide evenly into the number.  This took me around about 2 minutes for a whopping 239 points out of 250.  My solution:

public class DivisorDigits
{
	public int howMany(int number)
	{
		int count = 0;
		foreach (char c in number.ToString())
		{
			if (c == '0')
				continue;
			if (number % (c - '0') == 0)
			{
				count++;
			}
		}
		return count;
	}
}

In an attempt to stay “Ninja sharp” on the coding front, I’ve committed to solving a TopCoder problem from time to time.  This is really just a self-improvement effort, and I don’t intend to take on the cream-of-coding at TC anytime soon.  Having dipped my pinky toe in the water I have to say that (in my oh-so humble opinion) the standard is somewhat high.  In every practice room there are three problems: “easy”, “medium” and “hard” respectively based on the maximum points that can be awarded.  The point system is a little obscure, but what I have determined is that the points you can earn is exclusively determined by the time taken to complete the problem.  The relationship is non-linear and although I haven’t dug into the details, I’m assuming asymptotic with some minimum value.  That is, your points seem to fall off quickly but gradually level out until you can’t “lose” any more.  So far, I’ve concentrated on “easy” and although some problems can be safely lumped in the “trivial” category, others are deceptively difficult.

Given the one-and-only criterion for success, one is quickly honed into punching out working code as quickly as possible.  Coding standards and niceties go out the window–faster is better and style counts for nothing.  Each problem can be coded in one of three languages, viz., C++, Java or C# (some problems have a “Python” as well, but it’s greyed out–possible future functionality?); erm … that would be C# 2.0, no thumping the competition with a quick lambda expression and a couple of extension methods.

For the sake of reference (and of course discussion), I’m going to post my solutions and the time taken to complete them (give or take a few minutes due to distractions) as episodes.  TC no doubt are ready to disembowel your children should you cut-and-paste their problem descriptions, so I will provide a paraphrasing in each case.

Episode 1 involves a fictitious pack of cards.  TC have made a noble effort to keep their problems real-world whilst still making them challenging–never-the-less I have to admit that they can sometimes be a little contrived.  So … there’s this pack of cards containing an arbitrary number of cards.  The cards in the pack are represented by characters in a string.  The cards have values ’0′ to ’9′, ‘A’ = 1, ‘T’ = 10, ‘J’, ‘Q’ and ‘K’ = 11, 12 and 13 respectively.  The rules are: go through the pack, removing all ‘K’s, and removing all consecutive pairs of cards whose total value equals 13, repeating the cycle as needs be and finally return the number of cards remaining when you can no longer remove any cards.  Not hard, but a little tricky–this particular problem, if solved in an insanely short amount of time gets you 250 points.  I left it for a day and got 75… The plan is to actually be rigorous about timing myself, making sure that I do this when I won’t be interrupted.  That’s for the future.

Here’s my solution:

public class CircleGame
{
    public int cardsLeft(string deck)
    {
        char[] work = new char[deck.Length];
        for (int i = 0; i < deck.Length; i++)
        {
            work[i] = deck[i];
        }
        int lastix = -1;
        int loops = 0;
        int count = 0;
        while (loops < 3)
        {
            int countstart = count;
            for (int i = 0; i < work.Length; i++)
            {
                if (work[i] == 'K')
                {
                    work[i] = '.';
                    count++;
                    continue;
                }
                if (work[i] == '.')
                {
                    continue;
                }
                if (lastix == -1)
                {
                    lastix = i;
                    continue;
                }
                if (val(work[lastix]) + val(work[i]) == 13)
                {
                    work[i] = '.';
                    work[lastix] = '.';
                    lastix = -1;
                    count += 2;
                    continue;
                }
                lastix = i;
            }
            if (countstart == count)
                loops++;
            else
                loops = 0;
        }
        return deck.Length - count;
    }

    private int val(char c)
    {
        if (c >= '0' && c <= '9')
        {
            return (int)(c - '0');
        }
        if (c == 'T')
            return 10;
        if (c == 'J')
            return 11;
        if (c == 'Q')
            return 12;
        if (c == 'A')
            return 1;
        return 13;
    }
}