Tuesday, July 28, 2009

Fillomino puzzles

I work on the G12 constraint programming system. I've been putting together models for the forthcoming MiniZinc Constraint Solver Challenge; one of the most interesting was finding a model for fillomino puzzles. A fillomino puzzle looks like this (which I took from Vegard Hanssens' page to which I just linked):

1 . . . 1
. . . 1 .
2 4 . . .
1 . 2 1 .
3 . 1 . 2

The goal is to complete the grid by dividing it into "regions" (where a region is a maximally contiguous set of cells connected by their edges) where each cell in a region is labelled with the size of the region. Thus, a 1-region will contain a single 1 and have no bordering 1-regions; a 2-region will consist of two neighbouring cells containing 2s and have no bordering 2-regions; and so forth. Some regions may start with more than one cell filled in; some may have no clues filled in at the start. The solution to the problem above is

1 4 2 2 1
2 4 4 1 4
2 4 2 4 4
1 3 2 1 4
3 3 1 2 2

This is a surprisingly difficult puzzle to model due to the region contiguity constraints. My solution works as follows:
  • each cell is a potential "root" of a region (and each region has a single root);
  • neighbouring cells are either in the same region (and hence have the same number) or are in different regions (which must have different numbers);
  • each cell has a time step at which we label it (region roots are labelled at step 1, all other cells are labelled later);
  • any cell labelled at step t > 1 must be part of the region of a neighbouring cell labelled at step t;
  • each region must be labelled with the size of the region.
The time step labelling and the unique roots constraints ensure that regions grow contiguously. The problem with this model is that it is hard to get decent propagation out of it (propagation is where the search tree is pruned as far as possible after each choice point). A human solver will recognise that there's no point trying to fill in a region of four cells with 5s; I have not yet found any good way of describing this information in the model.

Google Wave

I watched the Google Wave presentation over the weekend. Wave is an open collaborative editing system that integrates e-mail, blogging, wikies, photo albums, various kinds of polling and data collection, under a single, simple abstraction. If it is as easy to use in practice as the demo looks, my guess is that it will radically change how people interact over the internet. Very, very cool.

Friday, July 24, 2009

I've just come across ASCIIMathML. It's superb!


`mu = E(X) = sum_x.x*P(X = x)`

`sigma^2 = V(X) = sum_x.(x-E(X))^2`

Update: there appears to be a bug in Chrome's rendering of these formulae in that the first `x`s should appear under the `sum` signs, not after them. I've added some '.'s to make the meaning clearer for Chrome users.

Tuesday, July 14, 2009

Solar power

This is a very interesting analysis of the cost of using solar power to provide base load electricity in Australia.

The numbers show that the Queanbeyan Solar Farm, which has been running in New South Wales since 1999, operates at a mean efficiency of 13.7%, with almost all energy being produced between 9a.m. and 3p.m., which is well outside the peak demand times. To move to an entirely solar based power system would therefore require masses of storage capacity, the cheapest of which would be pumped hydroelectric schemes. By the time you add everything up, the financial and environmental impact of going fully solar makes the whole idea impossible.

By contrast, going fully nuclear is vastly cheaper and, surprisingly, cleaner.

Update: here's a similar analysis for wind power. It doesn't look good, either.

Monday, July 13, 2009

Sleep habits

For the last couple of years or so I've found myself going to bed around 2 a.m. It's nice to have an hour to myself after the rest of the house is in bed, but staying up until the small hours has not been sensible. I've been increasingly ratty and lethargic and it's had an impact on the quality of my life. Last week my doctor told me to hit the sack as soon as I feel sleepy (usually before 11 p.m.), rather than push through the initial feeling of tiredness as I have been doing. Having tried this approach for a few days, I can't believe the difference it has made already: I feel years younger. Magic!

Friday, July 03, 2009

Scientific discourse and the climate debate

I've been following the global warming debate fairly closely for several years now. For a number of reasons, I am definitely skeptical about the standard alarming "concensus" predictions. To put it plainly, I remain to be convinced that the claims made really do stand up to scrutiny. For example, climate models are often consistently one or two degrees off the measured absolute temperature, which is why you only see reports of temperature anomalies - departures from some baseline. This, to me, rather flies in the face of glib claims that the models are "just physics". I have other issues with the models, but I don't want to talk about them right now.

What is depressing is the brutal, and in many cases embarrassing, level at which the climate debate is conducted. In any other field of science it is normal to have disagreements. Traditionally when this happens, one side or the other will eventually change their minds either through force of argument ("your logic is unassailable") or through reproducible experiment ("here is uncontrovertible evidence"). The argument may be vigorous, but it's almost never personal: the two sides can still go and enjoy a beer together even though they disagree.

The climate debate does not work this way. Instead of dispassionate argument, deeply unpleasant rhetorical devices are the norm. Here's a list I've observed in common use:
  • Pretend there is no debate. The matter is settled. Anyone who disagrees is either uninformed, deluded, or pushing some nefarious agenda.
  • Dismissing an argument simply because of who advanced it (ad hominem attacks are everywhere).
  • Compare the other side to some unpleasant group: if you disagree, then you're a denialist.
  • Question the intelligence and/or integrity of anyone who is not convinced.
  • Appeal to authority (which is apparently infallible).
  • You are not a climate scientist (and apparently therefore incapable of understanding or criticising any aspect of any climate science work).
  • Withholding of data and/or code so that results cannot be reproduced.
  • Censorship of critical commentary (thereby presenting a one-sided view of the debate).
  • There is a concensus. (I know of no other field where this argument would be advanced with a straight face.)
There are sinners on both sides, but in my experience the vast bulk of the mud slinging comes from the "warmists". Joining any discussion forum on the topic as a skeptic usually requires a strong stomach, a sense of humour, and is likely to leave an unpleasant taste in the mouth. What annoys me more than anything else is that the animosity makes it really hard to have a sensible argument: the warmists may well be correct, but they aren't going to convince me using the tactics I listed above.