Raku - Largest and Longest

by Arne Sommer

Raku - Largest and Longest

[103] Published 21. November 2020.

This is my response to the Perl Weekly Challenge #087.

Challenge #087.1: Longest Consecutive Sequence

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)

File: longest-consecutive-sequence 
#! /usr/bin/env raku

unit sub MAIN (*@N where @N.elems && all(@N) ~~ Int); # [1]

my @sorted = @N.sort.squish;                          # [2]

my @longest;                                          # [3]
my $longest = 0;                                      # [4]
my @current = @sorted.shift;                          # [5]
my $current = @current[0];                            # [6]

for @sorted -> $num                                   # [7]
{
  if $num == $current + 1                             # [8]
  {
    @current.push: $num;                              # [8a]
    $current = $num;                                  # [8b]
  }
  else                                                # [9]
  {
    if (@current.elems > $longest)                    # [9a]
    {
      @longest = @current;                            # [9b]
      $longest = @longest.elems;                      # [9c]
    }
    $current = $num;                                  # [10]
    @current = ($num);                                # [11]
  }
}

say @longest.elems > 1                                # [12]
  ?? "({ @longest.join(", ") })"                      # [12a]
  !! "0";                                             # [12b]

[1] Ensure that the values are integers, and that there is at least one of them.

[2] Sort the integers, and remove any duplicates with squish (that relies on a sorted list; use unique instead if the list is unsorted).

[3] The longest list, so far.

[4] The number of elements (numbers really) in the longest list.

[5] The working list, starting with one element.

[6] The value of the highest value in the current list.

[7] Iterate through the list.

[8] If we have the next number (current +1), add it to the list [8a] and record the new number as the highest.

[9] If not (the current number is not one above the previous one), check if the new list is longer than the old one [9a]. If so, save the new list [9b] and length [9c].

[10] We are starting a new sequence here. Record the start value,

[11] and put the value in the list.

[12] Do we have at least two elements? If so, print them [12a]. If not, print zero [12b].

See docs.raku.org/routine/squish for more information about squish.

See docs.raku.org/routine/unique for more information about unique.

Running it on the examples: 

$ ./longest-consecutive-sequence 100 4 50 3 2
(2, 3, 4)

$ ./longest-consecutive-sequence 20 30 10 40 50
0

$ ./longest-consecutive-sequence 20 19 9 11 10
(9, 10, 11)

A Perl Version

This is straight forward translation of the Raku version.

File: longest-consecutive-sequence-perl 
#! /usr/bin/env perl

use strict;
use feature 'say';
use List::Util qw(all uniq);
 
die "At least 1 value" unless @ARGV;
die "Integers only" unless all { $ ~= /^\-?\d+$/ } @ARGV;

my @sorted = uniq sort { $a <=> $b } @ARGV;      # [1]

my @longest;
my $longest = 0;
my @current = shift(@sorted);
my $current = $current[0];

for my $num (@sorted)
{
  if ($num == $current + 1)
  {
    push(@current, $num);
    $current = $num;
  }
  else
  {
    if (@current > $longest)
    {
      @longest = @current;
      $longest = @longest;
    }
    $current = $num;
    @current = ($num);
  }
}

say @longest > 1
  ? "(" . join(", ", @longest) . ")"
  : "0";

[1] Make sure that we sort the values numerically (with <=>), and not as texts (as we do not want the third example sorted as «10 11 19 20 9»).

Running it gives the same result as the Raku version: 

$ ./longest-consecutive-sequence-perl 100 4 50 3 2
(2, 3, 4)

$ ./longest-consecutive-sequence-perl 20 30 10 40 50
0

$ ./longest-consecutive-sequence-perl 20 19 9 11 10
(9, 10, 11)

Challenge #087.2: Largest Rectangle

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 ]

it follows from the second example that a single «1» does not form a rectangle. It is not clear if two «1»s on a row (or column) form a rectangle, so I have chosen to disregard rectangles with 1 row or column.

The first problem is how to specify the matrices to the program. I have chosen to place them in their own (text) files, like this:

File: example1.txt 
[ 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 ]

Reading a matrix from a file is a repetition of what I did in the second part of Four Corners with Raku, my response to the Perl Weekly Challenge #084. (Except that I have added the brackets this time, as introduced in the second part of A Different Puzzle with Raku and Perl, my response to the Perl Weekly Challenge #086.)

File: largest-rectangle (partial) 
#! /usr/bin/env raku

