6 ms·

The Search for the “perfect” Advent Calendar (involves Python and Processing)

40 points by jgrahamc 8y ago

ginko 8y ago
I was hoping for a bit shuffling approach that elegantly fills the rectangle in some quasi-random order. EDIT: Played around a bit myself, here's a quite pleasing order I came up with: 1 9 17 24 16 8 5 13 21 20 12 4 3 11 19 22 14 6 7 15 23 18 10 2 Python snippet here: https://pastebin.com/XNvjEmxc https://pastebin.com/XNvjEmxc
- camtarn 8y ago
  The funny thing about this one is while it mostly satisfies the constraint of not having consecutive numbers too close, it has a very obvious pattern to it. A nice example of overfitting, perhaps ;) What additional constraint could you add to shake this up? Perhaps a rule that, as well as number adjacency being penalized, adjacent distances between consecutive numbers also get penalized?
  - jgrahamc 8y ago
    It doesn't score very well on my metric. Not badly but not well. [[ 1 9 17 24 16 8] [ 5 13 21 20 12 4] [ 3 11 19 22 14 6] [ 7 15 23 18 10 2]] 400.634917287 Compare with this one found using the 'genetic algorithm': [[ 9 4 18 10 15 20] [16 21 12 1 22 7] [ 2 6 24 5 17 13] [14 8 19 11 23 3]] 386.229085028
    - zimpenfish 8y ago
      Best I've found (with a random shuffle of the numbers every 5M swaps) is (score verified with `advent.py`): [[11 16 8 13 2 20] [18 21 5 24 7 15] [ 3 9 1 19 22 4] [14 23 6 17 10 12]] 382.46224448143795
      - zero_iq 8y ago
        That's a lot of swaps! I played around with a simulated annealing approach in my lunch break which consistently gets down to 383.xx with about 10000 swaps, or 379.xx in 100000 swaps. I've yet to tweak the annealing parameters to see if I can get down to (or beat) the 378 example in the article. It's basically the same as the swap() function in advent.py except you sometimes allow swaps that result in worse scores according to an ever-decreasing probability ("temperature"). The added controlled randomness allows you to break out of local minima at the start and hone in on the local optimum towards the end. EDIT: after a little tweaking of the temperature schedule I got 377.59 after 10K swaps.
        zimpenfish 8y ago
        This is a purely random approach. Currently on 382.08832 after 1.4B swaps. Might have a look at tweaking things later when I'm not at work...
        jgrahamc 8y ago
        Interesting approach. Can you share your code?
        zero_iq 8y ago
        Sure. My best so far is: np.matrix('12 19 6 14 4 9; 8 17 1 24 22 16; 21 3 23 2 20 11; 15 10 5 13 18 7') which has a score of 376.899. This was produced in 20K swaps with the line: best, score = anneal(n=10000) which was then further refined with: best, score = anneal(start_temp=0.2, advent=best, n=10000) where anneal() is defined here: https://pastebin.com/xBVGJfQd https://pastebin.com/xBVGJfQd The score() function is a bit slow at the moment. If I get some time later, I might see if I can speed it up a bit, which will allow for some faster experimentation. EDIT: replaced code with pastebin link to save space in comments
        jgrahamc 8y ago
        Thanks. That's great.
IshKebab 8y ago
This is more or less a discrete version of a 2D low discrepancy sequence, which is often used for choosing different colours. The best known solution is plastic numbers. I expect you could use something like that here rather than brute force. http://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ http://extremelearning.com.au/unreasonable-effectiveness-of-...
- extremelearning 8y ago
  Although using a low discrepancy sequence (eg Halton, Sobol, R2) might be a good starting point, these sequences are designed to maximize the distance between points assuming that the left-and-right edges wrap, as well as the top-and-bottom. As it seems that the OP does not require this condition, I wold presume you get better solutions which involve lots of going to and from the far-left to the far-right, etc.. (Ordered dither matrices might offer another good starting point.)
  - IshKebab 8y ago
    Yeah that's what my "more or less" was referring to...
