I have all Testcases ‘green’ and 4 validators (1,2,3,6) failing …
I think the Testcases here should get a little rework …
2 Likes
Hi,
very cool Puzzle.
My Testcases are alle green, but in the validators i failed “Maze 2”.
Do you have any hint of what is special about this maze?
Are you making any assumptions (for example, that the drains should only be in squares with “1” values)?
If all the other validator works, but one, maybe it is also a problem with duration of program ? (For me, this is annoying not being able to know if we fail because of that or a wrong answer)
My program was passing all the test validators, but failing on several validators including Maze2, until I modified the way I was crawling through the squares
1 Like
Thanks for the help and ideas.
I think my code needs no assumptions and runs all tests in less than 0.002 seconds.
All in all it’s a very simple code:
- Watch for local mins (not necessarily at “1”)
- Check if mins connected
- Count connected mins
So i have to modify the code and see what happens
How do you find the local mins ? Computing gradients ?
I don’t know if it’s fast enough.
I thought of it first, but went for something simpler to implement, with sorting.
(Don’t know how much I could tell here)
How do you check if they are connected ? that might be the part where it is slow actually …(just neighbors, or a path from one to another ?)
Local Mins:
My code runs in worst-case O(n^2), where n is number of cells.
It doesn’t sort, but in avg case runs in O(2*n).
More details would spoiler, but I think the idea with sorting is similiar to mine
Connected:
Normal BFS for any (not connected) local min
My theorie: I have a small bug triggered by maze 2
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
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.
<–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.
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
That gets me started. Thanks.
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)?
It’s the 8th testcase of the puzzle (“Plateaus”), that I added.
Hmm… I’m passing it (as well as “Plateaus 2”). Its only “Maze 2” that fails.
Anyway, thanks for your reply.
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.
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
flat field 2 is a simplier version of flat filed
the difference is the grid size … with one dimension … shouldn’t have said that … 
2 Likes
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!!!
I used unionfind (disjoint set) at first with sorting / rowmajor indexing and it failed only maze 2. Then switched to BFS and it worked
This was a fun one! I found that it helped computationally to essentially merge sections of equal height first.