laurent_r

These are some answers to the Week 84 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days (November 1, 2020). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Reverse Integer

You are given an integer $N.

Write a script to reverse the given integer and print the result. Print 0 if the result doesn’t fit in 32-bit signed integer.

The number 2,147,483,647 is the maximum positive value for a 32-bit signed binary integer in computing.

Example 1:

Input: 1234
Output: 4321

Example 2:

Input: -1234
Output: -4321

Example 3:

Input: 1231230512
Output: 0

Note that the minimal value for signed negative integers is - 2 ** 31, i.e. - 2,147,483,648.

Reverse Integer in Raku

We first check if the input integer is negative and, if so, we take its absolute value and record the fact that the input was negative. Then, we just flip the digits. We set the result to 0 if the result exceeds the 32-bit limit for signed integers. We turn the result to a negative integer if the input integer was negative (and, by the way, numify the result to get rid of leading 0’s if any.

use v6;

constant $max = 2 ** 31 - 1; # i.e. 2_147_483_647

my $input = @*ARGS[0] // 1234;
my $positive = True;
if $input < 0 {
    $positive = False;
    $input = -$input;
}
my $output = $input.flip;
$output = 0 if $positive and $output >= $max;
$output = 0 if $output >= $max + 1; # 32-bit negative numbers can go up to 2 ** 31
# No specification for inputs ending with 0
# We numify $output and negate it if needed
$output = $positive ?? +$output !! -$output;
say $output;

Sample output for a few input values:

$ raku reverse-int.raku
4321

$ raku reverse-int.raku -1234
-4321

$ raku reverse-int.raku 1231230512
0

$ raku reverse-int.raku 1231230500
50321321

$ raku reverse-int.raku -1231230500
-50321321

Reverse Integer in Perl

This is simply a port to Perl of the Raku program above, please refer to the explanations above if needed.

use strict;
use warnings;
use feature "say";
use constant MAX => 2 ** 31 - 1; # i.e. 2_147_483_647

my $input = shift  // 1234;
my $positive = 1;
if ($input < 0) {
    $positive = 0;
    $input = -$input;
}
my $output = reverse $input;
$output = 0 if $positive and $output > MAX;
$output = 0 if $output > MAX + 1;
# No specification for inputs ending with 0
# We numify $output and negate it if needed
$output = $positive ? $output + 0 : -$output;
say $output;

Output for a few sample input values:

$ perl reverse-int.pl
4321

$ perl reverse-int.pl -1234
-4321

$ perl reverse-int.pl 1231230512
0

$ perl reverse-int.pl 1231230500
50321321

$ perl reverse-int.pl -1231230500
-50321321

Reverse Integer in Scala

This section with a Scala solution was added on Jan. 16, 2021. This is basically a port to Scala of the Raku and Perl solutions above.

object reverseInt extends App {
  val max: Long = (math.pow(2, 31) - 1).toLong
  val tests = List(1234, 678, -12, 432, 1147483647)
  for (item <- tests) {
    val result = flip(item)
    println(s"$item : $result")
  }
  def flip(input: Int): Int = {
    val negative = if (input < 0) true else false
    val in = input.abs
    val flipped = in.toString.reverse;
    if (negative) {
      if (flipped.toLong > max + 1) return 0
      return -1 * flipped.toInt
    } else {
      if (flipped.toLong > max) return 0
      return flipped.toInt
    }

  }
}

This program displays the following output:

1234 : 4321
678 : 876
-12 : -21
432 : 234
1147483647 : 0

Task 2: Find Square Matrices

You are given matrix of size m x n with only 1 and 0.

Write a script to find the count of squares having all four corners set as 1.

Example 1:

Input: [ 0 1 0 1 ]
       [ 0 0 1 0 ]
       [ 1 1 0 1 ]
       [ 1 0 0 1 ]

Output: 1

Explanation:
There is one square (3x3) in the given matrix with four corners as 1 starts at r=1;c=2.

[ 1 0 1 ]
[ 0 1 0 ]
[ 1 0 1 ]

Example 2:

Input: [ 1 1 0 1 ]
       [ 1 1 0 0 ]
       [ 0 1 1 1 ]
       [ 1 0 1 1 ]

Output: 4

Explanation:
There is one square (4x4) in the given matrix with four corners as 1 starts at r=1;c=1.
There is one square (3x3) in the given matrix with four corners as 1 starts at r=1;c=2.
There are two squares (2x2) in the given matrix with four corners as 1. First starts at r=1;c=1 and second starts at r=3;c=3.

Example 3:

Input: [ 0 1 0 1 ]
       [ 1 0 1 0 ]
       [ 0 1 0 0 ]
       [ 1 0 0 1 ]

Output: 0

Find Square Matrices in Raku

We first define an array of arrays of arrays representing an array of four matrices for our tests. We define a simple print-matrix subroutine to display any matrix in a human-eye friendly format. All the work is done in the find-squares subroutine, which contains three nested for loops: we loop on the possible square matrix sizes (between 2 and the smaller dimension of the input matrix), and then, for each possible size, we loop on each matrix item to see if that item can be the top left corner of a square matrix of the relevant size with each corner set to 1. If any of the four corners is 0, we move to the next item or to the next possible size once we have visited all relevant items with one size. Note that we print much more than what is requested in the task specification because we want to check the results (it would be very easy to remove these extra printed lines by commenting out the say statement near the end of the find-squares subroutine).

my @mat = [ [ [<0 1 0 1>], [<0 0 1 0>], [<1 1 0 1>], [<1 0 0 1>] ], 
            [ [<1 1 0 1>], [<1 1 0 0>], [<0 1 1 1>], [<1 0 1 1>] ],
            [ [<0 1 0 1>], [<1 0 1 0>], [<0 1 0 0>], [<1 0 0 1>] ],
            [ [<1 1 0 1 1 1>], [<1 1 1 0 1 0>], [<1 1 0 1 0 1>], 
                [<1 1 1 0 0 1>] ],
          ];

for @mat -> @m {
    print-matrix @m;
    say "Number of matrices: ", find-squares(@m), "\n";
}
sub print-matrix (@matrix) {
    for @matrix -> @row {
        say '[ ', @row.join(" "), ' ]';
    }
    say " ";
}

sub find-squares (@matrix) {
    my $nb_lines = @matrix.elems;
    my $nb_col = @matrix[0].elems;
    my $nb_squares = 0;
    my $max_square_size = min $nb_lines, $nb_col;
    for 2..$max_square_size -> $square_size {
        for 0..$nb_col - $square_size -> $j {
            for 0..$nb_lines - $square_size -> $i {
                next if @matrix[$i][$j] == 0;
                next if @matrix[$i][$j+$square_size-1] == 0;
                next if @matrix[$i+$square_size-1][$j] == 0;
                next if @matrix[$i+$square_size-1][$j+$square_size-1] == 0;
                say "Value in position $i, $j is the top left corner of a square of size $square_size";
                $nb_squares++;
            }
        }
    }
    return $nb_squares;
}

With the four sample input matrices, the program displays the following results:

[ 0 1 0 1 ]
[ 0 0 1 0 ]
[ 1 1 0 1 ]
[ 1 0 0 1 ]

Value in position 0, 1 is the top left corner of a square of size 3
Number of matrices: 1

[ 1 1 0 1 ]
[ 1 1 0 0 ]
[ 0 1 1 1 ]
[ 1 0 1 1 ]

Value in position 0, 0 is the top left corner of a square of size 2
Value in position 2, 2 is the top left corner of a square of size 2
Value in position 0, 1 is the top left corner of a square of size 3
Value in position 0, 0 is the top left corner of a square of size 4
Number of matrices: 4

[ 0 1 0 1 ]
[ 1 0 1 0 ]
[ 0 1 0 0 ]
[ 1 0 0 1 ]  
Number of matrices: 0

[ 1 1 0 1 1 1 ]
[ 1 1 1 0 1 0 ]
[ 1 1 0 1 0 1 ]
[ 1 1 1 0 0 1 ]

Value in position 0, 0 is the top left corner of a square of size 2
Value in position 1, 0 is the top left corner of a square of size 2
Value in position 2, 0 is the top left corner of a square of size 2
Value in position 1, 0 is the top left corner of a square of size 3
Value in position 0, 1 is the top left corner of a square of size 3
Value in position 0, 3 is the top left corner of a square of size 3
Number of matrices: 6

Find Square Matrices in Perl

This is a port to Perl of the Raku program immediately above, please refer to the explanations above if needed.

use strict;
use warnings;
use feature "say";

my @mat = ( [ [ qw<0 1 0 1> ], [ qw<0 0 1 0> ], [ qw<1 1 0 1> ], 
              [ qw<1 0 0 1> ] ], 
            [ [ qw<1 1 0 1> ], [ qw<1 1 0 0> ], [ qw<0 1 1 1> ], 
              [ qw<1 0 1 1> ] ],
            [ [ qw<0 1 0 1> ], [ qw<1 0 1 0> ], [ qw<0 1 0 0> ], 
              [ qw<1 0 0 1> ] ],
            [ [ qw<1 1 0 1 0 1> ], [ qw<1 0 1 0 1 1> ], 
              [ qw<1 1 0 0 1 0> ], [ qw<1 1 0 1 1 1> ] ],
          );

for my $m_ref (@mat) {
    print_matrix($m_ref);
    say "Number of matrices: ", find_squares($m_ref);
}
sub print_matrix {
    my @matrix = @{$_[0]};
    say "";
    for my $row (@matrix) {
        say '[ ', join (" ", @$row), ' ]';
    }
    say " ";
}

sub find_squares {
    my @matrix = @{$_[0]};
    my $nb_lines = scalar @matrix;
    my $nb_col = scalar @{$matrix[0]};
    my $nb_squares = 0;
    my $max_square_size = $nb_lines > $nb_col ? $nb_col : $nb_lines;
    for my $square_size (2..$max_square_size) {
        for my $j (0..$nb_col - $square_size) {
            for my $i (0..$nb_lines - $square_size) {
                next if $matrix[$i][$j] == 0;
                next if $matrix[$i][$j+$square_size-1] == 0;
                next if $matrix[$i+$square_size-1][$j] == 0;
                next if $matrix[$i+$square_size-1][$j+$square_size-1] == 0;
                say "Value in position $i, $j is the top left corner of a square of size $square_size";
                $nb_squares++;
            }
        }
    }
    return $nb_squares;
}

With the four sample input matrices, the program displays the following results:

$ perl square-matrix.pl

[ 0 1 0 1 ]
[ 0 0 1 0 ]
[ 1 1 0 1 ]
[ 1 0 0 1 ]

Value in position 0, 1 is the top left corner of a square of size 3
Number of matrices: 1

[ 1 1 0 1 ]
[ 1 1 0 0 ]
[ 0 1 1 1 ]
[ 1 0 1 1 ]

Value in position 0, 0 is the top left corner of a square of size 2
Value in position 2, 2 is the top left corner of a square of size 2
Value in position 0, 1 is the top left corner of a square of size 3
Value in position 0, 0 is the top left corner of a square of size 4
Number of matrices: 4

[ 0 1 0 1 ]
[ 1 0 1 0 ]
[ 0 1 0 0 ]
[ 1 0 0 1 ]

Number of matrices: 0

[ 1 1 0 1 0 1 ]
[ 1 0 1 0 1 1 ]
[ 1 1 0 0 1 0 ]
[ 1 1 0 1 1 1 ]

Value in position 2, 0 is the top left corner of a square of size 2
Value in position 0, 0 is the top left corner of a square of size 4
Number of matrices: 2

Note that the last example input matrix is not the same as the one in the Raku program, this is the reason why the result is different.

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, November, 8, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.