Surface puzzle discussion

@Elliot Yep for me too the recursive version couldn’t work no matter what, a switch to the stack version was enough for it to work properly.

Read here a non-recursive algorithm.

@nicolas_patrois Never saw the “Learning” games before , how do we get to them ?

you get to them from the forum, search the post from @loick_michard

2 Likes

@nicolas_patrois WoW A secret level :smiley:

Btw this level is too easy :joy:

#BFS + DP = GG :joy:

1 Like

There is another one, easier.

I used Java and saved all sets, each of which contains indices of the same lake. When finding the area of the lake given a cell, I simply searched the set the cell is in and returned the size of the set. When constructing the sets, I tracked flooded and to-flood cells. I did not encounter issues with the approach.

I’m having issue on C# for the validation of the large tests

Actually the code below timeouts.
If I can’t increment an integer 1 000 000 times I don’t really know how I’m supposed to read a 1000 x 1000 table, any clues ?

for (int i = 0; i < H; i++)
{
//if (i % 10 == 0)
//Console.Error.WriteLine(i + “/” +H);
string row = Console.ReadLine();
var cpt = 0;
for (int j = 0; j < row.Count(); j++)
{
}
}

The default code does not timeout for any test-cases. And the puzzle is solvable in C# too.

row.Length is better than row.Count btw.

Thank you I had overlooked that
Much easier when parsing the input in n^2 than n^3 :smile:

Hey coders !

Just for my information, how long does your implementation takes for #9 test (large map, large lake) ?

My classical flood algorithm in JavaScript took 64ms I’m sure compiled langages are even better, but I’d like to know.

I just inserted a clock function around my main() function
Reading the input and everything took 53.386002 ms in C++

I’m processing the map into “start, end” pairs on input to detect runs. This makes the subsequent searches much easier, as well as drastically reducing the memory footprint for the larger tests. I haven’t timed it, but it should be quite fast.

Unfortunately, even though my code passes all of the IDE tests (including the “all lake” test), it consistently fails the “No land” test on submission. Is that likely to be a validator bug?

The whole program takes 3.855 ms in Lua (according to a call to os.clock() right at the end).

Taking 53ms in C++ suggests a very suboptimal algorithm…

Doing it in C# and getting 80%. I fail the cases with 100+ tiles on a 1000x1000 board because I get a File Not Found exception… could not load file or assembly ‘System’. Sounds like a bug (maybe a different exception is getting masked or something) but I wanted to ask about it here before posting on the bugs forum. Has anyone seen this before?

…and trying the same code one day later, it all worked. Definitely a bug, but I guess a temporary one.

It seems need solved with the Loops, because with recursion I got always 80%,and have stack overflows at last test :confounded:

1 Like

I have the same problem :s too much recursion

Yeah. I solved this by turn recursion to loops

1 Like

Thank you ! I I have just ended it with loop. I never had rewritten a recursive algorithm to an iterative one, it’s a good exercice.

1 Like