planet.donarmstrong.com

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.

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

You are given 2 arrays of same size, @a and @b.

Write a script to implement Dot Product.

Example:

@a = (1, 2, 3);
@b = (4, 5, 6);

$dot_product = (1 * 4) + (2 * 5) + (3 * 6) => 4 + 10 + 18 => 32

An important point is that we are told that the arrays have the same size. Thus, we don’t need to check that. We’ll also assume that they contain only numbers.

Dot Product in Raku

Raku is particularly well-suited to solve this task.

Assuming we have the two arrays presented in the task description (@a = (1, 2, 3); and @b = (4, 5, 6);), the infix Z zip operator will interleave the values from the two arrays like a zipper, taking index-corresponding elements from each operand:

say @a Z @b;  # prints: ((1 4) (2 5) (3 6))

That’s already quite good, but Z is also a metaoperator) that can be combined with another infix operator that will be applied to each pair of the above result. Thus, using Z*, we obtain directly the individual products:

say @a Z* @b; # prints: (4 10 18)

Finally, we only need to add these partial results (with the built-in sum function or method, or with another metaoperator combination, [+]) to fulfill the task in just one very short code-line:

use v6;

my @a = 1, 2, 3;
my @b = 4, 5, 6;

say sum @a Z* @b;  # Could also be: say [+] @a Z* @b;

This script displays the following output:

$ raku ./dot-product.raku
32

Dot Product in Perl

Since Perl doesn’t have the Zip operator and metaoperator, we cannot port the Raku solution to Perl. But, using a map, we can nevertheless implement a fairly concise solution:

use strict;
use warnings;
use feature "say";

my @a = (1, 2, 3);
my @b = (4, 5, 6);

my $result = 0;
$result += $_ for map { $a[$_] * $b[$_] } 0..$#a;
say $result;

This script displays the following output:

$ perl ./dot-product.pl
32

Update (Jan 2, 2022): Added the new section below with 16 languages.

Dot Product in 16 Other Programming Languages

All these implementations basically implement the same idea, with some minor differences due to syntactic differences.

In Julia

#!/usr/bin/julia

function dot_product(a1, a2)
    res = 0
    for i in eachindex(a1)
        res = res + a1[i] * a2[i]
    end
    return res
end

print( "Dot product: ", dot_product([1, 2, 3], [4, 5, 6]))

Output:

$ julia ./dot-product.jl
Dot product: 32

In Python

def dot_product (a1, a2):
    res = 0
    for i in range(0, len(a1)):
        res += a1[i] * a2[i]
    return res

product = dot_product([1, 2, 3], [4, 5, 6])
print(product)

Output:

$ python3 ./dot-product.py
32

In Scala

object dot_product extends App {
  val a1 = Array(1, 2, 3)
  val a2 = Array(4, 5, 6)
  var res = 0
  for (i <- a1.indices) {
    res = res + a1(i) * a2(i)
  }
  println("Dot product: " + res)
}

Output:

Dot product: 32

In Lua

#!/usr/bin/lua

local function dot_product(a1, a2)
    res = 0
    for i, v in next, a1 do
        res = res + v * a2[i]
    end
    return res
end

print(dot_product({1, 2, 3}, {4, 5, 6}))

Output:

$ lua ./dot-product.lua
32

In Kotlin

fun dot_product(a1: List<Int>, a2: List<Int>): Int {
    var res = 0
    for (i in a1.indices) {
        res += a1[i] * a2[i]
    }
    return res
}
fun main() {
    println (dot_product(listOf<Int>(1, 2, 3), listOf<Int>(4, 5, 6)))
}

Output:

32

In Ruby

def dot_product(a1, a2)
    res = 0
    a1.each_with_index do |v, i|
        res += v * a2[i]
    end
    return res
end
print dot_product([1, 2, 3], [4, 5, 6]), "\n"

Output:

bundle exec ruby dot-product.rb
32

In Rust

fn dot_product(a1: Vec<i32>, a2: Vec<i32>) -> i32 {
    let mut res = 0;
    a1.iter().enumerate().for_each(|(i, v)| {
        res += v * a2[i];
    });
    return res
}
fn main() {
    println!("{} ", dot_product(vec![1, 2, 3],vec![4, 5, 6]));
}

Output:

32

In Awk

$ echo '1 2 3
4 5 6 '  | awk -e '{
    for (i = 1; i <= NF; i ++) {
        if (NR == 1) {
             col[i] = $i
        }
        else {
            result += col[i] * $i
        }
    }
}
END {
    print result
}
'
32

In C

#include <stdio.h>

int main() {
    int a1[] = {1, 2, 3};
    int a2[] = {4, 5, 6};
    int res = 0;
    int size = sizeof(a1)/sizeof(a1[0]);
    for (int i = 0; i < size; i++) {
        res += a1[i] * a2[i];
    }
    printf("%d\n", res);
}

Output:

$ ./a.out
32

In Pascal

program dot_product;
const
    SIZE = 2;
var
    a1: array[0..SIZE] of integer = (1, 2, 3);
    a2: array[0..SIZE] of integer = (4, 5, 6);
    result, i : integer;
begin
    result := 0;
    for i := 0 to SIZE do
        result += a1[i] * a2[i];
    writeln(result);
end.

Output:

32

In D

import std.stdio;

int a1[] = [1, 2, 3];
int a2[] = [4, 5, 6];
int main() {
    int result = 0;
    for (int i = 0; i < 3; i++) {
        result += a1[i] * a2[i];
    }
    writeln(result);
    return 0;
}

Output:

32

In Bash

$ echo '1 2 3
4 5 6 '  | bash -c '
    read -a a1
    read -a a2
    for ((i = 0; i < ${#a1[@]}; i ++))
        do  ((result += a1[i] * a2[i]))
    done
    echo $result
'
32

In Dart

var a1 = [1, 2, 3];
var a2 = [4, 5, 6];

void main() {
    int result = 0;
    for (int i = 0; i < 3; i++ ) {
        result += a1[i] * a2[i];
    }
    print(result);
}

Output:

32

In Go

package main
import "fmt"

func main() {
    a1 := [3]int{1, 2, 3}
    a2 := [3]int{4, 5, 6}
    var result int = 0
    for i := 0; i < 3; i++ {
        result += a1[i] * a2[i]
    }
    fmt.Printf("Dot product: %d\n", result)
}

Output:

Dot product: 32

In Nim

Remember that Nim uses Python-like code indentation.

proc dot_product (a1, a2: array[0..2, int]) : int =
    result = 0
    for i in 0..2:
        result += a1[i] * a2[i]
    return result

let a1 = [1, 2, 3]
let a2 = [4, 5, 6]
let res = dot_product(a1, a2)
echo "dot product: ", res

Output:

dot product: 32

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 use is as a guest language in the Perl Weekly Challenge to get a gist of it. Here we go.

see "Dot product: " + dot_product([1, 2, 3], [4, 5, 6]) + nl

func dot_product a1, a2
    res = 0
    for i = 1 to len(a1)
        res = res +  a1[i] * a2[i]
    next
    return res

Using the Ring online compiler, I obtain the following output:

Dot product = 32

Task 2: Palindromic Tree

This task requests us to implement a fairly complicated algorithm. I’ll try to come back to that later, if I have time and if I succeed to understand the requirement.

Update (Dec. 29): Finally, I have completed this second task here.

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.