Surface puzzle discussion

I’ve solved it using Python and lists and a dictionary too.
Does your code store the area for ALL the points of a particular lake once its area is calculated?

Yes, I did.
I used two structures to store the data.

Yes, entire lake is stored into a list.
if the tested case is ‘O’, I explore the lake using BFS returning a list, and then i simmply do a len(list) to get the surface

What I did was actually associate each point with its area in a dictionary. A list of points may not be as efficient.

I think I understand how you did.
Nevertheless, i can not see how it would work : the final test is just one biiiiig lake and my BFS algo seems too slow to calculate the lake list and then the surface.
Or maybe the way i calculate surface is not good…

Ah, I see what you mean. I also used a set to store the visited points during the search process.

I tried another approach, I used the Union Find algorithm to group the lakes and then I used a dictionary to store the number of lake cells for each parent.

Python here, the same. Didn’t even read the #, but :
RecursionError: maximum recursion depth exceeded while getting the str of an object for the last one :confused:

I can increase the recursion limit.

Finally, no needs for recursion. It was working fine, but i’ve changed it :
You read All the input, then, when you find a dot, you check the all island (i changed reccursion by while there)

How people manage to make the last test case?
I mean, i used the ‘trick’, but how people manage to assume it was possible, as i cannot event print all the input to visualize the map.

all the ide tests pass, yet my code is only 90% validated.
how can we have an explanation of the test that failed.
the
In the validator, test N°7 (100 tests we have 1000x1000 map) passes but not N°8 (300 tests we have 1000x1000 map)

I used a simple Queue based Floodfill as described on wikipedia for a start :slight_smile:

Optimization :

Summary

Every node stores its ‘visited’ bool from each test in a bool array. A higher scope array stores the lake size found for the corresponding test.

As such, any further test will check if the node was visited by a previous search, if it was (and the node is in the lake), a simple array lookup will give an instant answer

The puzzle is fascinating, I got a 80% score in Golang, because of the last validator, so how to optimize a Golang code

Good puzzle to learn and implement a simple BFS

instead of doing that trick if 99%+ is water, you can do it if l*h-min(l,h) < waterCells, that simply means that the amount of water is big enough to never be split, so you can be sure it all is connected :smiley: