January 2021

tgan · 2020-12-31, 08:10

https://www.research.ibm.com/haifa/p...nuary2021.html

Batalov · 2020-12-31, 09:57

Quote:

Unfortunately, the robot (distributing COVID-19 vaccines) was attacked by anti-vaccine bots

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

).

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:

Originally Posted by EdH

Is this one easy or am I doing something wrong?

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:

Originally Posted by LaurV

Easy. To brute force with a silly algorithm, only \(C_{50^2}^2\) cases. Two nested for's.

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:

Originally Posted by LaurV

It is known.

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?

2020-12-31, 08:10	#1
tgan Jul 2015 2⁵ Posts	January 2021 https://www.research.ibm.com/haifa/p...nuary2021.html

2021-01-04, 06:39	#9
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 26E9₁₆ Posts	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). Last fiddled with by LaurV on 2021-01-04 at 06:47*

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

2021-01-02, 16:12	#3
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 7·1,423 Posts	Nice one. And not difficult (search space only about \(\pi\) millions ).

2021-01-03, 01:17	#4
EdH "Ed Hall" Dec 2009 Adirondack Mtns 1000110010110₂ Posts	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. . .

2021-01-03, 12:24	#6
M344587487 "Composite as Heck" Oct 2017 19×47 Posts	It might be easy for a computer to brute force but I'm going to run out of pen ink :P

2021-01-04, 03:25	#8
uau Jan 2017 138₁₀ Posts	I wonder whether an answer to the ** bonus question is actually known by the problem setters or guaranteed to exist?

2021-01-20, 21:46	#11
dg211 Jun 2016 17 Posts	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?