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

 tgan 2020-12-31 08:10

January 2021

[url]https://www.research.ibm.com/haifa/ponderthis/challenges/January2021.html[/url]

 Batalov 2020-12-31 09:57

[QUOTE]Unfortunately, the robot (distributing COVID-19 vaccines) was attacked by anti-vaccine bots[/QUOTE]
bwa-ha-ha-ha-ha!
What a year!
What a problem!

 LaurV 2021-01-02 16:12

Nice one.

And not difficult (search space only about $$\pi$$ millions :razz:).

 EdH 2021-01-03 01:17

Is this one easy or am I doing something wrong? I appear to be able to get 188 pairs of coordinates rather easily for N=50. I think I'll try for the first bonus. . .

 LaurV 2021-01-03 05:07

[QUOTE=EdH;568126]Is this one easy or am I doing something wrong?[/QUOTE]
Easy. To brute force with a silly algorithm, only $$C_{50^2}^2$$ cases. Two nested for's.

 M344587487 2021-01-03 12:24

It might be easy for a computer to brute force but I'm going to run out of pen ink :P

 EdH 2021-01-03 13:22

[QUOTE=LaurV;568148]Easy. To brute force with a silly algorithm, only $$C_{50^2}^2$$ cases. Two nested for's.[/QUOTE]
Darn! I used 4. So, maybe I'll submit a pair and see what they say. . .

 uau 2021-01-04 03:25

I wonder whether an answer to the ** bonus question is actually known by the problem setters or guaranteed to exist?

 LaurV 2021-01-04 06:39

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 (yep, I don't know why they talk about N=6, to confuse us, because, if I understand the problem right, for N=4 you also need a bot, so they should just stay at the example they provided, with N=4). Then you need 2 bots "sometime in the future" as N increases, but again, after it, you may suffice with 1 bot only, for a while, and so on, until 1 bot is not possible anymore. In a certain point further you will need 3 bots. But then, some other higher grids can use only 2 bots for a while (only a guess, by seeing how the grid is filled for low values, I do not have solutions for * and **).

This is shitty in the sense that you can't do a binary search by N, you need to take N up, one by one, and do all combinations for it. You can't rely on symmetry either (the grid is not symmetric, due to initial orientation). You can however make some optimizations, for example, you can skip the squares not touched without any bot, when you put the first bot, and you can skip the squares not touched with one bot when you place the second bot, this reduces the cases to about a half (and doubles the speed), but the downside is that you need to keep evidence (you need anyhow, because you need to know when a walk finishes, i.e. it filled all the board, or it cycles - filling all the board is easy, just a sum of all vaccinations, but cycling, well... you need to keep the direction for every cell that reaches a 2, and if you reach it again with the same direction, then you are cycling).

This is only after playing a bit in Excel. I do not have a solution for the * and **, but I have a nice animation of what the vaccination bot is doing (that bot follows a quite inefficient path, actually, haha, to paraphrase Serge, "what a waste of resources!"), and I have some "gut heuristic" how to set the "anti" bots, which works most of the time (I may post that on YT after the solution is published, the walking of the bot is quite "funny"), and I could find a solution to N=50 "by hand" with it, after few trials in Excel.

Also, due to the modularity of the board, it doesn't matter where you start. You can start anywhere (and shift it accordingly when you send the solution). If we are starting in the middle of the board, the animation looks much better (and it is easier to guess the "heuristic" about placing the X-es (bots).

 uau 2021-01-04 14:16

[QUOTE=LaurV;568275]It is known.[/QUOTE]
How do you know that?

The "hint" doesn't seem to say anything - it's basically what I'd expect to be the case IF some N requires 3 or more bots, but I see no hint there WHY you'd expect some case to require that.

 dg211 2021-01-20 21:46

Has anyone made any progress on the second bonus question?

My initial attempts have been largely computational, without really doing any clever analysis of the problem. I found a heuristic which has worked pretty well so far for finding 2-bot placements while searching a very small section of the problem space. That is giving me values of N up to several hundred with 2-bot solutions (assuming my code is correct - I've submitted a solution but it hasn't been verified yet). But if there is a value of N for which 2 bots won't work, I don't see any purely computation-based way to verify it other than exhaustively testing every possible pair of placements, which would take days for N that large with my current code (which I think is reasonably optimized).

That all leads me to the conclusion that there must be some clever way to analyse the problem mathematically rather than just brute forcing it with compute, but I don't really see any way to get to grips with the problem that way. Has anyone had any luck with a more analytical approach?

 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]

 SmartMersenne 2021-01-22 07:48

