Shadows of the Knight - Episode 2 - Puzzle discussion

2 posts were merged into an existing topic: Shadows of the Knight - Episode 1 - Puzzle discussion

Thank you so much!!! I finally could be able to solve this puzzle by reading your comment! First time trying, I could only got all the test but the last one (which is really frustrating anyway :frowning: ) . Then after reading your statement, I could finally understanding what to do.

Guys (or girls), if you guys keep trying to mirror the coordinate through the bisector, it would make you jump back-and-forth around the edge if the the bomb is near the edge. And it would be reallyyyyyyyyyyyy time-consuming, considering that you have to visit the same old window multiple times. (And for me, the result is 5 rounds away from the actual number of rounds needed to solve the final case.)

So, my advice for you is that focus on the statement that Geropy has stated:

For anyone who could not wrap their head around this idea, I would give you a little hint:
Try to approach the edge fast, really, (but not too fast :wink: ).

By doing this, I got 3 spare rounds in the last case. And I really hope you could come up with something like this, or even better!!! ^^

And as always,
Happy Coding!!!

3 Likes

coz the bomb is at 999,999

5 ā‰¤ W constraint is not true in 3rd test, the tower one, since W = 1

1 Like

Fixed, thanks.

I also did the binary search separately for both coordinates with one optimization:
Because you cannot jump off of the grid, sometimes your next jump will not give you any information at all, just adjusts the position of the bat for future jumps. It makes sense to make these zero information jumps for both coordinates with a single two dimensional jump. Which means you have to work on both coordinates ā€œin parallelā€.

3 Likes

Hi, Iā€™m stuck on this problem for a while.
Iā€™m searching for the X and Y coordinates separately and everythingā€™s fine since I pass every test.
But here is my problem : when I submit my code, I get 87% cause I pass every test but the FIRST one.
Of course, there is no way to know why I donā€™t pass this test because of submission mode.
Did any of you have the same problem or any idea of what could be the reason (I know the data in sub mode are slightly different)?

1 Like

Maybe this was the most messy task for me so far. No matter what Iā€™ve tried it didnā€™t work, I had really tough time understanding why. At the end I got the logic with many many little tweaks and trials and errors and still everything is not clear to me why my solution works :slight_smile:

I donā€™t understand, how could people solve this by searching for the X and Y coordinates separately. With two separate binary searches, IDE test cases 07 and 08 use too much jumps and fail for me, so Iā€™m currently stuck at 75% and donā€™t know how to progress without hardcoding some jump-orders for specific testcases.

All I could say is searching separately for X and Y allows to reach 100% both during training and validation phase.

The sole tip I could give you is: if you know your next move wonā€™t learn you anything, then change your search axis.

3 Likes

yo i searching it seperately but still donā€™t have enough run (n)
do u have any advice for me pls?
thanks for reading man

For those who are doing binary search separately for each axis, some tips:

  1. Try to go the next move that mirrors the current move with respect to the lower and upper bounds for the axis. (this cuts the search area by half)
  2. If the next such move is out of bounds, then get back to within the lower and upper bounds (I went into the centre for my code)
  3. When mirroring, there is a tip to reduce the number of runs, by mirroring with an odd distance. Hereā€™s why:
    a) When the result is ā€œwarmerā€ or ā€œcolderā€, the centre row/column can be eliminated instantly
    b) When the result is ā€œsameā€, the centre row/column is the row/column with the bomb.
    Hence, an odd distance mirroring can significantly cut down the number of runs, with a potential for a jackpot ā€œsameā€ result, revealing the row/column instantly.
5 Likes

One of the tests (More Windows) only give you 16 rounds to find the bomb, while map is 49x49 and bomb is located in the position on the picture. Is it possible to find it that fast or is the test broken or something? Iā€™d like to know before I spend more time on this puzzle. Thank you.
image

i confirm that it is possible (we are 1495 to have successed)

moreover i can tell you that it is possible in 15 moves ā€¦

1 Like

Done. Nice and clan moving on multiple axes (not both at the same time though). This puzzle was a bit annoying. But it was worth the effort :v:

Isnā€™t the example wrong, though? On the SAME jump there are 5 blue squares which should represent the possibilities but thereā€™s only one since weā€™re talking eucledian distanceā€¦

no problem with the example . if you have a function distance( x1,y1,x2,y2) :
distance(7,2,5,4) == distance(7,6,5,4)
distance(7,2,6,4) == distance(7,6,6,4)
distance(7,2,7,4) == distance(7,6,7,4)
distance(7,2,8,4) == distance(7,6,8,4)
distance(7,2,9,4) == distance(7,6,9,4)
there are really 5 position with same distance after the jump than before

1 Like

Youā€™re right. Thanks :wink:

In an attempt to get a better understanding of the problem, I tried hard-coding a few windows. In several tests, the window changed every time. OK, fine, it says the bomb could move. But it moved differently every time, and when I updated my solutions to hit where it moved, it went in the very next window.
Now, it doesnā€™t say anything in the description about any limits to the bombā€™s movement, but I guess there must be something; otherwise, if it simply programmed to move when you nail it, no algorithm would ever work.
So, is it that it can only move to places you havenā€™t eliminated? Does the feedback you get remain valid regardless of the bombā€™s movement?
Because if that is the case, I donā€™t see how it makes any difference in the difficulty - you still have to narrow it down to one spot. And if it isnā€™t the case, and it can always move arbitrarily, it is impossible.

The bomb change of spot each time to avoid hard-coding. Its position is computed using your first move and then stay fix until the end of the game. The difficulty increase come from the fact that you donā€™t know the direction of the bomb, but only if you get ā€œwarmerā€.

1 Like