Perl Weekly Challenge 145: Palindromes
These are some answers to the Week 145 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a few days from now (on January 2, 2022 at 24:00). 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: Dot Product
This first task of this week’s challenge was covered in this blog post.
Task 2: Palindromic Tree
You are given a string $s.
Write a script to create a Palindromic Tree for the given string.
I found this blog explaining Palindromic Tree in detail.
Example 1:
Input: $s = 'redivider'
Output: r redivider e edivide d divid i ivi v
Example 2:
Input: $s = 'deific'
Output: d e i ifi f c
Example 3:
Input: $s = 'rotors'
Output: r rotor o oto t s
Example 4:
Input: $s = 'challenge'
Output: c h a l ll e n g
Example 5:
Input: $s = 'champion'
Output: c h a m p i o n
Example 6:
Input: $s = 'christmas'
Output: c h r i s t m a
The blog explaining palindromic trees is in my humble opinion somewhat unclear and quite difficult to follow.
If we look at the examples provided, the aim is to find all palindromes that can be formed from fragments of a word. For example, for the word redivider, the palindromic fragments are: r redivider e edivide d divid i ivi v. Note that a single letter is considered to be a palindrome, even though it is sort of a trivial solution. Also note that each palindrome appears only once in the output, so the algorithm somehow removes any duplicates. Finally, the palindromes are ordered by their place of occurrence in the input string.
With these properties in mind, we can write a much simpler algorithm to find all palindromes and generate exactly the requested output.
The point about the palindromic tree algorithm is that it is supposed to be efficient. Well, I’m not even sure that a proper palindromic tree implementation would run faster than my implementations below with the input examples provided. As Donald Knuth wrote in The Art of Computer Programming, “premature optimization is the root of all evil (or at least most of it) in programming.” So, before spending a lot of time and energy on implementing a fairly complicated algorithm, let’s see how a much simpler naive implementation behaves.
Well, with the six input words provided in the task specification, the Perl program below is timed as follows on my laptop (a relatively good computer, but certainly not a racing horse):
real 0m0,048s
user 0m0,015s
sys 0m0,030s
In other words, it runs in less than 50 milliseconds (compile time included). This is fairly good, isn’t it? Why, for heaven’s sake, would you want to optimize this? I certainly don’t want to spend hours on a complicated algorithm just to possibly scrap a few milliseconds.
Admittedly, for very long input strings, the palindromic tree algorithm may perform faster, but palindromes are normally used on actual words, which rarely have more than a dozen letters.
And, as we shall see, our output is exactly what is requested from us in the task specification. So, why bother?
Palindromes in Raku
We just use two nested loops to generate all fragments of the input words. Then we filter out fragments that are not palindromes and palindromes that have already been seen previously for the same input (to avoid duplicates).
use v6;
sub is-palindrome (Str $in) { return $in eq $in.flip; }
sub find-all-palindromes ($input) {
print "$input: ";
my BagHash $seen;
for 0..$input.chars -> $start {
for 1..$input.chars - $start -> $length {
my $candidate = substr $input, $start, $length;
next unless is-palindrome $candidate.Str;
next if $seen{$candidate};
$seen{$candidate}++;
print "$candidate ";
}
}
say " ";
}
for <redivider deific rotors challenge
champion christmas> -> $test {
find-all-palindromes $test;
}
This program displays the following output:
$ raku ./palindromes.raku
redivider: r redivider e edivide d divid i ivi v
deific: d e i ifi f c
rotors: r rotor o oto t s
challenge: c h a l ll e n g
champion: c h a m p i o n
christmas: c h r i s t m a
Palindromes in Perl
This is a port to Perl of the above Raku program. Please refer to the explanations above if needed.
use strict;
use warnings;
use feature "say";
sub is_palindrome { return $_[0] eq reverse $_[0]; }
sub find_all_palindromes {
my $input = shift;
print "$input: ";
my %seen;
my $str_length = length $input;
for my $start (0..$str_length) {
for my $length (1.. $str_length - $start) {
my $candidate = substr $input, $start, $length;
next unless is_palindrome $candidate;
next if $seen{$candidate};
$seen{$candidate} = 1;
print "$candidate ";
}
}
say " ";
}
for my $test (qw <redivider deific rotors
challenge champion christmas>) {
find_all_palindromes $test;
}
This program displays the following output:
$ perl palindromes.pl
redivider: r redivider e edivide d divid i ivi v
deific: d e i ifi f c
rotors: r rotor o oto t s
challenge: c h a l ll e n g
champion: c h a m p i o n
christmas: c h r i s t m a
Update (Jan 2, 2022): Added the new section below with 6 languages.
Palindromes in 6 Other Programming languages
In Python
def is_palindrome (str):
return str == str[::-1]
def find_all_palindromes (input):
seen = {}
result = f'{input} : '
for start in range (0, len(input)):
for endstr in range(1, (len(input) + 1)):
candidate = input[start : endstr]
if is_palindrome(candidate) and not candidate in seen:
result = result + " " + candidate
seen[candidate] = 1
print(result)
for test in ("redivider", "deific", "rotors", "challenge"):
find_all_palindromes(test);
Output:
$ python3 ./palindromes.py
redivider : r redivider e edivide d divid i ivi v
deific : d e i ifi f c
rotors : r rotor o oto t s
challenge : c h a l ll e n g
In Julia
function is_palin(instr)
return instr == reverse(instr)
end
function find_all_palindromes(input)
print("$input: ")
seen = Dict()
for startstr in 1:length(input)
for endstr in startstr:length(input)
cand = input[startstr:endstr] # candidate
if is_palin(cand) && cand ∉ keys(seen)
print("$cand ")
seen[cand] = 1
end
end
end
print("\n")
end
for test in ("redivider", "rotors", "deific", "challenge")
find_all_palindromes(test)
end
Output:
redivider: r redivider e edivide d divid i ivi v
rotors: r rotor o oto t s
deific: d e i ifi f c
challenge: c h a l ll e n g
In Rust
use std::collections::HashSet;
fn is_palindrome (instr : &str) -> bool {
return instr == instr.chars().rev().collect::<String>()
}
fn find_palindromes (input : &str) {
print!("{}: ", input);
let mut seen = HashSet::new();
for start in 0..input.len() {
for endstr in start+1..=input.len() {
let cand = &input[start .. endstr];
if is_palindrome(&cand) && !seen.contains(&cand) {
print!("{} ", cand);
seen.insert(cand);
}
}
}
println!(" ");
}
fn main () {
let tests = vec!["redivider", "rotors", "challenge"];
for test in tests.into_iter() {
find_palindromes(test);
}
}
Output:
redivider: r redivider e edivide d divid i ivi v
rotors: r rotor o oto t s
challenge: c h a l ll e n g
In Ruby
def is_palindrome (instr)
return instr == instr.reverse
end
def find_palindromes (input)
print input, ": "
seen = {}
for start in 0 .. input.length - 1 do
for endstr in start .. input.length - 1 do
cand = input[start .. endstr]
if is_palindrome(cand) and not seen[cand] then
print cand, " "
seen[cand] = 1
end
end
end
puts " "
end
for test in ["redivider", "rotors", "challenge"] do
find_palindromes(test)
end
Output:
$ ruby palindrome.rb
redivider: r redivider e edivide d divid i ivi v
rotors: r rotor o oto t s
challenge: c h a l ll e n g
In Lua
local function is_palindrome (instr)
return instr == string.reverse(instr)
end
local function find_palindromes (input)
io.write (input, ": ")
local seen = {}
for startstr = 1, #input do
for endstr = startstr, #input do
local cand = string.sub (input, startstr, endstr)
if is_palindrome(cand) and not seen[cand] then
io.write(cand, " ")
seen[cand] = 1
end
end
end
print(" ")
end
local tests = {"redivider", "rotors", "challenge"}
for _, test in pairs(tests) do
find_palindromes(test)
end
Output:
$ lua ./dot-product.lua
redivider: r redivider e edivide d divid i ivi v
rotors: r rotor o oto t s
challenge: c h a l ll e n g
In Ring
Ring is a new programming language. Well, it is at least completely new to me (I had never heard about it until this morning of Jan 2, 2022), but it was released for the first time in January 2016. Its documentation states:
The Ring is an Innovative and practical general-purpose multi-paradigm scripting language that can be embedded in C/C++ projects, extended using C/C++ code and/or used as standalone language. The supported programming paradigms are Imperative, Procedural, Object-Oriented, Functional, Meta programming, Declarative programming using nested structures, and Natural programming.
I thought it would be interesting to get a gist of it by using it as a guest language in the Perl Weekly Challenge. Here we go.
tests = ["redivider", "rotors", "challenge"]
for test in tests
find_palindromes(test)
next
func find_palindromes input
see input + " : "
seen = []
for start = 1 to len(input)
for length = 1 to len(input) - start
cand = substr(input, start, length)
if is_palindrome(cand) and not seen[cand]
see cand + " "
add(seen, cand)
ok
next
next
see " " + nl
func is_palindrome instr
reverse = ""
for i = len(instr) to 1 step -1
reverse = reverse + instr[i]
next
return reverse = instr
Using the Ring online compiler, I obtain the following output:
redivider : r e edivide d divid i ivi v i d e
rotors : r rotor o oto t o r
challenge : c h a l ll l e n g
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 January 9, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.