1/03/2010
I finally got some time to code up a messy script to test out a few variations of an algorithm to generate rectangle-free single colorings of a grid, as part of a lazy humble effort to solve the 17 x 17 challenge.
This post is going to be a bit of a code-dump. The algorithm is essentially:
- color cell,
- turn to the right,
- stop on first non-rectangle forming cell,
-
if the cell is uncolored, color it and turn to the right, else if the cell was already colored and has been entered from this direction already, then skip it, else turn to the right
Read the rest of this article »
10/02/2010
The function groupBy from haskell’s standard library is defined in terms of span, the effect being that the supplied predicate function is used to compare the first element of a group with successive elements.
This isn’t clear from the docs, and you might try to do this and wonder at the output you got:
*Main> groupBy (< =) [3,4,5,3,2,1,4,4,1,1,2,3,4,5,4,5,6,7]
[[3,4,5,3],[2],[1,4,4,1,1,2,3,4,5,4,5,6,7]]
Read the rest of this article »
31/01/2010
I just finished an initial release of an interpreter for the befunge programming language, based on the ‘93 spec. The project was quite fun! My goal was to produce a well-designed program with performance that didn’t suck too bad. Here are some highlights:
Design
I found that writing the core functionality of the interpreter took almost no time, once I settled on the approach I would take. I used a monad transformer for the first time, StateT:
type REPL a = StateT ProgramState IO a
This let me pass around the state of the computation in the State monad while doing IO actions. This made some potentially-awkward befunge commands really easy to implement.
Read the rest of this article »