Blog of Matthew Daws

Jam 2014 Round 1A

As ever, links to: Official Contest Analysis and my code on GitHub.

Of current interest is how to progress: top 1000 people go through, and for that you'd need 55 points in a reasonable time. That is, solve all but the tricky statistics based question, Problem C.

Problem A, Charging Chaos: The problem is the find a "mask" which when xored with each outlet gives each device. Of course, what makes this tricky is that there is also an unknown permutation to find, to map the outlets bijectively to the devices. But you can find these iteratively:

• For the first bit, try the mask having bit 0: then you partition the outlets into two sets, those with bit 1 having 0, and those with bit 1 being 1. Also partition the devices similarly, and then the sets need to match in size for a bijection to exist. Similarly if the mask has bit 1 (then 0 for outlet maps to 1 for device).
• Then carry on, further subdividing the sets
• This gives a Backtracking algorithm, or, what amounts to the same thing, a Depth First Search with pruning.
• This is rather different from the official solution.

Code Jam Qualification 2015

As expected, flight back from Boston to Leeds via Dublin resulted in zero sleep, and so hopes were not overly high for the 2015 Qualification Round. But, only 20 points needed to progress, which can't be too hard, right?

Anyway, in the end, I got 100%, and seem to be the highest ranked UK participant. This, one suspects, won't last...!

Some code on GitHub. On the todo list is to update this post with some comments, but my solutions are pretty similar to the Offical Analysis.

Jam 2008 Round 1B

I found this to be somewhat harder than round A. Also, my solutions in Python, running on my 2013 era laptop, are rather slow, so really a C++ or similar implementation would be needed, especially on 2008 era hardware.

Again, The Official Contest Analysis is a good writeup, so I won't say a great deal. See the code on GitHub.

Code Jam 2013 Qualification

Continuing, here is the 2013 qualification round.

As ever, the Official Analysis is very good, and similar to my approaches. Some code on GitHub.

Code Jam 2014 Qualification

While on holiday, what better way to unwind than solve some old Code Jam puzzles?

As ever, the Official Analysis is very good, and similar to my approaches. Some code on GitHub.

Jam 2008 Round 1A

These seem to me to be essentially pure mathematics, in that once I understood the problem, and the maths behind it, the implementation in code was almost trivial.

The Official Contest Analysis is a good writeup, so I won't say a great deal. See the code on GitHub.

Problem A, Minimum Scalar Product: The only comment I have is that the formal "proof" the contest analysis gives seems overly complicated to me.

Google Code Jam

I was hoping to take part in Google Code Jam this year, but for much of Saturday the 11th I'll be transatlantic, flying back from Boston to Leeds, and I'm not sure I fancy my chances so much with jet-lag, no sleep, and much reduced amount of time...

But anyway, I thought it would be fun to look at past problems, and also to try to solve them in C#, as a way of learning more about the language. I must say that I've found it useful to solve the problems in Python-- it's nice having an iterative environment, and Python is generally fast enough.

So, here are my thoughts on the 2008 Qual round. See my code on GitHub.

Hello World

I had a need to update and move my old academic website so thought I would take the plunge and host a site on GitHub. Here is an aide-memoire for myself as to how I did this:

• How to get a website for your GitHub project: Pages

This blog is built using Jekyll: