The Limber Lambda

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