So, when someone mentions palindromes, my mind immediately jumps to my favorite book on mathematics, algorithms, music, art, and philosophy: Gödel, Escher, Bach by Douglas Hofstadter. This was the book that introduced me to the idea of a musical palindrome, a piece of music that sounds the same played forwards and backwards, and the author cites J.S. Bach’s Crab Canon as an example.
So let’s approach Perl Weekly Challenge 288 from both sides… (no, no, I will not change the theme to Joni’s Clouds).
Task 1: Closest Palindrome
You are given a string, $str, which is an integer.
Write a script to find out the closest palindrome, not including itself. If there are more than one then return the smallest.
The closest is defined as the absolute difference minimized between two integers.
Example 1
Input: $str = "123"
Output: "121"
Example 2
Input: $str = "2"
Output: "1"
There are two closest palindrome "1" and "3". Therefore we return the smallest "1".
Example 3
Input: $str = "1400"
Output: "1441"
Example 4
Input: $str = "1001"
Output: "999"
Approach
It seems to me that this is most easily handled as two functions: one to determine if a number is a palindrome, and another one that steps way from a given number in two directions to find the closest palindrome.
There’s probably a numeric way to determine whether a number is a palindrome, but I’m going to use the easy-peasy stringy way: convert the number to a string, and then check to see if the reverse of the string is equal to the string itself.
Raku
Of course, coming from Perl, I immediately think of reverse to reverse a string, but…
Note that
reversealways refers to reversing elements of a list; to reverse the characters in a string, use flip.
Ugh. At least the docs know what mistake I was going to make.
sub isPalindrome($num) {
# convert numerics to Strings, then reverse one of them
return $num.Str eq $num.Str.flip;
}
sub closestPalindrome($str) {
my $num = $str.Int; # convert string to Integer
my $distance = 1;
while (True) {
# is the smaller number at this distance a palindrome?
if (isPalindrome($num - $distance)) {
return( ($num - $distance).Str );
}
# is the larger number at this distance a palindrome?
if (isPalindrome($num + $distance)) {
return( ($num + $distance).Str );
}
# step 1 number futher away
$distance++;
}
}View the entire Raku script for this task on GitHub.
$ raku/ch-1.raku
Example 1:
Input: $str = "123"
Output: "121"
Example 2:
Input: $str = "2"
Output: "1"
Example 3:
Input: $str = "1400"
Output: "1441"
Example 4:
Input: $str = "1001"
Output: "999"
Example 5: (it doesn't say the input is a POSITIVE int)
Input: $str = "-1"
Output: "0"Perl
In Perl 5.36, builtin::true was added as an experimental feature, and in Perl 5.40 those features became no longer experimental. Also I should point out the Perl idiom of adding 0 to a string to convert it to a number.
sub isPalindrome($num) {
# convert numerics to Strings, then reverse one of them
return "$num" eq reverse "$num";
}
sub closestPalindrome($str) {
my $num = $str + 0; # convert string to Integer
my $distance = 1;
while (true) {
# is the smaller number at this distance a palindrome?
if (isPalindrome($num - $distance)) {
return( ($num - $distance) );
}
# is the larger number at this distance a palindrome?
if (isPalindrome($num + $distance)) {
return( ($num + $distance) );
}
# step 1 number futher away
$distance++;
}
}View the entire Perl script for this task on GitHub.
Python
There’s a number of ways to reverse a string in Python, but my favorite is uses an extended string slice with a negative step value.
def isPalindrome(num):
# convert numerics to Strings, then reverse one of them
return str(num) == str(num)[::-1]
def closestPalindrome(string):
num = int(string)
distance = 1
while True:
# is the smaller number at this distance a palindrome?
if isPalindrome(num - distance):
return str(num - distance)
# is the larger number at this distance a palindrome?
if isPalindrome(num + distance):
return str(num + distance)
# step 1 number futher away
distance += 1View the entire Python script for this task on GitHub.
Elixir
In Elixir, once again I return to letting recursion do the heavy lifting, and I enjoy using |> to pipe the output of one function as the first argument to the next.
def isPalindrome(num) do
# convert numerics to Strings, then reverse one of them
Integer.to_string(num) ==
Integer.to_string(num) |> String.reverse
end
def closestPalindrome(num, distance) do
cond do
# is the smaller number at this distance a palindrome?
isPalindrome(num - distance) ->
Integer.to_string(num - distance)
# is the larger number at this distance a palindrome?a
isPalindrome(num + distance) ->
Integer.to_string(num + distance)
# step 1 number futher away
true ->
closestPalindrome(num, distance + 1)
end
end
def closestPalindrome(str) do
String.to_integer(str) |> closestPalindrome(1)
endView the entire Elixir script for this task on GitHub.
Task 2: Contiguous Block
You are given a rectangular matrix where all the cells contain either x or o.
Write a script to determine the size of the largest contiguous block.
A contiguous block consists of elements containing the same symbol which share an edge (not just a corner) with other elements in the block, and where there is a path between any two of these elements that crosses only those shared edges.
Example 1
Input: $matrix = [
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o', 'o'],
]
Output: 11
There is a block of 9 contiguous cells containing 'x'.
There is a block of 11 contiguous cells containing 'o'.
Example 2
Input: $matrix = [
['x', 'x', 'x', 'x', 'x'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
]
Output: 11
There is a block of 11 contiguous cells containing 'x'.
There is a block of 9 contiguous cells containing 'o'.
Example 3
Input: $matrix = [
['x', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x'],
['o', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x'],
]
Output: 7
There is a block of 7 contiguous cells containing 'o'.
There are two other 2-cell blocks of 'o'.
There are three 2-cell blocks of 'x' and one 3-cell.
Approach
I thought off and on about how to accomplish this task. Mostly, I pondered how to track what block of cells a particular cell was part of. I thought about creating a tree of cells in the matrix that were contiguous, but I realized that I didn’t need all that; all I needed was a second matrix where I replaced the xs and os with numbers designating which block the cells were part of. I could then just pass through the matrix cell by cell and check to see whether the adjacent cells that I had already visited had the same value, and, if so, make it part of the same block. The only thing I would have to backtrack for is if a block I was building wound up connecting with an existing block; but that wouldn’t be too hard.
Raku
As I was working on the solution, I was printing out the @blocks matrix as I was building it. In the first example, you can see how it’s numbering the block of os in the second row as a separate block before it gets to the end of the row:[
['0', '0', '0', '0', '1'],
['0', '2', '2', '2']
]
but then when it hits the end of the row and the block its building hooks up with the block at the end of the first row, it goes back and renumbers the block:[
['0', '0', '0', '0', '1'],
['0', '1', '1', '1', '1']
]
I think it’s cool looking at the third example as numbered contiguous blocks:
[
['0', '0', '0', '1', '1'],
['2', '2', '2', '3', '3'],
['2', '4', '4', '5', '5'],
['2', '2', '2', '6', '6']
]
# helper functions to determine if the adjacent cells
# BEFORE this one have the same value
sub prevXSame(@matrix, $x, $y) {
return $x > 0 && @matrix[$y][$x] eq @matrix[$y][$x-1];
}
sub prevYSame(@matrix, $x, $y) {
return $y > 0 && @matrix[$y][$x] eq @matrix[$y-1][$x];
}
sub contiguousBlock(@matrix) {
# first, find out the size of the matrix
my $height = @matrix.end;
my $width = @matrix[0].end;
# start a counter for the number of blocks
my $next_block = 0;
# a matrix of blocks
my @blocks;
for 0 .. $height -> $y {
for 0 .. $width -> $x {
if (prevXSame(@matrix, $x, $y)) {
# make this cell's block number match
# the one above it
@blocks[$y][$x] = @blocks[$y][$x-1];
}
if (prevYSame(@matrix, $x, $y)) {
# if we've already assigned a block number
# based on the prev X being the same, and
# it's a DIFFERENT block than the prev Y
if (@blocks[$y][$x].defined &&
@blocks[$y][$x] != @blocks[$y-1][$x]) {
# renumber the block for the prev X to
# match the block for the prev Y
my $new = @blocks[$y-1][$x];
my $old = @blocks[$y][$x-1];
for 0 .. $y -> $y2 {
for 0 .. $width -> $x2 {
@blocks[$y2][$x2] = $new
if @blocks[$y2][$x2] == $old;
}
}
}
# make this cell's block number match
# the one before it
@blocks[$y][$x] = @blocks[$y-1][$x];
}
if (! @blocks[$y][$x].defined) {
# neither previous adjacent cell matches,
# assign a new block number to this cell
@blocks[$y][$x] = $next_block++;
}
}
}
# now let's count the elements in each block
my @counts;
for 0 .. $height -> $y {
for 0 .. $width -> $x {
@counts[@blocks[$y][$x]]++;
}
}
return max(@counts);
}View the entire Raku script for this task on GitHub.
$ raku/ch-2.raku
Example 1:
Input: $matrix = [
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o', 'o']
]
Output: 11
Example 2:
Input: $matrix = [
['x', 'x', 'x', 'x', 'x'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o']
]
Output: 11
Example 3:
Input: $matrix = [
['x', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x'],
['o', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x']
]
Output: 7Perl
The big change in translating this from Raku to Perl is passing array references instead of arrays.
use List::AllUtils qw( max );
# helper functions to determine if the adjacent cells
# BEFORE this one have the same value
sub prevXSame($matrix, $x, $y) {
return $x > 0 && $$matrix[$y]->[$x] eq $$matrix[$y]->[$x-1];
}
sub prevYSame($matrix, $x, $y) {
return $y > 0 && $$matrix[$y]->[$x] eq $$matrix[$y-1]->[$x];
}
sub contiguousBlock($matrix) {
# first, find out the size of the matrix
my $height = $#{$matrix};
my $width = $#{$$matrix[0]};
# start a counter for the number of blocks
my $next_block = 0;
# a matrix of blocks
my @blocks;
foreach my $y (0 .. $height) {
foreach my $x (0 .. $width) {
if (prevXSame($matrix, $x, $y)) {
# make this cell's block number match
# the one above it
$blocks[$y][$x] = $blocks[$y][$x-1];
}
if (prevYSame($matrix, $x, $y)) {
# if we've already assigned a block number
# based on the prev X being the same, and
# it's a DIFFERENT block than the prev Y
if (defined($blocks[$y][$x]) &&
$blocks[$y][$x] != $blocks[$y-1][$x]) {
# renumber the block for the prev X to
# match the block for the prev Y
my $new = $blocks[$y-1][$x];
my $old = $blocks[$y][$x-1];
foreach my $y2 (0 .. $y) {
foreach my $x2 (0 .. $width) {
$blocks[$y2][$x2] = $new
if $blocks[$y2][$x2] == $old;
}
}
}
# make this cell's block number match
# the one before it
$blocks[$y][$x] = $blocks[$y-1][$x];
}
if (! defined $blocks[$y][$x]) {
# neither previous adjacent cell matches,
# assign a new block number to this cell
$blocks[$y][$x] = $next_block++;
}
}
}
# now let's count the elements in each block
my @counts;
foreach my $y (0 .. $height) {
foreach my $x (0 .. $width) {
$counts[$blocks[$y][$x]]++;
}
}
return max(@counts);
}View the entire Perl script for this task on GitHub.
Python
I got tripped up on line 37; even though I’d knowingly left the height and width in lines 13 and 14 to be the number of elements instead of the index of the last element because I knew in lines 20 and 21 that range(n) would produce 0 .. n-1, I wound up forgetting that once I got to line 37 where I wanted to have the range be 0 .. y, not 0 .. y-1.
# helper functions to determine if the adjacent cells
# BEFORE this one have the same value
def prevXSame(matrix, x, y):
return x > 0 and matrix[y][x] == matrix[y][x-1]
def prevYSame(matrix, x, y):
return y > 0 and matrix[y][x] == matrix[y-1][x]
def contiguousBlock(matrix):
# first, find out the size of the matrix
height = len(matrix)
width = len(matrix[0])
# start a counter for the number of blocks
next_block = 0
# a matrix of blocks
blocks = [[None for x in range(width)] for y in range(height)]
for y in range(height):
for x in range(width):
if prevXSame(matrix, x, y):
# make this cell's block number match
# the one above it
blocks[y][x] = blocks[y][x-1]
if prevYSame(matrix, x, y):
# if we've already assigned a block number
# based on the prev X being the same, and
# it's a DIFFERENT block than the prev Y
if (blocks[y][x] is not None and
blocks[y][x] != blocks[y-1][x]):
# renumber the block for the prev X to
# match the block for the prev Y
new = blocks[y-1][x]
old = blocks[y][x-1]
for y2 in range(y+1):
for x2 in range(width):
if blocks[y2][x2] == old:
blocks[y2][x2] = new
# make this cell's block number match
# the one before it
blocks[y][x] = blocks[y-1][x]
if blocks[y][x] is None:
# neither previous adjacent cell matches,
# assign a new block number to this cell
blocks[y][x] = next_block
next_block += 1
# now let's count the elements in each block
counts = [0 for x in range(next_block)]
for y in range(height):
for x in range(width):
counts[blocks[y][x]] += 1
return max(counts)View the entire Python script for this task on GitHub.
Elixir
I’m going to finish up the Elixir implementation once I get the hang of installing modules, since I really want to use the Matrix module.
Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-283/packy-anderson