Rafe's Blog

SnippetCompiler

2011-11-14T14:05:00.001+10:30

From time to time I need to try something out in C# in a few lines of code. It's always a bit of a pain setting up a new Visual Studio solution for the purpose (I've traditionally used a PlayPen project for this). I've recently discovered this little gem: SnippetCompiler. It's essentially a mini-IDE for just this situation. Smashing!

The Birthday "Paradox" and Guid Collisions

2011-09-29T15:44:00.002+09:30

The Birthday Paradox asks the question: how many people do you need in a room before you have a 50/50 chance of at least one pair sharing a birthday? It is a "paradox" only in the sense that the answer is a surprisingly small number to most.

Here's how it works.

Let `p` = "the probability of at least one shared birthday among `n` people".

We assume a year of `T = 365` days and, as usual with probability problems, we recast it by looking for the complement of the answer.

Let `p = 1 - q`, (i.e., `q` is the chance of no shared birthdays at all).

Well, there are `^T C_n` ways of picking `n` distinct days from `T` and there are `n!` ways of arranging each combination and there are `T^n` possible combinations. Hence,

`q = n! (^T C_n) / T^n`

We expand `q` as follows:

`q = (n! T!) / ((T - n)! n! T^n)`
`qquad = (T!) / ((T - n)! T^n)`
`qquad = ((T - 0) / T) . ((T - 1) / T) . ((T - 2) / T) ... ((T - (n-1)) / T)`
`qquad = (1 - 0/T) . (1 - 1/T) . (1 - 2/T) ... (1 - (n-1)/T)`

When `x` is small, we can use the approximation `e^x ~~ 1 + x`. This give us

`q ~~ e^(-0/T) . e^(-1/T) . e^(-2/T) ... e^(-(n-1)/T)`
`qquad = e^[-(n(n-1))/(2T)]`

And, since we're approximating, `n(n-1) ~~ n^2`, hence

`q ~~ e^(-n^2/(2T))`

Through the magic of logarithms we can infer that

`p = 1 - q`
`qquad ~~ 1 - e^(-n^2/(2T))`

`e^(-n^2/(2T)) ~~ 1 - p`

`-n^2 ~~ 2T ln (1 - p)`

`n^2 ~~ -2T ln (1 - p)`

`n ~ = sqrt[-2T ln (1 - p)]`

Now, for `p ~~ 1/2`, we need `n = 23`.

So, at any given soccer match, there is a 50/50 chance that at least one pair drawn from the players and the referee will share a birthday.

Guid collisions

A guid is, essentially, a 128-bit random number. Guids are used as an easy way of giving statistically (globally!) unique names to things without ever having to look at any of the other things that we have named, or anyone else has named, or will ever be named.

How many things do we have to name before we risk, say, a one in a billion chance of a naming collision?

`n ~~ sqrt(-2^129*ln(1 - 10^-9))`
`qquad ~~ 10^15`

That is, we can assign guids to about a million billion things before we have a one in a billion chance of a collision. Having even a million records in any application is rare. To put this in perspective, a billion seconds is roughly thirty years.

For almost all applications, this means you don't have to worry about guid collisions! [There's a much higher chance of something else being wrong with your program than a guid collision causing you trouble -- indeed, adding code to work around guid collisions is quite likely to increase the likelihood of a bug in your program.]

Robustness of the thermometer record

2011-07-19T14:57:00.000+09:30

