Sunday, October 24, 2010

Doublets - A Word Puzzle Game

Doublets is a word puzzle game invented by Lewis Carroll where the objective is to turn one dictionary word into another by changing one letter at a time. At each step, one letter may be changed, and the resulting word must be a valid dictionary word.

For example, to turn "milk" into "wine", "milk" changes into "mink", "mink" changes into "mine", and "mine" changes into "wine". Each intermediate word is a valid dictionary word. If we are given two arbitrary words, how do we determine the minimal number of intermediate steps needed to transform one word into the other?

Monday, October 18, 2010

Currency Arbitrage In 99 Lines of Ruby

A few months ago, I had the crazy idea of writing some code to automatically detect currency arbitrage given current foreign exchange rates. The brilliant plan was to (1) develop this evil-genius program (2) unleash it upon the market (3) and profit. Okay, not really, but the thought did cross my mind when for some unknown reason I was reminiscing about homework problems from my introductory data structures class. One of the problems involved looking for currency arbitrage in a graph of exchange rates, albeit it was a simplified exercise in depth-first search. The actual problem involves looking for a sequence of currency exchanges (a path in the graph) that starts at a given currency and ends up with more units of that currency than we started with. This problem is straight out of CLRS, and there are various solutions to it floating around on the web. Nevertheless, I decided to give it a go and see if arbitrage situations can really be found using real-world exchange rates.

Wednesday, October 13, 2010

Facebook Puzzles - User Bin Crash

The User Bin Crash puzzle (usrbincrash) is a quick and fun puzzle to solve (note: Facebook took down the original puzzle so I'm linking to another site with the description). After reading the problem statement, it should be easily recognizable as an inverted instance of the knapsack problem. The fact that there is a weight requirement is a dead giveaway. Unlike a burglar trying to maximize the value of the stolen goods in his knapsack, you're trying to minimize the cost of the goods being thrown out of the plane. Although the knapsack problem is NP-complete, it can be solved in a straightforward manner using dynamic programming.

Of course, it would be no fun to simply reveal the solution. Instead, I've decided to formulate the problem in parable form with a tropical theme. Hopefully, it'll help provide a more intuitive understanding of the knapsack problem. If you've been following along with my posts about various Facebook Puzzles and are interested in trying some of them out yourself, getting a good handle on dynamic programming will prove to be quite useful.

Saturday, October 9, 2010

Facebook Puzzles - Dance Battle

As I set out to solve the Dance Battle Facebook Engineering Puzzle (dancebattle), I realized that it was really just some sort of game (note: Facebook took down the original puzzle so I'm linking to another site with the description). It had alternating turns, repeatable moves, moves represented by non-negative integers, and was zero-sum. After some digging around, I realized that it was just a thinly-veiled version of a game of dominoes.

Naturally, it seemed fitting to present the solution to the puzzle in the form of the game it was modeled after. I had never played dominoes before, but I knew what the basic game pieces looked like since dominoes sets are among some of the more popular swag that certain companies like to give away at college career fairs. Nonetheless, I exercised due diligence and did some research on the game. Thus, I present to you Dance Battle, played out in the form of dominoes.

Wednesday, October 6, 2010

The Lego Minifigure Collector's Problem

I recently attended BrickCon and had the pleasure of listening to a very entertaining talk about Lego Minifigures. For those not in the know, Lego recently released a set of Lego Collectible Minifigures. Apparently, the collectible minifigures were made available for only a limited time, and come in "mystery" packages that don't show the minifigures inside, just like a pack of baseball cards.

In the Lego lovers circuit, these things are currently selling like hotcakes. The speaker at BrickCon likened the minifigures hysteria to a virus in that the collectible minifigures are like "small infectious agents." Lego fans are doing everything they can in order to collect every figure in a series.

Saturday, October 2, 2010

Facebook Puzzles - Gattaca

Continuing with my Facebook Engineering Puzzles series, here's the writeup for Gattaca (gattaca) (note: Facebook took down the original puzzle so I'm linking to another site with the description). The original problem statement is interesting in that it has a computational biology twist, but it's really a weighted interval scheduling problem in disguise. This one took me a while to recognize, even though I was barking up the right tree by looking for an optimal substructure that would lend to a dynamic programming solution. Ultimately, the key to the problem is that the order of the gene predictions is important, and is part of the solution.

For this writeup, I reformulated the problem in a more "classic" interval scheduling manner. I think treating the DNA strand as a timeline and the gene predictions as time intervals is a good way to gain an intuitive understanding of the problem and the solution.