Alright, we’ve covered search trees in some detail, and they work great for problems where we have clear states and rules of production to move from one state to the next. Sometimes that’s not a very convenient way to state a problem, though, and a more natural way to think about things is as a bunch of variables which can take values in a certain domain, and a number of constraints which describe the relationships of these variables to each other.
The canonical example here is Dijkstra’s eight queens problem. However, that’s been done to death, so let’s instead have two queens and seven knights, and instead of the usual 8×8 chess board, let’s have a 6×6 one.
But people are fucking morons upon whom democracy is wasted.
Yes, we had federal elections yesterday. I was summoned as a bijzitter, which meant I had to get up at 7 to help open a polling station and then put 1,242 stamps onto 1,242 ballots (621 each for Kamer and Senaat) and about five hundred on as many election summons (compulsory voting, dontchaknow), and I didn’t even get to keep the stamp afterwards. Then at the end we all got to wait around for two more hours because apparently the problem with selecting members of the public to help manage elections is that the vast majority of the public is terminally innumerate, so our ballot count was off by one.
It eventually got resolved, but the upshot of this is that I was too tired to bother with writing this post last night, when the votes were counted (we count more quickly than the Americans or the British or even the Dutch).
You may be wondering why we’re having federal elections in 2010 when the last time I complained about federal elections was in 2007. A lot of countries have been having elections lately, but Belgium’s wasn’t planned for another year.
The reason for that is that Alexander De Croo felt he wasn’t getting enough media attention, so he took his ball (the Flemish liberal party) and went home, thereby imploding the Leterme government for, what, the eighth time now? Even the King couldn’t pretend there was no problem this time, so in the good tradition of Christian democrat majority governments, emergency elections had to be called.0
You can find all results here, as usual, and as usual I don’t know how long they’ll last, so I’ll steal some graphics.
Everyone knows BBCode is a pain to work with, and while WordPress supports limited HTML in user comments, it should be obvious HTML is no better. The unnecessary repetition of SGML-based languages and the insistence on the proper nesting of tags makes them all hideous and unnecessarily error-prone. We can do better.
The discussions of learned societies on the subject have been less than satisfactory, so I decided to just implement my own mark-up language, based on the venerable S-expression:
{b This} is {i {u expert} {o mark-up}}.
This will turn into:
This is expertmark-up.
The immediate problem is that nesting problems and text redundancy immediately disappear. The syntax also lends itself to easy function composition:
{b.i.o.u EXPERT}
EXPERT
Finally, for this first version,0 we also support function iteration:
{sup*3 To the moon}{sub*3 and back.}
To the moonand back.
It goes without saying this can be combined with function composition in arbitrarily complex expressions, with the iteration operator having a higher precedence than the function composition operator.
I’ve elected to use curly braces rather than the more typical parentheses, because curly braces barely see any use in natural language, which is where this mark-up would generally be used. If you do need literal curly braces, you can escape them with a backslash (and if you need a literal \{, you can escape your backslash with a backslash).
As a proof of concept, and because I eat my own dog food, I’ve written (and enabled) a WordPress plugin that enables this SexpCode in blog comments. For sanity, iteration doesn’t go beyond *3. Supported tags are b, i, u, s, o, sub, sup, code, spoiler, quote, blockquote, and m. If you want to use it yourself, adding more tags or changing their definitions should be straightforward.
Trying to use an unsupported or empty tag, or having unbalanced braces (except for closing braces at the end), will assume you’re actually trying to post C-like code, and disable SexpCode for your comment.
Ladies and gentlemen, BBCode was our COBOL. This is our Lisp.
Edit: People who want to implement this themselves should be following this document rather than this post.
0 Future versions of the language are expected to add support for function arguments (for things like url, img, and colour) and the ability to define aliases (for example, {define exp b.i.o.u}, which would let you use a new exp function as if it were b.i.o.u).
In my post on the Mandelbrot set earlier, I mentioned the Julia sets of the quadratic polynomial fc(z) = z2 + c where c is a given (constant) complex number and z are the points of the complex plane. Because I wanted to visualise how those Julia sets changed as c varied, I’ve written a short program to do that for me.
You can find it here. As usual, you’ll need Allegro, and the compilation instruction is on the first line.
What it does is take two complex numbers as parameters, plus the number of steps it should take to go from the first to the second. At each step, it will calculate and display the Julia set of the quadratic polynomial with that complex number as c, and hopefully your computer is fast enough that the successive Julia sets look like an animation.
For example, if you invoke it as:
./julia -0.8 -1 -0.8 1 200
you’ll see the following:
Though probably not at the same speed. I’ve made no effort to maintain a certain frame rate; the whole thing moves as quickly as your CPU can keep up, because I just wanted a visualisation of how Julia sets change, not a screensaver. If it’s moving too slowly for you, you can try reducing the number of steps, or lowering the numbers in the ZOOM or ITERS#defines, though the first one will make the image smaller and the second will make it darker. If you aren’t interested in the window title, you can also remove the snprintf and set_window_title steps for a significant speed-up.
If it’s too fast, you can do the reverse, or you can build in a delay with Allegro’s install_timer and rest, or POSIX’s usleep or nanosleep.
(Once it’s done, it will just pause at the last Julia set. Press any key to close it. If you want to close it before it’s done, you’ll have to kill it manually.)
The interesting points to explore are the ones inside the Mandelbrot set, as anything else will just be Fatou dust (though you’ll probably still be able to see it because of the grey). For those points, the salient area is the one within 2 unit lengths of the origin, which is why the field displayed ranges from (-2, 2) in the top left corner to (2, -2) in the bottom right (or probably (-2, -2) to (2, 2), I don’t remember). If you need a bigger plane, replace all instances of ZOOM * 4 with ZOOM * (bigger number), and all instances of ZOOM * 2 with ZOOM * (half of bigger number) (if you want to keep the origin in the center of the window).
If you actually want to save the animations, man 3alleg save_bitmap and assemble the images yourself in something like the GIMP. I initially started out doing it this way, but animated GIFs get really big really quickly, so I went with this instead.
People who take an active interest in AI are quite unlikely to have very many friends, so it should come as no surprise that trying to get computers to play games has always been a popular subfield of AI. Traditionally that game has mostly been chess, but I feel chess has a grinding tedium to it, so we’re going to look at tic-tac-toe instead, because that at least has the benefit of being over quickly.
Last time we looked at how to solve the eight puzzle using the hill climbing algorithm, which gave us a result much more quickly than a blind depth-first search did, but we wondered if the solution we found was the best we could do, and we asked if there was a way to use heuristics to find not just a solution, but the best solution. Today, we’ll see that there is, and it’s actually really straightforward.
Today we’ll be looking at the hill climbing algorithm, which is just a plain old depth-first search with heuristics added.
“Heuristics” is a fancy word (from the Greek εὑρίσκω, “I discover”) for a very simple concept. In the context of search trees, it simply means that at a every node, you’re going to look at each possible branch, and take the one that looks the most promising first, instead of just one at random. “Most promising” can be a tricky concept, though.0
Our river-crossing example isn’t necessarily the best one to demonstrate the concept, so let’s go with another classic: the 8 puzzle.
A decent proportion of my readers are noobie programmers or people who aren’t in a position to receive a formal CS education, so I thought I’d cover the basics of a fundamental concept most people cover in their first semester of algorithms or AI today: search trees. The fact that my college considers this to be third-year material so advanced they cannot in good faith make the class compulsory is neither here nor there.
Consider the famous problem of the farmer who wants to cross a river with his fox, goose, and grain, though the only boat can only carry himself and one of these three possesions. Ignore for a moment why a farmer would own a fox, and let’s stretch credibility a bit more by assuming that while the fox and goose are well-trained enough not to wander off in the absence of the farmer, they are not trained not to eat the goose or the grain, respectively, in said absence. How can he safely get to the other side without losing his goose or grain?
Having finished another popsci book on chaos theory recently (Ian Stewart’s Does God Play Dice?), I thought it’d be an interesting exercise to visualise the Lorenz attractor, and since it’s been a while since I’ve done anything new in programming, to take the opportunity to get into Xlib, the X Window System C library. Results aren’t very encouraging.
I mean, I got something to work easily enough, but any attempt at introducing color beyond black and white for clarity fails miserably and in non-deterministic ways. Eventually I gave up and redid it using something I know.
Compare:
(It’s prettier animated, so do compile the code yourself and see.)
In both cases, the screen represents the Cartesian plane (X-axis horizontal, Y-axis vertical, origin right in the center; one unit is ten pixels). In the Xlib version (left) the Z component is ignored entirely (so it’s really a projection of the attractor onto the Cartesian plane), in the Allegro version (right) some attempt at representing it using shades of gray has been made, with z=0 being black and z=55 being white (though because it is drawn with no real care, it will happily scribble dark lines over light ones if it has to).
You can mess with the variables and starting condition to see how it behaves, or swap around some Xs and Ys and Zs to get different angles, and at least in the Allegro version, messing with color is trivial enough.
Which brings me to my question: does anyone know of decent introductions to Xlib? The Internet is full of tutorials, and as usual, all of them seem to suck. I know Xlib isn’t really supposed to be used directly, but I want to.
It’s probably unlikely that I’m going to finish another book in the five and a half hours left in 2009, so I’m going to post this while we’re waiting for snacks.
I don’t have any bad habits, so my only New Year’s resolution tends to be to read fifty books in a year. Last year I didn’t quite make it, but apparently I more than made up for it this year. I finished eighty-eight:
The Ancestor’s Tale Richard Dawkins Snow Crash Neal Stephenson An Appeal to the Toiling, Oppressed and Exhausted Peoples of Europe Leon Trotsky The Origin of Species Charles Darwin The Fabric of the Cosmos Brian Greene Anansi Boys Neil Gaiman I Am a Strange Loop Douglas Hofstadter Why I Am Not a Christian Bertrand Russell Gödel, Escher, Bach Douglas Hofstadter JPod Douglas Coupland Your Inner Fish Neil Shubin Deep Simplicity John Gribbin On Natural Selection Charles Darwin Mathematics for the Imagination Peter M. Higgins The Open Society and Its Enemies, Volume 1 Karl Popper Atheist Manifesto Michel Onfray The Satanic Verses Salman Rushdie Yiddish Policemen’s Union Michael Chabon The Extended Phenotype Richard Dawkins The Chronicles of Narnia Clive “Staples” Lewis Freakonomics Steven D. Levitt, Stephen J. Dubner How to Solve It George Pólya Failed States Noam Chomsky Hegemony or Survival Noam Chomsky Necronomicon: The Best Weird Tales of H. P. Lovecraft H. P. Lovecraft What We Say Goes Noam Chomsky Wealth of Nations Adam Smith Consciousness Explained Daniel Dennett Life’s Grandeur Stephen Jay Gould A Mathematician Reads the Newspaper John Allen Paulos The Myths We Live By Mary Midgley The Tiger That Isn’t Michael Blastland, Andrew Dilnot The Essential Turing B. Jack Copeland The Mismeasure of Man Stephen Jay Gould Faust (Frühe Fassung) Johann Wolfgang Goethe Paradise Lost, and Other Poems John Milton Physics of the Impossible Michio Kaku Guns, Germs and Steel Jared Diamond The Trouble With Physics Lee Smolin The Handmaid’s Tale Margaret Atwood De la Terre à la Lune Jules Verne The Drunkard’s Walk Leonard Mlodinow Of Mice and Men John Steinbeck Stephen Fry in America Stephen Fry The Road Cormac McCarthy Voyage au Centre de la Terre Jules Verne De Weduwe Becker Maurice Roelants Jonathan Strange & Mr. Norrell Susanna Clarke You Shall Know Our Velocity Dave Eggers Frankenstein Mary Shelley Computer Networks Andrew S. Tanenbaum Midnight’s Children Salman Rushdie Pride and Prejudice Jane Austen The Fountainhead Ayn Rand Lolita Vladimir Nabokov The Greatest Show on Earth Richard Dawkins Sense and Sensibility Jane Austen Dubliners James Joyce Fear and Loathing in Las Vegas Hunter S. Thompson Het Achterhuis Anne Frank God Created the Integers Stephen Hawking Shalimar the Clown Salman Rushdie Nation Terry Pratchett Extremely Loud & Incredibly Close Jonathan Safran Foer Pride and Prejudice and Zombies Seth Grahame-Smith, Jane Austen A Confederacy of Dunces John Kennedy Toole The Penelopiad Margaret Atwood Dracula: the Un-dead Dacre Stoker, Ian Holt House of Leaves Mark Z. Danielewski The Universe John Gribbin The Zombie Survival Guide Max Brooks Fahrenheit 451 Ray Bradbury Strange Case of Dr. Jekyll and Mr. Hyde Robert Louis Stevenson Treasure Island Robert Louis Stevenson The Curious Incident of the Dog in the Night-Time Mark Haddon Curious Pursuits Margaret Atwood Speak, Memory Vladimir Nabokov We Have Always Lived in the Castle Shirley Jackson Winnie-the-Pooh A. A. Milne The Night Watch Sergei Lukyanenko The Oxford Book of Modern Science Writing Richard Dawkins Unknown Quantity John Derbyshire A Christmas Carol Charles Dickens The Yellow Wallpaper, and Selected Writings Charlotte Perkins Gilman The Day Watch Sergei Lukyanenko The Twilight Watch Sergei Lukyanenko The Last Watch Sergei Lukyanenko Lord of the Flies William Golding
So I guess I only need 46 next year to maintain my average.
Reviews for a significant number of those can be found on the Facebook (or here, which is the same place). I’d use LibraryThing, but you need a paid account to have more than two hundred books on it, and I don’t trust them enough to give them credit card information.
If someone wants to send me money for it, though, you know my Paypal address.
Highlights: Best fiction: probably Salman Rushdie’s Midnight’s Children, though Margaret Atwood is a good writer. Worst fiction: Rand, obviously. CS Lewis is a close second. Even Neal Stephenson isn’t that shit. Best non-fiction: Nothing earth-shattering this year. I guess John Allen Paulos’s A Mathematician Reads the Newspaper was pretty good. Worst non-fiction: Mary Midgley’s Myths We Live By. I’m not sure it even deserves to be called non-fiction. Runner-up goes to Gould’s The Mismeasure of Man.
My social and academic environments aren’t exactly intellectually stimulating, so I get most of the programming problems I fill my days with—and of which the ones that are the most fun to talk about end up here—from books I read. Since I’ve already read every interesting sciencey non-fiction book available in Leuven, I’ve mostly been reading fiction lately, which doesn’t exactly inspire interesting algorithms, which is why I haven’t been bloggering as much.
In an effort not to let my programming skills get too rusty, I decided to write a thing that validates and parses ISBNs, extracting the publisher information and other things that are supposed to be in ISBNs. This turned out to be annoyingly non-trivial, so instead I’m just going to write about the numbers themselves.
As you probably know, ISBNs are a book numbering scheme standardised by ISO in 1970 (as ISO 2108), based on an earlier 9-digit scheme (SBN) used in the UK. It had ten digits until recently (January 2007), when it was expanded to 13. I assumed the expansion was because they were running out of numbers (which they were), but I also noticed every 13-digit ISBN started with 978, which was odd.
Old ten-digit ISBNs consist of a group identifier, which mostly identifies the language the work is in and is of variable length (it’s a prefix code,0 to avoid ambiguity; the 9-digit SBNs ISBN is based on didn’t have a group identifier, but prepending a 0 to them (one of the codes for English-language works) turns them into valid ISBNs), followed by a publisher code (again of variable length), followed by an item identifier, followed by a single check digit, used to make sure the other numbers were entered properly.1
New thirteen-digit ISBNs are basically the same thing with 978 prepended, and the check digit is calculated differently.
So hey, this doesn’t expand the number space. What’s the deal?
The deal turns out to be EAN, or European Article Numbers.
EANs are similar to North-American UPCs, with which they are compatible. It’s a barcoding technology intended to help track items in stores. UPC numbers are twelve digits long, and EANs thirteen.2
EANs start with a two- or three-digit GS1 prefix, which is basically a country code. Somewhere along the way someone realised that books are things that are sold too, and books have ISBNs, and let’s not waste a lot of disk space storing two numbers when one will do, so the GS1 prefix 978 was created, for Bookland, the magical land where all books are printed.
Because someone had the foresight to realise ISBN would run out of numbers eventually, they also reserved 979, and since the last digit of an EAN is also a checksum digit, people didn’t want to maintain two different methods of computing checksums, and the 13-digit ISBN was created. All of the old ISBNs map to new ones seamlessly, and new ones will mostly continue to be allocated in area 978 until that’s full, which is why 978 numbers are still by far the most common ISBN-13s.3
The term Bookland is now considered deprecated because people are boring twats and GS1 prefixes stopped being country codes and started being organisation codes, and 978 and 979 are registered to the International ISBN Agency, but it’s a cute bit of trivia.
Anyway, because I don’t want this post to be entirely worthless, here‘s a tiny script that takes a 9-digit SBN or 10-digit ISBN as input and produces the new 13-digit equivalent.
(Incidentally, that image is the ISBN for Karl Popper’s Logik der Forschung. It should not be taken as an endorsement of that tedious asshole’s work, but rather as laziness on my part, because it’s the first picture in the Wikipedia article on ISBN.)
0 Meaning that no valid code is the prefix of another valid code. Like in Huffman coding.
1 Wikipedia claims it’s a modulo 11 affair, with X substituting for 10, but I don’t think I’ve ever actually seen X as a check digit. I’ll admit I haven’t been paying a lot of attention, though.
2 EAN-13, at least, which is the most common. There are others, but I’ve never seen them used. Apparently EAN-8 is common on cigarettes.
3 Something analogous happened with periodicals and their ISSN, with Unique Country Code 977, but that story is a bit more complicated because ISSNs are only eight digits long.
I’m in a class called Netwerkbeheer (Network Management), which spans two semesters and is a transparent excuse to peddle CCNA certifications. As a result, I spend a lot of time playing with Cisco routers and switches, and one of the many, many things that annoy me about Cisco’s IOS is their cavalier attitude towards security and cryptosystems. A particularly egregious example of this is Cisco’s type 7 encryption.
If you’ve ever configured a Cisco router, you’ve probably encountered it. When the misleadingly named service password-encryption is running, setting a password with the enable password command “encrypts” the password, so that when you issue the show running-config command, you’ll see a line like
enable password 7 08314940000A
instead of the plaintext password, which you’d see if the so-called “password-encryption” was turned off.
Type 7 “encryption” manifests itself in a few other places, including in FTP passwords and various routing protocol authentication passwords.
Type 7 has been known to be broken for a decade and a half now,0 but people continue to use it, almost always for bad reasons.1,2 To drive home just how broken type 7 is, let’s look at it in detail.
The general form of the type 7 “ciphertext” is (0[0-9]|1[0-5])([0-9A-F]{2})+. Some experimenting finds that the length of the “ciphertext” is always twice the length of the plaintext, plus two. Can you guess why?
The “encryption” key is always a number in the range 0-15, which would be easy enough to bruteforce, but that turns out to be unnecessary, since it’s provided (in decimal form) as the first two characters of the “ciphertext”.
That key determines the starting point in a table of twenty-six secondary keys (which, incidentally, is dsfd;kfoA,.iyewrkldJKDHSUB; I don’t know why the table has 26 entries instead of 16), which are XORed in turn with the characters in the plaintext. If the key is, say, 7, the first character in the plaintext is XORed with the seventh character in the table, the second character in the plaintext is XORed with the eighth character in the table, the third with the ninth, &c.
Each resulting character is then converted to two hexadecimal digits (the input can only be ASCII, of course) and appended to the ciphertext.
And that’s seriously all there’s to it. The result is a “cipher” that’s either slightly less or slightly more secure than writing out your passwords in permanent marker on the outside of the door of the server room, depending on how you manage your configuration files.
Because I know this is going to be an issue at some point, I’ve written a simple utility that encrypts and decrypts passwords using type 7, which you can find here.
You’d think this would be a moot point because people should realise their configuration files are sensitive information, but people are, of course, idiots. In that sense, type 7 isn’t just worthless, but actively harmful, because it gives people a false sense of security.
1 The original intent of type 7 was apparently to foil shoulder-surfers, who might see your configuration file as it scrolls by on your screen. Cisco’s official stance (now) is that if security is an issue, the router configuration file itself should be treated as vulnerable data, not just the passwords that may or may not be displayed in it. That would be fair enough, if it wasn’t at odds with Cisco’s default way of saving and loading configuration files, which is through plain TFTP over the regular network, with no options for encryption of either the config or the passwords themselves. But, you know.
(The claim that type 7 is so weak because the router has to be able to reverse it is bullshit, of course. At most it’s true for PAP authentication, but anyone who considers PAP passwords secret information has no business being anywhere near a router.)
2 Cisco themselves now advise against using it, instead suggesting people use type 5, which isn’t encryption, but just hashing with MD5. Which is also broken, of course. The CCNA materials also state that at least type 7 is “better than no encryption”, but I’d argue that it’s worse, because its security is equivalent to plaintext, while also giving idiot network admins the impression that it’s not.
I’m told a type 6 exists now, which is based on AES and supposed to be better. AFAIK our routers don’t support it, and I’m not holding my breath either way.
I’m not even talking about apartheid or AIDS. I’m talking about language. Quite apart from the fact that they incomprehensibly keep pretending their dialect is a language in its own right, they keep applying the wrong words to things, and then passing them on to other languages.
Three examples.
Exhibit A: Meerkat
This is probably the most famous example, and also an odd one, because mainstream Dutch is in the wrong here too. Examine the pictures above.
The one on the left is Suricata suricatta, a member of the mongoose family. In Afrikaans this has been called a meerkat, and this has been adopted into English. In regular Dutch it’s a stokstaartje (“little stick tail”).
The one on the right is a vervet monkey (Chlorocebus pygerythrus), one of thirty-five species of Old World monkey in the tribe Cercopithecini, which in Dutch are collectively called meerkatten.
This is, of course, an absurd name for either of those, as meerkat means “lake cat”. If anything should be called this, it should be Prionailurus viverrinus, which currently labors under the descriptive but utterly boring name fishing cat.
This medium-sized cat is semi-aquatic, and while it prefers streams and swamps to actual lakes, at least the name would be sort of appropriate. Being medium-sized, it’s also meer kat than the housecat.
Let’s just agree to call Suricata suricatta suricates, okay?
Exhibit B: Steenbok
The one on the left is Raphicerus campestris, a small antelope native to southern and eastern Africa. For some reason, it was named “steenbok” after the one on the right, Capra ibex, the ibex, one of a few goat species called steenbok in Dutch. I have no idea what Afrikaners call the actual steenbok (the one on the right, that is; I know Germans call it Steinbock, and the other one Steinböckchen—that is to say, the diminutive), but the Dutch have taken to calling R. campestris “steenbokantilope”, which at least is fair enough.
Steenbok, of course, translates to stone buck (as in a male goat), which makes sense for the ibex because it lives in the Alps. It very much does not make sense for an antelope that spends its days in grassland.
Since it’s closely related to the two species of grysbok (which by rights should be spelled grijsbok), call it the fancy grysbok and stop confusing people.
Even though it’s not grey.
Exhibit C: Eland
The last one is particularly ridiculous. Yes, that’s a moose. In Dutch, meese (elk, in European, though the North-American elk is something else; that’s a different discussion) are called eland. Afrikaners named two species of antelope eland because apparently they’re blind. Even the giant eland (Taurotragus derbianus, pictured) doesn’t even come close to Alces alces in size. The common eland, Taurotragus oryx, is even smaller.
The common eland (just eland in Afrikaans) is called the elandantilope in Dutch. The giant eland is reuzenelandantilope (the prefix reuzen- meaning “giant”). If you’re going to keep the dumb name, “eland antilope” and “giant eland antilope” seem like a good compromise.
I hate Afrikaans.
Having said that, there are some words that made it into English that they get right (boomslang, for example, means tree snake, and it’s exactly that), and a lot that, while dumb, aren’t confusing (aardvark (“earth pig”), aardwolf (“earth wolf”), wildebeest (“wild beast”), hartebeest (more correctly hertebeest, “deer-type animal”); all of these are at least vaguely misspelled by modern standards). Many non-animal words that made it into English are even fully accurate: spoor, veld, trek, and, of course, apartheid.
The three listed examples, though, are bunk. The animals are awesome enough to deserve decent names of their own.
And I still say Afrikaans is just a dialect of Dutch. It’s closer to standard Dutch than, say, Limburgs or West-Vlaams, and while there’s a movement to have those recognised as separate languages, that’s a tiny, tiny minority. The only real difference is that Afrikaans has a standardised spelling and good reasons to hate the Dutch.
If you follow these things at all, you’ve probably heard by now: creationists are once again inventing a controversy where there is none, this time by pretending that it matters at all whether Dawkins’ venerable Weasel program uses locking or not, and claiming that his “unwillingness” to dig up code written in the ’80s and release it means… well, something significant.
In case you’ve forgotten what the Weasel program is, here’s a video (using a different phrase, but the same concept):
If you’re a long-time reader and that looks familiar, it’s because I’ve talked about it twicebefore. The experiment is simple enough that any idiot can repeat it, but of course creationists are a very special kind of idiot.
So this time, let’s walk through writing our own Weasel program and settle this once again.
I’ll be doing this in a kind of “literate Python”, because everyone understands Python and it doesn’t require compilation, so even the most technologically inept don’t have any excuse not to follow along.
If you don’t have Python installed (or aren’t sure if you do), get it here. Get the 2.6.2 one (if you aren’t sure which you need, you’ll need this one). If that’s too hard already, you shouldn’t be on the Internet in the first place.
I’ll be preceding lines of Python code with > signs, façon literate Haskell. The Python interpreter doesn’t understand this style, so I’ll also be providing a link to the final script at the end.
To recap, we’ll start with a random string composed of symbols chosen from a specific alphabet, and a target string which we’re hoping to achieve.
For randomness, we’ll be using Python’s inbuilt random module, so let’s import it.
> import random
The genetic alphabet is just “CGTA” for DNA, but ours will be a bit longer:
> alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
Note that that includes the space at the end. We could make it even longer by including minuscules and punctuation, but it really makes no difference to the principle of the thing.
And here’s our target string:
> target = "METHINKS IT IS LIKE A WEASEL"
Of course it’s important that all symbols in the target string are also in the genetic alphabet, or we’ll never find it.
At the heart of every genetic algorithm, there’s a fitness function. In our case, this is just something that compares our string of “DNA” with the target string symbol by symbol, and just says how many symbols match. Strings with more matching symbols are obviously more like the target string, and will be selected to breed for the next generation.
> def fitness(child):
> fit = 0
>
> for a, b in zip(child, target):
> if a == b:
> fit += 1
>
> return fit
The built-in zip function pairs items in a given list, creating a pair of the first character in both the “organism” and the target string, then the second, then the third, and so on. For each pair, it’s then going to check if both members of the pair are the same symbol. If they are, the fitness value is incremented by one. At the end, it’s returned.
This should be obvious.
Equally important, of course, is the reproduction function. Dawkins’ Weasel strings reproduce asexually, so there’s only one parent for each child. The parent copies his entire “DNA”, and each locus has a small chance of mutating.
How high the mutation rate is isn’t that important, because the point of the Weasel program isn’t to simulate real-life life perfectly, but just to demonstrate that descent with modification is more effective than a random search. Let’s give our strings a mutation rate of 1 chance in 50 at each locus. If that seems too high, remember that our genome will be 28 loci in length, so there’ll already be a lot of generations where no mutation will happen at all.
> def reproduce(parent):
> child = ""
> for gene in parent:
> child += random.choice(alphabet) if random.randint(1, 50) == 1 \
> else gene
> return child
Did you follow that? Our child starts off as an empty string, and then we iterate over the genes of the parent. There’s 1 chance in 50 that a mutation occurs, in which case we randomly select a gene from the alphabet to add to the genome. Otherwise, we use the parent’s gene.
At the end, the constructed child is returned, ready to have its fitness judged.
Now that we have those two important functions, the rest of the program is straightforward. First, we construct a completely random starting point:
> parent = [random.choice(alphabet) for _ in target]
Our Adam. Let’s put him and his fitness on display:
The generation variable will keep track of how many generations have passed.
We’re just about ready to enter our reproduction cycle now. Every generation, our parent will have one child, and if this child is fitter than his parent, this child will be the next parent. Otherwise it is mercilessly discarded and the parent will parent the next generation as well.
As you can undoubtedly tell, this loop will exit once the fitness of the mutating string equals the length of the target; that is, when both strings are equal.
The string "METHINKS IT IS LIKE A WEASEL" is 28 symbols long. With a 27-symbol alphabet, a random search would take on average 2728 / 2 generations to match it. That's 5,986,257,591,281,009,894,301,370,013,358,523,552,840 generations. Even if we're doing a trillion1 generations a second, that would take 189 million trillion2 years to finish.
Our little program will be doing a bit better than that. The final generation number will be displayed before the final generation genome, of course, but let's rub it in again just to be sure:
> print "Finished! Target reached in %d generations!" % generation
Running it a thousand times, I got an average of 8012.58 generations. Suck it, creationists. Descent with modification and selection really is faster. Just like the last time. And every other fucking time.
And as promised, the full code is here. Just save that somewhere and double-click it to run it (you'll need to chmod +x on sane platforms, but you know that).
And that really should be that. Dembski can wave giant-sleeve-clad arms about free lunches all he likes, but in the real world, not everyone is innumerate. It’s just sad that decent people have to waste time on his bullshit.
I doubt this will actually do much good (of course it won’t; even the creationists themselves (exceptionally dense specimens excepted, as usual) realise this time that there’s no controversy here, just a giant heap of time-wasting nonsense), but if nothing else, I hope I’ve demonstrated even an elementary school student could do this. If the original code is of any interest at all, it’s because of archaeological reasons, because old code is usually interesting, not because the algorithm is that fascinating or complicated.
1 Short scale. 1012. 2 1018. Yes, I know the proper name for that is a quintillion in the short scale and a trillion in the long scale.
And then he fell down some stairs. He was at a hospital in Brussels when it happened (psychiatric hospital, strictly, but close enough), replacing smoke detectors (he’s a fire safety person), so they reached him pretty quickly. That was yesterday. He’s currently at said hospital, under induced hypothermia (and stable), until later today.
He’d been having heart problems for a while, and after his boss had to drive him back home after he collapsed on a company trip recently, he had a stent inserted into his heart and was on a ton of medication, but obviously he still smokes and he has very irregular sleeping patterns.
I don’t know what his prognosis is, but in general these things don’t tend to go well (though the fact that he survived this far means he’s already doing better than most people).
This left his car unattended in Elsene overnight, though, so obviously someone felt the need to smash the back passenger window. So right now, aforementioned boss is driving my mom and my sister to Brussels in her PT Cruiser to retrieve my dad’s personal possessions and the car, and I’m watching the dogs. Tonight, they’re taking the train back to visit him, because visiting hours are weird and at least he’d probably be awake then.
My grandfather, who’s a bit high-maintenance at the moment for various reasons, is being looked after by my aunt and uncle, who came over from Limburg for moral support.
Last night was also the hottest night in six years, and the whole week has been hot enough that I haven’t really slept at all, so fun times.
More on the story as it develops. I’d put this on Facebook, because that’s where everyone who might care about this is, but my mom’s there too, and she doesn’t need to see this again. I’m pretty sure she doesn’t read my blog.
Update: He was still asleep when they visited yesterday, though they’d stopped the hypothermia treatment. Now they’re beginning to reduce the medication used to keep him unconscious. No real news otherwise, though the prognosis is cautiously good. It’s now Friday morning, and it happened Wednesday afternoon.
My grandfather, who’s in the hospital for being old (nothing life-threatening), will be able to move straight from the hospital to the home where my grandmother is also staying, so that’s nice.
Too many curious people are calling. I’ve answered more phones today than in the rest of my life combined.
Update: Apparently after they cut off the medicine used to keep him asleep yesterday, he got “agitated” and they put him back on it. Now they’ve cut it again, and he should be waking up “within days or weeks”. Hospital drugs don’t fuck around.
Update: Saturday now. He’s still not awake. My uncle (who’s a radiologist) is on his way from Andorra, and an MRI has been scheduled for Monday.
Update: Sunday. My uncle arrived, and already talked to the hospital’s doctor over the phone and is optimistic. My other uncle and my mom are picking him up and driving him to the hospital itself. Apparently they’re going to try to get my dad moved to Gasthuisberg, in Leuven. His doctor there (the one who placed the stent) said the stent probably collapsed (“sheer bad luck”), but he’s in Sicily at the moment, so he can’t be sure.
Haskell is humping my aunt’s leg.
Update: They’re back. He’s breathing on his own and everything, and he reacted to my mom’s voice (but not my uncle’s), so my uncle is making her visit him every day from now on. The stent is fine, it was probably an infarction, and the move to Gasthuisberg isn’t happening for the moment. And apparently it takes five to seven days on average for a person to wake up, so when the nurse said “yes” when my mom asked if it was a bad sign that he wasn’t awake yet, she was wrong. Probably a language issue.
Basically everyone’s optimistic.
Update, Friday Aug 28: I went to visit him for the first time today, and he seems to be doing well. He’s been “awake” since Wednesday, and he was really responsive today. He seemed to recognise us, and when my mom asked him to squeeze my hand when I was holding his he did. He’s still very drugged up, but I think that if it wasn’t for the feeding tube they cut his throat for, he would have been able to at least say our names, if not hold up his end of the conversation.
Brussels is a filthy, filthy town.
Update, Monday Aug 31: He’s being moved to Leuven tomorrow.
I’ve never had much use for source control, but after that one thread broke /prog/scrape I realised it might be useful to have somewhere centralised to put the source code and recent diffs, instead of just having a possibly-up-to-date file hidden here somewhere and having people download that whenever their shit breaks without really knowing if I fixed it yet. Github was an obvious choice, not least because bandwagons are awesome, but then I lost interest and forgot about it until now.
Incidentally, when you create a new repository on Github, it automatically generates a URL for you to push to, of the form git@github.com:username/projectname.git. The project name can’t have any characters outside [a-zA-Z0-9-], though, so when it does they’re replaced with dashes.
Whoever wrote that piece of code, though, forgot that project names apparently also can’t start with a dash, so when you try to push to it, it just gives you an unhelpful error message:
Invalid repository url. Make sure you include the .git, e.g. git@github.com:defunkt/ambition.git
And then it breaks the connection, which is particularly nice when your first experience with git involves pushing a project named -prog-scrape.
Anyway, easy enough to fix. I do like that it uses ssh, so I don’t have to type my password every time. I’ll probably be creating additional repos for my many, many other projects that people find useful.
So hey, this doesn’t expand the number space. What’s the deal?
I’m in a class called Netwerkbeheer (Network Management), which spans two semesters and is a transparent excuse to peddle CCNA certifications. As a result, I spend a lot of time playing with Cisco routers and switches, and one of the many, many things that annoy me about Cisco’s IOS is their cavalier attitude towards security and cryptosystems. A particularly egregious example of this is Cisco’s type 7 encryption.
I’ve never had much use for source control, but after 