mersenneforum.org March 2017
 Register FAQ Search Today's Posts Mark Forums Read

 2017-02-27, 14:19 #1 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2×709 Posts March 2017 The new Ibm Ponder This puzzle is out: https://www.research.ibm.com/haifa/p...March2017.html
2017-04-03, 10:57   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×709 Posts

The official solution is at: https://www.research.ibm.com/haifa/p...March2017.html

My sent solutions were:
One possible initial config. of the 64 watches for that we can get no more than 37 watches (and here 37 is reachable):

2 3 3 1 3 1 1 3
1 1 1 1 3 1 1 2
1 1 1 2 1 3 1 3
3 3 2 3 1 3 2 2
2 1 2 1 3 2 3 1
3 1 1 1 2 2 2 2
2 2 1 1 2 3 3 2
2 2 1 3 1 1 1 2

First observe that we need to know only the hour mod 3 on the watches, because the mark on the watch is in those positions (3,6,9,12), where hour mod 3 = 0. Thus it is enough to see what is the hour ahead adjust mod 3 on the columns (on arms), and on rows (on a single octopus). But if we fix the adjust on the columns, then in each row we can select the best adjust in just O(N) time (select that hour mod 3 that gives the most number of zeros mod 3). Hence the total time to get the optimal number of marks here (per matrix) is O(3^N*N^2), in our case N=8. Generate random matrix, and compute the optimal (most) number of marks on the watches, we can get a solution for the puzzle (where the optimal marks is at most 37) roughly in a minute (depends on srand()). See the attached c code!

From the 2nd email:

To get a star:

1 1 1 1 1 1 1 1
1 3 3 3 1 2 2 1
1 3 2 3 2 1 3 1
1 3 1 2 3 3 1 2
1 2 1 3 3 2 2 2
1 2 3 2 1 3 3 2
1 2 3 1 2 1 2 3
1 1 2 2 2 2 3 3

you can get at most 36 marks for this initial configuration. In my search we perturbate the matrix: if you find a "good" matrix (say the maximal number of marks is m) then in each fixed row/column try all 3^N different watches to see if this gives another "good" matrix, if yes (say: the max. number of marks is at most m+1), then save this matrix. With some precomputation we can do this in O(N*9^N) time. At eah step we select the best unexamined matrix.

But in this search you will get many "similar" matrix: observe that we can set the matrix that the first row and column contains only 1, because we can reach this state with some number of adjusts on the rows and columns (the opt. number of marks won't change), furthermore we can sort the rows in a lex. way (the most significant digit is the last term in the row). The above "canonical matrix" comes from such a search, for me it takes roughly 1 minute to find the first such matrix. (after that it is producing matrixes for m=36 marks at a much higher speed).
Attached Files
 ibm03.txt (1.1 KB, 77 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Puzzles 2 2018-04-08 13:45 Xyzzy Puzzles 21 2016-06-09 20:26 Xyzzy Puzzles 15 2015-04-02 02:19 Prime95 Lounge 20 2006-03-21 04:35 Mystwalker GMP-ECM 4 2006-02-01 12:00

All times are UTC. The time now is 16:59.

Sun Nov 29 16:59:10 UTC 2020 up 80 days, 14:10, 4 users, load averages: 1.20, 1.02, 1.01