Dodge is a simple Flash game by Lewpen Kinross-Skeels. It’s difficult to play on a touchpad, and that was my excuse for not beating my friends’ scores until I wrote a program to do this (Vimeo).

Strawberry Fields

Strawberry Fields is a combinatorial optimization problem posed by ITA Software. I started working on it because I thought it was neat that, for the natural LP relaxation, the column generation subproblem is the two-dimensional maximum subarray problem examined by Jon Bentley in Programming Pearls. It turns out that Kadane’s algorithm for the maximum subarray problem cannot handle the side constraints introduced by branch and price, but the solver that I built for Strawberry Fields is still four orders of magnitude faster on the sample instances than a commercial integer program solver with no problem-specific tuning.

Since ITA Software has stopped using Strawberry Fields as a recruiting puzzle, here is my source code (tbz), to which I reserve all rights.