Here’s a horrid hack or neat trick to work around a gaping inefficiency in the MySQL query planner:

Imagine you have a very large table and a composite index e.g. the fields A, B, C and D.

Imagine you have a query WHERE A = ? AND C = ?

MySQL will use the index to check all the values of A but dereference each row with the matching A before checking the C.

You can see what is happening using EXPLAIN SELECT by looking at the KEY and KEY_LEN columns: the index will be named the KEY (good so far!) and the KEY_LEN will be the max size of column A (ugh!). 

If you supply a dummy clause constraining B too then you can force MySQL to check the C constraint before it dereferences any rows: SELECT … WHERE A = ? AND B != ? AND C = ? (where B can be checked against some value that it can’t possibly be).

You can confirm this is happening by looking that the EXPLAIN SELECT again: the KEY will still be the name of the index (if it isn’t, you can force the index to be used with a USE INDEX clause) and the KEY_LEN will now be the maximum length of the A, B and C fields combined.

You can even use this trick to get an index used even if the very first field in the composite index is not constrained, e.g. WHERE A != ? AND B = ?

This isn’t foolproof - you always need to benchmark with your database!  Using any index and the additional dereference cost compared to just doing a table scan in the first place assumes that the index is dramatically cheaper to walk and will dramatically reduce the number of rows that need to be dereferenced.  If only a tiny subset of the table needs to be dereferenced, the index will help; if a large proportion of the table is going to be dereferenced anyway then it’d be better to do a table scan from the get-go.

However, if you have very large tables and you have composite keys that cover your fields but which some of the composite keys unconstrained then its well worth evaluating this approach which, in the right circumstances, can give orders of magnitude improvements.

Why doesn’t MySQL use this trick internally?  Well, it should!  If its already decided to use a composite ordered index for some prefix of the constrained fields, then it should always check all constraints it can before dereferencing any actual rows. If MySQL used this trick you wouldn’t have to find some impossible value to fake a check against either.

Its a bit harder to say if it can work out when to use a composite index when there is no prefix at all.  And of course it doesn’t work with hash indices.

Does MariaDB use this trick internally automatically?  I don’t know but I doubt it.

Does PostgreSQL?  No idea.  Etc.

If you liked this you might like my recent stats on database compression or browse some of my earlier posts 

TL;DR: use TokuDB.  Always.  It massively reduces storage requirements and is massively faster than InnoDB, even on low end hardware.  My tables were compressed to just 12% original size and that’s fairly typical.

A very simple structure:

CREATE
                TABLE test (
      date DATE NOT NULL,
      site VARCHAR(8) NOT NULL,
  
                   order_id VARCHAR(64) NOT NULL,
      time TIME NOT NULL,
      kind ENUM(...) NOT
                NULL,
      account INTEGER,
      user INTEGER,
      client_price
                BIGINT,
      supplier_id INTEGER,
      supplier_cost BIGINT,
    
                 client_ref VARCHAR(32),
      data JSON,
      PRIMARY KEY (date, site, order_id),

                     INDEX (account, user, client_ref)
                ) DEFAULT CHARSET utf8
