mersenneforum.org January 2021
 Register FAQ Search Today's Posts Mark Forums Read

 2021-01-20, 22:49 #12 dg211   Jun 2016 138 Posts Actually, to check if my code is correct, could someone please check if they are able to verify one of my solutions for a largeish N? For example, for N = 345, I get (317, 335), (60, 169) as a 2 bot placement.
 2021-01-21, 03:02 #13 SmartMersenne   Sep 2017 11810 Posts I have (70, 65) and (13, 5) for N=77.
2021-01-21, 03:11   #14
SmartMersenne

Sep 2017

2·59 Posts

Quote:
 Originally Posted by dg211 Actually, to check if my code is correct, could someone please check if they are able to verify one of my solutions for a largeish N? For example, for N = 345, I get (317, 335), (60, 169) as a 2 bot placement.
If I start with these two bots, I can see the matrix getting full, so

 2021-01-21, 06:08 #15 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24×613 Posts How long does it take for you two to fill the matrix, at 345? (to know if I have any chance, haha).
2021-01-21, 07:21   #16
SmartMersenne

Sep 2017

2×59 Posts

Quote:
 Originally Posted by LaurV How long does it take for you two to fill the matrix, at 345? (to know if I have any chance, haha).
Filling it easy, it just takes a few seconds, but finding a solution requires ~345^4 possibilities to try (345 for each coordinate value).

2021-01-21, 08:01   #17
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2·23·137 Posts

Quote:
 Originally Posted by SmartMersenne Filling it easy, it just takes a few seconds, but finding a solution requires ~345^4 possibilities to try (345 for each coordinate value).
Are you sure it isn't 345^2 * (345^2 - 1) / 2?

Last fiddled with by retina on 2021-01-21 at 08:02

2021-01-21, 08:44   #18
SmartMersenne

Sep 2017

7616 Posts

Quote:
 Originally Posted by retina Are you sure it isn't 345^2 * (345^2 - 1) / 2?
"~" serves for that purpose. I meant O(345^4). But if you want to be literal it is C(345^2, 2), which is equal to your number.

And this is just for N=345. You need to check all N until you find the minimum.

Simply put: the number of possibilities is too large!

2021-01-21, 08:47   #19
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×23×137 Posts

Quote:
 Originally Posted by SmartMersenne Simply put: the number of possibilities is too large!
I think that is the point of the puzzle; to encourage thinking beyond the basic brute force.

2021-01-21, 09:34   #20
SmartMersenne

Sep 2017

2·59 Posts

Quote:
 Originally Posted by retina I think that is the point of the puzzle; to encourage thinking beyond the basic brute force.
I beg to differ. There has been many occations that the IBM puzzles were just solved by brute force. Even the solvers on this site admitted to that many times. This is true especially for the bonuses.

2021-01-21, 10:14   #21
dg211

Jun 2016

11 Posts

Quote:
 Originally Posted by SmartMersenne If I start with these two bots, I can see the matrix getting full, so
Thanks for verifying my solution.

I checked your N=77 solution and it works for me :)

2021-01-22, 06:33   #22
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

231208 Posts

Quote:
 Originally Posted by SmartMersenne Filling it easy, it just takes a few seconds
Thanks. Then, I have some chances... It takes much less for my vaccination bot to fill the board, when I know the solution, for N=345, but it still can be considerable improved, especially for the exit condition.

I use another 6 vectors, beside of the matrix. I am storing the sums by columns and the sums by rows in two vectors, whose right components increment every time when the robot increments a cell, to know when to exit (if a line is full, and I am moving along it, then I am done, this way I avoid a lot of tests, just test if the respective component of the respective vector is 2N, and you are done!), also I am storing the longest line of twos in each line and column in another four vectors - beginning and end of it - so if I am inside of such a line and moving along it, then I move directly to its end, saving a lot of intermediary "cell is 2, move along" steps, however, building the four vectors uses a lot of time at every other type of move, and there I could do it more efficient - for example, I could use 4 matrices and store the jump I have to take in any of the 4 directions, if I hit a 2, this would save even more steps and test, and it could also be build faster - that's some job for the weekend if swmbo doesn't have different plans...- this optimization is precious, because the movement of the robot is very inefficient, it goes up and down and left and right on the same column or row a million of times).

Also, related to searching for a solution, what I could do (and I don't do yet) in a more clever way it would be to use two additional look-up matrices, in the following way: run first the vaccination with no "anti-bots" (B), and store the configuration in a first look-up matrix. Then, place one B in some square which is not zero in the first lookup matrix. Every time I move this B, generate the coverage of the table with this single B and store it in the second lookup matrix. This way, the second B will only move to cells which are covered (i.e. not zero in this stored second table). As I have it now, the "anti-bots" can move to any cell (need as many tests as retina said, about N^4), once the first "anti-bot" is fixed, the second "anti-bot" will move to all positions situated after the first B (seeing the matrix as a row vector), but half of those positions are zero, never reached in the situation with a single bot, so the second bot won't influence that boards in any way! Therefore the second bot B2 needs to be placed only in squares reached by the main V-bot, when a single bot B1 is placed. Also, this single bot B1 should only be placed in squares which are reached by the main V-bot with no anti-bots on the table (otherwise the first antibot B1 has no influence). This would reduce the number of steps, therefore making the search 8 times faster.

Last fiddled with by LaurV on 2021-01-22 at 06:38

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 19 2021-11-22 10:55 Xyzzy Puzzles 11 2021-02-04 14:53 TommyJ Soap Box 2 2021-01-04 19:47 Uncwilly PrimeNet 5 2020-12-07 15:08

All times are UTC. The time now is 14:24.

Tue Nov 30 14:24:38 UTC 2021 up 130 days, 8:53, 0 users, load averages: 1.44, 1.26, 1.14