[Community puzzle] Unflood The World

Puzzles
#8

Are you local mins such that all neighbours are strictly superior ? (probably not, since it would only find isolated mins)

Then, when you do your BFS, are you looping over all the local minimas ? Are you not doing some redundancy here ?

I mean, once a square has been connected to a minima, I never look at it again.

I think in total, my program runs with O(n log n) for the sort (I think that’s worst case of python sort), and then O(4*n)
(each square can be looked at for all of his four neighbours, and I’m not even sure that’s possible. But maybe my calculation is wrong and it’s higher than that…

I’m really annoyed by not being able to know why we fail (as in wrong answer / delay) as it would help the debugging

#9

I also failed the “Maze 2” validator, but after some trial and error found a test case which I failed.
eulerscheZahl was so kind to add it to the test cases, you might want to have a look at it.

#10

<–NOOB here.

Looking for a hint on where to get started determining the drains. I’ve already read in the data and I can loop through the surface’s points. Just need an idea on what methodology to use to determine drains. Thought about assuming one or more drains then using recursion, but I thought there had to be a more elegant way.

#11

Drains are at minimal values of the surface points. The idea is to pick one of those, and check if it’s enough to drain the whole map. If not, you have to add other drains.

2 Likes
#12

That gets me started. Thanks.

#13

I’m a bit new at this and don’t see it, can you please give me a link to this test cases (or publish it here)?

#14

It’s the 8th testcase of the puzzle (“Plateaus”), that I added.

#15

Hmm… I’m passing it (as well as “Plateaus 2”). Its only “Maze 2” that fails.
Anyway, thanks for your reply.

#16

Maze 2 was also the last one for me to pass. A hint to others: I realized my error after reading one of the comments here (about assuming the drains have to be “1”). After doing one round of draining, I was going back to my map and just picking the next place to start draining from, rather than the best place. What’s interesting, I guess, is that this stupid method didn’t fail any of the tests, just only on submission.

#17

Hey guys, any idea what the input for Flat field 2 is? Passing every case except that. My algo is basically forming clusters of equal-valued squares, then adding outflow edges from higher-valued clusters to lower ones, and lastly counting clusters with no outflow edges

#18

flat field 2 is a simplier version of flat filed

the difference is the grid size … with one dimension … shouldn’t have said that … :wink:

2 Likes
#19

Holy shit at first i thought it couldnt handle the Nx1 or the 1xN cases, when actually it died at the 1x1 case. Had to move two lines up a bit to fix it. Im an idiot… Thanks!!!

#20

I used unionfind (disjoint set) at first with sorting / rowmajor indexing and it failed only maze 2. Then switched to BFS and it worked

#21

This was a fun one! I found that it helped computationally to essentially merge sections of equal height first.

#22

When i started this one i thought it was “easy” and 10 mins later i had have a solution that made all tests green, but missed 3 validators. I looked into the posts here and figured out, that this on is rated as “very hard” ;), with missing testcases. So i designed a “new” test
5 5
1 1 1 1 1
1 4 4 4 1
1 4 2 4 1
1 4 4 4 1
1 1 1 1 1
with solution 2
after i passed that one, all validators also went green ;).

1 Like
#23

I pass all testcases but miss validator Maze 2. Do you have some new testcase to help ?

#24

Do these previous comments help you?

https://forum.codingame.com/t/community-puzzle-unflood-the-world/1941/16

https://forum.codingame.com/t/community-puzzle-unflood-the-world/1941/20

#25

No, I have read all the comments.
This is my strategy:

  • list all numbers that don’t have lower neighbors (local minimum)
  • for each of these minima, perform a depth-first search to connect all cells of the same level and determine a set of distinct groups
  • eliminate false positives: for each group, recheck if these cells don’t have a lower neighbor and if so, eliminate the group
  • count the number of remaining group
#26

Your strategy sounds correct :thinking: Maybe there’s a bug in the implementation?

If you want, you may send your code to me in private message and I’ll take a look.

1 Like
#27

Thanks @5DN1L for your testcase, I could fix my error: when I created a new group I forgot to update the index of the element in the groups list.
This is the testcase that helped me if that can help you:

Input

5 5
6 1 5 4 2
1 4 4 4 1
4 6 1 1 8
6 1 6 8 9
1 1 2 2 5

Output

5
1 Like