This is an interesting post up at The Blackboard: it turns out that taking random 10% samples of the weather stations and computing global means gives you a very consistent picture (also, check out Steven Mosher's comment). This seems to align with Anthony Watts' Surfacestations project, which found that (somewhat to my surprise, at least) the poor siting of the majority of US weather stations doesn't actually affect the numbers very much.

These are both instances of good, basic fact checking carried out and reported honestly by eeevil sceptics.

Climate Model Accuracy on Absolute Temperature

2011-07-05T10:32:00.000+09:30

It has always bugged me that the output of climate models are reported as trends rather than as absolutes. Lucia Liljegren at The Blackboard putClimate model absolute temperatures together some time ago, which I think is illuminating. The climate models are way off base, it would seem.

Adding Files Etc. as "Resources" to Visual Studio Projects

2011-05-03T14:55:00.000+09:30

I recently wrote a unit test that needed some data that was too large to fit into a string literal. To fix the problem, I added the file containing the string data as a resource to my project:

In Solution Explorer, right click on the project Properties;
Click on Open;
Click on the Resources tab;
Click on Add Resource and follow the dialogue for adding a file.

In the source code I can refer to the string contents of my resource file simply as

MyNameSpace.Properties.Resources.MyResourceName

Of course, this scheme also works for data needed in other situations (e.g., logo images), not just unit tests.

Regular Expressions and State Machines

2011-04-15T11:14:00.006+09:30

I recently found out that some of my colleagues did not know (much) about regular expressions or state machines. These are amazingly useful concepts that I use on a daily basis, so I thought I'd try to set down everything you need to know about these subjects in one page (or thereabouts).

Regular Expressions for Searching

The most common use of regular expressions is for searching through text files. For example, if I wanted to search my source code for all class definitions that include the word 'Collection' in their class names, I would search on the following regular expression: 'class .*Collection'. This is read as "the word class, followed by a space, followed by zero or more of (*) any character (.), followed by the word Collection". That is, most characters are interpreted literally in a regular expression, but some are treated specially (e.g., '.' and '*').

Here's the typical core grammar of regular expressions (I use a, b, c to denote non-special characters and x, y, z to denote arbitrary regular expressions):

a -- the regular expression matching the (non-special) character 'a';
xy -- the regular expression matching x followed by y;
(x) -- the regular expression matching x (it is sometimes useful to treat a complex regular expression as a single item);
x|y -- the regular expression matching x or y;
x* -- the regular expression matching zero or more instances of x;
nil -- the regular expression matching the empty string (which in practice is just written as the empty string, rather than 'nil').

So, for example, the regular expression '(aa|bb)*c' matches any sequence of aa or bb pairs, followed by a c. That is, the language recognised by '(aa|bb)*c' consists of the strings {c, aac, bbc, aaaac, aabbc, bbaac, bbbbc, ...}.

In practice, the language of regular expressions is extended with plenty of syntactic sugar. Here are some standard extensions:

x+ -- the regular expression matching one or more instances of x (i.e., x+ = xx*);
x? -- the regular expression matching zero or one instance of x (i.e., x? = (x|nil);
[abc] -- the regular expression matching any of the characters a, b, or c;
[a-f] -- the regualar expression matching any of the characters in the range a..f;
[^abc] -- the regular expression matching any character that is not a, b, or c;
[^a-f] -- the regular expression matching any character that is not in the range a..f;
^ -- the regular expression matching the start of a line of text;
\$ -- the regular expression matching the end of a line of text;
\a -- the regular expression matching the escape sequence a (e.g., \* matches a literal *, \t matches a tab character, \( matches an open parenthesis, etc.)

There are many more (see, e.g., http://msdn.microsoft.com/en-us/library/az24scfc(v=VS.100).aspx for the .NET 4 regular expression language).

Learning these is easy and really, really useful!

State Machines

Imagine a machine with a set of lights. Each light is called a state and the machine is called a state machine. When the machine is started, it always starts with a particular light on (all other lights are off); this is the start state.

The machine takes as input a sequence of symbols of some type (e.g., characters, GUI events, messages, whatever you like.). As each symbol is read by the machine, which light is shining changes depending on which light was shining just before the new symbol was read and on what particular symbol was just read in. For example, if the machine is in state 3, say (i.e., light number three is on) and the next symbol read in is a 'q', then light 3 might turn off and light 7 might come one (i.e., reading a 'q' when in state 3 causes the machine to change to state 7). The machine has a transition rule like this for every possible input for every possible state.

Each of the lights on the machine is either red or green. The green lights denote accepting states and the red lights denote non-accepting states. If the input sequence finishes with the machine showing a green light, then the input sequence was accepted by the state machine. Otherwise the input sequence was not accepted.

The language accepted by the state machine is the set of input sequences that leave it in an accepting state. In fact, every regular expression has a corresponding state machine and vice versa -- they are two ways of describing the same thing!

For example, here's a state machine to match our earlier pattern (aa|bb)*c:

State	Input	Next state
s1 [start]	a	s2
	b	s3
	c	s4
	(...)	s5
s2	a	s1
s2	(...)	s5
s3	b	s1
s3	(...)	s5
s4 [accepting]	(...)	s5
s5 [error]	(...)	s5

Observe the inclusion of an error state (s5) which, like the Hotel California, you can never leave. This state just ensures that the state machine never enters an accepting state once the input has differed from the pattern we are trying to match.

[Aside: the fancy name for what I've just described is a deterministic finite automaton or DFA.]

Deterministic and Non-deterministic State Machines

The state machine described above is deterministic, meaning it is only ever in one state and each state transition is defined entirely by the current state and the next symbol to be read. This is a very useful notion for designing programs that have to process sequences.

One can also imagine a nondeterministic state machine. Such a machine would works like this: at any point, any collection of lights can be on (i.e., the machine could be in any one of these states given the input so far). The transition rules are relaxed so that each state can have multiple possible successors for each input, plus have the option of having successor states that can be reached without consuming any input at all. For example, the transition rules for state 3 might say "move to state 7 after reading a 'q' or move to state 8 after reading a 'q' or move to state 9 without reading anything". So, for our non-deterministic state machine, if light 3 is one of the lights that is currently on, then light 9 must also be on (because it is a "no input" successor to 3); also, if a 'q' is read next, then both lights 7 and 8 will come on.

Why is this idea useful? Well, here's the magic: you can always turn a non-deterministic state machine into a deterministic state machine (how this magic happens is a little beyond the scope of this article, but the starting point is to imagine every possible subset of lights on the non-deterministic state machine as corresponding to a single state on the equivalent deterministic state machine).

It's easy to see how to construct a deterministic state machine that handles simple sequences of symbols or repetition of simple sequences, the tricky bit is handling alternation (i.e., regular expressions of the form x|y). The easiest way of constructing a state machine to match x|y is to construct a non-deterministic state machine from the two state machines for recognising x and y (hopefully you can imagine how this might be done without too much difficulty), then we can turn that into a deterministic state machine.

In practice, textual regular expressions are typically just compiled into representations of their non-deterministic state machines and the matching algorithm simulates all possible state transitions at each point. This is actually quite effective, since the cost of searching a string of m characters with an n state machine is just O(mn) (and typically much less).

What Can't Regular Expressions Match?

Roughly speaking, regular expressions can't match any pattern that requires counting to arbitrarily large numbers. For example, you can't write a regular expression that checks whether the parentheses ( ) in a program are properly balanced, because a program can contain any number of parentheses.

[What follows is for extra credit.]

There is something called the pumping lemma, which says that for any state machine with n states that accepts some input of length n or more symbols, then that input can be written somehow as xyz (where y is a non-empty sequence and the length of xy is at most n) and the machine must also accept all patterns of the form xy*z (i.e., the machine had to go through at least one loop while recognising the y part in xyz).

How does this relate to counting patterns? Well, let's say we did claim to have a state machine with 4 states that matched all and only programs with properly balanced parentheses. Now consider the balanced input sequence '((((a))))', which our state machine duly accepts. The pumping lemma tells us that this must be decomposable as some xyz where y is non-empty and the length of xy is at most 4. Well, we only have four possibilities for x and y here -- it doesn't matter which one we end up with. Let's say the answer happens to be x = '(((' and y = '(' -- leaving z = 'a))))'. The pumping lemma says that our machine must accept all strings of the form xy*z, which clearly includes just xz, namely '(((a))))', which is clearly not balanced! Therefore our claim must be wrong: our 7 state machine does not match all and only well balanced programs. Since there is nothing in our argument that really depends on the 4 states starting point, the same thing must be true for any number of states that a parenthesis-matching state machine might have. Therefore, there is no regular expression (or state machine) that matches all and only well balanced programs. If you don't believe me, I encourage you to have a go at designing such a state machine!

I find all this stuff really rather beautiful.

What About Counting Support in Modern Regular Expressions?

Modern textual regular expressions usually include some support for counting, such as x{40,70} meaning "between 40 and 70 instances of the pattern x". This functionality comes at a cost: since the size of the equivalent ordinary regular expressions for these "counting" patterns quickly grows out of hand, they are implemented using backtracking pattern matchers. These are exponentially slower than non-deterministic state machines and it is easy to construct pathological search patterns that will cause these matching algorithms to take forever.

Further Reading

Here is a brilliant paper on implementing regular expression matchers.

Bayes' Theorem

2011-03-24T09:30:00.001+10:30

I recently read this beautiful explanation of Bayes’ theorem. I’d always thought it was a statement of philosophy, but it isn’t: it comes from plain old probabilities.

The formula for the conditional probability of A being true given that B is true is

P(A | B) = P(A & B) / P(B)

That is, the proportion of things that are A that are in B is equal to the fraction of the proportion of things that are A and B over the proportion of things that are B (I like to think of these things in terms of Venn diagrams).

We can rearrange the above to get

P(A & B) = P(A | B).P(B)

Now for Bayes’ theorem: let’s write H for our hypothesis and E for our evidence. We want to know how seeing the evidence E affects the probability of our hypothesis H being true. From the first rule above we have

P(H | E) = P(H & E) / P(E)

Now we can apply the second rule to P(H & E) to get

P(H | E) = P(E | H).P(H) / P(E)

Et voila! No magic at all.

As an aside, the raven paradox has convinced me that Bayesianism is philosophically superior to frequentism.

Radiation

2011-03-22T09:42:00.000+10:30

This chart tells you all you need to know.

Debugging WCF

2011-01-10T10:27:00.003+10:30

I'm relatively new to the world of Microsoft foundation libraries. For the most part I am impressed, but I cannot understand the idea of development libraries doing their best to hide errors from you unless you first speak the magic rites (I would have thought there ought to be magic rites to cause error hiding, not the other way around). Anyway, WCF -- Windows Communications Foundation -- is a pretty good RPC system which has this property. To turn on tracing so you can debug your application, follow this advice:

After some Live Searching (i was actually googling, but let’s make Microsoft think at least someone outside of Redmond uses Live Search) i discovered that you can enable WCF tracing. Bingo! Why didn’t Juval Lowy’s book mention this? It’s supposed to be the WCF Bible…. Oh well, thanks to Google, i mean Live Search, we now know how to enable WCF’s tracing:

<system.diagnostics>
<trace autoflush="true" />
<sources>
<source name="System.ServiceModel"
  switchValue="Information, ActivityTracing"
  propagateActivity="true">
<listeners>
<add name="wcfTraceListener" type="System.Diagnostics.XmlWriterTraceListener"initializeData="WcfTrace.svclog" />
   </listeners>
   </source>
   </sources>
  </system.diagnostics>

You can also use the Service Configuration Editor tool which is available in the Windows SDK, but spare yourself the pain of that tool and just copy/paste this xml in your config file.
Now run the service again, and do whatever it was that triggered the weird client-side exception. After the exception occurred, open the WcfTrace.svclog file with either an editor (it’s not very readable though) or with the Microsoft Service Trace Viewer tool (which is not too bad actually).

Mark Twain

2010-12-09T11:22:00.000+10:30

A Plan for the Improvement of English Spelling
by Mark Twain

For example, in Year 1 that useless letter "c" would be dropped to be replased either by "k" or "s", and likewise "x" would no longer be part of the alphabet. The only kase in which "c" would be retained would be the "ch" formation, which will be dealt with later. Year 2 might reform "w" spelling, so that "which" and "one" would take the same konsonant, wile Year 3 might well abolish "y" replasing it with "i" and Iear 4 might fiks the "g/j" anomali wonse and for all. Jenerally, then, the improvement would kontinue iear bai iear with Iear 5 doing awai with useless double konsonants, and Iears 6-12 or so modifaiing vowlz and the rimeining voist and unvoist konsonants. Bai Iear 15 or sou, it wud fainali bi posibl tu meik ius ov thi ridandant letez "c", "y" and "x" -- bai now jast a memori in the maindz ov ould doderez -- tu riplais "ch", "sh", and "th" rispektivli. Fainali, xen, aafte sam 20 iers ov orxogrefkl riform, wi wud hev a lojikl, kohirnt speling in ius xrewawt xe Ingliy-spiking werld.

.NET: IEnumerable is not lazy

2010-11-16T10:13:00.001+10:30

Just spent ten minutes working this one out.

If you have a variable

IEnumerable<Foo> SomeFoos = [...LINQ expression returning an enumerable...];

and then do this

foreach (var foo in SomeFoos) { [...update foo...] }

you will almost certainly not see any changes in the values in SomeFoos. Why not? Because each time you iterate through SomeFoos, the enumerator is run again, quite possibly recreating each item.

A solution is to force each item in SomeFoos to be manifested once. For example,

List<Foo> SomeFoos = [...LINQ expression returning an enumerable...].ToList();

Now things will work as expected.

[N.B. When I say "laziness", I refer to the standard functional programming practice of replacing an evaluated thunk with the result, thereby avoiding any repeated processing effort on subsequent reads of the thunk.]

WPF: Making ListBoxItems stretch the width of the ListBox

2010-11-11T13:51:00.000+10:30

This is unbelievably hard for something which must be universally desired.

By default, ListBoxItems occupy the width required by their contents, not by the width of the containing ListBox. This causes your optimistically formatted columns in each ListBox to fail to align.

Instead, add this in the Resources section:

<Style x:Key="StretchingListBoxItemStyle" TargetType="ListBoxItem">
<Setter Property="HorizontalContentAlignment" Value="Stretch"/>
</Style>

and add ItemContainerStyle="{StaticResource StretchingListBoxItemStyle}" to your ListBox attributes.

Strewth.

How to Make Visual Studio Really, Really Responsive

2010-10-08T16:22:00.003+10:30

Turn off ReSharper. So far, I miss it not a whit.

Configuring Visual Studio 2010's Tooltip Colours

2010-10-08T15:54:00.000+10:30

This has taken some finding. First, install the Productivity PowerTools Add-in. Then go to Tools > Options... > Environment > Fonts and Colors > Text Editor and change the settings for the Signature Help items.

Excellent C# Resource

2010-10-08T15:19:00.000+10:30

http://www.blackwasp.co.uk/Articles.aspx

Making things stretch in WPF

2010-10-01T16:28:00.002+09:30

I quote from a StackOverflow reply by one Matt Hamilton:

There are also some properties you can set to force a control to fill its available space when it would otherwise not do so. For example, you can say:
HorizontalContentAlignment="Stretch"
... to force the contents of a control to stretch horizontally. Or you can say:
HorizontalAlignment="Stretch"
... to force the control itself to stretch horizontally to fill its parent.

That should come in handy in future.

Synchronization in .NET: ManualResetEvents and Monitors

2010-09-30T09:37:00.003+09:30

I recently needed to simultaneously wake an arbitrary number of waiting threads, each waiting on some condition. My first approach was to have a shared ManualResetEvent, a subclass of EventWaitHandle with the property that "Once it has been signaled, ManualResetEvent remains signaled until it is manually reset. That is, calls to WaitOne return immediately." (MSDN docs.) [.NET also has AutoResetEvents, but with these only one waiting thread is woken when the event is signalled.]

The idiom I was using was this: I had a global ManualResetEvent called WakeUp; threads waiting on the condition would call WakeUp.WaitOne() (causing them to sleep until...); a thread identifying the waking condition would call WakeUp.Set(); WakeUp.Reset(). My reading of the MSDN documentation is that the call to Set() should wake all waiting threads, while the call to Reset() should reset the event handle for the next wake-up signal.

Tragically, this did not work and my program would randomly flounder. If I added a delay between the Set() and Reset() calls, the likelihood of floundering reduced, but wasn't eliminated -- and, besides, that is too disgraceful a hack to contemplate for more than a moment.

The right solution was to use a Monitor. The idiom here is as follows:

For Threads Waiting On Some Condition

Monitor.Enter(SyncObj);
while (!condition) { Monitor.Wait(SyncObj); }
Monitor.Exit(SyncObj);

which can be abbreviated to

lock (SyncObj) {
while (!condition) { Monitor.Wait(SyncObj); }
}

For Threads Establishing Some Condition

Monitor.Enter(SyncObj);
// Establish condition.
Monitor.PulseAll(SyncObj);
Monitor.Exit(SyncObj);

which can be abbreviated to

lock (SyncObj) {

// Establish condition.

Monitor.PulseAll(SyncObj);

}

Peace at last... (For the curious, in this particular application it would not have been sensible to set up a separate event handle for each condition, which is what one would normally do.)

State Machine Compiler

2010-09-22T15:07:00.000+09:30

I've just read about SMC, an open source state-machine compiler targetting multiple languages, including C#. I can see this coming in rather handy.

Trouble with nulls

2010-09-13T14:02:00.000+09:30

Following a conversation with a colleague, I have decided to put to paper what I think is wrong with nulls.

Essentially, this: to the compiler, null means "uninitialised". It is the default value given to references.

As programmers, however, we invariably overload null with other meanings, such as "the empty list", "the empty string", "the unspecified option", and so forth.

This is bad, because I want the tools (compiler, debugger, etc.) to tell me the difference between "I have forgotten to initialise this variable" and "I have put the wrong value in this variable".

As it is, I end up with a bastardised mixture of meanings in my code requiring a lot of checking that would otherwise be redundant.

Maybe code contracts will be able to clean up this mess...

Equality in C#

2010-09-06T12:09:00.000+09:30

Here is a good article on the subject.

I wish, I wish, I wish that C# had ditched nulls and default reference equality; that's such a 1960s resource limited way of thinking. Equality should mean structural equality by default; one should have to explicitly ask for reference equality or nullable types.

Oh well, here's the summary:

Implement IEquatable.Equals(T).

Remember to check for null and reference equality.

Override object.Equals(object).
object.Equals(object, object) does what you expect by first testing for nulls and reference equality.
Override object.GetHashCode.
If you implement == (reference equality by default), also implement !=.
Implement the == and != operators for value types to avoid the need for boxing.

WPF and XAML

2010-09-01T15:20:00.000+09:30

WPF is Windows Presentation Foundation. It seems like a first class framework to me.

XAML is Microsoft's eXtensible Application Markup Language. It is a way of describing user interfaces in XML. It is rich and powerful.

But, why, in the name of all that is holy, is it not composable?! For the life of me, I cannot understand why a fragment X works as expected in context Y, but not in context Z. Nor does the documentation I have been wading through (as in, trying to make progress through the Augean stables) been of any help. The whole of the net is filled with anecdotal solutions to common problems with, so far, not one whit of a general set of principles to help guide one through the quagmire of UI development using XAML. I am giving serious consideration to not using it on my next project, but rather coding everything up directly in C#. I would put money on this being vastly more productive.

I have just ordered a book on the subject that sounds as though it will explain things to my satisfaction ("Applications = Code + Markup" by Charles Petzold, who is apparently something of a luminary). Of course, this being a modern programming book it doubles as a keep-fit device, weighing in at something over 1000 pages.

PowerTab for PowerShell

2010-08-10T09:48:00.000+09:30

PowerShell is excellent.

The default command line environment was obviously written by a bunch of monkeys (who on Earth wants to block select rectangles of text rather than lines of text?).

PowerTab is a module that goes some way towards fixing the woeful keep-tabbing-until-you-hit-the-completion-you-want tab-completion behaviour.

Dates and Times and Timezones and .NET

2010-08-05T12:56:00.000+09:30

Yesterday I learned something about parsing dates and times. I was trying to get a .NET application to process date/time strings of the form "2010-08-04T16:30:00 CEST" using DateTime.TryParse. This approach didn't work because .NET doesn't grok timezone strings like "CEST" (Central European Summer Time).

My first thought was that since CEST is defined as UTC+2 (i.e., Universal Coordinated Time plus two hours), I could rewrite these date/time strings as "2010-08-04T16:30:00+02:00", which DateTime.TryParse can handle (note that the timezone delta on the end must be subtracted from the preceding date/time to obtain UTC). My attempts to tackle this were stymied by the fact that timezone names are not unique. For example, CST can mean either Central Summer Time or Central Standard Time, and that's just in Australia!

So, to conclude, for the love of all that is holy, don't use timezone names in your date/time strings. Use attached UTC deltas instead.

[For those who are wondering, as I did, the difference between UTC and GMT is never allowed to exceed 0.9s; UTC is atomic clock time with some leap seconds added here and there; GMT is not.]

DNS Problems with Blizzard's StarCraft II Patch Installer

2010-07-29T22:32:00.000+09:30

After much anticipation, my copy of StarCraft II arrived in the post yesterday. I installed it. I ran it. It immediately started downloading a patch. Ten megabytes later, I lost all internet connectivity. Again, again, and a-bloody-gain. Now, it turns out I had recently upgraded to Windows 7, a thing of beauty, which automatically ran a network diagnostic tool and reported that there was a problem with the DNS service. Hmm, thinks I, maybe iiNet (who are my otherwise rather good ISP) have cocked up their DNS server. After a bit of resettery, I discover that Google have a publically available DNS server (8.8.8.8). I add this as the backup DNS server and, lo and behold, glorious sustained connectivity.

Having shared this with you, I am now about to abandon society and join the StarCraftiverse for some time. Adieu.

Changing Jobs!

2010-06-25T16:25:00.000+09:30

After nine excellent years at the University of Melbourne, I'm leaving to take up a new position as a senior software engineer at an IT firm in the heart of Melbourne. I'll miss working with everyone at the University, but I'm also very excited about the new challenge. The chaps here had a whip-round and bought me a 1997 Speyside single malt. FANTASTIC! This bottle is what I believe is cask strength, at nearly 60% alchohol, and will have to be approached with caution.

Farewell drinks tonight!

Searle on Deconstructionism

2010-06-09T11:11:00.000+09:30

This is John Searle's priceless take on deconstructionism. One footnote is particularly amusing:

I said that deconstruction had found little appeal among professional philosophers. But there are some notable exceptions, much prized by deconstructionists. They tend to be ambiguous allies. One of these characterized Derrida as "the sort of philosopher who gives bullshit a bad name." We cannot, of course, exclude the possibility that this may be an expression of praise in the deconstructionist vocabulary.

A marvellous crytpic crossword clue

2010-06-02T14:23:00.000+09:30

Clue: hijklmno (5 letters)

Answer: water (highlight with your mouse to see the solution).

C# Namespaces

2010-05-01T16:48:00.002+09:30

Do not use the same name for a namespace and a class.

It only leads to madness and divorce.

I've just spent a merry half hour finding this out.

WotD: tropology and tropometer

2010-04-30T10:35:00.000+09:30

From Jarrold's Dictionary of Difficult Words:

tropology, n. figurative style of writing; interpretation of Bible stressing figurative nature of language.

tropometer, n. instr. measuring rotation.

WotD: ambry and ambsace

2010-04-29T09:21:00.000+09:30

From Jarrold's Dictionary of Difficult Words:

ambry n. niche; cupboard, espec. containing sacred vessels in chancel.

ambsace n. double ace; lowest score; bad luck.

False positives

2010-04-28T11:46:00.000+09:30

Consider an individual X who is tested for a disease.
Let D mean "X has the disease" and -D mean "X does not have the disease".
Let T mean "X has tested positive for the disease".
Let P(A) mean "the probability that A is true".
Let P(A|B) mean "the probability that A is true given that B is true".

We are given P(D), P(T|D), and P(T|-D).
(i.e.: the probability that X has the disease; the probability of getting a positive test if X really does have the disease; and the probability of getting a false positive test if X actually doesn't have the disease, respectively).
Note that P(-D) = 1 - P(D).

What is P(D|T)?
(i.e.: what is the probability that X has the disease given that X tested positive for the disease?)

Let u = P(D).P(T|D) be the probability that X tests positive and has the disease.
Let v = P(-D).P(T|-D) be the probability that X tests positive and yet doesn't have the disease.

These are the only ways X can get a positive test result. It follows that

Solution: P(D|T) = u/(u + v)
(i.e.: the probability that X has the disease given X tested positive is the fraction of positive results for X that are actually correct).

Practical application.

Since disease is rare, P(-D) will be much larger than P(D). Therefore if P(T|-D) (the chance of a false positive) is not very small, then v = P(-D).P(T|-D) will be large, hence P(D|T) will be relatively low (i.e., a positive test will probably not mean that X actually has the disease).

Bottom line: make sure your tests have a low false-positive rate.

Covariance and Contravariance

2010-04-23T12:36:00.002+09:30

On occasion I've mixed these terms up. Taking X : T to mean "X has/is compatible with type T", then:

X : T is covariant if X can also take on a subtype of T;

X : T is contravariant if X can also take on a supertype of T.

Consider the expression Ys = map(F, Xs) where
Xs : list(Tx),
Ys : list(Ty), and
F : U -> V.

Clearly F must accept values of type Tx (or some supertype thereof), therefore U must be of type Tx (or some supertype thereof), hence F is contravariant in its argument.

On the other hand, F must return values of type Ty (or some subtype thereof), therefore V must be of type Ty (or some subtype thereof), hence F is covariant in its return type.

Ugly Betty - Nooooooooo!

2010-04-19T14:00:00.000+09:30

Ugly Betty has aired it's final episode. We grow sad...

UB was the finest, smartest comedy I've seen on television and the cast and scriptwriters managed to maintain the level from start to end throughout all four of its seasons. Good for them for finishing it well rather than running the show into the ground.

UB was the comedy that the West Wing writers could have written. It was just that good.

My First StarCraft On-line Win!

2010-04-03T11:50:00.000+10:30

Kum bay yah, I have finally won a game. This is more of an achievement than you think given how bad I am at StarCraft. (I play as 'theoctopi' on ICCup if anyone's interested.)

Extended C type generator tools

2010-04-03T11:48:00.000+10:30

I've extended my set of C tools for generating common data types. Now there are generators for list types, 'maybe' types, and expanding array types. Now with one command line invocation you can generate hundreds of lines of bug-free (!) boilerplate C code.

Tool for generating algebraic types in C

2010-03-30T09:31:00.000+10:30

I've spent a few evenings crafting a tool to automatically generate C code implementing algebraic data types (or discriminated union types) from short specification files. For example, the following specification

@ type a_b_tree
@ constructor a
@ constructor b
@ constructor branch
l : a_b_tree *
r : a_b_tree *
@{
    if (l == NULL || r == NULL) {
        fprintf(stderr, "a_b_tree: branch cannot have NULL arguments.\n");
 exit(1);
    }
}@
@ end

expands to 144 lines of C (counting the .h and .c files).

The transformation supports

generation of constructor, deconstructor, and freeing functions;
optimised handling of constructors with no arguments (memory is not allocated for separate instances of these);
optimised handling of types with only a single constructor (there is no need in this case to distinguish between the type and its constructor);
user specifiable malloc and free functions;
user specifiable header and footer code for the generated .h and .c files.

You can download this tool here.

The anomaly method and UHI

2010-03-11T12:15:00.000+10:30

This is rather interesting. It seems the anomaly method of only considering digressions from the mean of a temperature series (i.e., the series' anomalies) does account for the urban heat island effect (i.e., it effectively removes the unwanted UHI component from the signal).

Grammar

2010-03-04T15:36:00.000+10:30

This is witty and helpful.

I particularly like

Don't string too many prepositional phrases together unless you are walking through the valley of the shadow of death.

Cute "proof" of Pythagoras' theorem

2010-03-01T10:00:00.009+10:30

[For reasons I have yet to fathom, the ASCIIMathML plugin doesn't want to work for this page...]

I'm reading The Mathematical Mechanic by Mark Levi, a tour of various mathematical results that can be obtained much more directly (albeit without proof) by appealing to our mechanical intuition.

Here's a beautiful proof from the book of Pythagoras' theorem, `a^2 + b^2 = c^2` where `a` and `b` are the opposite and adjacent sides of a right angled triangle and `c` is the hypotenuse.

Consider an ice skater of mass `m` on a perfectly smooth ice rink. The skater starts in the South West corner of the rink and pushes off against the South wall; the skater is now moving North with velocity `a` and hence has kinetic energy `ma^2/2`. Next the skater pushes off against the West wall and adds an Easterly component `b` to their velocity. The energy acquired from this second push is `mb^2/2`. Now, the skater's overall velocity is `c` and overall kinetic energy is `mc^2/2`. But this must be the sum of the energy acquired from each push, hence `ma^2/2 + mb^2/2 = mc^2/2`. Cancel the `m/2` terms and you have Pythagoras' theorem!

A roguelike I can enjoy

2010-02-24T14:58:00.001+10:30

Dungeon Crawl is a roguelike that I can actually enjoy over a coffee break (i.e., I don't have to dedicate years of my life to it). And you can play it over ssh.

Latin phrases

2010-02-23T09:48:00.003+10:30

"Nil carborundum illigitimi" - don't let the bastards get you down.;
"Nullius in verba" - take no-one's word for it (motto of the Royal Society, apparently suspended for climate related issues);

and my personal favourite:

"Sic biscuitus disintegrat" - that's the way the cookie crumbles.

Probability

2010-02-22T13:43:00.003+10:30

There's an interesting discussion on probability at William Brigg's blog.

Briggs claims, and is supported by some of his readers, that given

I have some six sided object in my pocket
Exactly one face is inscribed with '6'

we can conclude

P(a '6' shows uppermost after a roll) = 1/6.

I, and some other readers, contend that no such statement can be made. The discussion is interesting because some, like myself, see probability as a description of reality, whereas others see probability as a description of a state of knowledge.

I'll be fascinated to see how this one turns out.

Nuclear Power and Sustainability

2010-02-20T15:19:00.002+10:30

This is excellent: all the costs and numbers in context. If there's one good thing about AGW madness, it's that nuclear power is back on the table as a viable option.

Global temperature reconstructions

2010-02-09T11:10:00.002+10:30

This is an interesting and large collection of temperature reconstructions derived from various proxies. There is a pronounced Mediaeval Warm Period in most of them.

Homeopathic dilutions

2010-02-08T16:35:00.001+10:30

This is a hoot!

A quote from the full article:

Molecules are tiny: it takes about a billion of them to cover a standard metric full-stop. To put homeopathy in a medicinal context, if you wanted to consume a normal 500mg paracetamol dose you would need ten million billion homeopathic pills. Where each pill is the same mass as the Milky Way galaxy. There is actually not enough matter in the entire known Universe to make the homeopathic equivalent of a single paracetamol pill.

Handy WPF Tutorial

2010-02-02T10:45:00.000+10:30

This is a very helpful site.

I dearly love the English language

2010-01-20T13:45:00.002+10:30

I like things to be simple and regular.

Except for English. And women.

You should also read this. I particularly like

"Beware of malapropisms. They are a communist submersive plot."
"Don't string too many prepositional phrases together unless you are walking through the valley of the shadow of death."

Gnu readline wrapper

2010-01-20T11:25:00.001+10:30

I've just come across rlwrap, a neat little readline wrapper for other scripts and programs.

British Isles Snowbound

2010-01-10T09:50:00.002+10:30

This is an amazing satellite image:

Aikido

2009-12-21T09:20:00.003+10:30

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.

An interesting discussion

2009-11-30T16:20:00.000+10:30

Take a look at this.

Scientific integrity

2009-11-25T12:36:00.003+10:30

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

Corruption of the scientific process

2009-09-25T11:32:00.005+09:30

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.

The Coloured Stamps Problem

2009-09-11T10:36:00.006+09:30

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

2009-09-11T10:22:00.002+09:30

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.

The Stony Brook Algorithm Repository

2009-08-19T16:41:00.001+09:30

I've just stumbled across the Stony Brook Algorithm Repository. Could be handy.

Tents puzzle google gadget

2009-08-16T12:33:00.003+09:30

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.

Watchmen

2009-08-03T14:09:00.000+09:30

Brilliant, brilliant film.

Fillomino puzzles

2009-07-28T10:27:00.002+09:30

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

2009-07-28T10:23:00.003+09:30

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.

2009-07-24T15:20:00.010+09:30

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.

Solar power

2009-07-14T10:20:00.004+09:30

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.

Sleep habits

2009-07-13T10:07:00.002+09:30

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!

Scientific discourse and the climate debate

2009-07-03T15:39:00.002+09:30

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.

ICFP Contest 2009

2009-06-29T12:31:00.002+09:30

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.

JavaScript: DOM quick reference

2009-05-25T12:05:00.001+09:30

This is a rather handy quick reference to the JavaScript DOM interface.

Google Pages is migrating to Google Sites

2009-05-20T14:23:00.003+09:30

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.

Variable capture in C# closures

2009-05-17T11:45:00.003+09:30

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.

Plants vs Zombies

2009-05-10T13:06:00.001+09:30

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

I'm having a hoot playing this game.

Coin tossing problem

2009-05-07T15:17:00.008+09:30

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

Play by web board games

2009-05-05T10:17:00.002+09:30

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.

Escaping code symbols in blog postings

2009-05-04T15:13:00.009+09:30

I wrote two bookmarklets to help escape code symbols in <textarea>s in blog postings (e.g., convert < to < 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!

2009-05-03T17:38:00.001+09:30

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

WPF: StackPanel vs DockPanel and ScrollViewer

2009-05-03T16:59:00.009+09:30

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

2009-05-03T14:52:00.003+09:30

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

2009-05-03T14:51:00.002+09:30

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

2009-05-03T14:50:00.002+09:30

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

C#

2009-05-03T14:42:00.003+09:30

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

2009-05-03T14:40:00.002+09:30

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.

Blackbelt

2005-11-07T11:43:00.000+10:30

My Blackbelt Grading

I took my aikido blackbelt test on Saturday (5 November 2005) and passed! Two days later and I still have an enormous grin plastered across my face. This grading was, I suppose, the first major examination I've had since I sat my first degree back in '92 (my Ph.D. viva in '98 was nerve wracking, but in that situation I was the expert in the room). I've always enjoyed exams; I get butterflies, but I still usually manage to have fun. My blackbelt test was a bit different in that I was performing in front of the entire dojo and a scary Sensei.

I was convinced I'd fluffed it up. Everything was going really well: I reckon I was doing solid, spirited, precise technique, with virtually no corrections from the auxiliary examiners on my mat, until it came to kokyu nage, when my mind went completely blank and I froze up. It was a total nightmare: Sensei was going off at me, everybody was
waiting for me to do something, and I couldn't think of a single thing. I started thinking through everything I knew, picked the one thing I couldn't think of the name for, and it turned out to be right. Thank God. (Kokyu nage is the kind of "miscellanous" bin of aikido technique.) The nightmare continued. The next technique Sensei asked for - and he was still focussing on me - was tsuki tenchi nage (tsuki = straight punch, tenchi nage = Heaven-and-Earth throw), something which all the senpai I'd asked assured me didn't exist. So while everyone else on the mats was looking confused, I was the one getting the grilling. In the end I made something up and it must have been mildly convincing because I got away with it! In the break between gradings, everybody, including the instructors, were all trying out tsuki tenchi nage to try and work out what on Earth it might be... I'll have to ask Sensei what the answer is. The second set of candidates were a bit luckier: they had an identical test except no tsuki tenchi nage, lucky buggers. Anyway, after a second disaster I was sure I'd failed, so I just relaxed and tried to have fun. I was so frazzled that doing the high falls, which usually scare the bejeesus out of me, were a breeze. In fact, I think that was the most fun part of my test.

Richard said the look of surprise on my face when Sensei told me I'd passed was priceless.

Anyway, now that I'm a blackbelt I get to wear the hakama: the enormous baggy black aikido pants. Excellent!

Claire, Jill, Fergus, Rulande, and more aikido

2005-10-25T10:46:00.000+09:30

Claire

Friday I met up after work for drinks with Claire, who I haven't seen in over a decade. Claire is an old friend of Sarah, who I was going out with in Cambridge over ten years ago. I received an e-mail from Sarah out of the blue mentioning that Claire was working for six months in Melbourne, didn't know anyone yet, and could I take her out and get some drink into her. Which I did. I caught up with Claire at the Trust, an excellent city pub on Flinders Lane. Amazingly we recognised one another immediately! Anyway, we drank many drinks, ate some high quality Chinese food at Ants on the Tree in Chinatown, failed to get into Loop (apparently full to capacity), managed to get a few martinis in at the neighbouring bar (whose name I have never learned), and basically had a complete hoot. Much fun.

Jill

The next day I got up late and hungover and made a total horlicks of taking a short-cut to Hawthorne East where
Ammy and her mum Jill live. I arrived an hour late, which meant Ammy (a punctuality Nazi) was furious with me for at least ten minutes. God, I love a woman who forgives easily and I am going to marry her. Which, essentially, was the reason I was at Jill's place: Ammy had insisted that the Right Thing to Do was to ask for her mum's blessing before buying rings and proposing and that sort of thing. So I did and Jill (who had advanced notice) make a good attempt at looking surprised and then welcomed me into the family. The bottle of vintage Domaine Chandon I'd brought with me may also have helped. Jill is very like my mum in many respects and five minutes later she was making weakly veiled suggestions that I do something about my hair...

Fergus and Rulande

Fergus and Rulande are back in Melbourne for a couple of weeks and Ammy and I had them around to my place on Saturday night for dinner. In the end I cleaned and Ammy cooked: a kind of chilli con carne soup which turned out excellently. Much booze was consumed and a good night had by all. Marriage definitely suits F + R. Hopefully we'll get drunk with them again e're they fly back to Oregon.

Aikido

I've been training like crazy the last couple of months what with my black belt test coming on 5 November. The scariest thing by any reach has been learning high-falls. High-falls are necessary when someone is really going for it and is about to take off your head or your arm during a throw. When that happens you don't have time for a break-fall, which is where you fall underneath the attack. Past a certain level, you have to take high-falls instead, which involve doing a somersault in mid-air over the stressed joint (so this usually happens somewhere between waist and shoulder height) and hitting the mat with a spectacular thump on the other side. Eventually most people learn to do this with grace and style, but (a) I'm a rank beginner at these falls and (b) they scare the willies out of me. The trick is to be moving slightly ahead of the person throwing you, be very relaxed, jump high, stay connected with nage (the thrower), and not look down. Anyway, I did some pre-class training on Friday with Stewart, who is a seven foot giant with a black belt. I took high falls from him out of all the techniques I need for my black belt, they didn't hurt, and I was having a whale of a time (love those endorphins...). So Friday and Saturday I was feeling pretty good about my aikido.

Then on Sunday I went and trained in the park with Lucy and Elli and Dhao (who are also going for black belt) as has become our custom. Training went well until Richard, Lucy's fiancee, all round excellent chap, and superb nidan (second degree black belt), came over to test my high falls. Now Richard always does technique in a very effective, tight, correct fashion, which is actually much harder and scarier to fall out of in my humble opinion. Richard differs on this, but I think he sometimes forgets quite how much distance there is between a first and second degree black belt. Either way, after a fair deal of advice and correction I started thinking about the bloody high falls rather than just doing them, which for me is a fatal mistake. I ended up with sore joints and bruises and a severely battered ego. Grrrr!

But all is not lost. I trained a bit more on Monday evening with Neela and did passable high falls out of shiho nage and juuji garame, two of the scary throws. So I am resolved to avoid further advice from Richard on the topic (Rich has been so much help in training it's not true, but he just makes me more scared of the forward high falls when he tries to help there), just keep practicing, and hope not to need an ambulance on the big day!

Jiu waza (dealing with multiple attackers) is definitely improving. Got some very helpful sneaky-fix-up advice from James, another tops nidan.

2004-04-13T10:01:00.000+09:30

I declare this blog open!