While the puzzle is interesting, I think this sentence in the statement is rather misleading: As such, the volume of water on the left is the same as on the right (6x "~").
This “6x ~” implies as if the water volume is to be calculated base on the char counts in the grid.
(Because in the provided ascii art example, the real areas of the trapezoids are NOT the same.)
After wasting an hour on a ‘char grid flood’ based solution, and after checking some test cases, now it seems to me that this approach is incorrect and we have to calculate the volumes (or areas in 2D) exactly, and taking into account the slopes as well.
EDIT: the trapezoid areas are indeed the same in the example, my mistake. But the ‘char counting’ approach still seems to be a dead end to me, because only the statement example has 45 degrees slopes, other test cases are more varied…
My approach was to split the landscape into vertical bands based on segment intersections, and find out which bands get flooded before others. I had to use recursive ‘banding’ to compute larger composite bands but it worked out in the end.
Hi, could you send validators in private message please I have all test cases running but I didn’t validate validators 2,7 and 11. I’m a bit messed up with all the cases and this would help me solving the puzzle. I have spent quite a lot of time on it yet, my strategy is to compute the volumes and set of segments defining them, necessary for each town to be raised by water level, and then sorting towns according to which they submerge when submerged, and if a tie occurs, necessary volume comes in to seperate cases.
All the best
It’s OK thanks I have changed my approach : from source I fill in by smallest volume available, if source is overflooded, it goes vertically to water level, and last town not flooded wins. I used the Thales theorem to fill in a given trapeze by a given volume. All the best
but it worked out in the end.