Eternities

Sunday, July 29th, 2007

Several years ago, before I even started this blog, I got caught up in an effort to solve an impossible jigsaw puzzle with a prize of 1 million pounds attached. Needless to say, I did not win the prize, but I did find the whole experience somewhat addictive, in that as a programmer I could of course leverage my skills to try to solve the thing computationally.

The puzzle was called Eternity, and in the end it was solved sooner than expected (within 16 months), by Alex Selby and Oliver Riordan. Pictured here is their solution (one of only two found, of a potential set of millions). And yes, the 209 pieces of the puzzle are uniform in color. They are also reversible, very sharp and made of cheap nasty plastic.

Two people I particularly remember collaborating with (sharing ideas datasets etc) were Brendan Owen and Miroslav Vicher.

Eternity the Second

Anyhow, now I find myself in a tricky position— should I dive into the new version? Considering how much time I spent on the last one, I’m not sure I can afford to… I have enough of a things-to-do backlog as it is, and an open-ended project like this could really suck up any and all of my free time.

I did of course go out and buy a copy yesterday (the worldwide launch date), and I can’t help observing that this puzzle feels like it was made for a computer solver. There are 256 square pieces to be placed on a 16×16 grid such that adjacent edges match colors and pattern, as in the simple 4×4 example to the right. Note that this sample has only 4 different symbol/color combinations, whereas the full EternityII has 22 variants… making it extremely color-blind unfriendly!

So… I guess it’s obvious that I’m going to spend at least some of my time exploring this puzzle (I don’t really expect anyone else to see this as a productive use of my time) and it remains to be seen just how deeply immersed I become.

UPDATE: Brendan recently appeared on Australian TV with Christopher Monckton (the puzzle’s creator) to talk about Eternity II, here is a to the interview on Youtube, where Monckton states that 10,000 of the world’s fastest computers searching until the end of time might not find a solution.

Early Results and Observations

Although Eternity II features 22 different joining symbols (or "colors" for brevity’s sake) only 17 are used internally, with the remaining 5 used only in the border pieces. This means that you can encode the puzzle with only 17 colors, since we can reuse 5 for the border pieces. For example, the mini-puzzle above could be encoded using only 2 colors even though it is represented here with 4, since 2 of the colors only appear in border pieces and the other 2 only appear internally.

Implementing the most basic brute force algorithm in software gives impressive results very quickly, with puzzles up to 12×12 in size being very quick to solve (just a few seconds in many cases), but as you step to 13×13 and beyond things get much harder very quickly. Another approach is to vary the number of colors instead of the board size… for example a 16×16 puzzle with 25 colors is pretty fast to solve (under an hour) since there are fewer ways to join pieces when so many colors are used. Conversely, using many fewer colors also makes it easier to solve, since there will be so many ways to join pieces that multiple solutions are bound to exist. 17 appears to be about the right number of colors required to make E2 impossibly hard.

The brute force approach is quite simple and uses a concept known as backtracking, which means that we place pieces in a very organized way (eg top to bottom) and when we get to a point where we can not place another piece we undo the last piece placed and try the next available option. If none of those options work out (which they likely won’t) then we backtrack further and try again. It’s a very easy method to encode and understand; the problem with it is that we could potentially tile 95% of the board before we get stuck, and sometimes the backtracking will take us all the way back to the first piece we placed.

Apocrypha

Tuesday, July 24th, 2007

INT. NIGHT - A HUMBLE LODGING WITH LARGE TABLE, AT WHICH JESUS SITS SURROUNDED BY HIS DISCIPLES, EATING BREAD AND DRINKING WINE.

Jesus:
I say again, one of you sitting at this very table will betray me. Nay, has already betrayed me.

Disciples:
No! No! Not us! Never!

Jesus:
And Peter, thou will deny me thrice before the cock crows…

Peter:
My lord, never!

A COMMOTION CAN BE HEARD OUTSIDE. BOOTS, HARSH VOICES AND THE SOUND OF SPEARS RATTLING.

Disciples:
Aieee! It’s the Romans!

Jesus:
It is as I have foreseen… Alas, the end is near.

Jack Bauer:
Sir, the soldiers will find us within moments. We have to move you, now!

Jesus:
No Jack, my time is come and there is nothing to be done. Be at peace.

Disciples:
We’re going to die! We have to escape!

Jack:
[pulling Jesus aside]
Sir, with all due respect I find this unacceptable– I cannot allow you to be captured, your mission is too important… you have to let me them take me in your place. If you hurry you can escape while there is still time!

Jesus:
Dearest Jack, I thank you for your concern, but I will have it no other way. You must let them take me, for it is me they have come for. I am ready, come what may.

Jack:
Yes sir… if that’s how it must be.
[he bows, then pauses]
There’s just one thing I need to know…

