[Community Puzzle] A child's play

Puzzles
#1

https://www.codingame.com/training/medium/a-childs-play

Send your feedback or ask for help here!

Created by @Magicien-d-oz,validated by @bbb000bbbyyy,@dbdr and @JBM.
If you have any issues, feel free to ping them.

#2

the code of my progress has disapeared, what happened?

#3

it most likely happened because the contribution has been updated. This is a bug on our side. I’ll check with the devs where we are on the resolution. Meanwhile, you can access your submit history by clicking on “results” on the left menu and then the “history” tab.

#4

Hello everyone,

Anyone had a problem with validator test 5 ?
I pass everything else (tests + validators).
Or maybe can i have what is tested specifically in this test more than in others ?
(i’m pretty sure it’s not because of the time taken because i use the trick with a “path” built until we reach the start position).

Thx

#5

Hi Pox,

I had the same issue and it took me a while to figure out that you may not always reach the start position. This assumption was at least the problem for me to fail at Validator 5 while passing all other tests…

Best regards
Masshood

1 Like
#6

I will look at it more closely.
Thank you

#7

I would suggest a test 6, where the map path is a P and the robot make a loop but does not go back to initial position, such as:
##########
#. . . . . . . . #
#. ######. #
#. ######. #
#. . . . . . . . #
#. ########
#o########
##########

6 Likes
#8

Plot twist: I tried adding it, but even the author’s code won’t get it right.

This puzzle has already been “solved” by 331 persons now, it’s a bit late to invalidate all of their solutions.

I’ve updated the puzzle statement to subtly hint the robot is already on the loop path; you’re welcome to submit a harder version of it if you’re so inclined. (by harder I mean: not initially being on the path won’t be enough, add another twist please).

4 Likes
#9

Can someone tell me if I am on the right track, test 1 is looking for (7 1) but my robot never ends up there. It keeps following this loop

...#........
...........#
............
............
..#↑........
..........#.
Turning E
Turn: 986 (3, 1)
...#........
...→.......#
............
............
..#.........
..........#.
Turning S
Turn: 985 (10, 1)
...#........
..........↓#
............
............
..#.........
..........#.
Turning W
Turn: 984 (10, 4)
...#........
...........#
............
............
..#.......←.
..........#.
Turning N
Turn: 983 (3, 4)
...#........
...........#
............
............
..#↑........
..........#.
Turning E
Turn: 982 (3, 1)
...#........
...→.......#
............
............
..#.........
..........#.

Fixed it - i thought the robot continued forward until it hit a wall but it only moves 1 square at a time.

1 Like
#10

Now I am failing all tests from 3 onwards due to timeouts. I am using SplFixedArrays to speed things up but still no luck. Is this challenge possible in php?

2 Likes
#11

In one word : yes
I solved it in php and without SplFixedArrays.
Tips : try to look the robots movements …

1 Like
#12

Hello,

Masshood was right, for the 5th validator, it seems you never reach the initial position (it can be seen like the example of docbohanh).
The fact is with my algorithm, i stop stepping only if i reach the initial position.

So instead i can give this advice which worked for me : i add another variable that compute the maximum that can be for the path taken.
e.g : if you have a 5w 6h array and 10 obstacles, you have 5*6 - 10 (= 20) steps maximum until reaching a loop (it can be optimized but that’s not the goal).
So if you reach this maximum, it means you will never reach your initial position, so you can set the new initial position where you stand because it is in the loop.

If you take the example of docbohanh, it means you can compute the max : 10w, 8h, 58 obstacles = 10*8 - 58 = 22.
So after 22 iterations, you are assure to be in a loop where you will be again, so you can set the new initial position and continue your algorithm as usual.

Not sure if i’m clear, so don’t restrain to ask questions.

see ya

5 Likes
#14

Your assumption is correct only when the path never crosses itself, it won’t work in a case like this:

##########
#......###
#.####.###
#.#......#
#.#.##.#.#
#.#.##.#.#
#O.......#
###.##.###
###....###
##########

You can largely overestimate the bound by multiplying the number of dots by four (since there are four directions), and it probably won’t matter because the grids are small anyway. But I would recommend using instead an algorithm such as the Tortoise and Hare one for detecting cycles.

On a more general note, about constraint 3, i.e.:

The obstacles are placed in such a way that the robot will never leave the map

I think that “never” is a bit ambiguous, because it is not clear that this constraint will still apply beyond the step number n.

#15

Hello,
I passed all the test and the validator except validator 6. I can’t figure what is the problem and I already test all the proposition given in this forum. Especially the solution to the situation where you never reach the initial position with w*h - obstacle but it seems this solution was for validator 5 and it’s the 6 which pose problems.
Thanks for your answer

#16

Hello,
validator 6 is almost the same as testcase 6. Only line 2 is 14 instead of 15.
The solution is “2 2”

1 Like
#17

I do not know I am new I dont even know how to do any thing I am on task 3
and I need help. So can you help me??

#18

I enjoyed this, but, after reading the problem, I did not clearly understand the sequence of the robot’s movement logic and what exactly constituted an operation. No real problem there, sometimes that’s part of the puzzle.

I would have liked some test cases with small operation counts to let me explore and test the problem. With even the small test cases still having hundreds of operations, small changes in your code produce large changes in your output. That, combined with the relatively small number of positions that the robot can occupy, makes it difficult to correlate changes with results. I found I had to adopt a trial-and-error exploration strategy instead of a more granular, incremental one.

Long story short, I think this puzzle would be better with some “bunny slope” test cases that you could use to examine individual aspects of the robot’s behavior. After you understand that, you can move on to more intricate paths and cases where exhaustive simulation results in timeout failure.

3 Likes
#19

It looks like all the tests and validators currently in use start the robot in a position that is already on a repeating path.

After thinking about it for a bit, I think the best solution (if the robot did not start on a repeating path) would be to track the robot’s state (x, y, facing direction) until it repeats. Once that happens, you can be confident that the robot will only travel through states that it has been in before, since the robot’s behavior is deterministic and the map is immutable. I.e., there is only one path that the robot can take from any given state. Once it has been in the same place, looking the same way, twice, it has done all its tricks.

2 Likes
#20

I pass all tests successfully but when I submit for final score, it says that I failed #4. Since all tests pass, I just can’t think of a scenario that isn’t accounted for. Any suggestion?

#21

the only particularity that i see in validator #4 is that the robot starting position is on the border of the map.

others cells on the border are all ‘#’.

1 Like