The bomb change of spot each time to avoid hard-coding.
Hmm. It also says, “The tests provided are similar to the validation tests used to compute the final score but remain different.” That’s how most puzzles prevent hard-coding.
Its position is computed using your first move and then stay fix until the end of the game.
Maybe something like that, but not exactly. I hardcoded up to 3 sets of coordinates based on how it moved, and looped those 3, and it moved the bomb to a 4th position. So it isn’t just the first move. I suspect it looks for any hard-coded coordinates and avoids them.
The difficulty increase come from the fact that you don’t know the direction of the bomb, but only if you get “warmer”.
Well, that is the difficulty increase between the first puzzle and the second. I understood that the moving bomb was to make the second puzzle (this one) more challenging than it would be otherwise.
I find the wording confusing:
For some tests, the bombs’ location may change from one execution to the other : the goal is to help you find the best algorithm in all cases.
That implies that an algorithm that solves a non-moving bomb won’t work on a moving one.
From what others are saying, it sounds like you can simply solve it using binary search, the way it seems. The fact that the bomb may move sounds irrelevant.
I actually meant to ask only one specific question:
When the bomb moves, does it respect the previous feedback of COLDER, WARMER and SAME? Or could it move the bomb somewhere that makes one of them no longer true? I am guessing it does respect the previous messages, since debug mode actually shows me visually what areas are left. But I wanted to ask around before working it out!
Thanks!
You don’t understand. The bomb position is fixed for one entire test. If you replay the same test, the bomb could be in another place, but it doesn’t move during the game.
You don’t understand. The bomb position is fixed for one entire test. If you replay the same test, the bomb could be in another place, but it doesn’t move during the game.
Ah, I see. That does answer my question. Thank you!
If you do the dimensions simultaneously, you have to deal with Pythagoras, and you’ll rarely get SAME.
If you do the dimensions separately, there’s no reason you need to make set-up jumps separately for the two dimensions.
It is then possible to guarantee yourself two halving jumps per dimension for each reset. Just enough for test 8.
I figured out the algorithm on paper, sitting in my car waiting for my daughter at gymnastics. That wasn’t so difficult. Turning that list of instructions into C++ took some struggle, but… well, I did it!
Solved it!
Not so difficult after all. I simply used binary search on x and y separately until I go out of the grid, at which point I make a useless move to get back in the area of interest.
I also did a tiny optimization to finish last test with 3 remaining jumps (though not a really robust one).
Good luck!
Props to everyone who tackled this one with centroids and polygons, but I’m pretty sure that’s the hard way. I did a separated x and y binary search, and I am happy to confirm it is able to solve every validator with moves to spare.
If you find you’re running out of jumps on the big levels, look closely at what your search is doing when jumping to and from the edges of the building. Maybe there’s a way to set up Bats so that his next jump will eliminate a larger part of the unsearched area. Maybe even bisect it…
Tried and failed to solve it using polygons. It was very hard for me to compute best-cut… So I tried it solving both axis separately
My solution is based on 3 steps:
step - jump so that you split searched area in half. Do not forget, you cannot cross board boundaries - 50% score
step - if jump computed in step 1 won’t improve your solution (new centroid outside actual search area) - jump either to start or end of actual search area/interval - 87% score
step - if you see repeating steps around boundaries (0/width/height) try to search just around the boundaries - 100% score with huge reserve
Hi all,
my stategy is to list all the possible nodes from the beginning
and then remove the nodes where the bomb can’t be. I confirm that
at the beginning, moving batman to the opposit of the centroid is a good
idea because it removes half of the buliding in one round. After that I
usually move to the centroid of the remaining nodes and it works well.
This works well up to test 6. After that (7 and 8) it doesn’t work because
making the list of all possible nodes is to slow (several seconds) compared
to what is expected (<150ms). One can easily imagine that for example
with the case of 8000x8000, the list will be quite long…64Millions of terms
I’m looking for a new strategy taking into account what is said in this forum
about working on x and y separately.
define a rectangular search window of the size of the board
Mesh the search window to have a reasonable number of points (~300, python is slow)
Check if each point is compatible with the results obtained during the previous moves (closer to point A than to point B, equidistant between A and B). Keep only the valid points.
Compute the new search window from the valid points.
Compute the centroid of the known valid points
Move Batman to the known valid point closest to batman central symmetry to the centroid (If you aim for the centroid you are not discriminating enough points).
Why i get WARMER , while it’s COLDER
d = distance(0,6,4,10)
d2 = distance(0,5,4,10)
d = 5.656854249492381 d2 = 6.4031242374328485
I get WARMER with coordinate (0,5) while (0,6) is nearest of (4,10)
So i suppose the optimal solution is one where you make your polygon of n sides from ideal slices using 2d cartesian geometry and bresenham’s and keep slicing down till you only have 1 point left…
but the binary search on individual dimensions slicing down rectangles is so much easier.
it just feels icky to feel like i lucked out on some of the bigger test cases.
I used dichotomy to solve one axis and then the other. Splitting in half makes you waste a lot of moves if the target is close to the edge, because if you get COLDER, you cannot split the remaining zone anymore and you basically lose a move. My strategy to mitigate those scenario was to split unevenly (i used 1/4 - 3/4) if you’re against an edge, so if you “lose a move” you at least reduced the zone more, and take much less moves, at a small cost, because if the bomb is in the 3/4 zone, you can immediately start splitting equally again.
Hey,
In order to debug your code, I recommand you to decompose it as much as possible.
In codingame you have a few errors indicated, but the best option stay to create your own debug’s error.
Just put as much as possible error lines.
I see you’re working with VB.Net, this is how you can create a error lines : Console.Error.WriteLine("Debug messages...")
For example put some before and after a condition or loop :
Console.Error.WriteLine("I'm before my condition.")
if(a>b){
Console.Error.WriteLine("My condition is true.")
Console.WriteLine("A is bigger than B");
} else {
Console.Error.WriteLine("My condition is false.")
}
Console.Error.WriteLine("I'm after my condition.")
When you find where is the problem, it’s more easy to search for a solution
You’ll want to use the same idea behind the binary search - you want to come as close as possible to cutting the problem in half with each attempt. I’ll walk you through the logic on the first test case A Lot of Jumps.
Unfortunately, I can’t post images, so you’ll have to follow along in text.
I’m not sure if it’s the same variables for everyone, so here are mine:
W:5 H:16 X0:1 Y0:5 N:80
The bomb is located at (4,10).
There are 80 windows and 80 turns. Technically you could solve this one via brute force, but let’s be a bit more efficient.
We definitely won’t need 80 turns. The building has an even number of floors (rows) and an odd number of windows per floor (columns) so we’re going to eliminate 8 floors because slicing vertically risks only eliminating 2/5 (40%) of the windows instead of a guaranteed 8/16 (50%). We’re down to 40 windows remaining.
Our first move is to (1, 10) giving a reply of WARMER - we can now eliminate the top half of the building. 20 windows remain.
We’re going to move again to eliminate more floors for another guaranteed 50%. Our next move is to (1, 13) giving a reply of COOLER. 10 windows remain
We can’t slice it perfectly in half again without guessing a window we’ve already eliminated. We could choose that window, or we could choose one that gets us as close to 50% while still being a viable option. I’ll opt for the one that’s a viable option and we’ll go with (0,8) to try to eliminate as close to half as we can. This gives us a response of WARMER and we’re down to 6 windows.
Our next move to slice it in half will be (4,10), and that’s the bomb! Solved in 4 windows.
Can you think of a better strategy? This example didn’t make good use of the option for the distances to be the same.
I feel like there’s an issue with this puzzle, I got a wierd case but with the bomb in (22,22), I had batman on (22,20) sent him on (20,22) and got the answer “Warmer” but it should have been “same” since he is 2 windows off in a straight line both times. Or is same only in the case if both jumps are in the same line/column ?