PARTITION BY RANGE (TO_DAYS(date)) ( ...

This system is using the RDBMS as a document store; the order items are being flattened into a document store (the ‘data’ field).

The ETL is upserting order events as they are processed, using multi-row INSERT INTO … ON DUPLICATE KEY UPDATE …

And I’ve been running performance tests with some real data.  27M rows of real data, all on the same day (so all in the same partition).  37M upsert statements inserting or updating those 27M rows, issued in batches of 1K-2K per multi-row statement.  This is enough rows to be able to get a grasp of upsert performance and extrapolate storage requirements.

The test box is an AWS t2.medium instance.  This is a very weak VM with 2 (virtual) CPUs and 4GB RAM.  Not normal DB fare, so performance beware.

The 27M rows take 10.48GB uncompressed.  It takes InnoDB 10 hours to load all the data.

In the old days, MySQL InnoDB offered ‘row_compression’.  This compresses individual rows.  This reduces disk requirements to 5.73GB (45% space saved).  So it halves the disk space!  Sadly, the test now took 15 hours instead of 10 hours.

More recently, MySQL introduced ‘table compression’.  (MariaDB also added it, calling it ‘page compression’; the CREATE TABLE syntax is infuriatingly slightly different).

Underneath, InnoDB is organized as ‘pages’.  This table compression intercepts these page reads and writes and, as pages are written to disk, they are individually compressed and written as a ‘sparse’ file.

As these InnoDB pages are larger than the file system pages, there is the opportunity for a ‘hole’ to be ‘punched’ in each InnoDB page.  Imagine an InnoDB page is 12KB, and the file system page size is 4KB.  The page may compress down to 1KB, meaning it only needs the first file system page (4KB),  and 8KB would be saved.  This example illustrates how wasteful this approach can be; there can still be a lot of slack in each page.  The total file-size as reported by ls is unchanged, but the actual used disk space (as shown by e.g. ls -s) is reduced.  Page compression compresses this table to 4.07GB (61% savings).  The bad news is that performance sinks awfully!  I aborted the run after 32 hours, as upsert speed had dropped to under 100 orders/sec.  I’ve seen this on MariaDB RDS and on my little t2.medium.  Its atrocious!

TokuDB is an alternative storage engine to InnoDB.  It is nicely packaged by Percona so its very straightforward to install.

TokuDB compresses databases with zlib by default.  It compresses pages, but doesn’t store them as sparse files; instead, the total file size you see on disk is the total file size.

TokuDB with zlib compresses to 1.45GB (86% savings)!  This is the same compression algorithm as InnoDB page compression and operating at much the same logical page level, but conferring much bigger savings because each ‘page’ is not rounded up to a multiple of the file system page size.

Because InnoDB puts the whole table (or, as in this case, partition) into a single file you cannot see how much of the storage is for the primary rows and how much is for secondary indexes.  TokuDB, however, has separate files for each index.  So in this case there are two files for the partition, and I can see that the 27M rows takes 1.02GB and the by-client index takes 0.44GB.

TokuDB allows you to specify other compression algorithms.  The weakest (thus fastest) is ‘snappy’, which is an LZ77 compressor without entropy coding.  It compresses to 2.31GB (78% savings; same ratio rows to index).

There is also QuickLZ (between snappy and zlib in CPU requirements; 1.95GB; 81% savings) and LZMA (stronger than zlib; 1.23GB; 88% savings!).

LZMA is a clear winner here.  What’s fascinating about the TokuDB though is not just its space-saving but also its performance: it takes just 2 hours to run my ETL and choice of compression algorithm has no noticeable effect on that!

Now the dire uncompressed InnoDB performance is perhaps the classic “InnoDB is not good with databases that don’t fit into RAM”.  I was using Percona packages so the defaults were not as mad as they used to be out-of-the-box with other linux sources, but I did up it to 2GB and a big log.  Configuring InnoDB optimally is like reading tea leaves and no amount of doing it makes me confident I’ve hit the sweat spot for any particular workload.  This upsert workload seems to be particularly stressful.  The t2.medium has two (virtual) CPUs, and as upsert performance dropped I saw ‘top’ reporting load average over 2.0 even though ETL was waiting on the DB.  Not good.

However the dire compressed InnoDB performance I saw repeated on a MariaDB RDS m4.2xlarge with the same data-set.  There’s something wrong with either InnoDB page compression, or with EBS spare file performance!

On the other hand, TokuDB shows how to do things properly!  The out-of-the-box defaults are very sane (it doesn’t use O_DIRECT; instead, it takes 50% to store uncompressed pages, and lets the OS cache the compressed pages in the normal file buffer cache.  Inspired!).  And the performance is just so stable!  On the t2.medium, which is a piddling little box, I saw 5000 orders/sec sustained throughout the entire run.

I think I’ve heard that TokuDB is marginally slower than (uncompressed) InnoDB on small tables.  And perhaps most users have small tables.  I don’t think there’s actually that measurable a gap when everything is tiny.  But the moment you go over a million rows or contemplate partitioning then I think TokuDB is the obvious choice.  In fact it would make a very good default.

Oh, and for kicks, try a COUNT(*) on a big InnoDB table.  And then go make a coffee!  TokuDB … snap!  Not based on meta-data like MyIASM did neither; just so much faster.

TokuDB redefines what a ‘small’ database is.  It moves the goalposts.  It means I can build bigger systems without scaling sideways.  I don’t get why everyone still uses InnoDB ;)

see also:

• Enigma Machine on Paper and Python
• Fast Enigma sim in C++
• A brief history of the Enigma and the pre-war cracking of it
• Enigma in a spreadsheet!

My favourite book was Fermat’s Last Theorem by Simon Singh.  So when in 1999 I saw his new book - The Code Book - in shops I just had to buy it, despite it being incredibly expensive (for a very poor student like myself).  I then took my new prize procession with me expectantly on the summer holiday.  And when I reached the end of the book that I discovered it contained a Cipher Challenge!

