Learn the Zen of a Programming Language with Koans

I love the idea behind Ruby Koans: write a set of failing unit tests that teach you about the essence of ruby as make every test turn green. It's a brilliant idea. The tests themselves are usually simple and illustrative. You even get encouragement (or enlightenment? :-) as you fix them.

The good news is that this idea has spread beyond ruby. There are koans in many languages:

While learning a programming language is best achieved by writing a useful application, these koans are a very welcome (and fun!) addition.

Solving the Hyperpublic Coding Challenge in Mathematica

I quite enjoy the various coding challenges that appear to be gaining in popularity. Greplin's was a lot of fun and yesterday Hyperpublic released one of their own. Since I just noticed that a number of people have posted their answers I thought I'd post mine.

I like to use Mathematica for these challenges. Why? It's a really powerful environment, it's a lot of fun to use, I have a copy :-), and completing these challenges always teaches me more about Mathematica itself.

Challenge 1

In this test you're given a file that represents which users have invited others, defines an influence metric, and asks you to find the influences of the top three influencers.

Read in the sample file
l = ReadList[NotebookDirectory[] <> "Hyperpublic Q1.txt", String];

Define a function that returns the positions of the Xs in a line
CalcFriends[s] := Map[(#[[1]] &), StringPosition[s, "X"]]
This returns a list of the positions of the Xs in a String
E.g. CalcFriends of the fifteenth line (which represents a user with four friends) generates the indices of those friends
{12, 23, 84, 93}
A line with all Os (no friends for this user) gives
{ }

Map CalcFriends over the list of lines
f = CalcFriends[#] & /@ l

A recursive function to calculate a user's influence
Influence[l_List] := Length[l] + Fold[Plus, 0, Influence[f[[#]]] & /@ l]

Now we just map Influence over the output of CalcFriends and take the top 3

Take[Reverse[Sort[Influence[#] & /@ f]], 3]

Challenge 2

Here we're (essentially) asked to find the minimum of moves to achieve a target.

For some reason, even though I knew this was a linear optimization problem, I started coding it. A mistake caused me to rethink my approach which, when you're using Mathematica, usually goes along the lines of "Why am I writing code?! I'm sure there's a function for this in here somewhere!" :-)

Lo and behold, there was:
FindMinimum[ {p1 + p2 + p3 + p4 + p5 + p6, 
2 p1 + 3 p2 + 17 p3 + 23 p4 + 42 p5 + 98 p6 == 2349 && 
p1 >= 0 && p2 >= 0 && p3 >= 0 && p4 >= 0 && p5 >= 0 && p6 >= 0 && 
p6 ∈ Integers && p5 ∈ Integers && p4 ∈ Integers && p3 ∈ Integers && p2 ∈ Integers }, 
{p1, p2, p3, p4, p5, p6}]

But you should see Yaroslav Bulatov's solution for this problem, it's much more elegant.

Fun stuff... Not only does Mathematica give you some great tools for solving problems, it also solves them fast.

A Puzzle To Die For

Came across this very cool puzzle at Brisbane's Museum of Science: they'd cut a die into nine pieces and it was up to you to put it back together. Being a big fan of polyhedra the puzzle instantly appealed to me, but I also like the fact that it forced people to think of how a die is constructed. For example, which faces are opposite which? Given there were only nine pieces it wasn't hard putting it back together again but Katrine and I had fun solving the puzzle nonetheless.

Optimizing Facebook's "Hoppity" Puzzle

I found Facebook's puzzle page the other day. While it has some very meaty challenges, it also has a couple of trivial ones. These easy puzzles are there to allow you to make sure you can submit solutions (I'm not consistently getting mine to run but I'm hopeful that turning off "Always send Windows-friendly attachments" in OSX Mail will do the trick).

One easy puzzle is called Hoppity. Essential you count up from 1 to a specified number and follow these rules
  • For integers that are evenly divisible by three, output the exact string Hoppity, followed by a newline.
  • For integers that are evenly divisible by five, output the exact string Hophop, followed by a newline.
  • For integers that are evenly divisble by both three and five, do not do any of the above, but instead output the exact string Hop, followed by a newline.
This very simple program is typically written with a few if then else's, though you could also simulate a bitmask and use a case statement:

As soon as I'd written it I started wondering: can I optimize this? I mean, this is Facebook we're talking about. Endless scale. So if they offered a Hoppity function on the main page, you bet they'd have to make it run fast! :-)

Looking at this program it's clear that the output should repeat every 15 counts. Here's a Mathematica plot to illustrate this where I've replaced Hoppity, Hophop, and Hop with 1, 2, and 3 respectively.

So if you're ever interviewing at Facebook and you're given this problem (which would be surprising, I agree), you can offer this optimization to make sure the Hoppity feature doesn't take down their servers when they release it to all their members :-)

Pre-computing is always useful!