aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-087/athanasius/perl/ch-1.pl170
-rw-r--r--challenge-087/athanasius/perl/ch-2.pl325
-rw-r--r--challenge-087/athanasius/raku/ch-1.raku168
-rw-r--r--challenge-087/athanasius/raku/ch-2.raku361
4 files changed, 1024 insertions, 0 deletions
diff --git a/challenge-087/athanasius/perl/ch-1.pl b/challenge-087/athanasius/perl/ch-1.pl
new file mode 100644
index 0000000000..ec9665f4ae
--- /dev/null
+++ b/challenge-087/athanasius/perl/ch-1.pl
@@ -0,0 +1,170 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 087
+=========================
+
+Task #1
+-------
+*Longest Consecutive Sequence*
+
+Submitted by: Mohammad S Anwar
+
+You are given an unsorted array of integers @N.
+
+Write a script to find the longest consecutive sequence. Print 0 if none
+sequence found.
+
+Example 1:
+
+ Input: @N = (100, 4, 50, 3, 2)
+ Output: (2, 3, 4)
+
+Example 2:
+
+ Input: @N = (20, 30, 10, 40, 50)
+ Output: 0
+
+Example 3:
+
+ Input: @N = (20, 19, 9, 11, 10)
+ Output: (9, 10, 11)
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2020 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+From the Examples, it appears that a "sequence" is an ordered set of TWO or
+more integers in which adjacent numbers differ by exactly 1. It is assumed that
+any duplicates in the input array are irrelevant to the solution and may be
+ignored.
+
+The algorithm used:
+ 1. Sort the input array in increasing numerical order.
+ 2. Create a list of sequences (an AoA) as follows: put the first element
+ into a new sequence, and then, for each succeeding element, either:
+ a. ignore it because it is equal to the previous element; or
+ b. add it to the current sequence because it is exactly one greater than
+ the last element added to that sequence; or
+ c. use it to start a new sequence.
+ 3. Find the longest sequence. If its length is 2 or more, output it, other-
+ wise output "0".
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+use Regexp::Common qw( number );
+
+const my $USAGE =>
+"Usage:
+ perl $0 [<N> ...]
+
+ [<N> ...] A non-empty, unsorted array of integers\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 087, Task #1: Longest Consecutive Sequence (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my @N = parse_command_line();
+
+ printf "Input: \@N = (%s)\n", join ', ', @N;
+
+ my @sequences = find_sequences( @N );
+ my @longest_seq = get_longest_seq(@sequences);
+
+ if (scalar @longest_seq <= 1)
+ {
+ print "Output: 0\n";
+ }
+ else
+ {
+ printf "Output: (%s)\n", join ', ', @longest_seq;
+ }
+}
+
+#------------------------------------------------------------------------------
+sub find_sequences
+#------------------------------------------------------------------------------
+{
+ my @N = sort { $a <=> $b } @_;
+ my $prev = shift @N;
+ my @seqs = [ $prev ];
+ my $index = 0;
+
+ for my $current (@N)
+ {
+ next if $current == $prev;
+
+ if ($current == $prev + 1)
+ {
+ push $seqs[ $index ]->@*, $current;
+ }
+ else
+ {
+ $seqs[ ++$index ] = [ $current ];
+ }
+
+ $prev = $current;
+ }
+
+ return @seqs;
+}
+
+#------------------------------------------------------------------------------
+sub get_longest_seq
+#------------------------------------------------------------------------------
+{
+ my @seqs = @_;
+ my $max_count = 0;
+ my @max_seq;
+
+ for my $seq (@seqs)
+ {
+ my $count = scalar @$seq;
+
+ if ($count > $max_count)
+ {
+ $max_count = $count;
+ @max_seq = @$seq;
+ }
+ }
+
+ return @max_seq;
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+ my @N = @ARGV;
+
+ scalar @N > 0 or die qq[ERROR: Empty array\n$USAGE];
+
+ for (@N)
+ {
+ /\A$RE{num}{int}\z/ or die qq[ERROR: "$_" is not an integer\n$USAGE];
+ }
+
+ return @N;
+}
+
+###############################################################################
diff --git a/challenge-087/athanasius/perl/ch-2.pl b/challenge-087/athanasius/perl/ch-2.pl
new file mode 100644
index 0000000000..48075544f2
--- /dev/null
+++ b/challenge-087/athanasius/perl/ch-2.pl
@@ -0,0 +1,325 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 087
+=========================
+
+Task #2
+-------
+*Largest Rectangle*
+
+Submitted by: Mohammad S Anwar
+
+You are given matrix m x n with 0 and 1.
+
+Write a script to find the largest rectangle containing only 1. Print 0 if none
+found.
+
+Example 1:
+
+ Input:
+ [ 0 0 0 1 0 0 ]
+ [ 1 1 1 0 0 0 ]
+ [ 0 0 1 0 0 1 ]
+ [ 1 1 1 1 1 0 ]
+ [ 1 1 1 1 1 0 ]
+
+ Output:
+ [ 1 1 1 1 1 ]
+ [ 1 1 1 1 1 ]
+
+Example 2:
+
+ Input:
+ [ 1 0 1 0 1 0 ]
+ [ 0 1 0 1 0 1 ]
+ [ 1 0 1 0 1 0 ]
+ [ 0 1 0 1 0 1 ]
+
+ Output: 0
+
+Example 3:
+
+ Input:
+ [ 0 0 0 1 1 1 ]
+ [ 1 1 1 1 1 1 ]
+ [ 0 0 1 0 0 1 ]
+ [ 0 0 1 1 1 1 ]
+ [ 0 0 1 1 1 1 ]
+
+ Output:
+ [ 1 1 1 1 ]
+ [ 1 1 1 1 ]
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2020 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+From Example 2, it is clear that the unit square [ 1 ] is not counted as a
+"rectangle". But squares in general are rectangles, so the obvious conclusion
+is that for the purposes of this Task an m x n rectangle must have m > 1 and
+n > 1. Nevertheless, the constant $MIN_DIM is provided to allow different
+constraints on the minimum dimensions of any candidate rectangle.
+
+The algorithm is an exhaustive search, beginning with each "1" element in the
+matrix which could (given the value of $MIN_DIM) be the upper, left-hand corner
+of a candidate rectangle. For each such element, two searches are conducted:
+one to the right, the other down. For example, given the following matrix:
+
+ [ 0 1 1 1 0 0 ]
+ [ 1 1 1 1 0 1 ]
+ [ 0 1 1 0 0 0 ]
+ [ 0 1 1 0 0 0 ]
+
+a right-search beginning from the element at (0, 1) yields the rectangle:
+
+ [ 1 1 1 ]
+ [ 1 1 1 ] (area 6),
+
+then a down-search beginning from the same element yields the larger rectangle:
+
+ [ 1 1 ]
+ [ 1 1 ]
+ [ 1 1 ]
+ [ 1 1 ] (area 8).
+
+Note that if more than one solution would yield a rectangle of the same maximum
+area, only the first will be output.
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+
+# The default value of $MIN-DIM is 2, ensuring that a rectangle has 4 distinct
+# corners within the matrix. Set $MIN-DIM to 1 if single-width rectangles are
+# to be allowed, e.g. [ 1 1 1 ]; but note that the unit square [ 1 ] will still
+# be excluded.
+
+const my $MIN_DIM => 2;
+
+const my $USAGE =>
+qq{Usage:
+ perl $0 [<rows> ...]
+
+ [<rows> ...] 1+ same-width rows, each a string of 1+ "1" & "0" chars\n};
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 087, Task #2: Largest Rectangle (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my $matrix = get_matrix();
+
+ print_matrix($matrix);
+
+ my ($rows, $cols) = find_max_rectangle($matrix);
+
+ if ($rows >= $MIN_DIM &&
+ $cols >= $MIN_DIM && ($rows > 1 || $cols > 1))
+ {
+ print_rectangle($rows, $cols);
+ }
+ else
+ {
+ print "Output: 0\n";
+ }
+}
+
+#------------------------------------------------------------------------------
+sub find_max_rectangle
+#------------------------------------------------------------------------------
+{
+ my ($matrix) = @_;
+ my $max_row = scalar @$matrix - $MIN_DIM;
+ my $max_col = scalar @{ $matrix->[0] } - $MIN_DIM;
+ my $max_area = 0;
+ my $max_height = 0;
+ my $max_width = 0;
+
+ for my $row (0 .. $max_row)
+ {
+ for my $col (0 .. $max_col)
+ {
+ if ($matrix->[$row][$col] eq '1')
+ {
+ for my $func (\&find_max_rect_right, \&find_max_rect_down)
+ {
+ my ($height, $width) = $func->($row, $col, $matrix);
+
+ if ((my $area = $height * $width) > $max_area)
+ {
+ $max_area = $area;
+ $max_height = $height;
+ $max_width = $width;
+ }
+ }
+ }
+ }
+ }
+
+ return ($max_height, $max_width)
+}
+
+#------------------------------------------------------------------------------
+sub find_max_rect_right
+#------------------------------------------------------------------------------
+{
+ my ($corner_row, $corner_col, $matrix) = @_;
+
+ my $max_row = scalar @$matrix - 1;
+ my $max_col = scalar @{ $matrix->[0] } - 1;
+ my $width = 1;
+
+ for my $c ($corner_col + 1 .. $max_col)
+ {
+ if ($matrix->[$corner_row][$c] eq '1')
+ {
+ ++$width;
+ }
+ else
+ {
+ last;
+ }
+ }
+
+ my $height = 1;
+
+ ROW:
+ for my $r ($corner_row + 1 .. $max_row)
+ {
+ for my $c ($corner_col .. $corner_col + $width - 1)
+ {
+ last ROW unless $matrix->[$r][$c] eq '1';
+ }
+
+ ++$height;
+ }
+
+ return ($height, $width);
+}
+
+#------------------------------------------------------------------------------
+sub find_max_rect_down
+#------------------------------------------------------------------------------
+{
+ my ($corner_row, $corner_col, $matrix) = @_;
+
+ my $max_row = scalar @{ $matrix } - 1;
+ my $max_col = scalar @{ $matrix->[0] } - 1;
+ my $height = 1;
+
+ for my $r ($corner_row + 1 .. $max_row)
+ {
+ if ($matrix->[$r][$corner_col] eq '1')
+ {
+ ++$height;
+ }
+ else
+ {
+ last;
+ }
+ }
+
+ my $width = 1;
+
+ COLUMN:
+ for my $c ($corner_col + 1 .. $max_col)
+ {
+ for my $r ($corner_row .. $corner_row + $height - 1)
+ {
+ last COLUMN unless $matrix->[$r][$c] eq '1';
+ }
+
+ ++$width;
+ }
+
+ return ($height, $width);
+}
+
+#------------------------------------------------------------------------------
+sub get_matrix
+#------------------------------------------------------------------------------
+{
+ scalar @ARGV > 0
+ or error('Missing input matrix');
+
+ my @rows = @ARGV;
+ my $width = length $rows[0];
+ my @matrix;
+
+ for my $i (0 .. $#rows)
+ {
+ my $row = $rows[$i];
+
+ $row =~ / ( [^10] ) /x
+ and error(qq[Invalid character "$1" in the input matrix]);
+
+ length $row == $width
+ or error('Inconsistent number of columns in row ' . ($i + 1));
+
+ push $matrix[$i]->@*, split(//, $row);
+ }
+
+ return \@matrix;
+}
+
+#------------------------------------------------------------------------------
+sub print_matrix
+#------------------------------------------------------------------------------
+{
+ my ($matrix) = @_;
+
+ print "Input:\n";
+
+ for my $i (0 .. $#$matrix)
+ {
+ printf " [ %s ]\n", join ' ', $matrix->[$i]->@*;
+ }
+
+ print "\n";
+}
+
+#------------------------------------------------------------------------------
+sub print_rectangle
+#------------------------------------------------------------------------------
+{
+ my ($rows, $cols) = @_;
+
+ print "Output:\n";
+
+ for (1 .. $rows)
+ {
+ print ' [ ';
+ print '1 ' for 1 .. $cols;
+ print "]\n";
+ }
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+ my ($message) = @_;
+
+ die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-087/athanasius/raku/ch-1.raku b/challenge-087/athanasius/raku/ch-1.raku
new file mode 100644
index 0000000000..26e841e59b
--- /dev/null
+++ b/challenge-087/athanasius/raku/ch-1.raku
@@ -0,0 +1,168 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 087
+=========================
+
+Task #1
+-------
+*Longest Consecutive Sequence*
+
+Submitted by: Mohammad S Anwar
+
+You are given an unsorted array of integers @N.
+
+Write a script to find the longest consecutive sequence. Print 0 if none
+sequence found.
+
+Example 1:
+
+ Input: @N = (100, 4, 50, 3, 2)
+ Output: (2, 3, 4)
+
+Example 2:
+
+ Input: @N = (20, 30, 10, 40, 50)
+ Output: 0
+
+Example 3:
+
+ Input: @N = (20, 19, 9, 11, 10)
+ Output: (9, 10, 11)
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2020 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+From the Examples, it appears that a "sequence" is an ordered set of TWO or
+more integers in which adjacent numbers differ by exactly 1. It is assumed that
+any duplicates in the input array are irrelevant to the solution and may be
+ignored.
+
+The algorithm used:
+ 1. Sort the input array in increasing numerical order.
+ 2. Create a list of sequences (an AoA) as follows: put the first element
+ into a new sequence, and then, for each succeeding element, either:
+ a. ignore it because it is equal to the previous element; or
+ b. add it to the current sequence because it is exactly one greater than
+ the last element added to that sequence; or
+ c. use it to start a new sequence.
+ 3. Find the longest sequence. If its length is 2 or more, output it, other-
+ wise output "0".
+
+=end comment
+#==============================================================================
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 087, Task #1: Longest Consecutive Sequence (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+ #| A non-empty, unsorted array of integers
+
+ *@N where { @N.elems > 0 && .all ~~ Int:D }
+)
+#==============================================================================
+{
+ my Int @n = @N.map: { .Int };
+
+ "Input: @N = (%s)\n".printf: @n.join: ', ';
+
+ my Array[Int] @sequences = find-sequences(@n);
+ my Array[Int] $longest-seq = get-longest-sequence(@sequences);
+
+ if $longest-seq.elems <= 1
+ {
+ 'Output: 0'.put;
+ }
+ else
+ {
+ "Output: (%s)\n".printf: $longest-seq.join: ', ';
+ }
+}
+
+#------------------------------------------------------------------------------
+sub find-sequences
+(
+ Int:D @N #= The input array of unsorted integers
+--> Array:D[Array:D[Int:D]] #= An array of sequences of successive integers
+)
+#------------------------------------------------------------------------------
+{
+ @N = @N.sort;
+
+ my Int $prev = @N.shift;
+ my UInt $index = 0;
+
+ my Array[Int] @seqs;
+ @seqs[$index] = Array[Int].new($prev);
+
+ for @N -> Int $current
+ {
+ next if $current == $prev;
+
+ if $current == $prev + 1
+ {
+ @seqs[$index].push: $current;
+ }
+ else
+ {
+ @seqs[++$index] = Array[Int].new($current);
+ }
+
+ $prev = $current;
+ }
+
+ return @seqs;
+}
+
+#------------------------------------------------------------------------------
+sub get-longest-sequence
+(
+ Array:D[Array:D[Int:D]] @seqs #= An array of sequences of successive
+ #= integers
+--> Array:D[Int:D] #= The longest sequence
+)
+#------------------------------------------------------------------------------
+{
+ my UInt $max-count = 0;
+ my Int @max-seq;
+
+ for @seqs -> Int @seq
+ {
+ my UInt $count = @seq.elems;
+
+ if $count > $max-count
+ {
+ $max-count = $count;
+ @max-seq = @seq;
+ }
+ }
+
+ return @max-seq;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+ $usage.put;
+}
+
+##############################################################################
diff --git a/challenge-087/athanasius/raku/ch-2.raku b/challenge-087/athanasius/raku/ch-2.raku
new file mode 100644
index 0000000000..917546fe20
--- /dev/null
+++ b/challenge-087/athanasius/raku/ch-2.raku
@@ -0,0 +1,361 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 087
+=========================
+
+Task #2
+-------
+*Largest Rectangle*
+
+Submitted by: Mohammad S Anwar
+
+You are given matrix m x n with 0 and 1.
+
+Write a script to find the largest rectangle containing only 1. Print 0 if none
+found.
+
+Example 1:
+
+ Input:
+ [ 0 0 0 1 0 0 ]
+ [ 1 1 1 0 0 0 ]
+ [ 0 0 1 0 0 1 ]
+ [ 1 1 1 1 1 0 ]
+ [ 1 1 1 1 1 0 ]
+
+ Output:
+ [ 1 1 1 1 1 ]
+ [ 1 1 1 1 1 ]
+
+Example 2:
+
+ Input:
+ [ 1 0 1 0 1 0 ]
+ [ 0 1 0 1 0 1 ]
+ [ 1 0 1 0 1 0 ]
+ [ 0 1 0 1 0 1 ]
+
+ Output: 0
+
+Example 3:
+
+ Input:
+ [ 0 0 0 1 1 1 ]
+ [ 1 1 1 1 1 1 ]
+ [ 0 0 1 0 0 1 ]
+ [ 0 0 1 1 1 1 ]
+ [ 0 0 1 1 1 1 ]
+
+ Output:
+ [ 1 1 1 1 ]
+ [ 1 1 1 1 ]
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2020 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+From Example 2, it is clear that the unit square [ 1 ] is not counted as a
+"rectangle". But squares in general are rectangles, so the obvious conclusion
+is that for the purposes of this Task an m x n rectangle must have m > 1 and
+n > 1. Nevertheless, the constant $MIN-DIM is provided to allow different
+constraints on the minimum dimensions of any candidate rectangle.
+
+The algorithm is an exhaustive search, beginning with each "1" element in the
+matrix which could (given the value of $MIN-DIM) be the upper, left-hand corner
+of a candidate rectangle. For each such element, two searches are conducted:
+one to the right, the other down. For example, given the following matrix:
+
+ [ 0 1 1 1 0 0 ]
+ [ 1 1 1 1 0 1 ]
+ [ 0 1 1 0 0 0 ]
+ [ 0 1 1 0 0 0 ]
+
+a right-search beginning from the element at (0, 1) yields the rectangle:
+
+ [ 1 1 1 ]
+ [ 1 1 1 ] (area 6),
+
+then a down-search beginning from the same element yields the larger rectangle:
+
+ [ 1 1 ]
+ [ 1 1 ]
+ [ 1 1 ]
+ [ 1 1 ] (area 8).
+
+Note that if more than one solution would yield a rectangle of the same maximum
+area, only the first will be output.
+
+=end comment
+#==============================================================================
+
+# The default value of $MIN-DIM is 2, ensuring that a rectangle has 4 distinct
+# corners within the matrix. Set $MIN-DIM to 1 if single-width rectangles are
+# to be allowed, e.g. [ 1 1 1 ]; but note that the unit square [ 1 ] will still
+# be excluded.
+
+my UInt constant $MIN-DIM = 2;
+
+# Matrix elements must be "1" or "0" only
+
+subset Element of Str where '1' | '0';
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 087, Task #2: Largest Rectangle (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+ #| 1+ same-width rows, each a string of 1+ "1" & "0" chars
+
+ *@rows where { @rows.elems > 0 && @rows[0].chars > 0 }
+)
+#==============================================================================
+{
+ my Str @str-rows = @rows;
+ my Array[Element] @matrix = get-matrix(@str-rows);
+
+ print-matrix(@matrix);
+
+ my UInt ($rows, $cols) = find-max-rectangle(@matrix);
+
+ if $rows >= $MIN-DIM &&
+ $cols >= $MIN-DIM && ($rows > 1 || $cols > 1)
+ {
+ print-rectangle($rows, $cols);
+ }
+ else
+ {
+ 'Output: 0'.put;
+ }
+}
+
+#------------------------------------------------------------------------------
+sub find-max-rectangle
+(
+ Array:D[Element:D] @matrix #= The matrix to search
+--> List:D[UInt:D] #= The height and width of the largest
+ #= rectangle found
+)
+#------------------------------------------------------------------------------
+{
+ my UInt $max-row = @matrix\ .elems - $MIN-DIM;
+ my UInt $max-col = @matrix[0].elems - $MIN-DIM;
+ my UInt $max-area = 0;
+ my UInt $max-height = 0;
+ my UInt $max-width = 0;
+
+ for 0 .. $max-row -> UInt $row
+ {
+ for 0 .. $max-col -> UInt $col
+ {
+ if @matrix[$row; $col] eq '1'
+ {
+ for &find-max-rect-right, &find-max-rect-down -> &func
+ {
+ my UInt ($height, $width) = &func($row, $col, @matrix);
+
+ if (my UInt $area = $height * $width) > $max-area
+ {
+ $max-area = $area;
+ $max-height = $height;
+ $max-width = $width;
+ }
+ }
+ }
+ }
+ }
+
+ return [$max-height, $max-width];
+}
+
+#------------------------------------------------------------------------------
+sub find-max-rect-right
+(
+ UInt:D $corner-row, #= 0-based row of the upper left corner
+ UInt:D $corner-col, #= 0-based col of the upper left corner
+ Array:D[Element:D] @matrix, #= The matrix to search
+--> List:D[UInt] #= The height and width of the largest
+ #= rectangle found by a right-search
+)
+#------------------------------------------------------------------------------
+{
+ my UInt $max-row = @matrix\ .elems - 1;
+ my UInt $max-col = @matrix[0].elems - 1;
+ my UInt $width = 1;
+
+ for $corner-col + 1 .. $max-col -> UInt $c
+ {
+ if @matrix[$corner-row; $c] eq '1'
+ {
+ ++$width;
+ }
+ else
+ {
+ last;
+ }
+ }
+
+ my UInt $height = 1;
+
+ ROW:
+ for $corner-row + 1 .. $max-row -> UInt $r
+ {
+ for $corner-col .. $corner-col + $width - 1 -> UInt $c
+ {
+ last ROW unless @matrix[$r; $c] eq '1';
+ }
+
+ ++$height;
+ }
+
+ return [$height, $width];
+}
+
+#------------------------------------------------------------------------------
+sub find-max-rect-down
+(
+ UInt:D $corner-row, #= 0-based row of the upper left corner
+ UInt:D $corner-col, #= 0-based col of the upper left corner
+ Array:D[Element:D] @matrix, #= The matrix to search
+--> List:D[UInt] #= The height and width of the largest
+ #= rectangle found by a down-search
+)
+#------------------------------------------------------------------------------
+{
+ my UInt $max-row = @matrix\ .elems - 1;
+ my UInt $max-col = @matrix[0].elems - 1;
+ my UInt $height = 1;
+
+ for $corner-row + 1 .. $max-row -> UInt $r
+ {
+ if @matrix[$r; $corner-col] eq '1'
+ {
+ ++$height;
+ }
+ else
+ {
+ last;
+ }
+ }
+
+ my UInt $width = 1;
+
+ COLUMN:
+ for $corner-col + 1 .. $max-col -> UInt $c
+ {
+ for $corner-row .. $corner-row + $height - 1 -> UInt $r
+ {
+ last COLUMN unless @matrix[$r; $c] eq '1';
+ }
+
+ ++$width;
+ }
+
+ return [$height, $width];
+}
+
+#------------------------------------------------------------------------------
+sub get-matrix
+(
+ Str:D @rows #= Matrix rows represented as strings of "1"s and "0"s
+--> Array:D[Element:D] #= The input matrix
+)
+#------------------------------------------------------------------------------
+{
+ my Array[Element] @matrix[ @rows.elems ];
+
+ my UInt $width = @rows[0].chars;
+
+ for 0 .. @rows.end -> UInt $i
+ {
+ my Str $row = @rows[$i];
+
+ $row ~~ / ( <-[ 1 0 ]> ) /
+ and error(qq[Invalid character "$0" in the input matrix]);
+
+ $row.chars == $width
+ or error(qq[Inconsistent number of columns in row { $i + 1 }]);
+
+ my Element @chars = $row.split: '', :skip-empty;
+
+ @matrix[$i] = @chars;
+ }
+
+ return @matrix;
+}
+
+#------------------------------------------------------------------------------
+sub print-matrix
+(
+ Array:D[Element:D] $matrix #= The input matrix
+)
+#------------------------------------------------------------------------------
+{
+ 'Input:'.put;
+
+ for 0 .. $matrix.end -> UInt $i
+ {
+ " [ %s ]\n".printf: $matrix[$i].join: ' ';
+ }
+
+ ''.put;
+}
+
+#------------------------------------------------------------------------------
+sub print-rectangle
+(
+ UInt:D $rows, #= The height of an all-"1" rectangle
+ UInt:D $cols #= The width of an all-"1" rectangle
+)
+#------------------------------------------------------------------------------
+{
+ 'Output:'.put;
+
+ for 1 .. $rows
+ {
+ ' [ '.print;
+
+ '1 '.print for 1 .. $cols;
+
+ ']'.put;
+ }
+}
+
+#------------------------------------------------------------------------------
+sub error
+(
+ Str:D $message #= An error message
+)
+#------------------------------------------------------------------------------
+{
+ "ERROR: $message".put;
+
+ USAGE();
+
+ exit;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+ $usage.put;
+}
+
+###############################################################################
generated by cgit (git 2.34.1) at 2026-03-20 12:30:22 +0000