StavrosK 8y ago
This is good, but it bugs me that the "perfectly ordered" calendar doesn't have the worst score. Maybe consider the calendars tiled on an infinite grid? That way 5 will be one right and one down from 4, instead of four left and one down. Maybe even shift the next line up, so 4 is next to 5...
- jffry 8y ago
  I'll toss my hat in the ring for maximizing the measure instead of minimizing it "Cortex" [[ 6 7 10 11 23 24] [ 5 8 9 12 22 21] [ 4 3 13 16 17 20] [ 1 2 14 15 18 19]] 529.6200384399018 The path traced from 1-24 is rotationally symmetric and folds up in on itself sort of like a Hilbert curve. And now I'm curious how this problem might look for other MxN aside from 6x4
  - StavrosK 8y ago
    I think you nailed it, it seems to me that a Hilbert curve will always have the maximal score.
ihuman 8y ago
The perfect advent calendar already exists https://adventofcode.com/ https://adventofcode.com/
m4lvin 8y ago
Why not leave out "max -" and maximize instead of minimize?
jffry 8y ago
This is a fun problem to play with. Like others, I've been trying the general approach of generating random configurations, then iterating by swapping pairs of elements (each time choosing the pair that yields the best local improvement). Lowest value found, has vertical symmetry (notice how (1,24), (2,23), (3,22), (4,21) and so on are paired) [[14 7 19 12 5 17] [21 9 2 24 22 10] [ 4 16 23 1 3 15] [11 18 6 13 20 8]] 375.923809971073 Highest value found, has rotational symmetry (see how the path from 1-24 is almost like a squished Hilbert curve) [[ 6 7 10 11 23 24] [ 5 8 9 12 22 21] [ 4 3 13 16 17 20] [ 1 2 14 15 18 19]] 529.6200384399018 Code is at https://gist.github.com/jffry/fab43b5b65499c3f513fea701597806b https://gist.github.com/jffry/fab43b5b65499c3f513fea70159780.... Probably full of new-to-Rust mistakes, so please let me know where I've strayed from the light if you're particular about Rust! As mentioned elsewhere I'm very curious about how this generalizes to grid sizes other than 6x4
- zimpenfish 8y ago
  Noticed that my best was almost horizontally symmetrical apart from two slots - except swapping those slots changes the score from 375.99867 to 376.19293. Most perplexing.
zero_iq 8y ago
Just a quick note to say thanks for posting this: I've had great fun exploring it: it's a simple puzzle to understand, yet harder than it first appears, and a low barrier of entry thanks to your posted code. Genuinely interesting seeing the symmetry appearing in the low-scoring solutions, and also an element of friendly competition and shared discovery as we post our scores. Cheers!

40 points by jgrahamc 8y ago

I was hoping for a bit shuffling approach that elegantly fills the rectangle in some quasi-random order. EDIT: Played around a bit myself, here's a quite pleasing order I came up with: 1 9 17 24 16 8 5 13 21 20 12 4 3 11 19 22 14 6 7 15 23 18 10 2 Python snippet here: https://pastebin.com/XNvjEmxc https://pastebin.com/XNvjEmxc

camtarn 8y ago
The funny thing about this one is while it mostly satisfies the constraint of not having consecutive numbers too close, it has a very obvious pattern to it. A nice example of overfitting, perhaps ;) What additional constraint could you add to shake this up? Perhaps a rule that, as well as number adjacency being penalized, adjacent distances between consecutive numbers also get penalized?
- jgrahamc 8y ago
  It doesn't score very well on my metric. Not badly but not well. [[ 1 9 17 24 16 8] [ 5 13 21 20 12 4] [ 3 11 19 22 14 6] [ 7 15 23 18 10 2]] 400.634917287 Compare with this one found using the 'genetic algorithm': [[ 9 4 18 10 15 20] [16 21 12 1 22 7] [ 2 6 24 5 17 13] [14 8 19 11 23 3]] 386.229085028
  - zimpenfish 8y ago
    Best I've found (with a random shuffle of the numbers every 5M swaps) is (score verified with `advent.py`): [[11 16 8 13 2 20] [18 21 5 24 7 15] [ 3 9 1 19 22 4] [14 23 6 17 10 12]] 382.46224448143795
    - zero_iq 8y ago
      That's a lot of swaps! I played around with a simulated annealing approach in my lunch break which consistently gets down to 383.xx with about 10000 swaps, or 379.xx in 100000 swaps. I've yet to tweak the annealing parameters to see if I can get down to (or beat) the 378 example in the article. It's basically the same as the swap() function in advent.py except you sometimes allow swaps that result in worse scores according to an ever-decreasing probability ("temperature"). The added controlled randomness allows you to break out of local minima at the start and hone in on the local optimum towards the end. EDIT: after a little tweaking of the temperature schedule I got 377.59 after 10K swaps.
      - zimpenfish 8y ago
        This is a purely random approach. Currently on 382.08832 after 1.4B swaps. Might have a look at tweaking things later when I'm not at work...
      - jgrahamc 8y ago
        Interesting approach. Can you share your code?
        zero_iq 8y ago
        Sure. My best so far is: np.matrix('12 19 6 14 4 9; 8 17 1 24 22 16; 21 3 23 2 20 11; 15 10 5 13 18 7') which has a score of 376.899. This was produced in 20K swaps with the line: best, score = anneal(n=10000) which was then further refined with: best, score = anneal(start_temp=0.2, advent=best, n=10000) where anneal() is defined here: https://pastebin.com/xBVGJfQd https://pastebin.com/xBVGJfQd The score() function is a bit slow at the moment. If I get some time later, I might see if I can speed it up a bit, which will allow for some faster experimentation. EDIT: replaced code with pastebin link to save space in comments
        jgrahamc 8y ago
        Thanks. That's great.

