Skip to main content

The search for the "perfect" Advent Calendar (involves Python and Processing)

I grew up with Advent Calendars, and they are very common in the UK. Shops across the country sell calendars with typically 24 doors on them, one for each day from December 1 to December 24. Behind each door is a small gift (usually chocolate or something similarly sweet and edible).


The numbers on the doors of the calendar are usually arranged somewhat haphazardly. Part of the fun each day is finding the next door to open. It's the search for the chocolate that makes the calendars enjoyable. Here's an example layout from an Advent Calendar that I bought in Paul in London:


This is an example of a very common 6x4 (and sometimes 4x6) layout for calendars. In this blog I'm going to develop code to find "pleasing" Advent Calendar layouts in the 6x4 shape. But first, here's a little animation of the Paul calendar in action. What makes it "pleasing" is that the numbers don't cluster together (mostly).


So, that calendar isn't bad but it would be nice to generate a calendar where the numbers are spread about such that from day to day you have to hunt for the next number. The number you are searching for won't be near yesterday's number and if you see a number close to it then you are likely in the wrong place. That latter restriction adds a lot of pleasure because we are so used to seeing consecutive numbers that our brains instantly start looking nearby.

To do that I broke out the Python (I'm no Python expert so I appreciate Pythonistas who write in with improvements to my code).

First I needed a way of measuring whether an Advent Calendar is pleasing. I settled upon the following score. If you're not into mathematics it might look formidable but the basic idea is that if two numbers are close together (e.g. 1 and 3) then they need to be far apart when put on the calendar.


And we want to find a calendar with the lowest score possible (the score gets bigger when numbers that are near each other (e.g. 2 and 5) are placed close to each other on the calendar). I assume the calendar is laid out with coordinates 0 through 5 for the horizontal and 0 through 3 for the vertical and (xi, yi) are the coordinates of the number i where it appears on the calendar. For example, in the Paul calendar the number 24 appears at (x24, y24) which is (4, 2).

With that implemented in Python I can get a score for the Paul calendar above: it's 419.923652806. Now let's try a really boring calendar like this. It's not fun at all:


And it has a score of 474.491619783. But if you really want to have no fun at all you make this Advent Calendar which has a score of 504.143329596. It's horribly regular and boring.


So, to find the "perfect" calendar I wrote some more Python code to generate random calendars and score them. After running 1 million calendars this is the one that's the most pleasing and has a low score of 386.229085028.


I used brute force and randomness to find a pleasing calendar but there are likely other interesting techniques for laying the calendar out. I would love to hear from readers with ideas.

In the mean time feel free to steal my "Perfect Advent Calendar Layout" for your own creations!

 

Animations


The animations were made with a small program written in Processing that outputs 25 frames as separate, numbers PNG files. I combinted these into a GIF using ffmpeg.

Generate the palette:

ffmpeg -i advent-1-7-13-19-2-8-14-20-3-9-15-21-4-10-16-22-5-11-17-23-6-12-18-24-4d.png -vf palettegen palette.png

Combine the frames into a GIF:

ffmpeg -v warning -i advent-1-7-13-19-2-8-14-20-3-9-15-21-4-10-16-22-5-11-17-23-6-12-18-24-4d.png -i palette.png -lavfi "paletteuse,setpts=20*PTS" -y advent-1-7-13-19-2-8-14-20-3-9-15-21-4-10-16-22-5-11-17-23-6-12-18-24.gif

 

Code


The code can be found in the advent repository on my GitHub. advent.py is the program for scoring and generating advent calendars. advent.py is for scoring and generating calendars. advent.pde is the Processing code to animate found calendars.

 

How did Haribo do?


The real Advent Calendar at the top of this blog is from Haribo and is in the 6x4 layout and so I can feed it to my code and score it: 411.18428542. Hmm. Not so great. Here's that calendar animated:


A lot of the early numbers are close together spoiling the score and the fun of the search.

Update


A reader suggested a genetic algorithm approach and so I've added a function called swap() that generates a random calendar and then swaps random elements trying to find a better layout. It works very nicely.

Here's a layout with score 378.277000309 found using that function:

Others have found even better layouts. See the comments below and this Hacker News thread.







Comments

palavrov said…
This search seems good for evolutionary algorithm i.e. you can start with random combination, then randomly swap two cells and if it scores better continue with the new set. Instead of randomly swapping you could swap closest dates with priority, etc
David said…
I managed to get 376.789 using a biased random-key genetic algorithm (BRKGA).

Objective: 376.789
12 19 10 17 8 15
5 23 3 2 22 6
14 21 1 24 13 20
7 16 9 18 4 11

Code at https://github.com/eisenstatdavid/advent
David said…
Slight improvement by halving the number of chromosomes and decoding symmetrically:

Objective: 376.688
9 14 7 18 11 16
20 4 24 1 21 5
12 22 2 23 3 13
17 6 15 10 19 8

Code in the same repo as above, on the symmetric branch.
Thanks David and palarov. I don't know much about evolutionary/genetic algorithms and this is fascinating and given me lots of things to Google!
zimpenfish said…
[[17 11 6 19 14 8]
[ 4 22 24 1 3 21]
[ 9 15 2 23 12 16]
[13 20 7 18 5 10]]
375.998672775885

Go code, only keeping swaps if they lower the score, nothing else.
Dave O said…
Here's an improved one found via simulated annealing:

Objective: 375.9986727758851
11 18 6 13 20 8
4 16 23 1 3 15
21 9 2 24 22 10
14 7 19 12 5 17
Dave O said…
Small improvement via simulated annealing:

Objective: 375.92380997107347
14 7 19 12 5 17
21 9 2 24 22 10
4 16 23 1 3 15
11 18 6 13 20 8

Same score for:
11 18 6 13 20 8
4 16 23 1 3 15
21 9 2 24 22 10
14 7 19 12 5 17
(I'm guessing it is symmetrical to the other one, but haven't confirmed)

Popular posts from this blog

Your last name contains invalid characters

My last name is "Graham-Cumming". But here's a typical form response when I enter it:


Does the web site have any idea how rude it is to claim that my last name contains invalid characters? Clearly not. What they actually meant is: our web site will not accept that hyphen in your last name. But do they say that? No, of course not. They decide to shove in my face the claim that there's something wrong with my name.

There's nothing wrong with my name, just as there's nothing wrong with someone whose first name is Jean-Marie, or someone whose last name is O'Reilly.

What is wrong is that way this is being handled. If the system can't cope with non-letters and spaces it needs to say that. How about the following error message:

Our system is unable to process last names that contain non-letters, please replace them with spaces.

Don't blame me for having a last name that your system doesn't like, whose fault is that? Saying "Your last name …

Importing an existing SSL key/certificate pair into a Java keystore

I'm writing this blog post in case anyone else has to Google that. In Java 6 keytool has been improved so that it now becomes possible to import an existing key and certificate (say one you generated outside of the Java world) into a keystore.

You need: Java 6 and openssl.

1. Suppose you have a certificate and key in PEM format. The key is named host.key and the certificate host.crt.

2. The first step is to convert them into a single PKCS12 file using the command: openssl pkcs12 -export -in host.crt -inkey host.key > host.p12. You will be asked for various passwords (the password to access the key (if set) and then the password for the PKCS12 file being created).

3. Then import the PKCS12 file into a keystore using the command: keytool -importkeystore -srckeystore host.p12 -destkeystore host.jks -srcstoretype pkcs12. You now have a keystore named host.jks containing the certificate/key you need.

For the sake of completeness here's the output of a full session I performe…

More fun with toys: the Ikea LILLABO Train Set

As further proof of my unsuitability to be a child minder (see previous post) I found myself playing with an Ikea LILLABO 20-piece basic set train.


The train set has 16 pieces of track (12 curves, two straight pieces and a two part bridge) and 4 pieces of train. What I wondered was... how many possible looping train tracks can be made using all 16 pieces?

The answer is... 9. Here's a picture of the 9 different layouts.


The picture was generated using a little program written in Processing. The bridge is red, the straight pieces are green and the curves are blue or magenta depending on whether they are oriented clockwise or anticlockwise. The curved pieces can be oriented in either way.

To generate those layouts I wrote a small program which runs through all the possible layouts and determines which form a loop. The program eliminates duplicate layouts (such as those that are mirror images of each other).

It outputs a list of instructions for building loops. These instructions con…