My son recently picked up a copy of Rubiks Race, a kids’ board game that’s essentially a slide puzzle turned into a two-player showdown. You first generate a random target pattern by rolling nine six-coloured dice in a little container, and then each player slides their tiles around to match the pattern. Sometimes the target pattern is invalid – when it has 5 or more of the same colour – but how often exactly?
An application I’m writing requires a lot of linear interpolation of a function. There’s so much of it, in fact, that it was the biggest single contributor to the running time. In this article I show how I used Template Haskell to make it much faster and cut the overall running time of the application by about a third.
Diagrams is the best library for drawing diagrams in Haskell. But can it be used as part of a user interface so you can interact with parts of a diagram?
The answer is: yes.
Recently I was surprised by the behaviour of a Haskell program I wrote. This simple example demonstrates the problem:
This computes the length of the list formed by every n-sized combination of the letters “a”, “b” and “c”. For example, if
n is 4, the first few elements of the list are “aaaa”, “aaab”, “aaac”, “aaba”. (In other words, it’s a slow way to compute 3 to the power of
n.) I expected this program to take near-constant space, even though the list might be very long, because it can be consumed by
length as it is produced by
n increases the space required grows exponentially.
This article covers a small part of the internals of Diagrams, a Haskell library for drawing static and animated diagrams. In particular, I give an overview of how a diagram is represented, how paths work, and how attributes are applied to diagrams. The Diagrams library has a lot in it, so not everything can be covered in great detail in such a short article.
Understanding the internals of Diagrams is not necessary for using it effectively – you can make complex diagrams without knowing any of how it works. You might be interested in the internals if you want to extend the library, or add a new rendering backend, or just fix a bug or add documentation. This material might also be of interest to people who want to see examples of type classes, existential types and heterogeneous lists.
The schedule for the International Workshop on Modelling and Reformulation for Constraint Programming is now available.
The submission deadline for the International Workshop on Modelling and Reformulation for Constraint Programming has been extended to 16 July 2012.
Get more information here.
The game Minesweeper is a fun diversion, but even more fun would be to get the computer to solve it for us. I’ve written a basic solver for the version of Minesweeper from Simon Tatham’s excellent Portable Puzzle Collection, called Mines. My solver interacts with the game just like a human player would: by reading the screen’s contents and moving and clicking the mouse.
Here is a video of the solver in action.
The International Workshop on Modelling and Reformulation for Constraint Programming is on again! The submission deadline is 13 July 2012.
Get more information here.
A few months ago, Laurent Vaucher wrote a couple of articles (starting with this one) about solving the puzzle game Hexiom using search algorithms and hand-crafted constraint propagation. It looked like an interesting puzzle, and I was curious about how well a generic constraint solver would perform and how to model the problem. Here I describe how I used MiniZinc and Gecode to tackle it.