Jesus:
Yes, my ch–

WITHOUT WARNING JACK SLUGS JESUS IN THE JAW, KNOCKING HIM DOWN HARD, AND OUT COLD. JACK CROUCHES TO CHECK HIS PULSE THEN DRAGS THE UNCONSCIOUS JESUS INTO THE SHADOWS

Jack:
[hissed whisper]
I need to know you’ll stay alive.

SEVERAL ROMAN SOLDIERS COME BARGING INTO THE ROOM.

Head Soldier:
Where is Jesus of Nazareth, we have an order for his arrest!

Jack:
I am he.

Disciples:
Wha…?

Jack:
My friends, it’s over. Let them take me and do not resist– that’s an order. This is for the best, I swear to you.

Disciples:
Uh, ok, I guess, Jesus.

EXT. PILATE’S HOUSE - JACK IS HELD BY SOLDIERS AND FACES PILATE WHILE THE JEWISH HIGH PRIESTS OBSERVE.

Pilate:
So, you are this King of the Jews everyone is talking about eh?

Jack:
If you say so.

Pilate:
I hear such great things of you, some even say that you perform miracles… Why not show me some of this magic of yours!

Jack:
[gritting his teeth]
I can’t.

Pilate:
And so modest! Oh come on… turn my water into wine, and I shall set you free!

Jack:
I said I can’t.

Pilate:
[menacingly]
Do you understand what will happen if you do not do as I ask?

Jack:
I do.

Pilate:
So be it.
[he washes his hands]
I wash my hands of you…
[to the assembled]
Take him away and crucify him!

Jack:
Dammit!

The TV I don’t watch

Friday, July 20th, 2007

CSI anything, Criminal Intent, Law and Order SVU etc… I really don’t like these forensic/psychological investigation shows. Every episode seems to open with these incredibly judgemental pricks standing over the corpse of someone who’s just been killed in an unusual way, and making the most terrible unfunny jokes at the victim’s expense. Heaven forbid if you’re transexual or a performance artist and you get murdered in New York or Miami…

Medium, Ghost Whisperer… Oh how I hate these with a passion. So so awful. How many times can they refer to their "gift" in a single episode? Did Sarah Michelle Gellar ever speak reverently of her "gift"…? The answer is no, because Buffy was never intended to be taken seriously by a credulous public. And Patricia Arquette’s monotonous falsetto is worse than nails on a blackboard… arggg!

Men in Trees, Desperate Housewives, Grey’s Anatomy… hurrrrkk! So very very painful, so full of manly men with stubble who inexplicably appear to enjoy the hyperactive banter of insecure, overachieving women with intimacy issues. Far too many meaningful looks, and painfully self-conscious comic relief.

The New Adventures of Old Christine, The War at Home, How I Met Your Mother, My Wife and Kids… I suspect this stuff is just junk we buy cheap to fill air time, because no one in their right mind could ever describe themselves as a fan of one of these shows. These are like the death rattle of the American sitcom.

I need defragging

Thursday, July 19th, 2007

My ability to process anything is really piss poor right now… I seem to be in a perpetual state of distraction so that no project or activity gets the attention it requires. I really want to be able to launch my all new non-wordpress blog in time for the 5th aniversary of intepid/jujublog next month, but progress is unbelievably slow. I spend 10 minutes fiddling about and then become overwhelmingly tired and have to go to sleep.

Probably it’s also something to do with working full time as a programmer… that’s where all my creative energy is going right now, and it’s hard to do anything but laze about in my spare time, but I really want to get things done in my spare time as well, otherwise I feel guilty and annoyed because I am making no progress on my own projects. When I wasn’t working full-time I certainly procrastinated, but at least the procrastination would often involve starting whole new projects or being otherwise creative.

And so now in my spare time I mostly just download and watch TV, because it requires so little from me :)

Harry Potter and the something of the something

Monday, July 16th, 2007

A lot more enjoyable than Ocean’s 13, but still left me rather cold. A similar complaint is that made up technology is no substitute for real action, although in this case the technology is of the magical variety. Wizard fights are just boring because magic has no set limits, and there’s only so many bolts of enery shot out of wands I can sit through before it all gets a bit ho hum. Dumbledore is brilliant, Snape is good, Sirius is not seen nearly enough (considering the plot), but the kids are very forgettable— except perhaps for Luna Lovegood, who is likable mostly because she is different.

Also shown at the screening was a trailer for The Golden Compass, the first in the His Dark Materials adaptation, and I was slightly saddened to see how much it looked like a blend of Harry Potter and Narnia… I really wish they’d focus less on the glorious fantasy vistas and more on the incredibly strong characters and story. The casting seems pretty decent at least, with Daniel Craig beardied up as the gruff professor and Nicole Kidman as [ice queen bitch from hell] Ms Coulter. I can’t wait to see how much of the church bashing makes it into the final cut (probably not much, but here’s hoping).

