The Bear's Den

Enter at your own risk

06 November 2026 Challenge 145

Dotted Trees

TASK #1 › Dot Product

Submitted by: Mohammad S Anwar

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

Solution

This is my solution dated 30 Apr 2023:

use strict;
use warnings;
use PDL;

sub dot_product ($x, $y) {
    (pdl($x) x pdl($y)->dummy(0))->sclr;
}

See the full solution to task 1.

TASK #2 › Palindromic Tree

Submitted by: Mohammad S Anwar

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

Solution

Sadly I was not able to use the information from the linked blog for an actual implementation. Therefore I searched for other sources. Though I was not satisfied with any of these neither, in summary all these sources turned out to be sufficient. Certainly I didn’t want just to port any of the provided implementations to Perl.

In my first attempt I used Graph to build the Eertree. Some try-and-error cycles led to a working solution, with two findings:

With these insights I started with a new version from scratch.

The basic design:

Starting with Eertree::Edonode, we need a constructor and some accessors.

Some details:

package Eertree::Edonode;

sub new ($class, $palindrome) {
    bless {
        palindrome => $palindrome,
        length => defined($palindrome) ? length($palindrome) : -1,
        suffix => undef,
        transition => {},
    }, $class;
}

sub palindrome ($self) {
    $self->{palindrome};
}

sub length ($self) {
    $self->{length};
}

Getter and Setter for transition and suffix links:

sub transition ($self, $char, $dest=undef) {
    if (@_ == 2) {
        return $self->{transition}{$char};
    }
    $self->{transition}{$char} = $dest;
    $self;
}

sub suffix ($self, $dest=undef) {
    if (@_ == 1) {
        return $self->{suffix};
    }
    $self->{suffix} = $dest;
    $self;
}

Finally there is a method to extend a palindrome by one character. The character is prepended to a defined palindrome and appended to any.

sub extend ($self, $c) {
    my $ex = $self->palindrome;
    $ex = $c . $ex if defined $ex;
    $ex .= $c;
    $ex;
}

Next comes the Eertree class with its constructor that initializes:

Note: The undefined/odd root per definition represents a palindrome and a suffix of any string, while the even/empty root obviously possesses these properties.

package Eertree;

sub new ($class) {
    my $empty = Eertree::Edonode->new('');
    my $undef = Eertree::Edonode->new(undef);
    $empty->suffix($undef);
    $undef->suffix($undef);
    bless {
        empty => $empty,
        undef => $undef,
        source => '',
        current => $undef,
        sequence => [],
    }, $class;
}

We need an internal helper method to determine the longest predecessor palindrome, that - when extended by the new character - is a suffix of the source string, starting the search at a given palindrome node.

There is a vital precondition for this method to produce a valid result:
R: The given node’s palindrome must be a suffix of the source string without its trailing character.

As this is an internal method, it’s the caller’s responsibility that this precondition is fulfilled for the given starting node.

sub _longest_predecessor ($self, $node) {
    for (; $node; $node = $node->suffix) {
        my $pos = length($self->{source}) - $node->length - 2;
        last if $pos >= 0 &&
            substr($self->{source}, $pos, 1) eq substr($self->{source}, -1);
    }
    $node;
}

And now for the heart of the implementation: Augment the Eertree by one character.

In the following, terms in italics refer to a specific, fixed object within the described process.

sub add ($self, $c) {
    $self->{source} .= $c;
    my $predecessor = $self->_longest_predecessor($self->{current});
    my $pc = $predecessor->transition($c);
    return $self->{current} = $pc if $pc;

    my $palindrome = $predecessor->extend($c);
    my $new = Eertree::Edonode->new($palindrome);
    push $self->{sequence}->@*, $new;
    my $suffix = $new->length == 1 ?
        $self->{empty}
    :
        $self->_longest_predecessor($predecessor->suffix)->
            transition($c);
    $new->suffix($suffix);
    $predecessor->transition($c, $new);
    $self->{current} = $new;
}

Finally, a method to return all sub-palindromes in creation order:

sub palindromes ($self) {
    map $_->palindrome, $self->{sequence}->@*;
}

Wrapping these parts into a single function:

package main;

sub eertree ($s) {
    my $eertree = Eertree->new;
    $eertree->add($_) for split //, $s;
    $eertree->palindromes;
}

The order of the identified sub-palindromes is partially different from the examples:

$ perl/ch-2.pl rotors
r o t oto rotor s

See the full solution to task 2.

References: