Monday, December 21, 2009

Aikido

My aikido club held a black-belt grading last weekend. There were some excellent demonstrations of technique, including one standout first degree test and at least one top notch second degree test.

Since I wasn't up for grading, I had to take ukemi (i.e., act as a crash test dummy for the deshi who were grading). Somehow, every time I was called up the technique was something like shiho nage, which is one of the scariest throws to take. I was more than a little chuffed to find I'm finally relaxed enough to take these big throws without having to worry - if anything, I was having fun.

Th day after, however, I felt as though I'd been through the spin cycle in a washing machine. Ouch.

Wednesday, November 25, 2009

Scientific integrity

Incredible. In fact, the whole "climategate" release of letters is some of the best scientific street theatre we've had in decades.

The Australian press has, so far, been virtually silent on the issue, even though this unauthorized release of thousands of e-mails and files from the top players in climate science casts serious doubt on the credibility of climate reconstructions and the integrity of some key figures. This is especially significant now because of the carbon emissions (economic suicide) legislation currently being bulldozed through parliament.

Part of the reason may be because of the embarrassing level of uncritical support that the local science journalists have provided over the years to any alarming climate science findings. [Note to journalists: we scientists spend a lot of time being wrong - that's why it's called research and not engineering.]Link

Friday, September 25, 2009

Corruption of the scientific process

This is an amusing and disturbing description of a scientist trying to get a journal to publish his reply to a paper erroneously refuting his life's work.

The author refrains from mentioning his field, but it isn't the first time a story like this has come to my attention (see, e.g., Steve McIntyre's various experiences in the world of climate research at www.climateaudit.org).

Here's another amusing/disturbing story from the top ranks of the climate world.

Astounding. Compared with the commonly held myth that "peer reviewed" means "case proven", this sort of thing can only be doing real damage to both the scientific process and the wider public perception of science.

Addendum: I should qualify that last remark that by explaining that I am, and have been, a reviewer for several top tier computer science conferences for about a decade. My job as a reviewer is to decide (a) whether a paper is original, (b) whether it defends its thesis, (c) whether it has provided satisfactory answers to the reader's questions, (d) whether it is readable, and (e) whether it explains the research well enough for the work to be reproduced with reasonable effort by any other member of the community. If a paper fails this last hurdle then it is essentially a set of claims lacking adequate support. Now, even if I recommend a paper for publication, that does not mean I accept its conclusions as truth. Rather, I am suggesting that the work is of sufficient value that it may be worth replication. Replication, not publication, is the gold standard of science.

Friday, September 11, 2009

The Coloured Stamps Problem

This is a trickier variant of the Coloured Hats problem, due to Raymond Smullyan.

This time a mischievous student has placed two stamps on the foreheads of each of three sleeping philosophers, X, Y, and Z. The student then wakes them and explains that the pairs of stamps were drawn randomly from a set of four green and four red stamps (the remaining pair of stamps being hidden). He proceeds to ask each of the philosophers in turn whether they know which colour stamps are on their forehead:
X: no.
Y: no.
Z: no.
Then the student goes around the group again asking the same question:
X: no.
Y: yes!
How did Y solve the problem?

Solution

Let us write rr, gg, and rg for the three possible stamp combinations (red/red, green/green, and red/green). We will write X is rr to denote X having red/red on his forehead, and so on.

