I’ve always meant to write down a programming “stucklist”. It’s a list which you consult when you’re stuck. Maybe it tells you that you’re solving the wrong problem. Maybe it provides inspiration to fix the problem in a different way. Either way, when you’re under deadline pressure and your brain is dribbling out of your ears, a stucklist might just provide a way out. So, without further ado, here’s my initial stucklist:

Avail yourself of more facts
Can you solve a different problem?
Get out of the office and go for a walk.
How can else you make the problem go away without coding a fix for it?
Could you make the endusers avoid the problem area?
Go home and do something less boring instead.
Look at a more general version of the problem.
Or consider a more specific version of the problem.
Is it actually so bad not to fix the problem?
Fix one or more of the variables to simplify the problem
Grab someone, say “I’m a bit stuck” and throw some ideas around
Get someone else to fix it (evil bonus: they have to fix the fix too)
Can you buy in a solution, or spend money to make the problem go away?
Tell your manager that you’ve hit a problem and see if you can have more time, or redistribute work.
Get everyone else to workaround/avoid the problem area
Code a solution using a different style – recusive/iterative, stateful/pure, push/pull, table-based/computed.
How would you solve the problem if you had infinite memory or a super-fast CPU?
Can you put any supporting framework in place which makes the problem easier to fix?
Draw a diagram – I find it’s easier to walk through examples when you can look at something and point at it.
Assume that there’s a way to progress which doesn’t involve solve this problem – can you find it?

[Update: I’ve since found this page on the wiki which is similar]

X11 and maps

X11R6.8 is set to be released soon, bringing some welcome technology improvements to X11 along with lots of pretty eye-candy.

Completely unrelatedly, for a while now I’ve been thinking about how to make a free-as-in-freedom map of Edinburgh. Not just the kind of map which you look at, but also a semantic map which computers could process. It would allow route-finding applications – not just finding routes for cars, but also for cyclists who want to avoid busy roads and hills. Another application could tell you where the nearest ATM or pub was. There are hundreds of useful applications, all of which need high-quality semantically-rich maps. But, as far as I can tell, in the UK all of the commonly used maps are derived from Ordnance Survey data which, despite being a sort-of public body, charge royalties for the data.

Now, on one hand, that’s quite reasonable because it takes a lot of effort to make good maps. But, on the other hand, I have a strong feeling that somehow this information ought to be in the public domain. Local people and companies could use this data in all sorts of ways. It ought to be a shared community resource.

So, I’m left wondering how I can use technology to map Edinburgh. Maybe a combination of a digital camera, GPS and a bicycle would be a good way of grabbing useful raw datapoints? Finding existing public domain map data would be a really useful start – satellite images and photos from aircraft. And there was a recent conference about open-source mapping tools. I think I need to do some basic reading about map-making, because quite honestly I don’t know where to start.

MD5/SHA collisions cont

Now that the updated paper has been published, here is how to see the collisions for yourself:

1. Create, containing the following:

my $p = 
"d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89" .
"55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b" .
"d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0" .
print pack("H*", $p);

2. Also create containing the following:

my $p = 
"d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89" .
"55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b" .
"d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0" .
print pack("H*", $p);

3. Download from here

4. Verify it works by doing “echo -n abc |”. You should get 900150983cd24fb0d6963f7d28e17f72

5. Run “ |” and “ |” and you should get the same hash value (79054025255fb1a26e4bc422aef54eb4)

MD5/SHA collisions

Today has been a somewhat unusual day in the crypto world. Some people have found collisions in some of the major hash algorithms used today. In itself, it’s interesting but not earthshaking – after all, by their very nature, hash functions contain collisions. But a method for finding collisions in some restricted case could well lead to more general methods, which would get exciting.

Being a cynic, I tried to verify the results in the paper using the funky MD5 in 8 lines of perl, but I couldn’t recreate their results. That was a bit unnerving. However, this page explains the discrepencies. Once the paper has been presented, presumably all will become clear.

Double-press instead of shift

Here’s a keyboard idea, which I’m writing up here on the off-chance that MS hasn’t already patented it. I was trying to figure out a better way of entering left-parenethesis and right-parenthesis on my keyboard (since I used them all the time when I’m writing code (and also when writing blog entries)). Currently, I have to do the shift-9 combination which is poor because I have to move my fingers off their home keys, and also involves a nasty stretch. However, there doesn’t look like many better alternatives since I use all of the non-shifted keys regularly – I’d find it inconvienient if they got remapped to ‘(‘ and ‘)’. So if there’s no unshifted keys left then it looks like I’m always going to have to use some kind of shift key?

No, we can take inspiration from the mouse. I suggest using double-clicks on the keyboard as a way of entering indicating alternative inputs. So, two presses on the ‘9’ key in rapid succession would mean left-parenthesis and two presses in rapid succession on the ‘0’ key would mean right-parenthesis. Obviously this impacts on my ability to type “99” and “00” quickly, but in an average day I typed hundred of parentheses and hardly ever need to type “99” or “00”. On the rare occasion that I need to type them, I can simply leave a little pause (sufficient to exceed the double-click timeout) just like you do when you’re sending txts on a mobile phone without predictive texting.

Alternatively, you could use the length of time which the key was held down for to indicate an alternative input mode. Currently, almost all the keys will just auto-repeat when held down. How often is auto-repeat useful? For delete and the cursor keys it is often useful, but for the other hundred or so keys, it is less useful. So why not hijack that behaviour for more useful purposes?

Finally, we can use “chords” to indicate a whole different set of behaviour. Currently, if you hold down, say, “f” and “j” at the same time the computer will act as if you pressed “f” followed by “j” (or vice versa). It doesn’t notice that you deliberately pressed them both at the same time. If we make the computer respond differently to multiple simultaneous keypresses, we open up yet another set of possibilities for keyboard input without removing our fingers from the home keys. Effectively, we’re using the keys “a” to “z” as shift keys themselves. Clearly, you’d want to minimize the chances of triggering them accidentally whilst typing normal text so you may want to choose unlikely combinations (such as f+j) which are unlikely to occur in your normal typing (unless you write about fjords lots).

This gets rid of the need to move my hands off the home keys, and also gets rid of the awkward stretches caused by shift/ctrl combinations (although putting ctrl in the place where caps lock usually lives helps a lot too). Once I have figured out a way to get X11 to handle these cases, I’ll post it up. I also think it’s likely that keyboards from older computers used these tricks and more, but have been forgotten in the passage of time. Certainly the Spectrum used to minimize keystrokes whilst programming by automatically switching between modes as you typed, which was confusing to the uninitiated but quite efficient once mastered.