Ocean’s 13

Monday, July 16th, 2007

I can’t believe I made the mistake of seeing this one; after the previous sequel I should know better. Ocean’s 12 made me angry with its stupid holographic Fabergé egg + Julia Roberts plot line, and 13 just makes me sad, because it is not even so imaginative. What kind of entertainment is there to be had in a heist movie when every problem and every solution consists of some bullshit made up technological contrivance? Ugh! And oh! but aren’t George Clooney and Brad Pitt just so dreamy when they slouch about in immaculate suits finishing each other’s sentences!

Google Primes

Sunday, July 15th, 2007

Seems like a reasonable description of numbers which only appear once in a google search. Try finding one shorter than nine digits, and you’ll be at it a while. The average number of matches for an eight digit number appears to be between 5 and 10, which means I have no trouble believing that their index really is frikkin huge. It’s also a great way to find a page almost randomly… maybe Google should have an "I’m feeling REALLY lucky" button for those occasions when you don’t even know what you’re searching for in the first place.

Unblogged Stories

Sunday, July 8th, 2007

Cleaning out my old document folders I came across some bits and pieces that I wrote years ago, before I had the sense to just start writing stuff in a blog instead. I still maintain this as one of the best reasons to make a journal public; it prevents the author from disappearing up their own arsehole, safe in the knowledge that it will never be read. Anyhow, quality varies wildly and most of it will never see the light of day, but the following brought back a funny memory.

Out walking in Newtown, waiting at traffic lights to cross the road (opposite the post office). On the other side is a cute girl, not unusual given the location. Waiting waiting waiting. She’s pretty cute.

Birdsong. Where the hell is that birdsong coming from? It sounds like one of those plastic whistles you put water in, but I can’t see who’s doing it. It’s coming from across the road.

The walk signal goes, everyone starts crossing, and she is looking straight at me— and smiling! And did I mention she is cute? Birdsong continues, still no idea where it’s coming from, and I’m meeting her gaze and now I’m smiling too. We’re walking toward each other grinning like idiots like we have some amazing shared secret. Time slows as we walk past each other but we can’t stop, so we keep walking, with a final sidelong glance. I get to the other side feeling kind of light, and still kind of in slow motion, and I turn slowly to see that she is doing exactly the same thing on the other side of the road, and for a frozen moment we are staring across at each other like a couple of weirdos. But I haven’t actually stopped walking, and so… I just keep walking. Like an idiot. And the birdsong is gone, still no idea where it came from.

A very nice moment though.

Then I think hey, she wasn’t really looking at me, maybe there was a giant sparrow circling just above my head, singing loudly. And then I realize, oh no I must have some kind of shit on my face, and she was laughing at me, not with me, and so then I walk along trying to discreetly examine my reflection in shop windows.

Ah yes, charmingly insecure me, eh? A nice epilogue to this story is that over coming weeks I found myself catching fragments of the same birdsong, and finally realized that it was this one homeless guy who just wandered up and down the length of King Street doing this amazing whistling in such a way as to be nearly undetectable. I hope he’s still around (beardy, thin, always wears shorts and blundstone boots).

Anyway, I really mean it about writing in public being better than writing in private. To illustrate with an only slightly exaggerated example, before I started blogging if I felt really down and negative about myself (lonely etc) I might sit down and write:

Why must I be so sensitive and intelligent?

Why can’t I just enjoy life like everyone else does?

What is it that makes a life good anyway?

Why doesn’t that girl break up with her stupid boyfriend and go out with me instead [because I’m nicer]?

… etc…

But obviously I would never write something so painfully adolescent and self-indulgent here (except in this context of course). I would be forced to actually come up with something worth reading which still communicated what I felt; and if it turned out that what I felt was really just a general malaise or ennui then all the better, I could identify it as such and move on. A blog can make you less precious about your troubles, and that’s one of the reasons I’m still doing it I think.

PS: For those who might be curious about my current mood, I have recently found myself single again after a very nice relationship which lasted four months. The split is totally amicable of course, but no matter how amicable it’s impossible not to become a little reflective about everything at times like this. Like being over 35. Hoo boy.

More Birds

I just realized this kind of segues into what I did today…

Although my physical health has been steadily improving since my time in hospital, my fitness level is at rock bottom, largely for lack of exercise. So even though it’s cold and damp here all the time, today I decided it was time I hauled my dimpled ass out of here and went for a decent walk if nothing else.

I tramped down to Mission Bay like I used to do regularly, and decided to get some chips for lunch and sit on the beach. Just me, my chips, a cold wind, and about a thousand seagulls giving me the eye. After tossing them a few morsels I remembered that there are more fun ways to feed seagulls than having them scrabbling in the sand; you can feed them in the air!