[QUOTE=LaurV;569812] This would reduce the number of steps, therefore making the search 8 times faster.[/QUOTE]

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. :bangheadonwall: :sad:

 Kebbaj 2021-01-22 08:22

[QUOTE=Batalov;567813]bwa-ha-ha-ha-ha!
What a year!
What a problem![/QUOTE]

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!

 Kebbaj 2021-01-23 11:11

[QUOTE=LaurV;568275]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.[/QUOTE]
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

 Dieter 2021-01-25 14:23

[QUOTE=Kebbaj;569909]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[/QUOTE]

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 2021-01-25 14:44

A little more precisely: It‘s the left column (x=0), up.

 Kebbaj 2021-01-25 20:44

[QUOTE=Dieter;570080]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.[/QUOTE]

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.
[url]https://youtu.be/LMi1vPmFOOw[/url]

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.!

 dg211 2021-01-25 21:00

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.

 Kebbaj 2021-01-25 22:22

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

 dg211 2021-01-27 17:34

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).

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).

 Kebbaj 2021-01-30 01:07

1 Attachment(s)
[QUOTE=dg211;570266]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).

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).[/QUOTE]
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!

 uau 2021-02-04 20:26

[QUOTE=uau;568256]I wonder whether an answer to the ** bonus question is actually known by the problem setters or guaranteed to exist?[/QUOTE]
Solution was published, and shows that they didn't know an answer or have a guarantee it exists...

 Kebbaj 2021-02-05 01:45

[QUOTE=dg211;569731]Has anyone made any progress on the second bonus question?

My initial attempts have been largely computational, without really doing any clever analysis of the problem. I found a heuristic which has worked pretty well so far for finding 2-bot placements while searching a very small section of the problem space. That is giving me values of N up to several hundred with 2-bot solutions (assuming my code is correct - I've submitted a solution but it hasn't been verified yet). But if there is a value of N for which 2 bots won't work, I don't see any purely computation-based way to verify it other than exhaustively testing every possible pair of placements, which would take days for N that large with my current code (which I think is reasonably optimized).

That all leads me to the conclusion that there must be some clever way to analyse the problem mathematically rather than just brute forcing it with compute, but I don't really see any way to get to grips with the problem that way. Has anyone had any luck with a more analytical approach?[/QUOTE]

I had seen something like that solution: there will always a solution with 2 rebots. A point that is repeated by a modulo, by visualizing the abandoning solutions that you are kind enough to publish. I am not pushing the question any further. I was waiting for a continuation of the question or a definitive answer when the solution will guiven. We had neither.
In French we says "Domage"! I dont know how to say it in English.

 SmartMersenne 2021-02-05 01:59

[QUOTE=Kebbaj;570893]I had seen something like that solution: there will always a solution with 2 rebots. A point that is repeated by a modulo, by visualizing the abandoning solutions that you are kind enough to publish. I am not pushing the question any further. I was waiting for a continuation of the question or a definitive answer when the solution will guiven. We had neither.
In French we says "Domage"! I dont know how to say it in English.[/QUOTE]

What a pity!

Shame!

What the ...?!

 Kebbaj 2021-02-05 08:53

[QUOTE=SmartMersenne;570894]What a pity!

Shame!

What the ...?![/QUOTE]
In any case.
For "**". I think the question was phrased well, but it is the solution that was not. Per what if me or many of us had answered "there is always a solution with 2 antibiot" without any prouven. Believe you that would be accepted. I would not accept it for me.
Opned question like many others.

 Zoozie 2021-02-09 21:29

[QUOTE=dg211;570266]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).

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

Besides looking for solutions with 2 bots in first column, did you use other tricks?
Seems only like 80% of the solutions has 2 bots in first column and finding a solution then takes much longer.

Here are some high solutions with 2 bots in first column:

1000: [(556,0),(569, 0)]
1500: [(484, 0),(852, 0)]
2000: [(892, 0), (1014, 0)]]

The simulation for the 2000*2000 takes almost 3.6M moves to complete.

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