Mythic squares/rectangles

[WraithX]

Originally Posted by R. Gerbicz

Stopped my search, updating all tables:

Some more excellent results! Like Till, I've come up with a better algorithm than what I started with, but it still can't compete with what you have going here.

Would you be willing to share your code and/or algorithm? I'd like to try to extend these tables to other sizes/bases.

[R. Gerbicz]

Originally Posted by WraithX

Would you be willing to share your code and/or algorithm? I'd like to try to extend these tables to other sizes/bases.

OK, here it is, rename it to tiling.c, as it is a pure c code.
some remarks:
1. comment out line 461 if you don't want to see the thread report after each completed search (though in larger searches it is useful to see the progress)
2. it could be possible to improve the memory usage/speed for larger grids
3. before line 518 you could set up various conditions what you want/don't want to search, I've given you 3 examples there, the default is to search every m,n combinations.
4. use line 20,22,25,28 to set your problem/limitations.

[R. Gerbicz]

Originally Posted by R. Gerbicz

some remarks:

adding:
base<=16 should be true! Not tried, it could start for base>16, but from the 2nd grid the results will be poor, because in the grid there will be at most only one digit>=16 due to the grid's storage.

[Till]

Thanks a lot for sharing your code, Robert!


Due to your great numbers, I halfways expected that you found an existing algorithm that matches the problem and works better than a random search (augmented after reading the word "color" in your code). But indeed it is a highly speed- and memory-effective implementation of a random search. A great example of performant software engineering art, I'ld say.


For those interested to understand the implementation:
* b is the currently investigated rectangle
* on each iteration, one "good" b is chosen and undergone a "mutation" in a single location
* good b rectangles are stored in "mygrids" as a list of 64bit ints, each 64bit int holding 16 4-bit values (the program is designed for bases <= 16)
* the hash condition checks if a rectangle b has been tested before
* rectangles are shuffled up and down according to their number of misses of scores <= an expected new record score "rec+1"

[Till]

Found a new 10x10 base 10 top score = 284:

1 1 6 9 1 9 1 8 1 9 
7 7 2 2 5 4 2 5 8 9 
0 2 4 2 3 1 6 1 0 1 
2 0 3 1 1 6 0 2 9 1 
6 5 2 8 1 4 1 3 6 0 
2 6 5 6 1 2 5 7 2 8 
3 7 2 1 7 9 1 1 5 2 
2 2 4 8 1 1 3 7 0 1 
8 4 7 0 4 3 8 2 7 9 
2 1 0 2 2 1 9 4 2 8

[science_man_88]

Originally Posted by Till

Found a new 10x10 base 10 top score = 284:

1 1 6 9 1 9 1 8 1 9 
7 7 2 2 5 4 2 5 8 9 
0 2 4 2 3 1 6 1 0 1 
2 0 3 1 1 6 0 2 9 1 
6 5 2 8 1 4 1 3 6 0 
2 6 5 6 1 2 5 7 2 8 
3 7 2 1 7 9 1 1 5 2 
2 2 4 8 1 1 3 7 0 1 
8 4 7 0 4 3 8 2 7 9 
2 1 0 2 2 1 9 4 2 8

corfirmed by eye.

[Till]

Originally Posted by science_man_88

corfirmed by eye.

One look?

[science_man_88]

Originally Posted by Till

One look?

no just remembered where I was ( 143 in one look I believe), then went back later.

[R. Gerbicz]

Originally Posted by Till

Found a new 10x10 base 10 top score = 284:

1 1 6 9 1 9 1 8 1 9 
7 7 2 2 5 4 2 5 8 9 
0 2 4 2 3 1 6 1 0 1 
2 0 3 1 1 6 0 2 9 1 
6 5 2 8 1 4 1 3 6 0 
2 6 5 6 1 2 5 7 2 8 
3 7 2 1 7 9 1 1 5 2 
2 2 4 8 1 1 3 7 0 1 
8 4 7 0 4 3 8 2 7 9 
2 1 0 2 2 1 9 4 2 8

Congrats! Probably there are still many easy fruits there, spent only roughly 1 day on base=10 (and also 1 day on base=2) using a core i7-6700 and the latest posted code (previous codes were [much] slower).

[science_man_88]

Originally Posted by R. Gerbicz

Congrats! Probably there are still many easy fruits there, spent only roughly 1 day on base=10 (and also 1 day on base=2) using a core i7-6700 and the latest posted code (previous codes were [much] slower).

if my counting is correct an absolute upper bound on 10 by 10 is 647 but that's likely unreachable. edit: okay plugging the math in PARI/GP gives 675 but that's still not 4 digits. 11 by 11 gives 819, 12 by 12 gives 979, and 13 by 13 breaks 1100 but again duplicates will.lower these.

[Till]

Originally Posted by R. Gerbicz

Congrats! Probably there are still many easy fruits there, spent only roughly 1 day on base=10 (and also 1 day on base=2) using a core i7-6700 and the latest posted code (previous codes were [much] slower).

Yes, it's quite easy to find better scores. Found several other small improvements but will post them all together.


On 10x10 base 10 I did a run over ~8 hours though because I was on a birthday party. My computer is a pretty old 7-2630QM.


I have a small improvement proposal: Instead of just collecting the number of misses, one could collect the scores actually missed and derive the next digit to place somewhere from that. So if your missing scores are 221, 222, 223 then you get a 7/9 chance that a "2" is placed, which will be a good choice. The collection can be stopped if the number of misses found is > your limit variable.