mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2021-01-20, 22:49   #12
dg211
 
Jun 2016

23 Posts
Default

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.
dg211 is offline   Reply With Quote
Old 2021-01-21, 03:02   #13
SmartMersenne
 
Sep 2017

2·72 Posts
Default

I have (70, 65) and (13, 5) for N=77.
SmartMersenne is offline   Reply With Quote
Old 2021-01-21, 03:11   #14
SmartMersenne
 
Sep 2017

2·72 Posts
Thumbs up

Quote:
Originally Posted by dg211 View Post
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
SmartMersenne is offline   Reply With Quote
Old 2021-01-21, 06:08   #15
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×7×53 Posts
Default

How long does it take for you two to fill the matrix, at 345?
(to know if I have any chance, haha).
LaurV is offline   Reply With Quote
Old 2021-01-21, 07:21   #16
SmartMersenne
 
Sep 2017

6216 Posts
Default

Quote:
Originally Posted by LaurV View Post
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).
SmartMersenne is offline   Reply With Quote
Old 2021-01-21, 08:01   #17
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

136778 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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
retina is online now   Reply With Quote
Old 2021-01-21, 08:44   #18
SmartMersenne
 
Sep 2017

2·72 Posts
Default

Quote:
Originally Posted by retina View Post
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!
SmartMersenne is offline   Reply With Quote
Old 2021-01-21, 08:47   #19
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,079 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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.
retina is online now   Reply With Quote
Old 2021-01-21, 09:34   #20
SmartMersenne
 
Sep 2017

2·72 Posts
Default

Quote:
Originally Posted by retina View Post
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.
SmartMersenne is offline   Reply With Quote
Old 2021-01-21, 10:14   #21
dg211
 
Jun 2016

810 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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 :)
dg211 is offline   Reply With Quote
Old 2021-01-22, 06:33   #22
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×7×53 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
February 2021 Xyzzy Puzzles 11 2021-02-04 14:53
Space plans for 2021. TommyJ Soap Box 2 2021-01-04 19:47
2021 project goals gd_barnes Conjectures 'R Us 2 2021-01-03 11:39
Is January 1, 2021 the time to see the end of FTC LL's? Uncwilly PrimeNet 5 2020-12-07 15:08

All times are UTC. The time now is 09:50.

Wed Mar 3 09:50:21 UTC 2021 up 90 days, 6:01, 0 users, load averages: 1.74, 1.59, 1.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.