http://qntm.org/ the personal website of Sam Hughes http://qntm.org/know http://qntm.org/know Ra » Previously Dr. Dan Czarnecki arrives at the lecture theatre thirty seconds after the lecture was supposed to begin and stalks down to the front through a noisy cloud of conversations-in-progress. He throws his leather briefcase at a chair, grabs a marker pen from the nearest shelf and begins scrawling a board-wide equation on the far left whiteboard. His handwriting is appalling, even worse on the board than it is on the heavily photocopied notes he sometimes remembers to hand out. Today, the marker pen is running out. Czarnecki realises this halfway through the equation, glares at what he's written, glares at the pen, caps it and hurls it overarm into the waste paper bin at the other end of the wide, mainly circular stage. The bin is metal, and there's a sharp and satisfying tang as it catches the pen. Czarnecki finishes the equation with a different colour. Only then does he turn around and start removing his gloves, hat and coat. This is also the point at which he will start speaki...]]> Thu, 02 Feb 2012 12:24:33 +0000 http://qntm.org/isnt http://qntm.org/isnt Ra » Previously When a man and his love interest first encounter one another in an adversarial setting, it's supposed to go like this: he proves overconfident; she proves overwhelmingly more competent; she decisively gets the better of him, with embarrassing and hilarious results; this impresses him (and anybody else who happens to be watching) while demonstrating that she's sassy and capable and can take care of herself. But this is a little too early in the lives of Nick Laughon and Laura Ferno, and neither of them can really take care of themselves yet. It's their first year at university and it's their first Beginner's Bojutsu lesson. Every time she lands a blow on him they both drop their bo staffs, and every time he tries any kind of clever spinning move (while the instructor, who would disapprove, is not looking) he loses his grip and ends up hitting himself in the stomach. The whole lesson is awkward stances, heavily telegraphed moves and clumsy falls. Fortunately, stage one in an...]]> Thu, 08 Dec 2011 23:03:44 +0000 http://qntm.org/ignorance http://qntm.org/ignorance Ra » Previously The first magic spell is spoken by a 90-year-old retired Indian physicist named Suravaram Vidyasagar on 1st June 1972. It is one hundred and seventy-nine syllables long, comprising equal parts Upanishadic mantra and partial differential equation. The effect of Vidyasagar's spell is nothing at all. He has discovered what will later be called "uum", the empty spell, which expends no mana and fails to rearrange the universe in any externally detectable way, but which then - crucially - returns to the dispatching mind and tells it so. Vidyasagar immediately notices the curious reaction to his new "differential mantra". He repeats it several times. Each time, he receives, in an almost-non-existent part of his brain, a tiny almost-thought: a thought so faint and difficult to get a grip on as to be a tiny elementary dream: "Success!" Vidyasagar is confounded. The result is completely unexpected. Later, many will call it dumb luck. "Luck" can certainly be made to stick: future re...]]> Tue, 11 Oct 2011 21:10:02 +0100 http://qntm.org/hypertime http://qntm.org/hypertime Blog » While trying to figure out the plot for Ra, I came up with a brand new model of time travel which I decided to call "hypertime" because it featured a second dimension of time. (This "hypertime" has no relation to the concept from DC comics.) However, I found this model of time travel so insanely complicated that I couldn't even reason logically about what would happen if the universe were to behave in such a way... let alone convey such a cosmic structure to readers in the form of a compelling story. So I abandoned the concept and I'm now exploring a new idea. However, I don't see any reason to just bury this idea for eternity, so here it is. Make of it what you will. I suggest you draw diagrams, it'll highlight how complicated this thing is. * There are parallel universes. Each universe is offset in time from the next, but each universe is exactly identical to the others. In our universe, it is currently 2011. In the universe "above" ours, however, it is 2012, and 2011 has...]]> Tue, 04 Oct 2011 22:50:57 +0100 http://qntm.org/sufficiently http://qntm.org/sufficiently Ra » Previously "Stab wound" is a really amazing phrase to suddenly be forced to consider from close, personal range. Laura Ferno wakes up the following afternoon with a belly wrapped in bandage, a mouth tasting like sun-dried vomit and two distinct hangovers: one from the alcohol, and one from the anaesthesia. She spends a restless and irritable Christmas in hospital, forced to keep still so as not to tear her side open again. She is discharged shortly before the New Year, with a sizeable antibiotics prescription and instructions not to drink alcohol while taking them, which only makes her angrier. After a month and a half, her doctor gives her permission to be physically active again, and doesn't bother to set up another appointment. And then the physical injury is totally in the past. Laura forgets about her scar for months at a time. It should be over. But this is the United Kingdom, and a muggee can't straight-up kill a mugger in self-defence and simply return home to unified raptur...]]> Thu, 29 Sep 2011 00:19:13 +0100 http://qntm.org/chess http://qntm.org/chess Blog » They've already made Clue (Cluedo). They've filmed Battleship and they're going to release that too. There's going to be a Monopoly movie. Somebody, somewhere, has the rights to Candyland. And, arguably, there are also Twister and Downfall. Okay, not really. But we were sitting around a hypothetical table in an internet chat room figuring out what other board games you could turn into profitable film franchises. Bruce Willis is played out; but ten years ago, he could easily have carried "Jenga" - obviously a disaster movie set in a high-rise building. "Hippos: The Hunger", a variation on "Anaconda". "Mousetrap", a remake of Mousehunt with more elaborate Rube Goldberg machines? Experimental science fiction slasher/horror "Rubik's Cube"? "Connect Four", followed by its sequel, "Connect Four II: Connect Five"? And then somebody threw this down on the table. I was blown away by the elegance of this concept. It's the E=mc2 of board game flicks. You don't even have to buy the rights. It's ...]]> Mon, 12 Sep 2011 23:28:34 +0100 http://qntm.org/timeline http://qntm.org/timeline Blog » Now accurate up to the end of production season 6. Notes The Futurama universe is assumed to be exactly identical to ours except where the show explicitly diverges from reality. Several episodes' dates are formed based on projections which may prove unreliable. For example, "Put Your Head On My Shoulder" can be firmly dated to 14th February only if Valentine's Day doesn't get moved over the next thousand years, and "That's Lobstertainment!" features the 1074th Academy Awards, which places it in 3002 only if no Oscar ceremonies are cancelled. Except where stated (and where direct contradictions arise), it is assumed that production order of episodes is the same as chronological order. The events of the episodes "The Why Of Fry", "Bender's Big Score" and "All The Presidents' Heads" resulted in changes to the Futurama timeline. This timeline deals solely with the final timeline to date. There are other timelines in which events played out differently, which no longer apply to...]]> Sun, 11 Sep 2011 18:37:42 +0100 http://qntm.org/city http://qntm.org/city Ra » "Nottingham has enough pubs and clubs", say the local police. If you wanted to get around every last one of them it would be a year at a brisk trot before you were starting to visit establishments more than one mile from the centre of the city. Pick a Friday or a Saturday, any Friday or Saturday of the year: the establishments will be rammed and jumping and the streets bustling with people in their most tightly-wound and elaborately crafted drinking costumes. It's almost Christmas but the cold season has not added much to the average number of layers. Multicoloured decorative illuminations span the alleys and narrower streets: yellow curlicues and red stars and inexplicably five-pointed white snowflakes. Orange light spills out onto the street from the pubs. Floodlit trams cruise past, bells ringing at stumbling people in the way. Officers with cars and vans and fluorescent visibility jackets hold a largely pre-emptive presence on various likely streets. Quite frankly, it's a quiet one...]]> Fri, 09 Sep 2011 20:32:21 +0100 http://qntm.org/ra http://qntm.org/ra Fiction » This is a science fiction story in progress. Read from top to bottom. Today in Ra... Thaumic City Sufficiently Advanced Technology From Ignorance, Lead Me To Truth Magic Isn't What You Don't Know ...]]> Fri, 09 Sep 2011 18:52:57 +0100 http://qntm.org/fib http://qntm.org/fib Code » This is me attempting to decode this. The problem Let's say you've got a function of one argument. Basic Fibonacci sequence. Recursive, calls itself. Returns an integer. var fibo = function(n) { return n == 0 ? 0 : n == 1 ? 1 : fibo(n-1) + fibo(n-2); }; alert("fibo(32) = " + fibo(32)); // Takes a little while Is there a way to create a new function which is identical but automatically caches answers before it returns them? Let's say, for simplicity of implementation, that the argument can always be used as the index in an object, which means that a simple object cache can be used to cache the results from the function. Then there sure is. For example, we could manually create a wrapper function fibo_caching: var fibo = function(n) { return n == 0 ? 0 : n == 1 ? 1 : fibo(n-1) + fibo(n-2); }; var fibo_caching = function(n, cache) { if(!cache[n]) { cache[n] = fibo(n); } return cache[n]; }; var ...]]> Wed, 07 Sep 2011 19:11:47 +0100 http://qntm.org/test http://qntm.org/test Blog » Firstly, it's a thing. I didn't even realise this at first. I was bred on a diet of console videogames and I knew in my soul that playing games was the best thing ever. Being paid to play games was obviously even better than the best thing ever. Being a professional videogame tester was, logically, the greatest profession possible. You get to play great games before anybody else, right? And you get paid for it! There was no lightning flash when I realised that being a professional videogame tester means playing great games before they are actually great (before, in fact, they can even be described as "games", or "playable"). It was just a realisation that I eventually came around to. If you need a lightning bolt, Here's Your Reality Program. Videogame testing is tiresome and unfun. Any videogame becomes tiresome and unfun to test, after ten months. Later, when I started coding as a hobby, my typical development process was to write some code, run the program and see if it failed in t...]]> Mon, 29 Aug 2011 19:50:39 +0100 http://qntm.org/twit http://qntm.org/twit Blog » The URL http://qntm.org contains 15 characters. Twitter's naïve URL "shortener" helpfully shortens this to 20 characters, leaving me with 120 remaining when I should have 125: If I type a full 140-character string, Twitter reports that I am 5 characters over budget and refuses to let me tweet: When is a URL shortener not a URL shortener? When it fails to ensure that the new URL is shorter than the original. I'm a professional software tester, you know. We catch this kind of thing. * This was the case as of 2011-08-16, and I only saw it in the main web interface, not when you (for example) click the "tweet this" button at the bottom of this page. Once it's fixed (I'll let them know about it tomorrow and I expect it'll be rectified in a day or two) I'll update this page, but until that time, try it for yourself....]]> Tue, 16 Aug 2011 00:59:12 +0100 http://qntm.org/crystal2 http://qntm.org/crystal2 Blog » Yesterday (Saturday 13th August 2011) we made our first attempt/reconnaissance run of the Crystal Maze Pub Crawl. There were a few question marks still remaining. For example, my route map doesn't contain any Mental, Mystery, Physical or Skill challenges. In my head, I had one Physical challenge worked out - "down your drink" and one Skill challenge worked out - "flip N beer mats where N is the number of people on the crawl". The night before the crawl, friend H and I sat down in the Railway Tavern on Tulse Hill (which is a great pub, though sadly a long way off the route) to bash out some additional challenges. Here's the full list we worked out. Challenges SKILL: Buy a bar snack, ideally peanuts. You must catch, in your mouth, one peanut thrown by each member of the team (including yourself). PHYSICAL: You may not touch the ground between this pub and the next one. (That is, your teammates will have to carry you.) SKILL: place a stack of N beer mats on the side of the table, ...]]> Sun, 14 Aug 2011 16:28:39 +0100 http://qntm.org/perl http://qntm.org/perl Blog » A bunch of new people started at work and we use a lot of Perl in our department. So I put together some information about Perl and I thought it might be worth sharing so here it is. Perl in about 2 hours 30 minutes This was originally dispensed in the form of a presentation and about a dozen Perl scripts and half a dozen modules, which I've consolidated into one fairly readable file. If you find something that has been omitted from the file, this is probably either because it isn't used very frequently in my department, because it's trivial to look up, or because it just wouldn't fit due to time constraints. It turns out that two and a half hours is barely enough to rattle through the essentials of Perl. The biggest example of this is use, a critical core feature which requires knowledge of packages, modules (which are different from packages), BEGIN blocks and class methods (i.e. object-oriented Perl) in order to fully explain....]]> Sat, 30 Jul 2011 22:42:50 +0100 http://qntm.org/tetris http://qntm.org/tetris Code » Exactly one of the following statements is true. In Tetris, you can always get at least one line before losing. In Tetris, a sufficiently evil AI can always force you to lose without getting a single line, by providing bad pieces. Which one? Prove it. The setup I created HATETRIS last year because I wanted Tetris players to suffer. It was something I created for my own amusement and as a programming challenge and to investigate the use of JavaScript as a gaming platform. HATETRIS explores only to a depth of 1 piece. It looks at the immediate future and chooses the single worst piece for the present situation, ignoring the possibility of the player using the current piece to set up a situation where the 2nd piece forces a line. After the first iteration of the game, I started using a bit mask to express each row of the playing field ("well"), which made testing the insertion and removal of possible pieces faster, to the extent that a new piece appeared more or less instantl...]]> Wed, 20 Jul 2011 23:26:17 +0100 http://qntm.org/cmd http://qntm.org/cmd Blog » Okay, I have finally sussed this problem on both Windows and Linux. The following code is written in Perl but it can be quite easily adapted to work for pretty much any programming language. Procedure for escaping an arbitrary argument for use at a command line sub escape_arg { my $arg = shift; # Windows cmd.exe: if($^O eq "MSWin32") { # Sequence of backslashes followed by a double quote: # double up all the backslashes and escape the double quote $arg =~ s/(\\*)"/$1$1\\"/g; # Sequence of backslashes followed by the end of the string # (which will become a double quote later): # double up all the backslashes $arg =~ s/(\\*)$/$1$1/; # All other backslashes occur literally # Quote the whole thing: $arg = "\"".$arg."\""; # Escape shell metacharacters: $arg =~ s/([()%!^"<>&|;, ])/\^$1/g; } # Unix shells: else { # Backslash-escape any hairy characters: $arg =~ s/([^a-zA-Z0-9_])/\\$1/g; } return $arg...]]> Fri, 15 Jul 2011 19:46:34 +0100 http://qntm.org/bulbs http://qntm.org/bulbs Blog » The problem You have a 100-storey building and 2 identical, supposedly-unbreakable light bulbs. You know for a fact that if you drop a bulb at floor 0 (i.e. ground level), the bulb will not break. You also know for a fact that if you drop a bulb at floor 101 (i.e. go to the roof and throw it off), the bulb will definitely break. In fact, there is some floor f with 0 ≤ f ≤ 100 such that if you drop a bulb at floor f or lower it will not break, and if you drop it at floor f+1 or higher, it will definitely break. You have only 2 light bulbs. Once they are both broken, there are no more. Assume that dropping a bulb multiple times does not weaken it. How many bulb drops must be performed to find f, in the worst-case scenario? Hint: the answer is below 20. Suppose we had just 1 bulb Consider a simpler scenario in which we have only 1 light bulb. In this case the solution is obvious. We cannot drop bulb 1 at, say, the 50th floor. If it breaks, then we have learned that f is betwe...]]> Tue, 12 Jul 2011 22:29:54 +0100 http://qntm.org/locoparser http://qntm.org/locoparser Code » Following up from Loco, which introduced Loco.php, here are some more examples built using this parser combinator library. Each of these examples enables you to parse a grammar and return a Grammar object capable of recognising that grammar. bnf.php - Defines $bnfGrammar, which parses grammars presented in Backus-Naur Form. wirth.php - Defines $wirthGrammar, which parses grammars presented in Wirth syntax notation. ebnf.php - Defines $ebnfGrammar, which parses grammars presented in Extended Backus-Naur Form. locoNotation.php - Defines $locoGrammar, which parses grammars presented in Loco notation (see below). Examples and demonstrations can be found in the unit testing sections at the bottom of each script. Alternatively, read on to see what each notation gives you: Backus-Naur Form BNF is generally pretty low-tech and lacks a lot of features. Sample grammar in Backus-Naur Form This appears on Wikipedia. This is a pretty clunky example because it doesn't handle wh...]]> Sun, 10 Jul 2011 18:36:29 +0100 http://qntm.org/loco http://qntm.org/loco Code » Loco is a library of parser combinators for PHP. Loco uses single-valued parsers called MonoParsers. A conventional, "enthusiastic" parser returns a set of possible results (which is empty if parsing is not possible). A "lazy" parser returns one possible result on the first call, and then returns further results with each subsequent call until no more are possible. MonoParsers simply return a single result or failure. By explicitly disallowing backtracking, this keeps parsing time linear (unless you use advanced, non-regular "regular expressions", but that's crazy talk). Loco.php Examples json.php - parse JSON expressions regEx.php - take simple regular expressions and parse them into data structures simpleComment.php - recognise HTML comments for here on qntm.org More examples For examples of using Loco to recognise grammar syntax notations such as Backus-Naur Form, see More Loco examples. Great things about Loco Parse in linear time Simple, logical,...]]> Thu, 30 Jun 2011 12:49:38 +0100 http://qntm.org/combinators http://qntm.org/combinators Blog » A parser is a function which takes a string (a series of tokens) as input, and returns a set of matches as output. In the most basic form, each match is simply an index, an integer marking a position further on in the string, but it could also be something more complicated, like a full parse tree. A combinator is a higher-order function (a "functional") which takes zero or more functions (each of the same type) as input and returns a new function of the same type as output. A parser combinator is a higher-order function which takes parsers as input and returns a new parser as output. Simple example parsers Suppose we had an extremely simple parser called A, designed to recognise the single character a. See what happens when we provide A with various strings as input: A(ε) = {} A(a) = {1} A(ab) = {1} A(acegi) = {1} A(aaaa) = {1} A(xa) = {} (We assume that the indices of characters in the string begin at 0. For example, the string xyz has 3 ...]]> Tue, 28 Jun 2011 22:24:46 +0100