We can immediately reject the X is gg and Z is gg case, since Y would know immediately that he is rr (but doesn't). Similarly for X is rr and Z is rr.

So Y starts by assuming Y is rr.

We can eliminate all possibilities where X is rr (since Z would immediately deduce that he is gg) or Z is rr (since X would immediately deduce he is gg).

This leaves the possibilities
  • X is gg and Z is rg, or
  • X is rg and Z is gg, or
  • X is rg and Z is rg.
If X is gg, then Z knows he is not rr (since X would know he is gg, but he doesn't), and that he is not gg (since Y would know he is rr, but he doesn't), hence Z would know that Z is rg. He doesn't, hence X cannot be gg.

If Z is gg, then X would know on the second round that he was rg. He doesn't, hence Z cannot be gg.

The remaining possibility is X is rg and Z is rg. In this case, after the first round, X would know he must be rg, but he doesn't. Therefore X cannot be rg.

Y therefore concludes that he cannot be rr.

By symmetry, Y also concludes that he cannot be gg.

Therefore, Y knows he must be rg.

The Coloured Hats Problem

I've been enjoying Raymond Smullyan's "Satan, Cantor, and Infinity", trying to solve all the problems therein. This one is cute:

The Coloured Hats Problem

A student has placed a green hat on the head of each of three sleeping philosophers, X, Y, and Z. He wakes them up and explains that each of them is wearing a red hat or a green hat, but of course none can see what they themselves are wearing. The student first asks the philosophers to raise their hand if they can see at least one green hat. Of course, all three raise their hands. The student then tells them to put their hands down if they know the colour of their own hat. After a few seconds thought, the smartest philosopher puts her hand down. How did she solve the problem?

Solution

Let's assume the smart philosopher is X. X reasons that if X had a red hat then one of the other philosophers, Y say, would be able to immediately deduce that their hat must be green because Z raised his hand (Z sees at least one green hat). Since this has not happened, X concludes that her hat cannot be red and therefore must be green.

Sunday, August 16, 2009

Tents puzzle google gadget


I finally got around to setting up my tents puzzle as a Google gadget. You can use the this link to add it to your iGoogle page.



I used the Google gadget editor to handle things. It's quirky, but usable, although I really wouldn't want to develop anything serious in it to start with. For a start, it doesn't work in Chrome at present, nor does the preview window seem to display things like tabs or dynamic height control. I'm sure all these things will be fixed before too long.

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!

`e^(ipi)=-1`

`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.

Monday, June 29, 2009

ICFP Contest 2009

I spent a chunk of the weekend having a go at this year's ICFP contest. I have to say I didn't find the task very engaging: it was all about moving a satellite into different orbits and rendezvousing with other satellites. Being a computer scientist and not a rocket scientist I found this challenging in a tedious way: the problem revolved around the kinds of continuous mathematics I haven't been good at since I was at school, lo these many years ago. Oh well, I had some minor successes, but spent most of my time screwing up pages of bad rocket calculations. Hopefully next year's contest will appeal to me more.

Monday, May 25, 2009

Wednesday, May 20, 2009

Google Pages is migrating to Google Sites

The problem here is that Google Sites doesn't support JavaScript, which is going to make my tents puzzle unplayable. However, it turns out Google Gadgets is just what I need. I'll be looking into this over the next few evenings.

Sunday, May 17, 2009

Variable capture in C# closures

You have to be careful about variable capture when constructing lambdas in C#.  The following code does not do what you might imagine:

var xs = new List<Action>();
for(var x = 0; x < 10; x++) {
xs.Add(() => {Console.Write(x + " ");});
};
foreach (var a in xs) {
a();
}

This prints the following: 10 10 10 10 10 10 10 10 10 10
The reason is that the variable x is captured by the lambdas, not the value of x at the time the lambda is created.

To avoid this situation we have to make a local copy of x for each lambda:

var xs = new List<Action>();
for(var x = 0; x < 10; x++) {
var x_copy = x;
xs.Add(() => {Console.Write(x_copy + " ");});
};
foreach (var a in xs) {
a();
}

This prints 0 1 2 3 4 5 6 7 8 9 as expected.

Sunday, May 10, 2009

Plants vs Zombies

"I know you're in there, I can smell your braiiiiins!"

I'm having a hoot playing this game.

Thursday, May 07, 2009

Coin tossing problem

I saw aproblem posed at Lubos Motl's blog that started me thinking about this question: how likely is a run of h heads or more in k tosses of a fair coin?

I came up with a recurrence relation. Let P(h, k) = n(h, k) / 2^k be the probability, where n(h, k) is the number of sequences of length k containing a run of h or more heads.

If h > k then n(h, k) = 0. Otherwise we have two possibilities for a sequence containing h or more heads in a row:
  • an initial run of h heads, followed by k-h "don't care" tosses or
  • a prefix of length j < k-h-1 not containing a run of h heads, followed by a tail, followed by h heads, followed by k-j-h-1 "don't care" tosses.
Assuming now that h <= k, we have

n(h, k) = 2^(k-h) + sum (j in 0..k-h-1) (2^(k-j-h-1).nbar(h, j))

where nbar(h, j) = 2^j - n(h, j) is the number of sequences of length j that do not contain a run of h or more heads. This gives

n(h, k)
= 2^(k-h) + sum (j in 0..k-h-1) (2^(k-j-h-1).2^j - 2^(k-j-h-1).n(h, j))
= 2^(k-h) + (k-h).2^(k-h-1) - sum (j in 0..k-h-1) (2^(k-j-h-1).n(h, j))


Let's try this out. Consider the case h = 2.
  • k = 2 sequences are {HH};
    n(2, 2) = 2^0 = 1.
  • k = 3 sequences are {HH*, THH};
    n(2, 3) = 2^1 + 2^0 - 2^0.n(2, 0) = 3.
  • k = 4 sequences are {HH**, THH*, *THH};
    n(2, 4) = 2^2 + 2.2^1 - 2^1.n(2, 0) - 2^0.n(2, 1) = 8.
  • k = 5 sequences are {HH***, THH**, *THH*, T*THH, HTTHH}.
    n(2, 5) = 2^3 + 3.2^2 - 2^2.n(2, 0) - 2^1.n(2, 1) - 2^0.n(2, 2) = 19.
  • ...

Tuesday, May 05, 2009

Play by web board games

I've recently discovered MaBiWeb, an on-line interface to a dozen or so "Euro"-board games. It's free, has a simple interface, and the pace is about right for me (one or two turns per day). Recommended.

Monday, May 04, 2009

Escaping code symbols in blog postings

I wrote two bookmarklets to help escape code symbols in <textarea>s in blog postings (e.g., convert < to &lt; and so forth): Escape and Unescape.

I used a bookmarklet editor to create them, then dragged the editor generated links on to my bookmark bar. To use them, I highlight the appropriate part of a textarea and click Escape or Unescape on the bookmark bar.

Here's Escape:

javascript:
(function(){
var textareas=document.getElementsByTagName('textarea');
for(var i=textareas.length-1;i>=0;i--){
textarea=textareas[i];
var start=textarea.selectionStart;
var end=textarea.selectionEnd;
var prefix=textarea.value.substring(0,start);
var text=textarea.value.substring(start,end);
var suffix=textarea.value.substring(end,textarea.value.length);
text=text.replace(/&/g,'&amp;');
text=text.replace(/</g,'&lt;');
text=text.replace(/>/g,'&gt;');
text=text.replace(/"/g,'&quot;');
textarea.value=prefix+text+suffix;
}
}
)()

Here's Unescape:

javascript:
(function(){
var textareas=document.getElementsByTagName('textarea');
for(var i=textareas.length-1;i>=0;i--){
textarea=textareas[i];
var start=textarea.selectionStart;
var end=textarea.selectionEnd;
var prefix=textarea.value.substring(0,start);
var text=textarea.value.substring(start,end);
var suffix=textarea.value.substring(end,textarea.value.length);
text=text.replace(/&lt;/g,'<');
text=text.replace(/&gt;/g,'>');
text=text.replace(/&quot;/g,'"');
text=text.replace(/&amp;/g,'&');
textarea.value=prefix+text+suffix;
}
}
)()
To add these as links you need to perform the following substitutions:

s/ /%20/g;s/'/%27/g;s/"/%22/gs;s/&/%26/g;s/</%3c/g;s/>/%3e/g

By the way, if anyone knows how to identify in a bookmarklet which <textarea> in an HTML page has the focus, please let me know!

Sunday, May 03, 2009

Me punting on the Cam in 2008.  (I just found this while rooting through my photo albums.)
Posted by Picasa

WPF: StackPanel vs DockPanel and ScrollViewer

Mucking around with WPF (Microsoft's latest and nicest way of putting GUIs together), I spent an hour googling to find the following gem.

A StackPanel allows its children to occupy whatever space they need. Therefore, you will never see a scroll bar you have attached (via a ScrollViewer) to a child of a StackPanel unless you have explicitly set the ScrollViewer Height property. You won't see the scroll bar because the child will be under the impression it has all the room it needs.

A DockPanel, on the other hand, requests that its children limit themselves to the area in the window occupied by the DockPanel.

On the left you can see an application where a ScrollViewer is attached to a StackPanel in a child of a DockPanel. The scroll bar is visible because the StackPanel cannot be fully displayed in the area made available by the DockPanel. The document structure looks something like this:

DockPanel
...
TabControl DockPanel.Dock=Top
TabItem
ScrollViewer
StackPanel



On the right you can see the same application where the ScrollViewer's parent is a child of a StackPanel. The scroll bar is not shown because the child StackPanel thinks it has all the display area it needs. This document structure looks something like this:

StackPanel
...
TabControl DockPanel.Dock=Top
TabItem
ScrollViewer
StackPanel


JavaScript

I've been learning a bit about JavaScript (here are my notes).  It's essentially Lisp based on hash tables rather than lists.  Here's my implementation of the Tents puzzle you can play in your web browser, which uses the rather excellent jQuery library (highly recommended for all your web page manipulation).


Build your own HTPC/media centre

I built a home theatre PC (HTPC)/media centre about eighteen months ago.  It is fantastic!

Here are my notes on the construction.

Visual Studio Shortcuts

Here's my list of Visual Studio shortcuts for C#.

C#

I've been spending some time learning C#.  I spent two years as a post-doc researcher with Microsoft Research in Cambridge who have recruited some of the finest language researchers in the world.  I'm not a fan of OO languages, but the bright chaps and chapesses at MSR have been doing a decent job pushing functional programming and decent type systems into .NET and C#.  After Mercury, C# is now my second language of choice for large scale programming.

Here are some notes I've been making.

It's been a while

Good grief, I'm shocking at updating these things.

News since my last missive:
  • I'm now married;
  • I'm a second degree blackbelt in aikido;
  • I've become a father.
Lawks.