[Community Puzzle] The lost child.Episode-1

Puzzles
#1

https://www.codingame.com/training/easy/the-lost-child-episode-1

Send your feedback or ask for help here!

Created by @jrke,validated by @elderlybeginner,@PascalBihari and @DPAmar.
If you have any issues, feel free to ping them.

1 Like
#2

Thanks for approval for any query ask it here only,Thanks

1 Like
#3

has lost is mother

in km.each block =10km

Would look even better if grammar/punctuation/spelling are improved. More improvement could be possible in the input/constraint sections.

In the above 2nd quote the mentioning of 10km can be unnecessary as this detail is already in input.

6 Likes
#5

In case the author do not know it… you can and should continue editing your published puzzle to improve wordings, fixing errors in statement, or even fixing bug in test cases/validators.

Puzzle approvers can also take up the role to make improvement. “With great power there must also come great responsibility” - Peter Parker.

2 Likes
#6

Thanks i will edit my puzzle and will fix wordings :slight_smile:

#7

Fixed them suggest any other changes if needed.

1 Like
#8

Passed all validators except of the 3rd. Any suggestions on possible problems?

#9

If your code passes all the IDE tests it should work on validator 3, it’s similar to test 3.

#10

Hi,
So I tried to resolve the problem (which is new for me)
From what I understood, a way to solve the problem is to use the dijkstra algorithm from the proposed ressource.
So I try to create a graphe composed of vertices and edges to apply the algorithm.
But here is the trouble: when I parkour the table, I add the vertices into a set (the set ‘vertices’) but for some reasons, even if I find the coordinates of my starting end my ending point, the value for the ending point “M” is always en empty tuple (which should be the coordinates of the value M in the table)…
Any help, its driving me crazy XD
Thank for the puzzles :wink:

#11

Ok the trouble came from the fact I called a variable ‘end_p’.
‘end_pa’ didn’t work neither.

The trouble add nothing to do with an immutable type or whatsoever… This was a trouble to find.

Sorry,

#12

a simple flood fill algorithm works for me

1 Like
#13

My code passes all tests but is failing on validator 4. What is execution time limit?

#14

Validator 4 is very similar to the 4th testcase so I don’t understand why you timeout.

You might have an infinite loop that never breaks or something.
Cause even with a lot of unnecessary stuff in your floodfill it shouldn’t take too long.

#15

Timing out is my only guess because test 4 is taking almost 1,5s to complete but rest of the test and validators are passed.

edit.

I used “expert” function and edited test case 4. If path is longer then “240km” my code is timing out :frowning:

#16

If your floodfill il done properly it’s impossible that it takes more than 0.5 sec.
So you probably do a lot of heavy copies for nothing or something like that.
Try to simplify the structure as much as possible, do in-place modifications instead of creating new objects, this kind of thing.

1 Like
#17

My guess would be not filtering already visited and expanding the same cell multiple times.

1 Like
#18

I thought about that too but wouldn’t it loop forever ?

#19

Not if you put it in a queue and always expand the “oldest” node. Just a horrible runtime.

#20

I saw that the top scored submission for Python do not pass test cases with distances bigger than 250 km. So, here are two suggestions of validators:
Input:

C.........
#########.
........#.
.######.#.
.#....#.#.
.#.#.M#.#.
.#.####.#.
.#......#.
.########.
..........

Expected output: 580km

Input:

C.........
#########.
..........
.#########
..........
#########.
..........
.#########
..........
.........M

Expected output: 540km

#21

People tend to vote for original/short solutions regardless the efficiency.
It happens quite often that the top voted solution has a bad complexity.
I remember a shortest path problem where the top voted Python solution used Floyd Warshall which is very slow (it gives all shortest pathes for any choice of two vertices, way too overkill for the problem).