Is this thing on?

With everything going on in the world I've been finding it hard to write stuff. But today the review of Week 79 of the weekly challenge was released. Andrew does an amazing job of going over the various Raku challenges and I've got to admit I love watching him go over my code. It's always good (and often nice) to see how other people react to your code. As a developer I have my code reviewed often and having it done in video is just great.

Watching the review I realised that I'd got into a situation I often get into which is latching onto a solution and not considering others. Firstly you need to bear in mind Challenge 75 which also involved histograms and I quite liked my code I wrote to draw them for that challenge.

(It is I know a bit over the top, I got a bit into my functional programming weeds there). But anyway, because I already had code to draw a histogram I figured I'd reuse that and repurpose it for this challenge.

The perils of cut and paste.

Cut and paste programming has lots going for it, it lets you get moving when a blank screen can leave you pulling out your hair. But it's also terrible for sending you down paths because of the ideas employed in the original code.

In this case I got caught up on the idea of calculating the area of a rectangle.

A simple example

Take the array of heights 3,0,0,0,3 this gives this histogram. (We assume there is a floor and water doesn't fall out the bottom).

#   #     #~~~#
#   #  => #~~~#
#   #     #~~~#

As we can see this has 9 squares of rain water and the area calculation is the width times the height or 3 x 3 = 9 nice and simple. (At this point I've started down the path which takes me all kinds of fun place).

Adding a floor

Of course generally all our heights are greater than 0 giving us a nice floor so here's another simple array 3,1,1,1,3.

#   #     #~~~#
#   #  => #~~~#
#####     #####

Here are area is 6, the calculation for this is the width inside (3) times the height of the edges (3) minus the sum of the internal heights (1+1+1). Giving us (3 x 3) - (1+1+1) = 6. Of course this is still a simple example.

(Note that this calculation still holds true for our original case it's just the internal heights sum up to 0).

Complication 1 : Different edge heights

So I'm still trundling along with my plan, it's making sense so far. But what if out edges have different heights? Lets try 5,1,1,1,3 and what do we get?

#         #
#         #
#   #  => #~~~#
#   #     #~~~#
#####     #####

Still 6 squares and it's easy to see our algorithm still works. We just use the height of the smaller edge for the height of the area. (3 x 3) - (1+1+1) = 6 nice and easy. At this point I felt I was on a winner.

Complication 2 : Rough ground

What if the floor isn't nice and smooth? Lets give this array a shot 4,1,2,1,3,4 and see :

#   #     #~~~#
#  ##  => #~~##
# ###     #~###
#####     #####

So our algorithm gives us a height of 4 and a width of 3 and inner heights of 1+2+3 = 6 so this comes to (4 x 3) - 6 = 6 and as we can see that's right.

So at this point I'm feeling pretty awesome... of course here's where it starts to fall apart.

The centre cannot hold

What if there's a spike in the middle? A point higher than the edges? Like 3,1,4,1,3 :

  #         #
# # #  => #~#~#
# # #     #~#~#
#####     #####

So our algorithm is going to get the smallest edge 3 and the width 3 and the internal heights 1+4+1 = 6 and we get (3 x 3) - 6 = 3... And that's wrong.

So here is where I probably should have taken a step back and wondered if there was a better way, but I was on a roll. Simple change to the algorithm now when summing the height was count either the height in the array or our minimum side height whichever is smaller.

This is a warning note really, if your simple algorithm is starting to have extra checks in it then you're maybe going the wrong way. It's also a warning that's really easy to spot in hindsight.

Anyway with that in place we now have (3 x 3) - (1 + 3 + 1) = 4 and we're done!

I actually thought I was finished at this point. I messed around with a few more arrays and then.... oh boy.

The slope to heck

Lets try something else I mean we've got an awesome algorithm right? 1,2,5,1,4 should look good.

  #        #
  # #      #~#
  # # =>   #~#
 ## #     ##~#
#####    #####

At this point the algorithm completely collapses giving (1 x 3) - (1+1+1) = 0.

Step away from the keyboard

There are moments when you need to step back. Which I did but... not that far back. See the algorithm worked for a lot of cases looking at this one I could see it could be considered 2 separate arrays.

  #        #   #
  # #      #   #~#
  # # =>   # + #~#
 ## #     ##   #~#
#####    ###   ###

1,2,5 and 5,1,4 with that we get two passes of the algorithm for the first we have a height of 1 a width of 1 and internal height of 1 so (1 x 1) - 1 = 0. Meanwhile we have in the second array we have a height of 4 a width of 1 and and internal height total of 1 so (4 x 1) - 1 = 3 add those up and you get 3. So the algorithm works from discrete chunks of the map.

At this point the functional programmer in me is reaching for the recursion hat. Raku multi method make it really easy to do a recursive function like this so in the end I found 3 cases :

1. There is a spike taller than the edges in the centre section
   • In this case we want to split our array into two sub arrays and check each of them
2. There is only 1 or two items in the array
   • In that case we always return nothing, there will be no rain fall. This is the case that Andrew didn't spot in the review.
3. The two edges are the highest possible and there is at least 1 space in between
   • Calculate the area using our simple algorithm

The code for this is as follows :

Firstly case 1. Where there is a spike inside a heights array. Note we pass an offset so the drawing code knows where this water is.

multi sub calculate-rain-levels( 
  @heights where { 
    any(@heights[0^..^*-1]) > any(@heights[0],@heights[*-1])  
  }, 
  $offset = 0
) {
  my $max = max(@heights[0^..^*-1]);
  # This is a bad name... it's really the first
  # Index of a height greater than the edges. 
  my $mid-idx = @heights[0^..^*-1].kv.map( 
    -> $k, $v { $v == $max ?? $k+1 !! Empty } )[0];

  # As calculate-rain-levels returns an array we slip it so
  # we don't end up with nested array.
  return ( 
    |calculate-rain-levels( @heights[0..$mid-idx],$offset ),
    |calculate-rain-levels( @heights[$mid-idx..*],$mid-idx+$offset ) 
  )
}

Case 3. Here we match again and were only accepting arrays with 3 or more values.

multi sub calculate-rain-levels( 
  @heights where { @heights.elems > 2 }, 
  $offset=0 
) {
  # Here is our simplified algorithm
  # Get the highest edge
  my $height = min( @heights[0], @heights[*-1] );
  # Area = height * width on the inside
  my $area = $height * ( @heights.elems - 2 );
  # Then remove the floors, no need to check the height.
  $area -= [+] @heights[0^..^*-1];
  # RainArea is a data transfer object that is used by the
  # drawing system
  return RainArea.new( 
    range => ( $offset..^($offset+@heights.elems) ), 
    :$area, 
    :$height 
  ); 
}

Case 2 (one or two items) is now the fallback case where we just want to return nothing. We use anonymous variables in the signature because we don't care about them

multi sub calculate-rain-levels(@,$) { Empty }

And there we go.

Hopefully this makes some sort of sense of the rambling thread of logic I followed to finish this challenge. Thanks again the Mohammad for all his work managing the challenge to Andrew for his Raku reviews and to everyone who takes part. I always enjoy Monday mornings brain teaser.

Have fun all and be well in this difficult times.