subset BinaryDigit where /^<[01]>$/;                                 # [1]

unit sub MAIN ($rectangle where $rectangle.IO.f && $rectangle.IO.r   # [2]
                  = 'sample1.txt',
	       :v(:$verbose), :s(:$show), :h($html));                # [3]

my @rectangle =
    $rectangle.IO.lines.map( *.words.grep(BinaryDigit) )>>.Array;    # [4]

my $rows = @rectangle.elems;                                         # [5]
my $cols = @rectangle[0].elems;                                      # [6]

die "All rows must have the same length"
       unless [==] @(@rectangle)>>.elems;                            # [7]

my $col-blue  = "\e[44m";                                            # [3a]
my $col-green = "\e[42m";
my $col-red   = "\e[101m";
my $col-stop  = "\e[0m";


if ($html)                                                           # [3b]
{
  $col-blue  = '<span class="text-primary">';
  $col-green = '<span class="text-success">';
  $col-red   = '<span class="text-danger">';
  $col-stop  = '';
}

[1] We allow 0 and 1 in the matrix, so we set up a custom type (with code>subset) to make validation easier.

[2] Ensure that we get a filename as parameter.

[3] I'll get back to these later on.

[4] Read the matrix, split it into a list of list, and assign it to a two-dimentional array.

[5] Get the number of rows (for use in loops, later on).

[6] Get the number of columns (ditto), for the top row.

[7] Ensure that all the rows have the same number of columns.

See docs.raku.org/language/typesystem#index-entry-subset-subset for more information about subset.

I have chosen to iterate through all the cells, and generate all the possible rectangles. Note the upper limit, so that we have at elast two rows and columns for the rectangles.

