2048

It's been a while without any new posts here; I've been focused on projects where JavaScript or C are more suitable than Haskell (for me, anyway). But I did dust off GHC this weekend to write this no-frills clone of Gabriele Cirulli's popular '2048' puzzle game. It didn't come out quite as concise as I had hoped - maybe I'm a bit rusty? :)

As usual with my graphical stuff, you'll need the legacy (1.2) versions of SDL to compile this. And the font path may vary; adjust it for your system.

ramanujan's Π summation

When G.H. Hardy first began his correspondence with Srinivasa Ramanujan, he was amazed by the prodigy's elegant and surprising series for irrational and transcendental values. Although Ramanujan hadn't included proofs of the theorems, Hardy told his colleagues, "they must be true, because, if they were not true, no one would have the imagination to invent them."

For example, here's Ramanujan's sum for Π which, after just 3 terms, overwhelms IEEE 754 double precision. Modern discoveries, like spigot algorithms on non-decimal bases, can find a given individual digit in constant time. But for fully expanding Π, no one has surpassed Ramanujan's expression: both the Chudnovsky brothers and Yasumasa Kanada adapted it to achieve their milestone calculations.

generalizing langton's ant

Christopher Langton's ant can be generalized by adding states to the ant, producing automata known as turmites. Shown here is the behavior of one interesting two-state turmite, started on an empty plane. Click the thumbnail to see more generations; you'll see that this turmite always produces a framed square with the same distinctive irregular pattern.

gumowski-mira attractor

Here's an unusual chaotic attractor: the web doesn't seem to have much information on this one, except that it was invented to model particle trajectories in physics. A google image search for 'mira fractals' does turn up some pretty results though.

The system seems to give interesting results only when b is close to one. It behaves less chaotically when b > 1 is fixed, so you can actually animate it - click the thumbnail to see.

128-bit AES electronic codebook

Rijndael (the core of AES) is an algorithm that might actually be shorter and simpler in C, but I was curious to see how natural I could make it look in Haskell. Thanks to Jeff Moser and Sam Trenholme for their clear elucidations.

Note that this code only does ECB mode; it computes rather than hard-codes the S-box; and it could be vulnerable to side-channel attacks. So enjoy reading it, but don't try to make a serious encryption app out of it. That kind of thing is best left to the professionals :)

butterfly curve

Temple Fay discovered this complicated curve in 1989. It can be defined either parametrically or as a polar equation; I did it the former way.

One application I thought of for this is object motion in games: I tried it out by writing this little Canvas game, where the comets follow the curve's trajectory. The differences in plot density along the curve create natural-looking comet tails.

bézier curves

De Casteljau's algorithm is a fast, numerically stable way to rasterize Bézier curves. This code implements an interactive demo: click to append nodes to the curve's defining polygon, and drag any node to alter the curve.

convex hulls

This code demonstrates the Graham scan, an O(n log n) method for finding the convex hull (smallest enclosing polygon) of a planar point set. It's a great example of exploiting order: it works by sorting the set by angle about a known extreme point, allowing the hull points to be found in linear time.

A variation on the algorithm, noted by A.M. Andrew, sorts the set lexicographically and finds the upper and lower hull chains separately. This 'monotone chain' version is often preferred, since it's easier to do robustly.

more Π obscurantism

Here's an illustration of an approach to Π pointed out by Kevin Brown. Define f(n) as the nearest greater or equal multiple of n-1, then of n-2, etc (yielding OEIS sequence 2491). Then, inverting a result found by Duane Broline and Daniel Loeb, Π = n² / f(n).

But as you can see from the comment, the series converges very slowly!

segment intersection search

Here's a simple method I learned from Gareth Rees for finding the intersection (or parallel / collinear status) of two line segments. Rees credits Ronald Goldman, though I'd imagine the technique goes further back.

today in oblique approaches

If your standard library offers complex numbers and you're not in any hurry, you can't ask for much simpler (or more obscure!) ways to compute Π than this.

ikeda map

Continuing the theme of strange attractors, here's the well-known one embedded in the Ikeda map. The thumbnail at left shows the central 'vortex' of the attractor, and links to a larger viewport.

In these images, I've plotted the real and imaginary components along the x and y axes respectively. But the more popular way to visualize this attractor adds an extra parameter to the system and is expressed in trigonometric functions. Such adaptation of the code below yields these results.

hénon attractor

French astronomer Michel Hénon reported on this strange, fractal attractor in 1976. Since then, it has been among the most studied examples of chaotic dynamical systems.

langton's ant

For a round of code golf, I wrote this spare implementation of Chris Langton's remarkably simple universal computer. If you want amenities like pause, random starting pattern or even quit, check out this more complete version.

connett circles

Like Barry Martin's 'Hopalong' fractal, this dynamical system from John Connett was first published in Scientific American in 1986. This demo is interactive: successively clicking two points specifies a rectangle to zoom into. Doing so, you'll see that the system isn't actually a fractal. Instead of self-similarity, deep zooms reveal peacock-like images.