Basically you just throw things up rather than down, and before you know it (if you have a good wind) you will be surrounded by a cloud of gulls, hovering in mid air just a few feet apart. You can then just toss food into the cloud and it never even hits the ground. The formation will ripple but then rapidly stabilize again. Simply handing them food works too— I didn’t cop any nasty bites or scratches while doing this. As long as you keep feeding them you can just marvel at these birds bobbing effortlessly right in front of you, and really really envy them.

Kudos to Coco for demonstrating this technique to me many years ago ;)

Robots in de skies

Thursday, July 5th, 2007

The new Transformers movie rawks! — especially when compared to my expectations for it, which were really quite low. It has more believability than Spiderman 3, and is just packed with exciting explosions and mayhem. Optimus Prime is voiced by Peter Cullen, who provided the voice for the original cartoon series, which means he can deliver those ridiculous monologues and still seem authentic. Considering the utterly terrible premise of the story I think Michael Bay did an outstanding job bringing this to the big screen.

To bring at least a tiny bit of credibility to the plot, it is made clear that the Autobots (and the Decepticons) have the power to choose their camouflage forms (I don’t think this was the case in the original series), which begs the question: Why are the Autobots so squeamish about flying? It takes them a long time to reach their destinations by road; meanwhile the Decepticons turn into helicopters and jet fighters and arrive in minutes.

Review: Belkin Tunetalk Stereo

Monday, July 2nd, 2007

One of the really annoying things about the iPod is that it could have been a really nice audio recorder if Apple had just included a microphone with it. Since they didn’t you have to buy weird looking overpriced third party accessories instead, like the badly named Belkin Tunetalk Stereo.

A lot of reviews (and even the box it comes in) claim it is only compatible with the iPod Video, but it also works with the 2nd gen nano— if you can live with the fact that the damn headphone socket is obstructed, so you can’t monitor while recording (update: RichardN informs me it doesn’t allow monitoring anyway), and it looks a bit clumsy and lopsided plugged into the itty bitty nano.

Tunetalk connected to nano I think I’d still rather record on a nano than a full-sized iPod, since this thing would almost certainly pick up sounds from a hard drive, even if it is a super quiet one. The nano, being completely solid state, seems like the ideal model to which to add recording functionality, but thus far I am unaware of a similar product made specifically for it, so for now the Tunetalk Stereo will have to suffice.

The things you want to know:

  • 16 bit recording at either 44.1kHz stereo or 22.05kHz mono
  • Records to uncompressed WAV format (shows up in a special "Voice Memo" playlist)
  • Stereo line-in (3.5mm)
  • allows recording while charging iPod via USB
  • can’t be used separately as a USB microphone :(
  • autogain switch, which is the source of an annoying rattle in a unit that otherwise has no moving parts. This is a stupid design flaw which can be rectified with a piece of sticky tape.
  • no software or drivers to install, just plug it in and it adds a new sub-menu to your iPod
  • recording time limited only by battery life and free space (eg 2 hours+ on iPod nano after using it for most of the day, 3+ on full charge) although recordings are broken into two-hour blocks.
  • LED glows when recording and flickers to indicate clipping when autogain is turned off
  • frequency response and SNR… no frikkin idea :)

I would have posted a sample recording, but I haven’t recorded anything interesting yet, and also I’m having trouble working out how to make the fabled Garage Band do complex and rarely used things like normalizing audio, fade in/out and saving to MP3… Is there a whole set of toolbars and menus I’m overlooking here, or is this program as crippled as I think it is?

UPDATE: This stupid piece of shit just corrupted my iPod and now I have to totally reformat the damn thing

If you want to try web development…

Sunday, July 1st, 2007

Download Web Developer Server Suite (for Windows). It includes Apache, MySQL and PHP, and comes preconfigured with additional stuff like Wordpress, PHPBB2 and other popular web applications. A simple install and you can be running and testing PHP/MySQL code locally, which is a lot bloody easier than uploading files for every minor code change (which is what I’ve been doing until now, for some reason).

So my tiny blog software is now coming along much faster. It is still very small, making use of very basic PHP and SQL functionality, and yet has nearly as much functionality as I require. I am especially keen to switch over soon since my hosting provider (ICDSoft) just started blocking access to xmlrpc.php because of its use by spammers and hackers. As I’ve mentioned previously, I’m sick of XML-RPC and will be replacing it with a simple HTTP POST approach (this is the mechanism by which online forms send their information, and has been in use since the early days of the web). I’ll also be using POST to replace FTP for uploading images.

Features I will not be including: Trackbacks and pingbacks, which are more annoying than anything; Support for any character encoding besides UTF-8.

Features I will be adding: private comment checkbox so comments can be marked for my eyes only (a good way of encouraging feedback from the shy).

Any other suggestions…?