mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2021-01-22, 07:48   #23
SmartMersenne
 
Sep 2017

32·11 Posts
Default

Quote:
Originally Posted by LaurV View Post
This would reduce the number of steps, therefore making the search 8 times faster.
I don't want to downplay it but 8x improment means instead of

C(345^2, 2) = 7083415800

we will have 885426975 possibilities to try, and this is just for N=345.

Trying one configuration takes a few seconds, but even if it is 0.1 second, it would take 88542698 seconds. Let's say you are lucky and found the answer after trying only 1% of the possible configurations, it takes 885427 seconds, which corresponds to 246 hours or 10 days.
SmartMersenne is offline   Reply With Quote
Old 2021-01-22, 08:22   #24
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

2×41 Posts
Smile

Quote:
Originally Posted by Batalov View Post
bwa-ha-ha-ha-ha!
What a year!
What a problem!
We are starting well the year 2021.Anti vaccine robots!
the second variant of covid19!
What does 2021 have in store for us?
If we still survive until 2022, we will be miraculous. Haha.

2021: [20 + 21, 2021] = [41, 43 * 47]: successive Primes
[4 + 1 , 4 + 3 , 4 + 7] = [5, 7, 11] successive Primes.

And [5,7,11] : [5+7+11]= 23 Prime!

Last fiddled with by Kebbaj on 2021-01-22 at 08:32
Kebbaj is offline   Reply With Quote
Old 2021-01-23, 11:11   #25
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

2·41 Posts
Default

Quote:
Originally Posted by LaurV View Post
It is known.

Hint: the ranges are not contiguous, for example the only square grids that can be filled with no bot are n=1 (trivial), 2, and 5. For N=3, 4, 6, 7, 8, 9, 10, .... you need 1 bot.
to check if my code is correct, could someone please check if my solutions for N=1 To N=10 ?

N=1 no Bot Trivial
2

N=2 no Bot
2,2
2,2

N=3 one Bot: (2,1)
2,2,2
B,2,2
2,2,2


N=4 one Bot: (1,2)
2,B,2,2
2,2,2,2
2,2,2,2
2,2,2,2


N=5 no Bot

2,2,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2

N=6 one Bot: (1,2)
2,B,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2

N=7 one Bot: (5,1)
2,2,2,2,2,2,2
2,2,2,2,2,2,2
2,2,2,2,2,2,2
2,2,2,2,2,2,2
B,2,2,2,2,2,2
2,2,2,2,2,2,2
2,2,2,2,2,2,2

N=8 Two Bots:(2,1) B(2,4)
2,2,2,2,2,2,2,2
B,2,2,B,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2

N=9 Two Bots: B(1,1) B(1,2)
B,2,B,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2

N=10 one Bot: (9,8)
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,B,2,2
2,2,2,2,2,2,2,2,2,2

Last fiddled with by Kebbaj on 2021-01-23 at 11:20
Kebbaj is offline   Reply With Quote
Old 2021-01-25, 14:23   #26
Dieter
 
Oct 2017

2×5×11 Posts
Default

Quote:
Originally Posted by Kebbaj View Post
to check if my code is correct, could someone please check if my solutions for N=1 To N=10 ?

N=1 no Bot Trivial
2

N=2 no Bot
2,2
2,2

N=3 one Bot: (2,1)
2,2,2
B,2,2
2,2,2


N=4 one Bot: (1,2)
2,B,2,2
2,2,2,2
2,2,2,2
2,2,2,2


N=5 no Bot

2,2,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2

N=6 one Bot: (1,2)
2,B,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2
2,2,2,2,2,2

N=7 one Bot: (5,1)
2,2,2,2,2,2,2
2,2,2,2,2,2,2
2,2,2,2,2,2,2
2,2,2,2,2,2,2
B,2,2,2,2,2,2
2,2,2,2,2,2,2
2,2,2,2,2,2,2

N=8 Two Bots:(2,1) B(2,4)
2,2,2,2,2,2,2,2
B,2,2,B,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2

N=9 Two Bots: B(1,1) B(1,2)
B,2,B,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2

N=10 one Bot: (9,8)
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2,2,2
2,2,2,2,2,2,2,B,2,2
2,2,2,2,2,2,2,2,2,2
I guess (and so I have submitted my solutions) that the numbers are not the indices of a matrix, but coordinates (x,y). Both beginning with 0, y positive down.
(0,0) (1,0) . . . (n-1,0)
(0,1)
.
.
(0,n-1) . . . (n-1,n-1)
So for checking I have to exchange and to decrement your indices.
Checking your solution for N=10 with one bot (9,8) => (7,8):
If my code works correctly, I get
2 2 2 2 1 1 2 2 2 2
2 2 2 2 2 2 2 2 2 2
2 2 2 2 1 1 2 2 2 2
2 2 2 1 0 0 1 2 2 2
2 2 1 0 0 0 0 0 1 2
2 1 0 0 0 0 1 1 1 2
2 1 1 0 0 2 2 2 2 2
2 2 2 1 1 2 2 2 2 2
2 2 2 2 1 2 2 B 2 2
2 2 2 2 0 2 2 2 2 2

Seems that you got stuck in a loop.

If my code works correctly, (x,y)=(9,1) or (x,y)=(0,7) are one-bot-solutions for N=10.
Dieter is offline   Reply With Quote
Old 2021-01-25, 14:44   #27
Dieter
 
