[Community Puzzle] Retaining Water

https://www.codingame.com/training/easy/retaining-water

Send your feedback or ask for help here!

Created by @Westicles,validated by @Wontonimo,@selenae and @murrayr.
If you have any issues, feel free to ping them.

It’s a good puzzle but if you don’t pay much attention to the cover and go directly to the IDE, you have to guess a bit cause the Problem doesn’t state much.

For example the whole structure is made of cubes, it’s never said at any point.

Also the word “pool” is a bit misleading, really a pool looks nothing like that.
It looks more like moutain areas with lakes of retained water than one single pool.

But despite that, it was a nice little puzzle.

1 Like

For many puzzles, the tags give an additional hint. Here, the lack of a tag is a hint itself: My first (wrong) reaction when reading the statement was “Hey, a floodfill in the easy category?”. Then I looked at the tags…
Nice puzzle, I liked it!

1 Like

I admit that I used unnecessary floodfills cause I followed my firsy idea which was:
for each level h from 1 to 25:
pour 1 volume of water in lvl h tiles if it doesn’t leak (and mark all tiles that leak)

But indeed a top-bottom “one huge canadair” approach is even simpler and doesn’t require any floodill.

LOL.
Yes, I wasted a bit of water, but conversing water was not part of the design target…

To better understand the puzzle:

What is result for 3x3 all X pool

XXX
XXX
XXX

Does water leak diagonally, what is result for:

XZZ
ZXZ
ZZZ

All X’s would be zero, since you are pouring water on a 3x3 stack of blocks 24 high surrounded by an outside area of zero height. All the water would run off and none would be retained. If the middle value is lower (like in your second example, where the answer would be 2), some water would pool.

I added a note that water does not leak diagonally, just to make it crystal clear.

2 Likes

Ok, Thanks

So result is 2 for:

XZZ
ZXZ
ZZZ

1 Like

The puzzle deserves medium imo, but it’s a good one :+1:

6 Likes

very nice puzzle ! I dried my brain to find a correct and naturel way to fill this pool until disaster… congrats.

1 Like

the explanation should probably be a bit clearer, but I had a lot of fun with this puzzle and was a tough one. an extended floodfill problem. Very good idea

2 Likes

Agreed. Once I understand that its like spilling water into the pool and count how much water stayed inside the pool it was a lot easier for me. Like the puzzle, very nice!

Hello !
I’m really a beginner in coding and this puzzle seems to me much more difficult than the other easy puzzle. There are everything in the explanations to understand the puzzle but it’s really not that obvious at the first reading.
The lack of tags or link to understand how to solve this problem are another negative points. It’s when I read the forum that I understand that I have to used a floodfill algorithm to solve the problem and even at this stage the algorithm that I code is too slow (I tried to work with a Four-way flood fill using a queue for storage).
I think I will wait to progress to solve this puzzle but I wanted to tell you that for me it’s not an easy puzzle. If you want to let it in easy maybe write a more detailed explanation with some clues to help to built the algorithm or some link to a lesson/video who explained how to solve (just with big step) the problem or at least this floodfill algorithm

1 Like

You don’t actually need floodfill here, it’s just one way to do it among several.
The solution can be very short and simple without nothing fancy.
That’s why it’s labelled easy, but it doesn’t mean the ‘simple’ method is super easy to find, you need to give it some thoughts.

About tags, I think at some point if you really want to progress you shouldn’t read them at all and approach any problem with a fresh mind, ready to try anything.

Also about giving a link to a page that explains the method, I’m not sure it’s a good idea in general. The only puzzles where I found it was legitimate is the collection of puzzle by aCat that aim at teaching classical algorithms(minimax with alpha beta pruning, MCTS, etc), and make sure you understood how to implement them.

1 Like

Wanted a better understanding of what the test cases look like.
Sharing for anyone who finds it useful: https://codepen.io/Abrman/full/abpKbRW

12 Likes

This is at least medium. Or I missed a more obvious easier solution. but enjoyed solving it.

1 Like

A very interesting puzzle, and indeed I wonder whether it’s an “easy” puzzle.

I can see two possible answers:

  1. “easy” refers to the CS methods that are required to solve the puzzle. In this case, the main method needed is flood-fill (whether explicitly implemented, or implicitly implemented as suggested above by by @pardouin, et al). Is this considered “easy” in terms of Codingame standards?
    In any case I believe both explicit and implicit implementations fall under “flood fill”
  2. “easy” refers to the algorithmical difficulty, in which case this puzzle would possibly earned a “medium”, at least compared to other puzzles in the easy category

I wish I could write more about the question of “flood vs. scans” and is it really different, but then it might hurt the experience of people who havn’t solved it yet. If anyone would like to continue this discussion in private - please :slight_smile:

3 Likes

Very nice puzzle! I have enjoyed it.

1 Like

This was fun! It does seem very challenging for an easy puzzle. If there is an easy solution, it’s a hard solution to find.

If someone has found a solution to this that doesn’t involve flood fill, it would be nice to post a hint about it here.

1 Like

It has been hinted above: imagine a huge canadair dropping a massive volume of water at once. Then, as long as you can find a spot where water can leak outside the map/flow to a lower spot, make it leak/flow.

2 Likes