(We'll sort the list of rectangles later on, by size, and pick the first one we encounter with only 1s.)

File: largest-rectangle (partial) 
my @partials;

for 0 .. $rows -1 -> $start-row                                # [8]
{
  for 0 .. $cols -1 -> $start-col                              # [9]
  {
    if @rectangle[$start-row][$start-col] == 0                 # [10]
    {
      say ": [$start-row,$start-col] skipped (is 0)" if $verbose;
      next;
    }

    for $start-row +1 .. $rows -1 -> $stop-row                 # [11]
    {
      for $start-col +1 .. $cols -1 -> $stop-col               # [12]
      {
        @partials.push(partial.new(:$start-row, :$stop-row,
                                   :$start-col, :$stop-col));  # [13]
	@partials[*-1].debug-output.say if $verbose;           # [14]
      }
    }
  }
}

4 loops inside each other is not very efficient, but it does not really matter as long as the matrices are small. As the examples are. (The short circuit filter in [10] helps somewhat.)

[8] For each row (except the last one).

[9] For each column (excpet the last one).

[10] Skip the cell (with next) if it is 0. This is a quick optimisation, as the rectangles must contain nothing but 1s. The rest is harder to check, so we do that later on.

[11] [8] and [9] gave us the start position, and this one gives the end position (row).

[12] End column if the end position.

[13] Generate a «partial» object (explained in the next section) and save it.

[14] Verbose output, if requested. This is done with a method on the object. The [*-1] syntax gives the last element in the array, which is the one we just added (in [13] with push).

File: largest-rectangle (partial) 
class partial                                          # [15]
{
  has $.start-row;                                     # [15a]
  has $.start-col;                                     # [15b]
  has $.stop-row;                                      # [15c]
  has $.stop-col;                                      # [15d]

  method size                                          # [16]
  {
    return (self.stop-row - self.start-row + 1) *
           (self.stop-col - self.start-col + 1);
  }

  method all-one                                       # [17]
  {
    for self.start-row .. self.stop-row -> $row
    {
      for self.start-col .. self.stop-col -> $col
      {
        return False if @rectangle[$row][$col] == 0;
      }
    }
    return True;
  }

  method debug-output                                 # [18]
  {
    return ": [{ self.start-row },{ self.start-col } -> \
     { self.stop-row },{ self.stop-col }] -> \
     { self.size } -> { self.all-one }";
  }

  method show                                         # [19]
  {
    for self.start-row .. self.stop-row -> $row
    {
      print "[ ";
      for self.start-col .. self.stop-col -> $col
      {
        print @rectangle[$row][$col] ~ " ";
      }
      say "]";
    }
  }
}

[15] The class, with four variables; the upper left corner ([15a] and [15b]), and the lower right corner ([15c] and [16d]) of the rectangle.

[16] A method calculating the size of the rectangle. We need this, as the challenge wanted the largest one.

[17] Does the rectangle contain 1s only?

[18] Used by Verbose mode only.

[19] Show the rectangle. This is used to print the answer to the challenge.

File: largest-rectangle (partial) 
say "" if $verbose;

my @sorted = @partials.sort({ $^b.size <=> $^a.size });  # [20]

for @sorted -> $candidate                                # [21]
{
  $candidate.debug-output.say if $verbose;               # [22]
  if $candidate.all-one                                  # [23]
  {
    coloured-matrix($candidate.start-row, $candidate.start-col,  # [24]
                    $candidate.stop-row, $candidate.stop-col) if $show;
    say "" if $verbose || $show;
    $candidate.show;                                     # [25]
    exit;                                                # [25a]
  }
}

sub coloured-matrix ($start-row, $start-col, $stop-row, $stop-col)  # [27]
{
  for ^$rows -> $row
  {
    print "[ ";
    for ^$cols -> $col
    {
      print $start-row <= $row <= $stop-row &&
  	    $start-col <= $col <= $stop-col
       ?? ( $col-green ~ @rectangle[$row][$col] ~ $col-stop ~ " " )
       !! ( @rectangle[$row][$col] ~ " " );

    }
    say "]";
  }
}

say 0;                                                   # [26]

[20] Sort the rectangles, by the size, with the largest first (as we have swapped the placeholders).

[21] Iterate over the (sorted) rectangles.

[22] The same verbose output as in [14], but this time sorted by rectangle size.

[23] The first one we encounter with only 1s is the answer,

[24] Show the original matrix, with the rectangle highlighted, if requested.

[25] Print the rectangle and exit, as we are done.

[26] No rectangles with only 1s? Then print 0.

[27] Print the matrix, with the values inside the spcified rectangle coloured.

Running it on the examples: 

$ ./largest-rectangle example1.txt
[ 1 1 1 1 1 ]
[ 1 1 1 1 1 ]

$ ./largest-rectangle example2.txt
0

$ ./largest-rectangle example3.txt
[ 1 1 1 1 ]
[ 1 1 1 1 ]

With «show» enabled, to see where the rectangles come from: 

$ ./largest-rectangle -s example1.txt
[ 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 ]

[ 1 1 1 1 1 ]
[ 1 1 1 1 1 ]

$ ./largest-rectangle -s example2.txt
0

$ ./largest-rectangle -s example3.txt
[ 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 ]

[ 1 1 1 1 ]
[ 1 1 1 1 ]

With Verbose mode: 

$ ./largest-rectangle -v example1.txt
: [0,0] skipped (is 0)
: [0,1] skipped (is 0)
: [0,2] skipped (is 0)
: [0,3 -> 1,4] -> 4 -> False
: [0,3 -> 1,5] -> 6 -> False
: [0,3 -> 2,4] -> 6 -> False
: [0,3 -> 2,5] -> 9 -> False
: [0,3 -> 3,4] -> 8 -> False
: [0,3 -> 3,5] -> 12 -> False
: [0,3 -> 4,4] -> 10 -> False
: [0,3 -> 4,5] -> 15 -> False
…

The first three lines are for the first 3 cells on the top row. They have a 0, so we can skip creating rectangles starting there (as they cannot contain only 1s).

The rest is for the 4th cell (with index 3). The values inside the brackets are the cooridinates for the upper left and the lower right corner of the rectangle. The next value is the size (number of cells), and finally we see if the rectangle contains only 1s. (None of them does.)

The illustrations shows the 8 different rectanges we got starting at [0,3]:

Cells with 1 are shown as green, and cells with 0 are shown as red.

The rest of the output: 

: [0,4] skipped (is 0)
: [0,5] skipped (is 0)
: [1,0 -> 2,1] -> 4 -> False
: [1,0 -> 2,2] -> 6 -> False
: [1,0 -> 2,3] -> 8 -> False
: [1,0 -> 2,4] -> 10 -> False
: [1,0 -> 2,5] -> 12 -> False
: [1,0 -> 3,1] -> 6 -> False
: [1,0 -> 3,2] -> 9 -> False
: [1,0 -> 3,3] -> 12 -> False
: [1,0 -> 3,4] -> 15 -> False
: [1,0 -> 3,5] -> 18 -> False
: [1,0 -> 4,1] -> 8 -> False
: [1,0 -> 4,2] -> 12 -> False
: [1,0 -> 4,3] -> 16 -> False
: [1,0 -> 4,4] -> 20 -> False
: [1,0 -> 4,5] -> 24 -> False
: [1,1 -> 2,2] -> 4 -> False
: [1,1 -> 2,3] -> 6 -> False
: [1,1 -> 2,4] -> 8 -> False
: [1,1 -> 2,5] -> 10 -> False
: [1,1 -> 3,2] -> 6 -> False
: [1,1 -> 3,3] -> 9 -> False
: [1,1 -> 3,4] -> 12 -> False
: [1,1 -> 3,5] -> 15 -> False
: [1,1 -> 4,2] -> 8 -> False
: [1,1 -> 4,3] -> 12 -> False
: [1,1 -> 4,4] -> 16 -> False
: [1,1 -> 4,5] -> 20 -> False
: [1,2 -> 2,3] -> 4 -> False
: [1,2 -> 2,4] -> 6 -> False
: [1,2 -> 2,5] -> 8 -> False
: [1,2 -> 3,3] -> 6 -> False
: [1,2 -> 3,4] -> 9 -> False
: [1,2 -> 3,5] -> 12 -> False
: [1,2 -> 4,3] -> 8 -> False
: [1,2 -> 4,4] -> 12 -> False
: [1,2 -> 4,5] -> 16 -> False
: [1,3] skipped (is 0)
: [1,4] skipped (is 0)
: [1,5] skipped (is 0)
: [2,0] skipped (is 0)
: [2,1] skipped (is 0)
: [2,2 -> 3,3] -> 4 -> False
: [2,2 -> 3,4] -> 6 -> False
: [2,2 -> 3,5] -> 8 -> False
: [2,2 -> 4,3] -> 6 -> False
: [2,2 -> 4,4] -> 9 -> False
: [2,2 -> 4,5] -> 12 -> False
: [2,3] skipped (is 0)
: [2,4] skipped (is 0)
: [3,0 -> 4,1] -> 4 -> True
: [3,0 -> 4,2] -> 6 -> True
: [3,0 -> 4,3] -> 8 -> True
: [3,0 -> 4,4] -> 10 -> True
: [3,0 -> 4,5] -> 12 -> False
: [3,1 -> 4,2] -> 4 -> True
: [3,1 -> 4,3] -> 6 -> True
: [3,1 -> 4,4] -> 8 -> True
: [3,1 -> 4,5] -> 10 -> False
: [3,2 -> 4,3] -> 4 -> True
: [3,2 -> 4,4] -> 6 -> True
: [3,2 -> 4,5] -> 8 -> False
: [3,3 -> 4,4] -> 4 -> True
: [3,3 -> 4,5] -> 6 -> False
: [3,4 -> 4,5] -> 4 -> False
: [3,5] skipped (is 0)
: [4,5] skipped (is 0)

: [1,0 -> 4,5] -> 24 -> False
: [1,0 -> 4,4] -> 20 -> False
: [1,1 -> 4,5] -> 20 -> False
: [1,0 -> 3,5] -> 18 -> False
: [1,0 -> 4,3] -> 16 -> False
: [1,1 -> 4,4] -> 16 -> False
: [1,2 -> 4,5] -> 16 -> False
: [0,3 -> 4,5] -> 15 -> False
: [1,0 -> 3,4] -> 15 -> False
: [1,1 -> 3,5] -> 15 -> False
: [0,3 -> 3,5] -> 12 -> False
: [1,0 -> 2,5] -> 12 -> False
: [1,0 -> 3,3] -> 12 -> False
: [1,0 -> 4,2] -> 12 -> False
: [1,1 -> 3,4] -> 12 -> False
: [1,1 -> 4,3] -> 12 -> False
: [1,2 -> 3,5] -> 12 -> False
: [1,2 -> 4,4] -> 12 -> False
: [2,2 -> 4,5] -> 12 -> False
: [3,0 -> 4,5] -> 12 -> False
: [0,3 -> 4,4] -> 10 -> False
: [1,0 -> 2,4] -> 10 -> False
: [1,1 -> 2,5] -> 10 -> False
: [3,0 -> 4,4] -> 10 -> True

[ 1 1 1 1 1 ]
[ 1 1 1 1 1 ]

We can optimize the program a little bit, by moving the «.all-one» check to the construction phase, so that we can sort only the rectangles that have 1s only, and not all of them (with 1 in the upper left corner).

File: largest-rectangle2 (changes only) 
      for $start-col +1 .. $cols -1 -> $stop-col
      {
      my $partial = partial.new(:$start-row, :$stop-row,
 	                        :$start-col, :$stop-col);
	$partial.debug-output.say if $verbose;
	@partials.push: $partial if $partial.all-one;
      }
    }
  }
}

say "" if $verbose;

my @sorted = @partials.sort({ $^b.size <=> $^a.size });

if @sorted
{
  @sorted>>.debug-output>>.say if $verbose;  # [1]

  my $candidate = @sorted[0];
  
  coloured-matrix($candidate.start-row, $candidate.start-col,
                  $candidate.stop-row, $candidate.stop-col) if $show;

[1] This calls the «.debug-output» method on all the elements (objects) in the array, and then .say on each one so that we get a newline after each line.

Running it shows the difference in Verbose mode. The original program shows all the rectangles sorted by decreasing size until we find a match (all 1s). This one shows all the rectangles that are 1s only, also sorted by decreasing size. 

$ ./largest-rectangle2 -v example3.txt
: [0,0] skipped (is 0)
: [0,1] skipped (is 0)
: [0,2] skipped (is 0)
: [0,3 -> 1,4] -> 4 -> True
: [0,3 -> 1,5] -> 6 -> True
: [0,3 -> 2,4] -> 6 -> False
: [0,3 -> 2,5] -> 9 -> False
: [0,3 -> 3,4] -> 8 -> False
: [0,3 -> 3,5] -> 12 -> False
: [0,3 -> 4,4] -> 10 -> False
: [0,3 -> 4,5] -> 15 -> False
: [0,4 -> 1,5] -> 4 -> True
: [0,4 -> 2,5] -> 6 -> False
: [0,4 -> 3,5] -> 8 -> False
: [0,4 -> 4,5] -> 10 -> False
: [1,0 -> 2,1] -> 4 -> False
: [1,0 -> 2,2] -> 6 -> False
: [1,0 -> 2,3] -> 8 -> False
: [1,0 -> 2,4] -> 10 -> False
: [1,0 -> 2,5] -> 12 -> False
: [1,0 -> 3,1] -> 6 -> False
: [1,0 -> 3,2] -> 9 -> False
: [1,0 -> 3,3] -> 12 -> False
: [1,0 -> 3,4] -> 15 -> False
: [1,0 -> 3,5] -> 18 -> False
: [1,0 -> 4,1] -> 8 -> False
: [1,0 -> 4,2] -> 12 -> False
: [1,0 -> 4,3] -> 16 -> False
: [1,0 -> 4,4] -> 20 -> False
: [1,0 -> 4,5] -> 24 -> False
: [1,1 -> 2,2] -> 4 -> False
: [1,1 -> 2,3] -> 6 -> False
: [1,1 -> 2,4] -> 8 -> False
: [1,1 -> 2,5] -> 10 -> False
: [1,1 -> 3,2] -> 6 -> False
: [1,1 -> 3,3] -> 9 -> False
: [1,1 -> 3,4] -> 12 -> False
: [1,1 -> 3,5] -> 15 -> False
: [1,1 -> 4,2] -> 8 -> False
: [1,1 -> 4,3] -> 12 -> False
: [1,1 -> 4,4] -> 16 -> False
: [1,1 -> 4,5] -> 20 -> False
: [1,2 -> 2,3] -> 4 -> False
: [1,2 -> 2,4] -> 6 -> False
: [1,2 -> 2,5] -> 8 -> False
: [1,2 -> 3,3] -> 6 -> False
: [1,2 -> 3,4] -> 9 -> False
: [1,2 -> 3,5] -> 12 -> False
: [1,2 -> 4,3] -> 8 -> False
: [1,2 -> 4,4] -> 12 -> False
: [1,2 -> 4,5] -> 16 -> False
: [1,3 -> 2,4] -> 4 -> False
: [1,3 -> 2,5] -> 6 -> False
: [1,3 -> 3,4] -> 6 -> False
: [1,3 -> 3,5] -> 9 -> False
: [1,3 -> 4,4] -> 8 -> False
: [1,3 -> 4,5] -> 12 -> False
: [1,4 -> 2,5] -> 4 -> False
: [1,4 -> 3,5] -> 6 -> False
: [1,4 -> 4,5] -> 8 -> False
: [2,0] skipped (is 0)
: [2,1] skipped (is 0)
: [2,2 -> 3,3] -> 4 -> False
: [2,2 -> 3,4] -> 6 -> False
: [2,2 -> 3,5] -> 8 -> False
: [2,2 -> 4,3] -> 6 -> False
: [2,2 -> 4,4] -> 9 -> False
: [2,2 -> 4,5] -> 12 -> False
: [2,3] skipped (is 0)
: [2,4] skipped (is 0)
: [3,0] skipped (is 0)
: [3,1] skipped (is 0)
: [3,2 -> 4,3] -> 4 -> True
: [3,2 -> 4,4] -> 6 -> True
: [3,2 -> 4,5] -> 8 -> True
: [3,3 -> 4,4] -> 4 -> True
: [3,3 -> 4,5] -> 6 -> True
: [3,4 -> 4,5] -> 4 -> True
: [4,0] skipped (is 0)
: [4,1] skipped (is 0)

: [3,2 -> 4,5] -> 8 -> True
: [0,3 -> 1,5] -> 6 -> True
: [3,2 -> 4,4] -> 6 -> True
: [3,3 -> 4,5] -> 6 -> True
: [0,3 -> 1,4] -> 4 -> True
: [0,4 -> 1,5] -> 4 -> True
: [3,2 -> 4,3] -> 4 -> True
: [3,3 -> 4,4] -> 4 -> True
: [3,4 -> 4,5] -> 4 -> True

[ 1 1 1 1 ]
[ 1 1 1 1 ]

Bonus

I had a go at beeing smart that did not pan out, before doing the brute force approach as described above.

The idea was to start by removing the 1s (i.e. replacing them with 0s) that could not be part of a rectangle, to make it easier to identify the possible rectangles later on.

It does the removal by inspecting the four 2x2 rectangles the current cell can be part of, and keeping the value if at least one of them has 1s only.

File: largest-rectangle-cleanup 
#! /usr/bin/env raku

subset BinaryDigit where /^<[01]>$/;

unit sub MAIN ($rectangle where $rectangle.IO.f && $rectangle.IO.r
                 = 'sample1.txt',
	       :v(:$verbose));

my @rectangle = $rectangle.IO.lines.map( *.words.grep(BinaryDigit) )>>.Array;

my $rows = @rectangle.elems;
my $cols = @rectangle[0].elems;

die "All rows must have the same length" unless [==] @(@rectangle)>>.elems;

my $pass = 1;
my $sum  = @rectangle>>.sum.sum;

LOOP: loop
{
  say ": Pass: { $pass++ }" if $verbose;

  for ^$rows -> $row
  {
    for ^$cols -> $col 
    {
      next if @rectangle[$row][$col] == 0;

      next if box4($row -1, $col -1) || box4($row, $col -1) || 
              box4($row -1, $col   ) || box4($row, $col   );

     @rectangle[$row][$col] = 0;
    }
  }

  my $new-sum = @rectangle>>.sum.sum;
  last if $new-sum == $sum;
  $sum = $new-sum;
}

say @$_ for @rectangle;

sub box4 ($row, $col)
{
  say ": box4($row, $col)" if $verbose;
  my $a = @rectangle[$row  ][$col  ] // return False;
  my $b = @rectangle[$row+1][$col  ] // return False;
  my $c = @rectangle[$row  ][$col+1] // return False;
  my $d = @rectangle[$row+1][$col+1] // return False;

  if $a + $b + $c + $d == 4
  {
    say ": - ok" if $verbose;
    return True;
  }

  return False;
}

Running it on the examples: 

$ ./largest-rectangle-cleanup ../example1.txt 
[0 0 0 0 0 0]
[0 0 0 0 0 0]
[0 0 0 0 0 0]
[1 1 1 1 1 0]
[1 1 1 1 1 0]

$ ./largest-rectangle-cleanup ../example2.txt 
[0 0 0 0 0 0]
[0 0 0 0 0 0]
[0 0 0 0 0 0]
[0 0 0 0 0 0]

$ ./largest-rectangle-cleanup ../example3.txt 
[0 0 0 1 1 1]
[0 0 0 1 1 1]
[0 0 0 0 0 0]
[0 0 1 1 1 1]
[0 0 1 1 1 1]

I stopped there. This approach had a «brute force»-ish feel, whithout actually solving the challenge. The third example shows that we have two candidates, and the task of picking one of them remains. So I decided to go for brute force instead, from scratch.

Perl ?

I did not have time for a Perl version of this one.

And that's it.

Links
 About me
 Keyword Index
Raku Courses
 Beginning Raku (book)
 RSS Feed
 Code (zip)
Reddit Comments