Oct 2017

2·5·11 Posts
Default

A little more precisely: It‘s the left column (x=0), up.
Dieter is offline   Reply With Quote
Old 2021-01-25, 20:44   #28
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

5216 Posts
Default

Quote:
Originally Posted by Dieter View Post
I guess (and so I have submitted my solutions) that the numbers are not the indices of a matrix, but coordinates (x,y). Both beginning with 0, y positive down.
......

Seems that you got stuck in a loop.

If my code works correctly, (x,y)=(9,1) or (x,y)=(0,7) are one-bot-solutions for N=10.
Thank you very much deater for all your remarks which are very correct. Yesterday I sent my solution for N = 50 and “*.” And i mad a video with no coordinate of course proving that the solutions are visually finshed the matrix.
https://youtu.be/LMi1vPmFOOw

But my solutions were expressed on indices for matrix starting with 1,1. Maybe the web master will consider it wrong. I converted the solutions to a coordinate of an axis starting with 0.0. And send it just now. Thanks!!

You're right my code was stuck in a loop. It was good at first but when I put matrix sum to make output calculation, that's where there was a problem. My code can't gave a solution for the large N. I was stuck, I no longer saw the error!. And I posted the question here. But as perssone did not answer me. I started over from the beginning and found the error.

That's why I thank you twice. For your answer and for the coordinates.!

Last fiddled with by Kebbaj on 2021-01-25 at 21:12
Kebbaj is offline   Reply With Quote
Old 2021-01-25, 21:00   #29
dg211
 
Jun 2016

23 Posts
Default

Awesome video Kebbaj! I was planning to do something similar to see if I could spot any patterns in the solutions, but I haven't had time. From your video it doesn't look like there is an obvious pattern.

The website was updated a day or two ago and no-one so far has got the second bonus question. So far my code has reached N=736 without finding a grid that couldn't be solved with 2 bots. I'm pretty pessimistic about finding a solution by brute force computation, but still not seeing any more elegant way to reason about the problem.
dg211 is offline   Reply With Quote
Old 2021-01-25, 22:22   #30
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

2×41 Posts
Default

Quote:
Originally Posted by dg211 View Post
Awesome video Kebbaj! I was planning to do something similar to see if I could spot any patterns in the solutions, but I haven't had time. From your video it doesn't look like there is an obvious pattern.

The website was updated a day or two ago and no-one so far has got the second bonus question. So far my code has reached N=736 without finding a grid that couldn't be solved with 2 bots. I'm pretty pessimistic about finding a solution by brute force computation, but still not seeing any more elegant way to reason about the problem.
There are some people who make videos for money. But your "superb video" gives me great pleasure. Thanks.

Getting to 736 is a record, I think we have to set records to soften the question.
I started the question too late on January 20th. I had stoped resolving puzzle since June 2020 (Situation Covid19. Mourning, I'm getting old too...).

I was going to stop at *( if is correct we never know) the time remaining and the difficulty. But you made me want to continue. Why not if I advance one point on 736.
Kebbaj is offline   Reply With Quote
Old 2021-01-27, 17:34   #31
dg211
 
Jun 2016

23 Posts
Default

In case it's any help to anyone trying to tackle the second bonus question, I've shared what I think are 2-bot solutions for N up to 762 (excluding N = 50 and N = 100 to avoid spoiling the other parts of the puzzle).

https://drive.google.com/file/d/1oU1...ew?usp=sharing

Maybe someone can spot a pattern which will lead to a more elegant way to approach the problem.

Note that these aren't a complete set of all possible 2-bot solutions, as my search would stop trying new placements for the first bot after it had found at least one solution (but it doesn't stop until after it has tried every possible second bot placement, so some values of N have multiple solutions, all with the same first bot placement).
dg211 is offline   Reply With Quote
Old 2021-01-30, 01:07   #32
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

5216 Posts
Default

Quote:
Originally Posted by dg211 View Post
In case it's any help to anyone trying to tackle the second bonus question, I've shared what I think are 2-bot solutions for N up to 762 (excluding N = 50 and N = 100 to avoid spoiling the other parts of the puzzle).

https://drive.google.com/file/d/1oU1...ew?usp=sharing

Maybe someone can spot a pattern which will lead to a more elegant way to approach the problem.

Note that these aren't a complete set of all possible 2-bot solutions, as my search would stop trying new placements for the first bot after it had found at least one solution (but it doesn't stop until after it has tried every possible second bot placement, so some values of N have multiple solutions, all with the same first bot placement).
I tried to locate something on your base which will lead a way to the solution **, by visualizing the movements.
I did not get there, I hope the web master will extend the question.
It's a great challenge!
Attached Files
File Type: 7z 20210128_101003.7z (2.09 MB, 34 views)
Kebbaj is offline   Reply With Quote
Old 2021-02-04, 20:26   #33
uau
 
Jan 2017

23×11 Posts
Default

Quote:
Originally Posted by uau View Post
I wonder whether an answer to the ** bonus question is actually known by the problem setters or guaranteed to exist?
Solution was published, and shows that they didn't know an answer or have a guarantee it exists...
uau 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 03:36.

Sat Apr 17 03:36:38 UTC 2021 up 8 days, 22:17, 0 users, load averages: 3.01, 2.47, 2.24

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.