The Limber Lambda

After a gruelling end of 2011, I’ve finally had an opportunity to have some time off.  When you’re head down having to deal with the stress of trying to reach a deadline, other things tend to get neglected.  In my case, “other things” includes staying up-to-date with the technology status quo, whether it be keeping pace with my RSS feed or learning new things.

There has been so much fuss about Ruby that I’ve finally capitulated and decided to learn it.  Learning a new language is nothing to be sniffed at though, it’s a bit like eating an elephant—there’s only one way to do it—small bite by small bite.

Whenever someone decides to dream up a new language my immediate response is: “why?”.  Why spend all that effort coming up with yet another language when so many already exist?  I’ve decided that the answer seems to be: “because you can”.  Ok, trying to be a little less facetious about it … the reason why new languages pop up is because, of course, there is a need.  If there wasn’t, then any new language would surely die as quickly as it was proposed.

Yukihiro Matsumoto says that the guiding principle of Ruby is that of “least surprise”, that is, programming in a language (any language) should be a natural and intuitive process.  One shouldn’t have to fight with the language; after all, computers are there to assist us in getting things done.

Word Games

I’ve become addicted to Zynga’s word games, that is, the ones where you play against other users.  The only issue is though, that lately I’ve had a sneaky suspicion that one or two of my opponents are cheating.  When confronted with a cheater, the only option is take it to ‘em.

Here’s “Hanging with Friends” a delightfully contrived game where your character gets to hang over runny lava with a bunch of helium balloons being his/her only saving grace.  You make up words and your opponent has to guess them and vice versa.  Incorrectly guessing a word means that you lose a balloon … getting that much closer to the hot stuff.

If you’re itching to play, you can pair up with a random user.  Despite being chosen randomly (I think) all of my opponents are doing a pretty bang-up job of lava-dunking my little guy, so I figured that it was time for a Ruby script to level the playing field.

There are two opportunities for cheating, that is, a) when trying to guess your opponents word and b) when trying to come up with a word that your opponent needs to guess.  I cheat at both points.  Getting some computer-aided assistance for the former is straightforward, and I might talk about that in another post.  Now though, I want to talk about the latter, that is, coming up with a new word.

You can’t just choose any word; you’re given a random selection of letters from which to build a word.  How about if we had something that could tell us what words can be made out of the given letter selection?

Something along the lines of:

1. Find all permutations of letters for a given set, and …
2. Select those permutations that are actual words.

Straightforward, really.

English Language Words

There are a whole bunch of word lists for download, categorised in various ways.  I’m not particularly fussy and just went for “Kevin’s Word List Page”, in particular, the “Spell Checker Oriented Word Lists” (SCOWL).  The lists comprise a bunch of files, categorised by type of English (UK, US, Canada) and in some other ways.  For the purposes of cheating, I don’t really care, because you don’t get penalised if you enter an incorrectly spelled word—you just have to try again.

Using SCOWL, to get a list of all words (including some proper nouns), is a matter of …

