Who’s Masking the Mask?

Wherein we study the things blocking our view and see them for what they are — not interfering obstacles but illuminating signs…

THE WEEKLY CHALLENGE – PERL & RAKU #152 task 2


“Humor is the mask of wisdom.”

— Friedrich Durrenmatt


Rectangle Area

Submitted by: Mohammad S Anwar

You are given coordinates bottom-left and top-right corner of two rectangles in a 2D plane.

Write a script to find the total area covered by the two rectangles.

Example 1:
Input: Rectangle 1 => (-1,0), (2,2)
       Rectangle 2 => (0,-1), (4,4)

Output: 22
Example 2:
Input: Rectangle 1 => (-3,-1), (1,3)
       Rectangle 2 => (-1,-3), (2,2)

Output: 25

ANALYSIS

I like it when a puzzle doesn’t explain with too much detail exactly what’s going on in its head. I enjoy the mystery, and the discovery in unwrapping the package.

At first, we can see we are given two rectangles and asked to find the area covered by both. Ok, sure. Deriving the area involves the application of a fairly simple formula. Do that for each and there we are.

But what if the rectangles overlap? Oh, right. That’s the puzzle. The part that isn’t mentioned. Now I get it.

If we simply sum the two areas, any overlap will be counted twice. And we simply can’t have that. What to do?

We need to find that overlap, that’s what, and do somehing about it. Stat.

What we are looking for then is the union of the two areas. For this we take the area covered only by one rectangle, the area covered only by the other, the area covered by both, and then we add all of that up. Or, you know, come to the same answer some other way. Like if we could find just the intersection area, we could subtract that from the sum of each considered independantly. That would work too, with less computation. That would be better.

So what is the overlap, then? We keep coming back to that question. Let’s answer it.

In the first example, we have two z-axis ranges, one for each rectangle…

…Oh wait, hold on.

A digression: before we begin, we’ll note that two points only determine a rectangle if it is laid out orthogonally on the plane. If we allow the shape to be rotated, which of course is prefectly allowable in a 2-dimensional Cartesian space, then we lose the meaning of the “bottom-left” and “top-right” corners as distinct properties. Although one (or two) points will always be bottom-most, unless we are orthogonally aligned that point will not also be left-most. The whole idea gets schmurtled.

So because we are only given the two points to define our rectangle, we can safely infer that that the two rectangles are orthogonally placed within the grid. This is good, because calculating the area in arbitrarily-rotated rectangles is considerably harder to do, and the overlap more so. Not impossible, but considerably more complicated.

That settled then: back to the overlap. Let’s break this down. we have two x-axis ranges, one for each rectangle, indicating the span between the left edge and the right. Any overlapped area will be defined by the overlap of these two ranges, at least as far as the x-axis component. Although ultimately the final intersection area may still be 0 if there is no y-axis overlap as well.

Which leads us to the y-axis, where the same rules apply. It is the overlapped combination of these four edge ranges, x and y for two rectangles, that in turn defines the left and right, and top and bottom extremities of the intersection.

So we get that shape, subtract it from the sum of the two rectangles, and we have our answer.

METHOD

We’re going to go with the subtractive solution outlined above. Let’s call the area of one rectangle A, the other B. Then we’re looking for the union of the two areas:

A ∪ B = A + B – ( A ∩ B )

Finding the area of an orthogonally-aligned rectangle is straightforward: we find the absolute difference between the x-coordinates and the same for the y, and multiply the two values together.

For the intersection that’s a little different. We need a means to find the overlap of points along each axis, but from there we don’t need to actually construct a rectangle. All we really need is a scalar value for the overlap — a distance. If we get these for both axes, we can multiply those together to get the area of the intersection without actually creating the shape first.

We’ll need four functions: a union() to sum the two rectangles and subtract the intersection; an area() to compute those areas; an intersection()to do the hard part; and a helper _overlap() to keep track of the varying ways the rectangle edges can, well, overlap.

PERL 5 SOLUTION

