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 
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 
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 
i have solve this puzzle with BFS and memorization.
i used the fact that object are mutable to not recalculate for point in the same lake.
points of the same lake have the same object (pointed to the same object)
Only after completing the task I realized that recursion was also on the menu. I didn’t use any, only kept track of visited coordinates and filled in the value accordingly, though as an afterthought I can easily see how this can be turned into a recursive solution. I directly converted the input map into an integer array of area values, which I used as a lookup and flood filled on-demand if no cached value was available.
As far as performance is concerned, my solution’s memory footprint is always WIDTH*HEIGHT * SIZE_OF_INTEGER, plus the “backtracking table” which would ostensibly be eliminated by a recursive solution, but we need to account for the fact that the coordinates are still placed in stack by each recursive call, so the overhead lies more in the performance hit by the logistics of dynamically adding entries to a go slice.
Probably will do a recursive one in C just to have fun with optimization.
I’m currently playing with Dart, so I tried Surface with it.
I’m sad because my code pass the last test, but not the one before (100 tests on 1000x1000)… but my debug show me I found the solution just before the timeout !
I tried several algorithms and optimizations around BFS and Flood Fill, even with the span fill-scan implementation that wikipedia says should be 2x faster, but no change in my results.
I suspect a bug on the Dart runner, as I already have an answer and the timeout occurs after.
Try adding the following line after you have output all the answers:
exit(0);
1 Like