3 ms·

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 1

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.
        zero_iq 8y ago
        Slight improvment to the above: [[12, 19, 6, 14, 4, 9], [ 8, 17, 1, 24, 22, 16], [21, 3, 23, 20, 2, 11], [15, 10, 5, 13, 7, 18]] Score = 376.6144674353488 Found by increasing number of iterations to 100000 Sim.annealing followed by an exhaustive pair-swap search to find the local minimum would have found this more efficiently. Possibly there are some further refinements left -- I haven't run the exhaustive pair search on the above!
        pentestercrab 8y ago
        My best so far, but not using the improvements above, just small tweaks to the code from the blog post: [[ 9 15 4 20 6 12] [18 23 11 1 22 17] [ 7 2 16 24 3 8] [13 21 5 10 19 14]] 376.364049355
        zimpenfish 8y ago
        My Go code, slightly tweaked from the pure random approach, got this one: [[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
  - madcaptenor 8y ago
    The matrix 8 20 15 10 5 17 13 4 22 12 23 1 18 2 24 21 3 7 11 6 16 9 14 19 gets a score 376.9629. This came from starting with a random matrix, trying all possible swaps and taking the best one, and iterating until a local minimum is reached.

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.
      - zero_iq 8y ago
        Slight improvment to the above: [[12, 19, 6, 14, 4, 9], [ 8, 17, 1, 24, 22, 16], [21, 3, 23, 20, 2, 11], [15, 10, 5, 13, 7, 18]] Score = 376.6144674353488 Found by increasing number of iterations to 100000 Sim.annealing followed by an exhaustive pair-swap search to find the local minimum would have found this more efficiently. Possibly there are some further refinements left -- I haven't run the exhaustive pair search on the above!
      - pentestercrab 8y ago
        My best so far, but not using the improvements above, just small tweaks to the code from the blog post: [[ 9 15 4 20 6 12] [18 23 11 1 22 17] [ 7 2 16 24 3 8] [13 21 5 10 19 14]] 376.364049355
        zimpenfish 8y ago
        My Go code, slightly tweaked from the pure random approach, got this one: [[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
- madcaptenor 8y ago
  The matrix 8 20 15 10 5 17 13 4 22 12 23 1 18 2 24 21 3 7 11 6 16 9 14 19 gets a score 376.9629. This came from starting with a random matrix, trying all possible swaps and taking the best one, and iterating until a local minimum is reached.