mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2017-02-27, 14:19   #1
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×709 Posts
Default March 2017

The new Ibm Ponder This puzzle is out:
https://www.research.ibm.com/haifa/p...March2017.html
R. Gerbicz is offline   Reply With Quote
Old 2017-04-03, 10:57   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×709 Posts
Default

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
File Type: txt ibm03.txt (1.1 KB, 77 views)
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
March 2018 Xyzzy Puzzles 2 2018-04-08 13:45
March 2016 Xyzzy Puzzles 21 2016-06-09 20:26
March 2015 Xyzzy Puzzles 15 2015-04-02 02:19
March Madness 2006 Prime95 Lounge 20 2006-03-21 04:35
gmp 4.2 due in March 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.