[Community Puzzle] Escaping the cat

Puzzles
#1

https://www.codingame.com/training/medium/escaping-the-cat

Send your feedback or ask for help here!

Created by @igolus,validated by @Schneewittchen,@CopperFr and @Illedan.
If you have any issues, feel free to ping them.

1 Like
#2

Hi,
Could anybody give me a hint? I passed all the tests but the last one. Basically my mouse looks for the pool edge from the line with direction mouse cat, and checks all the time if he can make it faster to the edge than the cat which go through the shortest arc length given by the chord cat, mouse, pool edge. If it can make it faster then, it fixes that location and just move towards that direction. I guess my mouse trajectory is not good enough (the cat catch me within 80 pixel radius). Is this a good approach? or shall i use an smarter method?

#3

The last test is very close, no margin of error basically. Are you using the radius + 1 as the mouse destination ? Because reaching the border isn’t enough, you need one more step.

2 Likes
#4

Hi thanks for your answer. I have tried that but without succeed yet. The cat catches me 3 pixels away from the destination. Tricky, tricky.

#5

Hi Everyone,

In this puzzle I seem to be experiencing some kind of bug. In the beginning I could play testcases and see how my mouse would swim for its life in 350 turns. After a few attempts, for some reason in the second test case after have the problem that when I click “Play Testcase”, the animation already in the beginning shows that I will have only 43 steps. After 43 steps (when the mouse is in the center of the pool) I get a “timeout” message. Does anyone have an idea how to get the 350 turns back?

Thanks and cheers,
Patrick

#6

It seems to me that this happens when you stop the output prints while continuing to read the inputs.
these are the output prints that increment the lap counter.
Is this your case?

#7

The game has crashed. Please contact the author and enclose the following error:

java.lang.StringIndexOutOfBoundsException: begin 0, end 10, length 9
at java.base/java.lang.String.checkBoundsBeginEnd(String.java:3319)
at java.base/java.lang.String.substring(String.java:1874)
at com.codingame.game.Referee.getMessage(Referee.java:290)
at com.codingame.game.Referee.gameTurn(Referee.java:144)
at com.codingame.gameengine.core.GameManager.start(GameManager.java:122)
at com.codingame.gameengine.core.RefereeMain.start(RefereeMain.java:67)
at com.codingame.gameengine.core.RefereeMain.main(RefereeMain.java:50)

#8

Same for me, and I wonder how the mouse can escape in last test case

#9

I finally made it. For me it worked to set a radius bigger than 500 when calculating the arclength and when i compare time needed to reach the pool for the cat and for the mouse i obligued the mouse to be a little bit faster (like 8/ cat_speed faster).

#10

ok thanks for the proof of concept :slight_smile: but the more I experiment trigonometric functions (math or numpy), less I understand. Though with mathematic operators on a written paper or scientific calculator, all is clear :o)

#11

Hi Zener,

Thanks for your feedback. As far as I can see, I’m writing output prints every time I read the input prints. Also, the animation starts out already with giving me only 43 steps. I’m a bit puzzled.

Cheers,
Patrick

#12

@igolus could you please check?

#13

Hi everybody.
I’m stuck on one logical passage.
My strategy is as follows:

  • whenever the mouse is at (0, 0) I simply move it 10 pixels opposite the cat’s position
  • otherwise I compute the landing point as the intersection of the line that connects (0, 0) to the mouse’s position AND the circle edge, and I also compute the number of turns it takes the mouse to reach it:
    • if the arc length between the cat’s position and the landing point is greater than (cat’s speed * turns) + 81, then I move the mouse 10 pixels towards the landing point
    • otherwise I would move the mouse 10 pixels towards the nearest point on the circumference with an arc distance of (cat’s speed * turns)+81: I’m stuck here because I cannot find a formula to find this point

Does anybody have a hint for me?

Thanks!
BG

#14

There is a circle centered on (0, 0) inside which the mouse can navigate faster than the cat angle wise (of course you need to find its radius :slight_smile:) So a good strategy is to get inside this circle, aim for the point on this circle opposite to the cat, then dash to the border.

5 Likes
#15

That’s a definitely good point!
But it’s not that simple.
The cat does not move while the mouse moves towards the center on the same line.
When the mouse reaches the circle where he can move faster than the cat angle wise, in order to reach for the point opposite to the cat he has two options:

  • he travels around the inner circle to the diametrally opposite point
  • he goes straight through the center to the diametrally opposite point

The first option has two downsides: 1) as soon as the mouse strays from the straight line connecting the center with the cat, the cat moves in the same direction, narrowing the advantage; 2) the path to the opposite side is longer

So let’s say we move across the center: as soon as the mouse crosses the center, the cat will move in either direction.
At maximum 10 pixels/turn, it will take the mouse at least 50 turns to reach the shore: if the cat moves at a speed higher than 31,4 pixels/turn, the mouse will have no chance whatsoever.

But your answer gave me an idea: I should focus on angles rather than arc lengths

Thanks!
BG

#16

Nice intuition, indeed, based on observation, without knowing the cat’s real behavior. It worked for me :slight_smile:

#17

See here : https://www.youtube.com/watch?v=vF_-ob9vseM

8 Likes
#18

My 4th version of idea finally worked.
The mouse go from the center, and zigzag in the opposite direction from the cat. It looks really fun !
Nice puzzle, really interesting. Thanks!

3 Likes
#19

Nice puzzle but the margin for escape is a bit vague.

I built a function f that evaluates if I have a lead or not depending on the angle I chose.
The function returns a number that is < 0 if I reach the bank before the cat, 0 if we meet exactly when I reach the bank and > 0 if he gets me.

So basically there’s a first step where I try to decrease my f value and as soon as I find x and y that guarantee a negative f value, I always print those x and y.
On the paper the problem is solved except that… it doesn’t work like this.
Even if the referee clearly shows me arriving before the cat, he still gets me if the margin is too small.

So I had to state that the f value had to be < -2.5 before I enter step 2, and it worked like this but it feels a bit random.
Edit: my bad, I just noticed that “The mouse is captured by the cat if the distance between mouse and cat is strictly less than 80 and then you lose the game.”
I added this in my function f and now it’s almost perfect, as soon as the f value reaches -.1 I can run to the bank and escape the cat.

#20

For a long time I thought about the problem. At first, the mouse tried to escape by looping and using complex trigonometric formulas. But the hungry cat always caught her :cry:. Then the mouse came up with a very simple idea and finally ran away from the cat! A difficult day for a mouse.
Thanks to the author for the job!

1 Like