I set about cracking the ciphers with gusto.  By chance I happened to have my 286 computer with me, and my hobby language of choice - Turbo Pascal 7. 

I think I skipped the ADFGVX cipher, so excited was I at the prospect of cracking the Enigma stage 8 of the contest.  Unfortunately, when I reached the Enigma, I was stumped.  I couldn’t make any headway with simulating the Enigma.  I wrongly assumed that the message would begin with the message key encrypted with the day key twice.  But my biggest mistake was not understanding how rings affected things.  I didn’t understand how rings affected things because The Code Book didn’t actually explain them!  The book instructed the intrepid explorer to search the Internet for more details and I didn’t take any heed of this because a) I couldn’t imagine the book wouldn’t actually give me everything I needed to crack the challenge, and b) I didn’t have any Internet.  The Enigma I was trying to crack wasn’t even an accurate Enigma.

So 17 years later I find myself on a whim tacking the Enigma once again.  And my computer is a bit faster too.  But I want to attack it my way, putting myself as much as possible in the shoes of my old self 17 years ago, only this time with Internet so I can double-check the correctness and completeness of my implementation of the Engima cipher machine.

This is my attack on the Enigma.  I will describe my attack on an M3 Enigma (used by the army and air force) and then I will generalize it to attack the M4 (used by the U-boats; what Alan Turing is famous for cracking).

A lot of people now think that Alan Turing cracked the Enigma.  A lot of people like to correct those people and say that it was the Poles who truly cracked the Enigma.  So we really need to correct everyone and set things straight, because it was far more nuanced than that, with far more people involved, and different versions of Enigma were cracked even earlier.  If you read enough about code breaking you end up with a fuzzy timeline in your head pieced together from all the various sources.  Here’s what I’ve osmosed:

Following on from my Python Enigma cipher machine simulator, I re-wrote it in C++ for maximum speed.

The settings for each rotor - its start position and ring setting - can actually be combined into a single offset. This is perhaps why all the popular treatments of the subject just ignore the impact of the rings on the number of combinations. In truth, their impact is hard to explain. The rings change when rotors rotate, and do have an impact on the number of combinations, but many initial starting positions are equivilent for short messages because the rings cancel out the rotor start position and do not cause a rotation because the message is too short.

The M4 Enigma - as infamously used by the U-boats - is usually described as a ‘four rotor’ machine. And that’s strictly true, I suppose, but I think I have a better way of describing it:

The M4 was a normal 3-rotor M3 Enigma chassis. A new 'thin’ reflector design was developed that could take a new, thinner 'greek’ non-rotating wheel. The thin greek wheel could be placed in any of 26 positions and clicked into the thin reflector. This could then be placed in the chassis in the normal reflector position.

So basically the M4 is an M3 Enigma with a configurable reflector.

I wrote the fast Enigma sim to serve as a basis of a statistical attack on the Enigma. In fact, if you look at my test vectors, you’ll notice one of them is Simon Singh’s Cipher Challenge Enigma stage 8, which I cracked using my statistical attack! More on that in the next post :)

And here’s the code. As you can see, the vast majority of the code is just test vectors to ensure its correctness:

(don’t forget to also read: my attack on the Enigma cipher machine)

It turns out my kids have been sending each other secret messages, enciphered with a substitution cipher of their own invention!  They only let me see the secret key when I agreed to help them mix up a very complicated recipe for invisible ink:

This reawakened fond memories of a young me getting a good way through Simon Singh’s The Code Book cipher challenge :)  (Also, see the Enigma Spreadsheet my friend made a few years ago!)

So my mind raced considering how fast todays laptops can brute-force, say, Enigma?  Even non-brute-force attacks are on a different scale if you have a computer.  For example, with Enigma, can you ignore the plugboard and go through every combination of day and message key, using a histogram to spot possible text that you then attack as a substitution cipher?

First I needed an accurate Enigma simulator.  To be honest, I found most descriptions a bit light on detail.  But I quickly found a paper Enigma, which I made:

From this, I was able to create a Python Enigma machine!  Source available here:

Its becoming a Ludum Dare tradition that I make a mosaic for each competition. I didn’t enter this time, but I still made a nice mosaic:

My daughters are really into robots.  They love going to the science camps during school holidays and the highlight is always programming the lego mindstorm robots.

