1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl
#
# whos-masking-the-mask.pl
#
# 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 the puzzle doesn't explain itself in too much
# detail as to what's going on with it. Here 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.
#
# If we simply sum the two areas, any overlap will be counted
# twice. We 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.
#
# 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 right. 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 cartesion 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 teh area in arbitrarily-rotated
# rectangles is considerably harder to do. Not impossible, but
# much more complicated.
#
# That settled, we have two x-axis ranges, one for each
# rectangle. Any overlapped area will be contained within the
# overlap of these ranges, although the area may still be 0 if
# there is no \y-axis overlap as well.
#
# Which leads us to th e\t-axis next. It is the combination of
# these four overlaped ranges that in turn defines the left and
# right, top and bottom extremities of the intersected area.
#
# So we get that shape, subtract it from the sum of the two
# rectangles, ad 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 )
#
#
# © 2022 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
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)
}
use Test::More;
is union( [[-1,0], [2,2]], [[0,-1], [4,4]] ), 22, 'ex-1';
is union( [[-3,-1], [1,3]], [[-1,-3], [2,2]] ), 25, 'ex-2';
is union( [[-2,-2], [0,0]], [[0,0], [2,2]] ), 8, 'figure-8, no overlap';
is union( [[0,0], [2,2]], [[0,0], [2,2]] ), 4, 'superimposed, all overlap';
is union( [[0,0], [2,4]], [[0,0], [3,4]] ), 12, 'A in B, left-aligned';
is union( [[0,0], [3,4]], [[0,0], [2,4]] ), 12, 'B in A, left-aligned';
is union( [[1,0], [3,4]], [[0,0], [3,4]] ), 12, 'A in B, right-aligned';
is union( [[0,0], [3,4]], [[1,0], [3,4]] ), 12, 'B in A, right-aligned';
done_testing();
|
