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 …

All the symmetrical watch faces (and code to generate them)

If you ever look at pictures of clocks and watches in advertising they are set to roughly 10:10 which is meant to be the most attractive (smiling!) position for the hands. They are actually set to 10:09.14 if the hands are truly symmetrical. CC BY 2.0image by Shinji
I wanted to know what all the possible symmetrical watch faces are and so I wrote some code using Processing. Here's the output (there's one watch face missing, 00:00 or 12:00, because it's very boring):



The key to writing this is to figure out the relationship between the hour and minute hands when the watch face is symmetrical. In an hour the minute hand moves through 360° and the hour hand moves through 30° (12 hours are shown on the watch face and 360/12 = 30).
The core loop inside the program is this:   for (int h = 0; h <= 12; h++) {
    float m = (360-30*float(h))*2/13;
    int s = round(60*(m-floor(m)));
    int col = h%6;
    int row = floor(h/6);
    draw_clock((r+f)*(2*col+1), (r+f)*(row*2+1), r, h, floor(m…

The Elevator Button Problem

User interface design is hard. It's hard because people perceive apparently simple things very differently. For example, take a look at this interface to an elevator:


From flickr

Now imagine the following situation. You are on the third floor of this building and you wish to go to the tenth. The elevator is on the fifth floor and there's an indicator that tells you where it is. Which button do you press?

Most people probably say: "press up" since they want to go up. Not long ago I watched someone do the opposite and questioned them about their behavior. They said: "well the elevator is on the fifth floor and I am on the third, so I want it to come down to me".

Much can be learnt about the design of user interfaces by considering this, apparently, simple interface. If you think about the elevator button problem you'll find that something so simple has hidden depths. How do people learn about elevator calling? What's the right amount of informati…