Wherein we pull a short con and switch the numbers around from low to high
THE WEEKLY CHALLENGE – PERL & RAKU #84
chapter one:
“Back to Front”
TASK #1 › Reverse Integer
Submitted by: Mohammad S Anwar
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
A NOTE ON the positional notation
This task is complex idea with the abstract idea of a positional number, but a simple dispatch if considered as a string. Fortunately for us, Perl excels at this idea of a single representation holding a dual personality. After all, mathematically speaking the characters recorded in a text aren’t truly the numbers per se any more than their formal written names are; both are only representations of them. The symbolic representation can change; the numerical essance remains outside of its physically recorded state. It’s not like the digits are likely to be manipulated within the computer in decimal, although decimal computers do exist. So there’s already a translation from what we write down to the binary encodings we use internally. It’s all a bit arbitrary as to what’s easiest and most useful, really. The numbers themselves don’t care how they’re viewed.
In fact, the familiar positional decimal system using Arabic numerals is globally ubiquitous today but this has hardly been true throughout history. Because of its practical linkage to the use of the abacus, the Roman numeral system maintained dominance in mercantile accounting well into the 14th or 15th century.*
Up until the medieval era merchants that used calculations daily preferred the physical existence of a strike on a counting board or a bead on an abacus. A chit was a thing, not an abstract idea. It was what they knew and it worked for them. Should they have need to physically write down a result, they used the Roman numbering system, which immediately reflected what they were seeing, fives and all.
Roman numerals held within them a decimal core — I, X, C, M for 1, 10, 100, 1000 — but with the addition of intermediary five or half units, depending on how you looked at them. The abstraction of of the glyphs was simpler, always referring back to a unary base: “I” was one stick, “III” was three sticks and “X” was the same as “IIIII IIIII”. “V” was half of an “X”, quite visually expressed. The abacus is a positional machine, but the positions are physical, and remain in existence even when empty.
Positional notation, on the other hand, depended on the idea of the zero as a placeholder, and practical as this idea might be in the long run, the modern methods faced stubborn resistance from the governments that held the merchant classes to account. It is argued that the essence of the zero —- something that exists but holds no value, signifying nothing; something there but also somehow not there at the same time — all this made the very idea of its use at least suspicious, if not “Saracen sorcery”. One Venetian source wrote: “the old figures [i.e. Roman numerals] alone are used because they cannot be falsified as easily as those of the new art of computation”2 Accounting was demanded to be written out in longhand, because it was more trustworthy.
Consider for a moment the tendered amount written out twice on a modern check. These ideas even hold out through this day, that somehow the written out words are more real than the numerical notation, more unalterably defined by the sentence describing them than by the numbers themselves. The textual phrasing anchors the abstract and elusive mathematical realm to the real world of here and now.
I believe you can still see the vestiges of this concreteness in the COBOL programming language as well, but that’s another story.
1 Durham, John W. “THE INTRODUCTION OF ‘ARABIC’ NUMERALS IN EUROPEAN ACCOUNTING.” The Accounting Historians Journal, vol. 19, no. 2, 1992, pp. 25–55. JSTOR, http://www.jstor.org/stable/40698081. Accessed 27 Oct. 2020.
2 Kaplan, Robert “The Nothing That Is” pp. 102 Oxford University Press 1999
Method
Treated as a string, this really is as easy as applying the reverse built-in function and we’re done. If the number is negative, we note that and take its absolute value, and add the sign back when we’re done. That truly isn’t very interesting in itself, but is included for completeness.
Alternately, I decided to complete he job in a thoroughly ridiculous manner, serving the course up a total of three ways.
In the opener we have the aforementioned sensible way to do things, by letting Perl consider it as a string and reversing it, adding back the sign. A comparison is then used to make sure it does not exceed the boundaries of a 32-bit signed int. We do run into an unforeseen problem when dealing with numbers ending in 0. These will be reversed into numbers with leadings g 0s, which is not what we want. In fact, if we’re not careful Perl will interpret these as octal, which is definitely not what we want. So we need to insert a step stripping the 0s from the end of the number before we reverse it. But we want to print the number for output! Ok, sure, no problem. Using the /r modifier we return the result of the substitution, rather than modifying $num, and we then print $out.
In the second, more elaborate, dish we first turn the number into a string, then convert that string into an array, preserving the positions of the characters. We create an iterator to access the indexes of the array, and multiply the value we find in the element by 10 to the power of the iterator, adding the result to an accumulating output. As index 0 is the left side of the string, it gets multiplied by 100, or 1. The last becomes the first, the first last and we’ve reversed our number.
In the third variety we eschew all this indexing completely, and proceed mathematically. To reverse the powers though we need to count down from the highest, which means an extra step to see how many powers we will need in advance. After that we loop through the powers and decrement them, doing modulo division to extra the last digit of the number until it is depleted.
I had considered pretending that this was in fact a 32 bit machine that literally could not store a number above 32 bits, and somehow detecting a integer overflow before it occurred, but found out Perl goes to great lengths to keep that from happening. Were you to exceed 2,147,483,647 on a 32-bit machine by adding 1, for instance, you would require more than the 31 bits available to store the positive side of a signed integer. Perl, detecting this, would change it silently under the hood to an unsigned integer type, doubling your capacity. Sneaky! And you’d never know. Another 2,147,483,647 steps later, though, you’d run out of space again. Undaunted, Perl recasts your value into a float, generally a 64-bit double, giving you access to the entire 53-bit mantissa to store your integer before losing precision. So even on a 32-bit machine (I mean, I have a PPC Mac mini in the back somewhere) we would have no troubles dealing with numbers up to 9,007,199,254,740,992, or 9 quadrillion. So I abandoned that idea as just too silly.
A thoroughly ridiculous process indeed.
Perl Solution
Oct 29, 2020 at 9:40:58 PM
~/PWC/reverse-and-repeat.pl
--------------------------------------------------------------------------------
=========================
the right way. Reverse the string:
input: 9271
output: 1729
=========================
hard mode, done positionally:
starting output = 0
--> adding 2 x 10^0 = 2
--> adding 1 x 10^1 = 12
--> adding 4 x 10^2 = 412
--> adding 7 x 10^3 = 7412
--> adding 4 x 10^4 = 47412
--> adding 8 x 10^5 = 847412
--> adding 3 x 10^6 = 3847412
--> adding 6 x 10^7 = 63847412
--> adding 4 x 10^8 = 463847412
--> adding 7 x 10^9 = 7463847412
the number 7463847412 cannot be fit into a 32-bit signed int
input : 2147483647
output: 0
=========================
hard mode, done mathematically:
7000000000
7400000000
7460000000
7463000000
7463800000
7463840000
7463847000
7463847400
7463847410
7463847412
input : 2147483647
output: 0
use 5.032;
use warnings;
use strict;
## ## ## ## ## MAIN:
##
## turning the tables served three ways:
##
my $def = 7463847412;
## 1. reverse
say '';
say "=" x 25;
say '';
say "the right way. Reverse the string:\n";
my $num = $ARGV[0] // $def;
my $sign = $num < 0 ? "-" : '';
my $out = $num =~ s/0+$//r; ## strip trailing 0s before reversing
my $rev = $sign . reverse abs $out;
say "input: $num";
say "output: ", -2147483648 <= $rev <= 2147483647 ? $rev : 0;
##--------------------------
## 2. positionally
say '';
say "=" x 25;
say '';
say "hard mode, done positionally:\n";
my $input = @ARGV[0] // $def; ##7463847412
$num = abs $input;
my $sign = $input adding $positions[0] x 10^$power = ",
sprintf "%10d", $reversed + $positions[0] * (10 ** $power);
$reversed += (shift @positions) * (10 ** $power);
}
$reversed = $sign . $reversed; ## prefix the sign
if (! -2147483648 < $reversed < 2147483647 ) {
say "\nthe number $reversed cannot be fit into a 32-bit signed int\n";
}
say '';
say "input : $input";
say "output: ", -2147483648 <= +$reversed <= 2147483647 ? $reversed : 0;
##----------------------------
## 3. mathematically
say '';
say "=" x 25;
say '';
say "hard mode, done mathematically:\n";
$input = @ARGV[0] // $def;
$num = abs $input;
$sign = $input 0;
while ($power--) {
$output += $num % 10 * 10 ** $power ;
say $output;
$num = int $num/10;
}
$output *= $sign;
say '';
say "input : $input";
say "output: ", -2147483648 <= $output <= 2147483647 ? $output : 0;Raku Solution
I think we’ve worked the alternate methods to death here, and so we’ll let this solution stand here. Note Raku is a little wiser about what we want when casting between numbers and strings, and leading 0s aren’t a problem.
unit sub MAIN (Int $num = -1729) ;
my $sign = $num < 0 ?? -1 !! 1 ;
my $out = $sign * $num.abs.flip ;
say -2147483648 <= $out <= 2147483647 ?? $out
!! 0;
chapter two:
“Four Corners Off A Twenty”
“Four corners off a twenty” is the name of a con I learned back in the 80’s from an itinerant grifter. You start with a hundred dollar bill, your capital, which to start the ball rolling is cashed into five twenty dollar bills. From four of the twenties, one corner is carefully removed, and those are then pasted onto the four corners of a one dollar bill. The ersatz twenty is either grouped back in with others and converted back back into a fresh hundred, should an exceptionally careless opportunity arise, or the original twenties, in their altered but still legal condition, are used to regenerate the hundred dollar source and the the bogus twenty is passed to an inattentive cashier. The transaction would be for a small purchase, with the aim of generating the maximum change. Misdirection at a critical moment and sleight of hand are part and parcel of the grifter’s toolbox, so the actual passing of the bill would comprise the art of this particular con.
Does it work? I have no direct confirmation, and I certainly wouldn’t exactly trust the source. But I have seen less plausible social engineering succeed so I imagine it does.
TASK #2 › Find Square
Submitted by: Mohammad S Anwar
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 (3×3) 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 (4×4) in the given matrix with four corners as 1 starts at r=1;c=1.
There is one square (3×3) in the given matrix with four corners as 1 starts at r=1;c=2.
There are two squares (2×2) 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: 0Method
We need to methodically examine quads of points, each expressing the four corners of an internal square. Each square in turn can be expressed as a base corner closest to the origin and an edge size. If all four corners are 1s, then we have a match and the square is logged. The squares to be looked at range in size from edge length 2 to the shorter dimension of the enclosing matrix. Every square group of a given size starts with the first instance in the upper left corner at (0,0) and from there gets translated righwards and down to map all possible placements. The number of repetions in each direction will be the length of the matrix dimension minus the square edge dimension.
The number of squares to be evaluated is defined by the sequence of the square pyrimidal numbers1, A00330 in the OEIS. Using the formula
an= n (n+1) (2*n+1) / 6
for generating the n-th number in the sequence, as we are only considering squares of minimum edge length 2, the number of squares S contained within an (M x M) matrix will be the “M – 1″th element in the sequence:
S = a(M-1)
We need to look at every point in the matrix, that much seems clear. However from that point we can employ a couple of optimizations to minimize the searching for squares portion of the program. Firstly, if when iterating through the array considering base vertices for out potential squares, if that particular vertex isn’t a 1 there’s no point in continuing and we should move on. Secondly, if when examining corners of a square of a particular size we employ a boolean chain of validations, so should any step fail the expression will immediately fail and short-circuit out. Thirdly, squares of increasing size are considered until one of the edges exceed the boundaries of the enclosing matrix. Once that happens, no further squares will remain in-bounds and so again we move on the the next base vertex.
In this way the checking process is pruned, and for sparser matrices especially the speedup is quite significant.
1 OEIS A00330, Kristie Smith, Apr 16 2002
Perl Solution
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
my $r = 100;
my $c = 10;
my $matrix = [ map { [ map { int rand 6 == 0 ? 1 : 0 } (1..$c) ] } (1..$r) ] ;
## print the matrix generated
say "@$_" for $matrix->@*;
say '';
my $cols = $matrix->[0]->@*;
my $rows = $matrix->@*;
my $min_dimension = $cols < $rows ? $cols : $rows;
my @output;
for my $c ( 0..$cols-2 ) {
for my $r ( 0..$rows-2) {
next unless $matrix->[$r][$c];
for my $size ( 2..$min_dimension ) { ## for each square size group
last if $c + $size > $cols || $r + $size > $rows;
if (four_corners($r, $c, $size, $matrix)) {
push @output, [ $r, $c, $size ];
}
}
}
}
# say "square at row $_->[0] column $_->[1] with size $_->[2]" for @output;
say "found ", scalar @output, " squares:";
for my $s ( sort { $a->[2] <=> $b->[2] } @output ) {
printf "column %d row %d from top - square of size %d \n", $s->[1]+1, $s->[0]+1, $s->[2];
}
## ## ## ## ## SUBS:
sub four_corners {
my ($r, $c, $size, $matrix) = @_;
## short-circuits out
return 1 if $matrix->[$r][$c] == 1
&& $matrix->[$r][$c+$size] == 1
&& $matrix->[$r+$size][$c] == 1
&& $matrix->[$r+$size][$c+$size] == 1 ;
return 0;
}Raku Solution
unit sub MAIN ($r = 5, $c = 6) ;
srand 20201031; ## keep this value fixed for development or comparison
sub four_corners ($r, $c, $size is copy, @matrix) {
$size--; ## square side includes corner element
return 1 if ( @matrix[$r;$c] == 1
&& @matrix[$r+$size;$c] == 1
&& @matrix[$r;$c+$size] == 1
&& @matrix[$r+$size;$c+$size] == 1 );
}
my @matrix.push: (0,1).roll($c) for ^$r;
.say for @matrix;
say '';
my $rows = @matrix.elems;
my $cols = @matrix[0].elems;
my @output;
for 0..$rows-2 -> $r {
for 0..$cols-2 -> $c {
next unless @matrix[$r;$c];
for 2..min($rows,$cols) -> $size {
last if (($c + $size > $cols) || ($r + $size > $rows));
if four_corners( $r, $c, $size, @matrix) {
@output.push: ($r, $c, $size);
}
}
}
}
say "found ", @output.elems, " squares:\n";
for sort {$^a[2] leg $^b[2]}, @output -> $s {
printf "column %d row %d from top - square of size %d\n",
$s[1]+1, $s[0]+1, $s[2];
}
Programming Excursions in Perl and Raku 