IshKebab 8y ago

This is more or less a discrete version of a 2D low discrepancy sequence, which is often used for choosing different colours. The best known solution is plastic numbers. I expect you could use something like that here rather than brute force. http://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ http://extremelearning.com.au/unreasonable-effectiveness-of-...

extremelearning 8y ago
Although using a low discrepancy sequence (eg Halton, Sobol, R2) might be a good starting point, these sequences are designed to maximize the distance between points assuming that the left-and-right edges wrap, as well as the top-and-bottom. As it seems that the OP does not require this condition, I wold presume you get better solutions which involve lots of going to and from the far-left to the far-right, etc.. (Ordered dither matrices might offer another good starting point.)
- IshKebab 8y ago
  Yeah that's what my "more or less" was referring to...

StavrosK 8y ago

This is good, but it bugs me that the "perfectly ordered" calendar doesn't have the worst score. Maybe consider the calendars tiled on an infinite grid? That way 5 will be one right and one down from 4, instead of four left and one down. Maybe even shift the next line up, so 4 is next to 5...

jffry 8y ago
I'll toss my hat in the ring for maximizing the measure instead of minimizing it "Cortex" [[ 6 7 10 11 23 24] [ 5 8 9 12 22 21] [ 4 3 13 16 17 20] [ 1 2 14 15 18 19]] 529.6200384399018 The path traced from 1-24 is rotationally symmetric and folds up in on itself sort of like a Hilbert curve. And now I'm curious how this problem might look for other MxN aside from 6x4
- StavrosK 8y ago
  I think you nailed it, it seems to me that a Hilbert curve will always have the maximal score.

ihuman 8y ago

The perfect advent calendar already exists https://adventofcode.com/ https://adventofcode.com/

m4lvin 8y ago

Why not leave out "max -" and maximize instead of minimize?

jffry 8y ago

This is a fun problem to play with. Like others, I've been trying the general approach of generating random configurations, then iterating by swapping pairs of elements (each time choosing the pair that yields the best local improvement). Lowest value found, has vertical symmetry (notice how (1,24), (2,23), (3,22), (4,21) and so on are paired) [[14 7 19 12 5 17] [21 9 2 24 22 10] [ 4 16 23 1 3 15] [11 18 6 13 20 8]] 375.923809971073 Highest value found, has rotational symmetry (see how the path from 1-24 is almost like a squished Hilbert curve) [[ 6 7 10 11 23 24] [ 5 8 9 12 22 21] [ 4 3 13 16 17 20] [ 1 2 14 15 18 19]] 529.6200384399018 Code is at https://gist.github.com/jffry/fab43b5b65499c3f513fea701597806b https://gist.github.com/jffry/fab43b5b65499c3f513fea70159780.... Probably full of new-to-Rust mistakes, so please let me know where I've strayed from the light if you're particular about Rust! As mentioned elsewhere I'm very curious about how this generalizes to grid sizes other than 6x4

zimpenfish 8y ago
Noticed that my best was almost horizontally symmetrical apart from two slots - except swapping those slots changes the score from 375.99867 to 376.19293. Most perplexing.

zero_iq 8y ago

Just a quick note to say thanks for posting this: I've had great fun exploring it: it's a simple puzzle to understand, yet harder than it first appears, and a low barrier of entry thanks to your posted code. Genuinely interesting seeing the symmetry appearing in the low-scoring solutions, and also an element of friendly competition and shared discovery as we post our scores. Cheers!