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).
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:
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).
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.
