laurent_r

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.