I’ve been doing the Weekly
Challenges. The
latest
involved various sorts of array hunting. (Note that this ends today.)
Task 1: Maximal Square
You are given an m x n
binary matrix with 0
and 1
only.
Write a script to find the largest square containing only 1's
and
return it’s area.
So basically it's a search. Start at each point, then accrete layers o
a square: first the point itself, then the three squares below and to
the right of it to make a 2×2, then the five more that make 3×3, etc.
In JavaScript:
function maximalsquare(a) {
Set up the maximum value latch and the array sizes.
let mx = 0;
const boundy = a.length;
const boundx = a[0].length;
Iterate over each starting point.
for (let y = 0; y < boundy; y++) {
for (let x = 0; x < boundx; x++) {
size
is the last square-size we've found.
let size = 0;
while (true) {
Build a list of points that need to be included in the next size of
square: horizontally including the corner
let tests = [];
for (let xx = x; xx <= x + size; xx++) {
tests.push([y + size, xx]);
}
and vertically.
if (size > 0) {
for (let yy = y; yy < y + size; yy++) {
tests.push([yy, x + size]);
}
}
If any of those is a zero, the previous size
value is what we've
got. (In most of these languages I have an any
filter, but min
works when I don't.)
if (Math.min(...tests.map(i => a[i[0]][i[1]])) == 0) {
break;
}
Otherwise, add one to size
and make sure that won't spill outside
the grid.
size += 1;
if (x + size >= boundx || y + size >= boundy) {
break;
}
}
I've been working in linear size, but we have to store the count of
points.
mx = Math.max(mx, size * size);
}
}
return mx;
}
I like this best in PostScript. Same algorithm, but the tests
list
can be an anonymous array.
/maximalsquare {
0 dict begin
/a exch def
/mx 0 def
/boundy a length def
/boundx a 0 get length def
0 1 boundy 1 sub {
/y exch def
0 1 boundx 1 sub {
/x exch def
/size 0 def
{
[
x 1 x size add {
[ exch y size add exch ]
} for
size 0 gt {
y 1 y size add {
[ exch x size add ]
} for
} if
]
{
/i exch def
a i 0 get get i 1 get get
} map
{ 0 eq } any {
exit
} if
/size size 1 add def
x size add boundx ge
y size add boundy ge or {
exit
} if
} loop
/mx mx size dup mul max def
} for
} for
mx
end
} bind def
Task 2: Right Interval
You are given an array of @intervals
, where $intervals[i] = [starti, endi]
and each starti
is unique.
The right interval for an interval i
is an interval j
such that
startj >= endi
and startj
is minimized. Please note that i
may
equal j
.
Write a script to return an array of right interval indices for each
interval i
. If no right interval exists for interval i
, then put
-1
at index i
.
This turned out rather easier than task 1.
Raku:
sub rightinterval(@a) {
Build a list of the i
values.
my @ss = @a.map({$_[0]});
Sort a list of indices by the i
values. (There's a term for this,
sorting the indices rather than the thing itself, but I can never
remember what it is.)
my @si = (0 .. @a.end).sort({@ss[$^a] <=> @ss[$^b]});
my @out;
For each interval set,
for @a -> @l {
Find the indices of intervals that are validly to the right of it.
my @ix = @si.grep({@ss[$_] >= @l[1]});
Since they're sorted, push the first one (if any).
if (@ix.elems > 0) {
@out.push(@ix[0]);
} else {
@out.push(-1);
}
}
@out;
}
Full code on
github.