So I got all excited about getting them a robot for xmas, and so I went looking.  My friend Roy recently blogged about robots (hacking a Roomba! and Makeblock) and this really wetted my appetite :)

In the end I got them a SparkFun Redbot inventor kit.  Its an Arduino with line followers, whiskers, accelerometer for bump detection and magnetic wheel rotation counters.

But its really bugging me how limited the Arduino is!

Here’s the Raspberry Pi Zero that I read about recently:

The programming blogosphere is chock full of hype with Apple open-sourcing their Swift language.

So is this exciting?  No, not really.  I can’t see what all the hype is about.

Swift is very much tied to Apple’s walled-garden of iOS app development.  Anyone developing for iPhone has to pick between anarchic Objective C and new shiny Swift.  Its a captive audience.  Its an audience unaffected by whether Swift is open-source or not.

Will Swift be used for anything else any time soon?  I think not.

If you’re developing for the server, are you going to adopt Swift?  For me, the fact that IBM is backing server-side Swift is all the death knell you need ;)

If you’re developing for the server you already have a myriad of languages to pick from.  From scripting languages like Ruby, Python and Javascript, to compiled languages like Java, C/C++ and Go, you have a full range.  If you want a ‘safer’ language you can go Haskell or Rust.  What is so compelling about adopting Swift on the server-side?   I can’t spot anything at all.

Swift on the server is going to be about as popular as C#.  Its a language you use if key parts of your project on other platforms are forced to use it.

I like how Swift reasons about integer overflow and nil.  I wish there was a ‘safe’ C.  But that’s not making me itching to go use Swift for server-side programming.

Aurel Bílý made this nice wallpaper, and told us how he did it:

Here are a couple of mosaics I made from the LD32 thumbnails:

(On the left, a target image.  On the right, a mosaic made from thumbnails of all the Ludum Dare 32 games, positioned using an MSE score metric.)

Making mosaics is in two steps:

1. score each tile in each position
2. determine the optimal positioning of all tiles to maximize the total likeness

The second part is easy (although I tried imprecise approximations at first, and only discovered it fairly recently): use the Hungarian Algorithm.

Its that first step that’s tricky.

I have been using Mean Square Error (MSE) and have been fairly happy with the result.  But readers have pondered if there aren’t better metrics that better account for shape and contrast and such…

So to please some Ludum Darers (and because I was curious), I tried out some algorithms.

First, Peak Signal to Noise Ratio (PSNR) is just a rephrasing of MSE and the results are much the same.

Second, I tried Structural Similarity (SSIM) index.  This was a promising avenue to explore.  My mosaic maker is Python and there’s a scikit helper, but scikit doesn’t work with pypy (and neither does a stock numpy; trying to get the mosaic maker to work happily in pypy with these kinds of dependencies has been a nightmare).  In the end I went with pyssim which turned out to not work in pypy either due to dependencies but I stuck with it on cpython anyway.  Its about 4x slower than MSE and most of the cost seems to be comparison overhead and not really affected by how big the patches I compared were.

SSIM is actually working in luma (eh fancy term for grayscale) and trying to account for shape not colour.

The results:

(On the left, the original.  In the middle, MSE.  And on the right, SSIM.  Tiles are the thumbnails of 2819 Ludum Dare 32 games (omitting 2 games with broken thumbnails!))

So I tried blending the MSE and SSIM scores (suitably scaled of course) but couldn’t get even a little bit of SSIM to help:

(Here 70% MSE and 30% SSIM.  I even tried 8% SSIM and it looked much the same.)

I also tested using the YCbCr colour-space too; results were much the same (as all the tiles are screenshots they are invariably natively RGB; if the tiles were made from photos there’s a good chance that YUV makes much more sense).

Now I am making a novice interpretation of this but my guess is that in mosaics, which are best viewed from a great distance where the tiles are increasingly pixel-sized, tile colour dominates over shapes within the tile?

Last Monday evening I got to look around, talk to and distract the Copenhagen Suborbitals team in Copenhagen.  Mondays is their planning day and perhaps I was bit in the way but the project is their favourite subject so perhaps they appreciated a willing listener ;)

They are an enthusiastic bunch of amateurs building a real proper space rocket!  They are aiming to launch a team-mate 100km straight up and bring them back down safely.  If I lived nearer I know I’d be sucked in and hopelessly trapped; there are like 20 or 40 of them or something and there’s people there every evening and often daytimes too and people are putting in 40+hours and stuff!  It reminds me of early accounts of Armadillo Aerospace.

