I really should be doing statistical things with PW data right now, but I suppose it doesn’t hurt to go through a few more Haskell warm-up exercises.

In the darcs repos now is another literate Haskell file, Region.lhs. This has the task of finding all the contiguous subregions of a 2D polyomino puzzle board where some of the squares are blocked out (e.g. because they already have a polyomino placed on them).

The idea is that by measuring the number of squares in each subregion, and comparing it to the sizes of the polyominoes we have to place, we can tell immediately if it’s impossible to fit those polyominoes into that region because there will always be one or two squares left over (or one or two too few). This is cheaper than trying out all of the possible placements of polyominoes in the region, and allows us to prune the search tree fairly drastically in some cases.

My initial approach was to use the Data.Graph module, build a graph of all of the connected squares, then get the strongly-connected subgraphs of that graph using the function provided. But it turned out to be fiddly to build the graph in the first place - by the time we’d found all the edges, we might as well have mapped out all the subregions as well.

The approach tried here makes what I hope is fairly sensible use of the State monad, although the result looks a little like object-oriented programming turned inside out.

I think Literate Haskell is a really good way to go, incidentally. I’m very bad at commenting, generally speaking, although I try to make up for it by not writing monstrously convoluted code. But describing an algorithm in English, mentioning in passing the steps taken to implement it, feels very natural for me.