David Eisenstat

Stack Overflow

I answer algorithm questions on Stack Overflow. Here is my profile.


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.

Snake lemma

The snake lemma is a basic result in a branch of mathematics called homological algebra. I wrote a program to find a proof by diagram chasing.

Self-hosting compiler

A compiler from a small subset of C to x86 assembly that can compile itself. There are many like it, but this one is mine.


“Dahlia”, my entry in Keith Enevoldsen’s Logo 15-Word Challenge, is my oldest surviving program. It won the “Pure Logo” prize.

repeat 8 [rt 45 repeat 6 [repeat 90 [fd 2 rt 2] rt 90]]