# RogerBW's Blog

Perl Weekly Challenge 84: Reverse squares 28 October 2020

I’ve been doing the Perl Weekly Challenges. The latest involved reversing integers and a two-dimensional search. (Note that this is open until 1 November 2020.)

# 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 first part is easy, of course. The second is rather harder: all four of the languages I'm using have larger standard integer types than 32 bits.

So in Perl we have:

``````  my \$r=join('',reverse split '',\$s);
if (\$r =~ /([0-9]+)-\$/) {
\$r="-\$1";
}
``````

Raku, with more complicated regexp syntax:

``````  my \$r=\$s.comb.reverse.join('');
if (\$r ~~ /(<[0..9]>+)\-\$/) {
\$r="-\$0";
}
``````

Python:

``````    a=str(s)[::-1]
if (a[-1] == '-'):
a='-' + a[0:-1]
``````

Ruby:

``````    a=str(s)[::-1]
if (a[-1] == '-'):
a='-' + a[0:-1]
``````

But how do we test whether the thing will fit into 32-bit signed?

Well, these languages may not have 32-bit data types, but they can encode/decode them for use with packed formats. So in Perl:

``````  if (unpack('l',pack('l',\$r)) != \$r) {
return 0;
}
return \$r;
``````

Python (needs a cast to integer):

``````    a=int(a)
try:
b=struct.pack('<l',a)
except struct.error as err:
return 0
return a
``````

Ruby (ditto):

``````  r=Integer(r)
b=[r].pack('l').unpack('l')
if b != r
return 0
end
return r
``````

But what about Raku? Well, its `pack` is still very primitive. But unlike the other languages here it does have an explicitly 32-bit-wide integer type. So I cast to that (which, perversely, doesn't raise an error if it doesn't fit) and see if it worked.

``````  my int32 \$b=Int(\$r);
if (\$b != \$r) {
return 0;
}
return \$r;
``````

# Task #2 › Find Square

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

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

So it's basically a two-dimensional search, but the delta-x and delta-y terms are always the same. Pretty straightforward really (using Perl for the example): find the array size;

``````  my \$t=0;
my \$maxx=\$#{\$s};
my \$maxy=\$#{\$s->};
``````

iterate over each possible starting point;

``````  foreach my \$x (0..\$maxx-1) {
foreach my \$y (0..\$maxy-1) {
``````

see if that point is a potential anchor;

``````      if (\$s->[\$x][\$y]==1) {
``````

if so, iterate over all the sizes of square that might fit;

``````        foreach my \$d (1..min(\$maxx-\$x,\$maxy-\$y)) {
``````

and check the other three corners.

``````          if (\$s->[\$x+\$d][\$y]==1 &&
\$s->[\$x][\$y+\$d]==1 &&
\$s->[\$x+\$d][\$y+\$d]==1
) {
\$t++;
``````

And the other languages basically work the same way. Python wants a `range` operator, but otherwise they're all identical apart from minor details of syntax.

One could I suppose build a table of potential opposite corners but I'm not convinced that there's much optimisation to be had.

Full code on github.

1. Posted by RogerBW at 02:35pm on 02 November 2020

Only nine other blog posts were registered this week, and four of them are on unresponsive hosts. (And I really can't be bothered to read through 100+ examples of code.)

As expected, the 32-bit check was the hard part of problem 1; some people ignored it, some invented very baroque ways of verifying it. Of the posts I could read, I seem to have been the only person to think of using internal 32-bit types or operators.

For part 2, the usual optimisations seem to be the same ones I used – drop out if the starting corner isn't a 1, and stop checking at once if any of the other corners isn't.