Here’s some old prototypes from their “museum corner”:

By far my best score ever!  Over 1000 other Jam entries, and I got Silver for Innovation and 4th for Theme!   Really really so so very very pleased about this! :D

In other news, Notch sells Mojang to Microsoft and goes “back to doing Ludum Dares and small web experiments”!

Full results here. 

As my game scrapes the LD30 game contest entries, I get to gather a lot of stats about who comments on whom.  And, I believe, comments are a good proxy for playings and ratings.

We’re over a week into the 3 week voting time, and already the activity on the site has dropped significantly.

Here’s the comments over time (PDT):

The high peaks are at 12 noon each day; it seems people play and rate in their lunch hours!  Even as the number of comments per hour drops steadily, it still has a local maximum at 12 noon each day. 

I know I play, rate and comment during my lunch breaks … but I’m not in the PDT timezone.

In fact, I have the supposed location of 617 players so far so I could actually do an ok job of determining the local time they comment, and perhaps its not their lunchtimes?  I may do this…

I was expecting the comment rate to pick up again at the weekend, but seemingly not.

The top-10 commented-on games are:

212 Close Your Eyes - nonetheless

195 Sinister - Joe Williamson

187 Heart Star - AdventureIslands

175 Connecting LD30 to the Real World - Will Edwards

161 Chipset-0 - deepnight

153 Waterfly Octus - gillenew

136 Starpiercer - Schrodinger Games

133 NOODLE FEELING - Magdev

128 Super Alien Bro - nerd burglars

128 This Little Piggy… - InfectionTeam

I updated my mosaic script to consider rotations of three tiles as well as straight swaps.  To be honest, its diminishing returns, but the mosaic is one of the prettiest yet:

More on the LD web site :)

Ludum Dare is a really popular game making contest.  Three or so times a year several thousand competitors all over the world wait for the theme to be announced and the contest to start!

Last weekend was the 30th contest (LD30) and the theme was “Connected Worlds”.

The voting wasn’t even close, which is a shame as I was very lukewarm to the theme.  I feared there’d be lots of platform games where you run two levels in parallel, or can swap between levels, etc.

And that’s what 90% of games are, sadly.  I don’t mean they are bad games - many of them are really exceptionally good! - I just mean the theme lent itself to a very literal interpretation.

My interpretation was to try and connect Ludum Darers to the real world instead :)

I recalled that hidden away on the LD website was a map where LDers could record their position on a map.  It was not terribly well known, but there were several hundred player’s latitude and longitude in there.  It was enough to make sure that any map wasn’t completely empty for the first player…

So I made a ‘game’ where you report your position, and then see other contestants near you and can browse LD games on the real world map.

The game aspect is the gamification of rating LD games.  In order to discover the overall LD winner, contestants play each other’s games and rate them.  They have 3 weeks to do this, and then the standings are announced.  And I wanted to encourage that participation, as there’s really games that go unplayed and contestants that don’t play.

I scrape the LD website and, as a proxy for rating others games, I note who has commented on whom.  As well as rating games you can comment on games, and whilst these are distinct they are often done together.

So I draw the map with line art, and use a GL stencil buffer to expose an underlying map where you’ve commented on games or others have commented on your game:

Play it online here!  If you’re not an LD player, you can pretend to be!

The map that you expose is illustrated by me and the usual suspect, who goes by the handle Wombatica on the LD site.

I’ve been overwelmed by the popular appeal and compliments!  I hadn’t expected to get so many appreciative LDers!  I’ve been rated over 150 times already, which is many times the ratings I’ve received on previous contests.  People keep coming back, and people keep checking progress.

People are saying the nicest things too!  Here’s some of the over-the-top ones :)

• WOW. Now that is original. Genius. I’ll be playing it for the next few weeks.
• Hah, what an awesome idea, gamification of Ludum Dare! This it how I’m going to vote all entries from now, keeps voting fun! 
• Thumbs up for innovation/originality!
• super awesome idea, have all my stars!
• Now the fourth wall have been shattered.  thank you.
• Will - really, really good job… This should win I think, just for the sheer cheek of subverting the idea and pointing LD at itself, can see this becoming a favourite interface for LD in the future… very great !
• You made playing games a game, that’s a 5 stars on innovation, no doubt. Also, connecting the LD world with the real world… Another 5 stars for theme!
• Man. This is SO neat! This game wins like all of the LDs. Amazing job!
• I gave you an award on your profile for this game.
• Oh my god this is briljant!