cat /tmp/scowl-7.1/final/*

… after unzipping the SCOWL zip.

Permutations

I’m not going to pretend that I have some fancy way of figuring out words—my methods in this case are very practical … brute-force-style practical.

The method, then, is straightforward.  Given a target number of letters, and given a selection of letters from which you can choose a word, just find all permutations of those letters fitting within the target number of letters and check whether or not each is a real word.

Example:

All permutations of maximum three letters of the following set of letters: [ “a”, “b”, “c”, “d” ], gives us:

["a", "b", "c"]
["a", "b", "d"]
["a", "c", "b"]
["a", "c", "d"]
["a", "d", "b"]
["a", "d", "c"]
["b", "a", "c"]
["b", "a", "d"]
["b", "c", "a"]
["b", "c", "d"]
["b", "d", "a"]
["b", "d", "c"]
["c", "a", "b"]
["c", "a", "d"]
["c", "b", "a"]
["c", "b", "d"]
["c", "d", "a"]
["c", "d", "b"]
["d", "a", "b"]
["d", "a", "c"]
["d", "b", "a"]
["d", "b", "c"]
["d", "c", "a"]
["d", "c", "b"]

Of those, following are real words: bad, cab, cad, dab.

Loading English Words, Ruby-Style

The easiest way of doing this is to load all words from our word lists into memory, into a Hash.  This is fairly pedestrian, and looks like this:

  1: def load_words(path_to_word_files)

  2:     raise "Path \"#{path_to_word_files}\" is not a directory" unless File.directory? path_to_word_files

  3:     @words = Hash.new

  4:     Dir.new(path_to_word_files).each do |f|

  5:         path_to_file = File.join(path_to_word_files, f)

  6:         if File.file?(path_to_file)

  7:             File.new(path_to_file).each_line do |l|

  8:                 word_without_newlines = l.chomp

  9:                 @words[word_without_newlines] = word_without_newlines

 10:             end

 11:         end

 12:     end

 13: end

As promised by Matz, this stuff is easy to write and easy to read.  Anyone who has written some Perl can see a influence coming in to Ruby, in particular chomp (for removing newlines) and unless (used as a statement modifier).

Permutations

Once all the words have been hashified, what remains is brute-forcing all permutations.  Fortunately, Ruby has permutation-finding built in to its Array implementation.  What we need to do becomes:

  1: def get_words_with_letters(letters, word_length=8)

  2:     word_length = letters.length if letters.length < word_length

  3:     found = Hash.new

  4:     letters.chars.to_a.permutation(word_length).each do |permutation|

  5:         candidate = permutation.join

  6:         next if found.has_key?(candidate)

  7:         found[candidate] = candidate if @words.has_key?(candidate)

  8:     end

  9:     return found.keys

 10: end

In a single chained call on a string containing the letters that we can work with, we:

1. Get an enumeration of characters comprising the string;
2. Convert the enumeration to an array …
3. create an array containing all the permutations for a given length of word (each permutation being an array of characters) and
4. Enumerate the array, passing each item to a block.

A few more statements with modifiers gives us a terse but expressive bit of code that eliminates duplicates (as a result of multiple of the same letter being part of the original set), and adds the item if it is a real word.

An initial, rough-and-ready but effective script is now ready to join my arsenal of cobbled-together tools needed to bring humility to any would-be “Hanging” challengers:

  1: #!/usr/bin/env ruby

  2:

  3: class EnglishWords

  4:     def initialize(path_to_word_files)

  5:         load_words(path_to_word_files)

  6:     end

  7:

  8:     def load_words(path_to_word_files)

  9:         raise "Path \"#{path_to_word_files}\" is not a directory" unless File.directory? path_to_word_files

 10:         @words = Hash.new

 11:         Dir.new(path_to_word_files).each do |f|

 12:             path_to_file = File.join(path_to_word_files, f)

 13:             if File.file?(path_to_file)

 14:                 File.new(path_to_file).each_line do |l|

 15:                     word_without_newlines = l.chomp

 16:                     @words[word_without_newlines] = word_without_newlines

 17:                 end

 18:             end

 19:         end

 20:     end

 21:

 22:     def get_words_with_letters(letters, word_length=8)

 23:         word_length = letters.length if letters.length < word_length

 24:         found = Hash.new

 25:         letters.chars.to_a.permutation(word_length).each do |permutation|

 26:             candidate = permutation.join

 27:             next if found.has_key?(candidate)

 28:             found[candidate] = candidate if @words.has_key?(candidate)

 29:         end

 30:         return found.keys

 31:     end

 32: end

 33:

 34: def print_usage_and_exit

 35:     puts <<EOF

 36: #{$0[/[\w\d_-]+/]} <path_to_words> <letters> <word_length>

 37:

 38:     <path_to_words>     A folder containing English word files.  The format of word files

 39:                         is one word per line.

 40:     <letters>           A string of letters, a subset of which determine words to find.

 41:     <length>            Length of words to find (must be less then the lesser of

 42:                         the length of <letters> and 9).

 43:

 44:     Example:

 45:

 46:     #{$0[/[\w\d_-]+/]} /tmp/scowl/final trasse 5

 47:

 48:     yields:

 49:

 50:     tasser

 51:     tasers

 52:     terass

 53:     reasts

 54:     asters

 55:     assert

 56:     straes

 57:     stares

 58:     stears

 59:     essart

 60: EOF

 61:     exit -1

 62: end

 63:

 64: print_usage_and_exit if ARGV.length < 3

 65:

 66: words = EnglishWords.new ARGV.shift

 67: letters = ARGV.shift

 68: word_length = ARGV.shift.to_i

 69:


 70: words.get_words_with_letters(letters, word_length).each { |w| puts w }

 

I don’t know what a tostados is, but “Hanging with Friends” seems happy with it .

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:

This one got me thinking for a long time, mostly because I subconsciously eliminated “cheat” solutions.  The problem is to calculate an estimate of π by working out the perimeter of an n-sided circle-inscribing polygon.  Let’s start with some pictures:

Now, the obvious solution (focus on Figure A) is to use a trigonmetric function to solve the problem.  Using a convenient r = 0.5 (implies that the perimeter of the circle is π) one side of our polygon (d) can be determined as follows:

d = 2rsin θ

And since the perimeter of the polygon = p = nd, and r = 0.5, and θ = 2π/2n, then:

p = nsin (π/n)

All too easy, and well … we’re using π to find an approximation of π.  Somehow that doesn’t sit well with me.  Which is the reason why I took two days to come up with a solution that didn’t involve trigonometric functions, or π.  Enter Figure B.

We apply a method of virtual construction–let’s assume a cartesian plane, our circle having centre (0,0), and radius r = 0.5.  The method is iterative, so we’ll need to start with a guess of the length of a side of the polygon, R_guess =P_guess / n, where P_guess is our “perimeter guess”.  P_guess can’t be any larger than π, so let’s make the upper bound = 3.2.  R_guess then forms the radius of a “construction circle”, with centre (x,y), starting at (x₀,y₀) in the diagram.  The intersection of said construction circle and our original circle will determine a polygon corner; of course, since there are two intersection points, we eliminate the one that has already been “visited” (or occurs where y is negative in the case of the first attempt).  We progressively “construct” our way around the circle n times, each time using the previously determined “corner” as the centre of the next construction circle, finally arriving at the final intersection point: (x_n, y_n).  If R_guess was correct, then (x_n, y_n) would equal (x₀,y₀).  Adjusting R_guess for the next iteration then becomes a case of increasing P_guess if y_n turned out negative and decreasing P_guess if y_n turned out positive.  A simple zero-by-halving (aka Bisection) technique is employed to get a value for the perimeter that satisfies the accuracy constraint (1e-9).

The source code for my π-less solution is below:

using System;

class Archimedes
{
    public double approximatePi(int numSides)
    {
        double upperPi = 3.5;
        double lowerPi = 0.0;
        while (Math.Abs(upperPi - lowerPi) > 1e-10)
        {
            bool first = true;
            double cx = 0.5;
            double cy = 0.0;
            double piGuess = (upperPi + lowerPi) / 2;
            double lastCx = 0.0, lastCy = 0.0;
            for (int i = 0; i < numSides; i++)
            {
                double[][] intersections = GetCirclesIntersection(cx, cy, piGuess, numSides);
                if (intersections[0][0] == Double.NaN ||
                    intersections[0][1] == Double.NaN ||
                    intersections[1][0] == Double.NaN ||
                    intersections[1][1] == Double.NaN)
                {
                    cy = 1;
                    break;
                }
                if (first)
                {
                    if (intersections[0][1] > 0)
                    {
                        lastCx = cx;
                        lastCy = cy;
                        cx = intersections[0][0];
                        cy = intersections[0][1];
                    }
                    else
                    {
                        lastCx = cx;
                        lastCy = cy;
                        cx = intersections[1][0];
                        cy = intersections[1][1];
                    }
                    first = false;
                }
                else
                {
                    if (Math.Abs(intersections[0][0] - lastCx) < 1e-10 &&
                        Math.Abs(intersections[0][1] - lastCy) < 1e-10)
                    {
                        lastCx = cx;
                        lastCy = cy;
                        cx = intersections[1][0];
                        cy = intersections[1][1];
                    }
                    else
                    {
                        lastCx = cx;
                        lastCy = cy;
                        cx = intersections[0][0];
                        cy = intersections[0][1];
                    }
                }
            }
            if (cy < 0.0)
            {
                lowerPi = piGuess;
            }
            else
            {
                upperPi = piGuess;
            }
        }
        return upperPi;
    }

    private double[][] GetCirclesIntersection(double xo, double yo, double piGuess, int n)
    {
        double e = xo;
        double f = yo;
        double p = Math.Sqrt(e*e + f*f);
        double k = (p * p + 0.25 - (piGuess / n) * (piGuess / n)) / (2 * p);
        return new double[2][] {
            new double[] {
                (e*k)/p + (f/p) * Math.Sqrt(0.25-k*k),
                (f*k)/p - (e/p) * Math.Sqrt(0.25-k*k) },
            new double[] {
                (e*k)/p - (f/p) * Math.Sqrt(0.25-k*k),
                (f*k)/p + (e/p) * Math.Sqrt(0.25-k*k)
            }
        };
    }
}

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

So, you’ve used delegates with gay abandon and everything just seems to work.  In particular, this sort of thing works without a hitch:

	class Proggy
	{
		public static void Main(string[] args)
		{
			var p = new Proggy();
			Console.WriteLine(p.StuffThatNeedsDoing()());
			Console.ReadLine();
		}

		public Func<int> StuffThatNeedsDoing()
		{
			var ia = new int[1];
			ia[0] = 2;
			return (() => ia[0] * ia[0]);
		}
	}

I’m referring, of course, to the bit that returns a delegate that references a method variable. I’ve always been curious as to how that works, so I dug into the IL to reveal the magic.

The interesting bit is the implementation of StuffThatNeedsDoing():

Let’s take a closer look as to what is happening here:

• Behind the scenes, the compiler generates a nested class called <>c__DisplayClass1
  and encapsulates our int[] in it.
• L_0000 to L_000e news up an instance of <>c__DisplayClass1 and assigns the ia field therein to a new int[] of size 1.
• L_0013 to L_001b assigns the value 2 to element 0 of ia within the instance.
• L_001c to L_0028 news up a Func<int>, passing to the constructor the reference to <>c__DisplayClass1 and the address of a method on <>c__DisplayClass1 called <StuffThatNeedsDoing>b__0 (which turns out to be our delegate implementation).
• The new Func<int> is then effectively returned.

In short – it looks (unsurprisingly) like the local ia is no longer a local, and naively referencing it from within the delegate has caused it to be treated like a heap variable.  Of course our “local” ia now has a lifetime consistent with the lifetime of the delegate returned by StuffThatNeedsDoing—not a problem if we don’t mind, but what if we had referenced a “local” IDataReader from within our delegate?  The IDataReader, and associated unmanaged resources, would lurk around possibly for a very long time … something to be aware of.

So, as it turns out, the thing that binds a function to it’s “environment” (in this case, the local that we referenced) is known as a closure.