JP Brown’s Serious LEGO – CubeSolver

One of the mailing lists I’m on pointed out the following project to make a LEGO robot that could solve the Rubik’s cube:

JP Brown’s Serious LEGO – CubeSolver

Very slick, but it mentioned something I found even more interesting: Herbert Kociemba’s algorithm for quickly solving the Rubik’s cube:

Cube Explorer

In his testing, he generated one million random cubes, and tried to solve them using his program. He found no candidates which could not be solved in 20 moves or less. As far as I know (and this might be out of date) there are proofs that 25 moves is sufficient, and there are positions for which 20 moves is necessarry, but it isn’t known what number actually suffices.

I spent six months carrying around a Rubik’s cube back when they were the fad in high school (at least among geeks like me), and ultimately had my own rather pathetic way of solving the cube (it was slow, and usually took me ten or fifteen minutes to do). Fun stuff.

Technorati Tags: , ,

Security, Counter Measures, Half Measures, and The Real Thing

Security is mostly theater: you are forced to take off your shoes or surrender your shampoo, but random testing of airport security checkpoints reveal that their highly trained personnel routinely miss test bombs which are placed in luggage to test the effectiveness of screeners. An alert comes in, and we are supposed to “achieve a state of higher awareness”, which usually means glaring angrily at those people who look Arabic. Or Muslim, whatever muslims are supposed to look like. It would be hilarious if it weren’t serious.

Over at Boing Boing, Cory posted a brief message about wiretapping, and supposedly gave you an mp3 that you could play to disable remote wiretapped recordings.

Boing Boing: HOWTO trick wiretaps into thinking you’ve hung up

Like most things, there is a grain of truth in this: but Cory didn’t tell you enough about what you needed to know to determine what was real about this and what was not. Luckily, I know where this idea came from. If you are interested in why playing this tone might actually defeat a wiretap, and how it actually works, check out the papers by Matt Blaze et. al here. I’ve attended a number of talks and demonstrations from Matt, and he’s one of the cleverest individuals I’ve ever met, with a special talent for matters relating to security. All that I know about safe cracking can be safely attributed to his influence.

Take that however you like.

Technorati Tags: ,

The Slug Lives Again!

I brought up my old Linksys NSLU2 again, after upgrading it to the unslung firmware and installing a 512Mb usb stick to serve as the main storage. Check out the link: it’s served from that little box, which is running an extra copy of the thttpd webserver (the other one runs the box’s configuration webpage). It’s really quite a quite toy.

If you want more info, clickthrough and read more.

Technorati Tags: , ,

May 25th is Towel Day

Carry a towel around tomorrow. Why? In the words of the sage:

A towel, it says, is about the most massively useful thing an interstellar hitch hiker can have. Partly it has great practical
value – you can wrap it around you for warmth as you bound across the cold moons of Jaglan Beta; you can lie on it on the brilliant marble-sanded beaches of Santraginus V, inhaling the heady sea vapours; you can sleep under it beneath the stars which shine so redly on the desert world of Kakrafoon; use it to sail a mini raft down the slow heavy river Moth; wet it for use in hand-to-hand-combat; wrap it round your head to ward off noxious fumes or to avoid the gaze of the Ravenous Bugblatter Beast of Traal (a mindboggingly stupid animal, it assumes that if you can’t see it, it can’t see you – daft as a bush, but very ravenous); you can wave your towel in emergencies as a distress signal, and of course dry yourself off with it if it still seems to be clean enough.

More importantly, a towel has immense psychological value. For some reason, if a strag (strag: non-hitch hiker) discovers that a hitch hiker has his towel with him, he will automatically assume that he is also in possession of a toothbrush, face flannel, soap, tin of biscuits, flask, compass, map, ball of string, gnat spray, wet weather gear, space suit etc., etc. Furthermore, the strag will then happily lend the hitch hiker any of these or a dozen other items that the hitch hiker might accidentally have “lost”. What the strag will think is that any man who can hitch the length and breadth of the galaxy, rough it, slum it, struggle against terrible odds, win through, and still knows where his towel is is clearly a man to be reckoned with.

Towel Day – Wikipedia, the free encyclopedia
If you’d like to celebrate the work of Douglas Adams, try getting yourself a copy of Douglas Adams reading Dirk Gently’s Holistic Detective Agency. It’s a great story, read very well by a great author. It’s the single greatest audiobook I’ve ever listened to.

Technorati Tags: , , ,

Homebrew CPU Home

The other cool project that I saw was Bill (sorry, can’t remember his last name, and I couldn’t find it on his webpage) Buzbee’s homebrew cpu: the Magic-1. And by homebrew, we really mean homebrew: he wirewrapped it from piles of conventional TTL logic gates. As I told him: dude, that’s hardcore.

Homebrew CPU Home Page

I had seen his webpage before when i was muddling this kind of thing as a project, but it appears he has made some progress since I last peeked in: he ported LCC to it, and is now running a small webserver on it.

Check it out.

You can even telnet in and play the original Adventure. That’s just too damned cool for words. I bow in humble awe at how cool this is.

Technorati Tags: , ,

