3 ms·
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
by 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 agoThanks. That's great.
- zero_iq 8y agoSlight 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 agoMy 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 agoMy 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
- zero_iq 8y agoOoh nice! That's the first one I've seen below 376.0 I've gotten close, but not cracked it yet. I was wondering if anyone would break the 376.0 barrier!
- zimpenfish 8y agoI'm wondering if vertical symmetry might be involved (and a way of optimising future efforts) - plotting the journeys of the top three on this post definitely seems to imply that. https://rjp.is/calendars/topthree.png https://rjp.is/calendars/topthree.png Compare and contrast the original set from @jgc's article: https://rjp.is/calendars/originals.png https://rjp.is/calendars/originals.png
- jgrahamc 8y agoThe symmetry thing makes sense, but now I wonder if there's are really "interesting" or not. Does the symmetry spoil the fun of searching or not?
- zero_iq 8y agoThanks for keeping track. Quite fascinating how algorithms employing so much randomization can arrive at such structure and symmetry. Finally got a < 376.0 from my own code using simulated annealing method... 375.998672775885 [[13 20 7 18 5 10] [ 9 15 2 23 12 16] [ 4 22 24 1 3 21] [17 11 6 19 14 8]] ...only to realise it's the same as yours, but with the rows reversed! Rather surprised, but I now wonder if there is only a small number of very-low-scoring solutions. So perhaps this is less of a coincidence than it first appears. I'm now using a much more aggressive temperature drop-off to find decent candidates early, followed by a tempering phase to search for nearby solutions, and a final cool-off to refine the final answer. I'm still using only random pair swaps in Python, so probably wasting a lot of cycles, but I'm still quite surprised how quickly it converges to some pretty decent scores. Beyond that I'm just going to try lots of random starting layouts. I'm interested to see if my method can find any of the other posted solutions or (fingers crossed!) any new ones, but I may need to crunch through a lot more candidates... I will have to translate from Python into something faster to up my game!