mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)

 dg211 2021-01-20 22:49

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.

 SmartMersenne 2021-01-21 03:02

I have (70, 65) and (13, 5) for N=77.

 SmartMersenne 2021-01-21 03:11

[QUOTE=dg211;569735]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.[/QUOTE]

If I start with these two bots, I can see the matrix getting full, so :thumbs-up:

 LaurV 2021-01-21 06:08

How long does it take for you two to fill the matrix, at 345?
(to know if I have any chance, haha).

 SmartMersenne 2021-01-21 07:21

[QUOTE=LaurV;569751]How long does it take for you two to fill the matrix, at 345?
(to know if I have any chance, haha).[/QUOTE]

Filling it easy, it just takes a few seconds, but finding a solution requires ~345^4 possibilities to try (345 for each coordinate value).

 retina 2021-01-21 08:01

[QUOTE=SmartMersenne;569755]Filling it easy, it just takes a few seconds, but finding a solution requires ~345^4 possibilities to try (345 for each coordinate value).[/QUOTE]Are you sure it isn't 345^2 * (345^2 - 1) / 2?

 SmartMersenne 2021-01-21 08:44

[QUOTE=retina;569757]Are you sure it isn't 345^2 * (345^2 - 1) / 2?[/QUOTE]

"~" 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!

 retina 2021-01-21 08:47

[QUOTE=SmartMersenne;569761]Simply put: the number of possibilities is too large![/QUOTE]I think that is the point of the puzzle; to encourage thinking beyond the basic brute force.

 SmartMersenne 2021-01-21 09:34

[QUOTE=retina;569762]I think that is the point of the puzzle; to encourage thinking beyond the basic brute force.[/QUOTE]

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.

 dg211 2021-01-21 10:14

[QUOTE=SmartMersenne;569747]If I start with these two bots, I can see the matrix getting full, so :thumbs-up:[/QUOTE]

Thanks for verifying my solution.

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

 LaurV 2021-01-22 06:33

[QUOTE=SmartMersenne;569755]Filling it easy, it just takes a few seconds[/QUOTE]
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.

[SPOILER]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.
[/SPOILER]

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