Focusing on the logic, we’ve again eschewed dealing with the complexities of inputting a pair of rectangles to be evaluated. The top function, union() takes two rectangle references, each an array of two points, themselves anonymous arrays of two coordinates. It adds up to a lot of nesting. For all of that, I’ve done my best to keep the dereferencing to the individual values as clear as I could. A little air in the code and considerate formatting helps too, I should hope.

The _overlap() function is the most complicated, taking two ranges, each a tuple [start,finish] pair of coordinates. The various cases are dealt with through a series of cascading ternary conditionals as explained in the comments.

Astute observers will notice the Unicode exponent in the top comment. We can do this because we have specified use utf8 in the boilerplate header.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


## a rectangle is defined as two point tuples [$p1,$p2] for the 
## bottom-left and upper-right vertices
## main functions return returns units²

sub area ( $rect ) { 
    my $x = abs( $rect->[0][0] - $rect->[1][0] );
    my $y = abs( $rect->[0][1] - $rect->[1][1] );
    return $x * $y;
}

sub intersect ( $rect1, $rect2 ) {
    _overlap( [ map { $_->[0] } $rect1->@* ],       ## rect 1 x-axis
              [ map { $_->[0] } $rect2->@* ] )      ## rect 2 x-axis
        * 
    _overlap( [ map { $_->[1] } $rect1->@* ],       ## rect 1 y-axis
              [ map { $_->[1] } $rect2->@* ] );     ## rect 2 y-axis
}

sub union ( $rect1, $rect2 ) {
      area ($rect1)  
    + area ($rect2)  
    - intersect ($rect1, $rect2) ;
}

sub _overlap ( $r1, $r2 ) {
## ranges are ordered 2-element tuples [start,end] : end > start
## no order is assumed between the two ranges $r1 and $r2
## returns absolute value of overlapping range
## there are five cases total:
##  1.  no overlap
##  2.  A overlaps start of B
##  3.  B overlaps start of A
##  4.  A completely encloses B
##  5.  B completely encloses A

    ## sort the ranges by start point (merge cases 2+3 and 4+5)
    $r1->[0] > $r2->[0] and ( $r1, $r2 ) = ( $r2, $r1 );
        
    $r2->[0] > $r1->[1] 
        ? 0                             ## no overlap (1)
        : abs( $r2->[0] 
            - ( $r2->[1] > $r1->[1]  
                ? $r1->[1]              ## intersection (2+3)
                : $r2->[1] )  )         ## A encloses B (4+5)
}

Raku Solution

I admit after completing and polishing the Raku version I went through and reworked the Perl for clarity, so there’s little difference, but the Perl owes a lot to the Raku in the end. I’ve found that Raku code can pack a lot of lot into a few swift actions, and consequently can get very dense, and with that feel quite opaque. To fight against this I find tossing a judicious amount of whitespace can serve to really focus the eye and make everything flow in a pleasing manner.

Whitespace is cheap, and hardly even takes up any disk. I frankly don’t understand why some people seem so averse to it.

unit sub MAIN () ;

sub area ( @rect ) {

    ((@rect[0][0] - @rect[1][0]) * (@rect[0][1] - @rect[1][1])).abs
}

sub intersect ( @rect1, @rect2 ) {

    _overlap( @rect1.map(*[0]),       ## rect 1 x-axis
              @rect2.map(*[0]) )      ## rect 2 x-axis
              
        * 
        
    _overlap( @rect1.map(*[1]),       ## rect 1 y-axis
              @rect2.map(*[1]) );     ## rect 2 y-axis
}

sub union ( @rect1, @rect2 ) {

      area(@rect1)  
    + area(@rect2)  
    - intersect(@rect1, @rect2) ;
}

sub _overlap ( $r1 is copy, $r2 is copy ) {

    ## sort the ranges by start point (merge cases 2+3 and 4+5)
    $r1[0] > $r2[0] and ($r1, $r2) = ($r2, $r1) ;
        
    $r2[0] > $r1[1] 
        ?? 0                           ## no overlap (1)
        !! abs( $r2[0] 
            - ( $r2[1] > $r1[1]  
                ?? $r1[1]              ## intersection (2+3)
                !! $r2[1] )  )         ## A encloses B (4+5)
}


The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s