Oh there’s more.  Lots more :)  Now excuse me while I float off ecstatically tired…

Someone got at Guido!  He comes back from some talk with the idea of blessing mypy type checking annotations in Python!

Now those following along may recall my own type-checking library obiwan that also uses annotations.  Its on pypi so you can use it already today!  What are you waiting for?

I’m keen on static checkers, although I prefer static type inference and have ideas along those lines such as Static Single Type Assignment (SSTA).

Fundamentally, though, restricted Python isn’t Python.  We want a dynamic language, and this hits on the limits of static checking.  Obiwan’s runtime checking is a compliment to a static checker and its ability to check external data e.g. tainted JSON input from an API is a major plus too.

What we want is for static checkers, auto-completion in IDEs and runtime checkers like obiwan to all use the same syntax and conventions.

But I don’t like the mypy syntax; its baroque and it even overloads comments (yuck!).  I much prefer obiwan’s style and would like annotations to be supported in-block as well as on the boundaries i.e. declarations.

Consider this mypy example:

 from typing import List, Dict

                def word_count(input: List[str]) -> Dict[str, int]:
                ...
                

Obiwan would instead say:

 def word_count(input: [str]) -> {str: int}:
                ...
                

Which I consider far clearer and pythonic.

My reply to the list is here.

FWIW, I don’t imagine anything will come from this.  There is unlikely to be consensus, and although I’d like a solid PEP that puts annotations into blocks it would so risk slowing down programs that I think it unlikely to be adopted.  So we may be left with a clear message that people are to use mypy or whatever, but no actual solid move forwards.

The newest rec.math Al Zimmermann Programming Contest is a solitaire Scrabble puzzle called ’Alphabet City’.

Wait, what do you mean you’re not entering that programming contest??  Its a really really nice clean problem and it’s addictive as 2048!

To lookup scrabble words quickly, people use a GADDAG.  The GADDAG is a tree data-structure.  Each node represents a character, and has pointers to all the child nodes that continue all possible words.

The key thing is that every rotation of each word is stored in the GADDAG.  To have a GADDAG of the words ALL, BALL and CALL, for each word we add all rotations.  This is LLA@, LA@L, A@LL for ALL, and LLAB@, LAB@L, AB@LL, B@ALL for BALL and so on.  (@ is my choice of ‘start-of-word’ marker; its a good choice because in ASCII its the character before A.  When you have arrays of child nodes [A..Z], this can easily be extended to have a slot pointing at the start-of-word node [@..Z].  And it looks nice enough in the graphs too.)

To speed up Scrabble searches, the prefix of each word is stored reversed which facilitates 'hook’ searches.  To search for all words with one letter then A then another empty then L (?A?L), you start with the first known letter - A - and look for all those with one character in front (a child with a @ child), terminated by an L.

A naive sparse implementation of a GADDAG takes absolutely loads of memory: over a GB is not startling.  Almost all those nodes will be duplicates of other parts of the tree and almost all possible children will exist.  So we really want to get the memory usage down if we want to avoid our program waiting on main memory all the time: bottom cache is typically in the tens of nanoseconds away, whereas main memory is around a hundred nanoseconds away.  Getting the GADDAG small enough to fit into cache, even the bottom level cache (as in slowest and biggest), can mean an order of magnitude speedup!  So its well worth compressing your GADDAG.

The original paper describes compression and gives an example of partial compression.  I will talk these through with graphs:

Here’s the uncompressed tree.  Sorry it takes so much screen space .. it has a lot of nodes in it, which is a point I want to make :)

3 words, 11 rotations and 27 nodes.

Lets start compressing it:

The first thing to note is that, unlike the ALL, BALL, CALL example on NullWords blog, I am storing the terminating characters (the blue nodes) in a separate set off the node.  This is how the prefix LLA is followed by a single node with both B and C in it.

I’m just back from pycon 2014 Sweden.

And all the tweets and commentary will be positive, as they always are. If you want to say something negative its best to not say it at all?

Hmm, not me.  Someone has to give this feedback; we can’t sweep it under the carpet.

As followers of the blog know (thx for the mails!), I’ve been making mosaics of Ludum Dare contest entries.  It started basic, and its got better.  Each of the ‘pixels’ in the Mona Lisa is actually a screenshot of a game!  Here’s how:

We have an target image, for example the Mona Lisa, and we have some large number of small input images which we want to arrange so that, when squinted at from a distance, it approximates the target image.