My Favorite Thing @ The Makers Faire: Tom Zimmerman and his DIY video microscope

I saw lots of cool stuff at the Makers Faire, but the thing which evoked the greatest “this is a cool idea that I could do” factor was Tom Zimmerman’s video microscope.

MAKE: Blog: Maker Faire: Tom Zimmerman and his DIY video microscope for backyard biology

The link doesn’t really describe why it’s a good idea, so allow me to elucidate. Basically Tom takes an ordinary webcam (or even one of those little $20 B/W security cams), pries the lens off, and he’s left with
the more or less naked sensor sitting there. He then takes a drop of fluid containing some of his desired microscopic critters (he was using little rotifers) and places it directly on the sensor. He then piped the video directly to a TV. Net result: blurry image, can’t
see a darned thing. That’s not too surprising, since there is no lens in the system, so nothing is in focus. Here’s the magic: He then took a tube (a toilet paper tube would be about the right dimension) which is
open at one end, and has a piece of foil with a small pinhole in it covering the other end. When this is placed over the sensor: voila! you can see the critters, in sharp focus, swimming around munching on algae. If your light source isn’t diffuse, you might actually see an image of the light source (just like you were using a pinhole camera), so Tom constructed a little light source using a bright blue LED which gave uniform illumination and looked great.

This is so simple, so clever, I’m just going to have to build one.

Here’s some YouTube video of the result, it doesn’t really do justice to the clarity of the images he was showing at the Faire:

Technorati Tags: , ,

Yesterday the Makers Faire — Today, Bay To Breakers!

Yep. Despite the fact that I’ve let my exercise program lapse, I’m off for the 7 point something mile race from the Bay to the Breakers, a San Francisco tradition, and the third year in a row that I’ve run it.

Wish me luck, and if you see me, throw ibuprofen rather than the traditional tortillas.

Addendum: Well, I’m done. Started late, time was a little over 2h38m, but included a bathroom break which I’m putting at 2h31m, sso I ran the 12k in 7 minutes. A new world record!

Idle Python inspired by Idle Thoughts on FoxMaths

I have a number of mathematical blogs in my blogroll: one I have found to be reasonably interesting is FoxMaths. Today, he had some idle thoughts about the a sequence of numbers that reminded me of the look and say sequence that John Conway explored. Basically, you begin with a sequence of digits (the “program” in the code below). Consider the final digit to be an argument, and the rest of the digits as being the coefficients for a polynomial. Evaluate the polynomial mod 10, and append that digit to the program and run again. The code below (written in Python) automates the process.

FoxMaths: Idle Thoughts…

#!/usr/bin/env python

import sys

program = sys.argv[1]

for x in range(1000):
        print '>>>', program
        arg = int(program[-1])
        powerseries = map(int, list(program[:-1]))
        total = 0
        for p in powerseries:
            total = (total * arg + p) % 10
        program = program + str(total)

My intuition is that ultimately programs will be cyclic, and it seems to be born out by a tiny bit of random testing, but I’m unsure whether my intuition is wholly justified. I’ll think about it when I’m exercising later today.

Subtlety in Algorithms: Binary Search and Alpha-Beta

John Bentley demonstrates quite adequately in his book Programming Pearls that to write even the simplest program, say, one that does binary search, is frequently fraught with peril and subtle errors. If you try to write a binary search, chances are you’ll get something wrong. Even Bentley’s own binary search contains a potential overflow condition which might manifest itself as an error if you are searching Google-sized tables.

It should come as no suprise that most implementations and descriptions of alpha-beta search (the key algorithm that you need to write, say, a checkers program) have similar flaws. Most of them don’t actually list the preconditions and invariants that are supposed to be maintained throughout program execution, and in fact, if you actually chose to write some down, you’d find that most of these implementations and descriptions wouldn’t actually work.

Irritatingly, most of them work most of the time. A couple of days ago I started doing what I should have done all along: develop some unit tests and scaffolding for my checkers program. The first thing I discovered was a subtle bug in my alpha-beta code. By comparing the score returned by alpha-beta and a simple minimax traversal of the same tree, I discovered that my code didn’t return the same values. It wasn’t hard to figure out the bug then.

I then tried doing some modifications to do aspiration search with very narrow, and ultimately empty search windows. I discovered an error in those too, and it was due to a misconception
of how alphabeta actually operates in so-called “fail-soft” mode. I had thought that the return value was the minimax value if it was greater than or equal to alpha and less than beta, but the reality is that is only true if the return value is greater than alpha and less than beta. If you get this wrong, null search windows don’t operate properly, and you won’t get the proper minimax value.

This all means that I’m making headway on my checkers program.

Random Thought — What happened to Prolog?

Back when I was in college, there was considerable interest in Prolog and logic programming languages, but you scarcely hear about it at all anymore. I wonder why that is? I mean, I was never a huge fan, but in most respects it just never enters any modern discussion of programming languages.

Prolog – Wikipedia, the free encyclopedia

Rounding the first marker…

Was at work till midnight last night, and that was the highlight of my day. One remaining shot is kicking my ass, but other than that, work is getting there. Probably won’t be the last late night of the show though.