## The Weekly Challenge 145

The Task 2 of the Weekly Challenge #145 asked us to build a Palindromic Tree. It also linked to a blog post explaining the "Eertree" data structure.

Maybe it was just me, but I found the blog post confusing. Fortunately, it further linked to a scientific paper that introduced the structure around 2014.

## Product SubArray

Given a list of **4 or more** numbers, write a script to find the contiguous sublist that has the maximum product. The length of the sublist is irrelevant; your job is to maximize the product.
Example

Input: `[ 2, 5, -1, 3 ]`

Output: `[ 2, 5 ]`

which gives maximum product `10`

.

The easiest (but probably not the fastest) method would be to start from each position and compute the products of all the possible sublists starting at the position, remembering the positions where the product is maximal.

I automatically reached for List::Util’s `product`

to get the products easily, but alas! Running

`product(-1, 3)`

caused a *Floating point exception* (bug reported). So, I had to implement `product`

myself:

## Excel Column

Write a script that accepts a number and returns the Excel Column Name it represents and vice-versa.
Excel columns start at **A** and increase lexicographically using the 26 letters of the English alphabet, **A..Z**. After **Z**, the columns pick up an extra “digit”, going from **AA**, **AB**, etc., which could (in theory) continue to an arbitrary number of digits. In practice, Excel sheets are limited to 16,384 columns.

Example

Input Number: 28
Output: AB
Input Column Name: AD
Output: 30

This seemed like a simple base 10 to base 26 conversion and back. I started by installing Math::Base::Convert, Math::BaseConvert, Math::BaseCnv, and Convert::AnyBase to quickly discover they wouldn’t help me much. What Excel uses for column names is a weird 26 digit system that lacks a symbol for zero, but has a symbol for 26 (or for 10_{26}). It’s called the bijective base-26 numeration system. The interesting fact about such systems is that digit addition, subtraction, and multiplication work the same way as in our common system (division is a bit problematic).

## Linked List

You are given a linked list and a value **k**. Write a script to partition the linked list such that all nodes less than **k** come before nodes greater than or equal to **k**. Make sure you preserve the original relative order of the nodes in each of the two partitions.
For example:

Linked List: 1 → 4 → 3 → 2 → 5 → 2
k = 3
Expected Output: 1 → 2 → 2 → 4 → 3 → 5.

We saw Linked List not so long ago, when solving the LRU Cache. Nevertheless, I didn’t reuse my solution, as I previously used a cyclic variant which doesn’t seem to be helpful here.

So, let’s start with a class of list elements. I call them “nodes”. Each node has a value and a link to a next node (undef if there’s none). A node can be disconnected from the next node, or a new node can be attached to it.

## Compare Version

Compare two given version number strings **v1** and **v2** such that:
- If
**v1** > **v2** return 1
- If
**v1** < **v2** return -1
- Otherwise, return 0

The version numbers are non-empty strings containing only digits, and the dot (“.”) and underscore (“_”) characters. (“_” denotes an alpha/development version, and has a lower precedence than a dot, “.”). Here are some examples:

v1 | | v2 | Result |

0.1 | < | 1.1 | -1 |

2.0 | > | 1.2 | 1 |

1.2 | < | 1.2_5 | -1 |

1.2.1 | > | 1.2_1 | 1 |

1.2.1 | = | 1.2.1 | 0 |

When I read the task assignment, I thought to myself: I’m not the first person in the world that needs to compare versions. There already must be a module on CPAN that does exactly that. As usually, it wasn’t so simple.

## Shortest Unique Prefix

Write a script to find the shortest unique prefix for each each word in the given list. The prefixes will not necessarily be of the same length.
Sample Input

[ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ]

Expected Output

[ "alph", "b", "car", "cadm", "cade", "alpi" ]

Let me start with the second task as it was definitely simpler (at least for me).

We iterate over all the input words. For each word, we try to find the shortest prefix possible. To know what prefixes have already been used, we keep two hashes: one stores the abandoned prefixes (i.e. those that were not unique anymore), the second one stores the “current” prefixes (the prefix is the key, the actual word is the value). We start from length 1 and add 1 in each step. If the prefix isn’t used and hasn’t been used, we assign it to the word and proceed to the next word. If the prefix is currently used for a different word, we store the prefix as “used” and prolong the prefix for the old word by one—but we continue the loop for the current word, in case their common prefix is longer.

## Diff-K

You are given an array **@N** of positive integers (sorted) and another non negative integer **$k**. Write a script to find if there exists 2 indices **$i** and **$j** such that `$A[$i] - $A[$j] == $k and $i != $j`

. It should print the pairs of indices, if any such pairs exist.
Example:

```
@N = (2, 7, 9);
$k = 2;
```

Output: 2, 1

I totally ignored the fact that the input array is sorted. My solution works for any input array, but it’s still rather efficient.

The basic trick is that we don’t have to compute `$A[$i] - $A[$j]`

for each combination or `$i`

and `$j`

. We know `$k`

from the very beginning, so we can just iterate the array for the first time to store it in a hash, and iterate it for the second time to check the hash whether the corresponding number exists in the array.

```
#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
my @N = (2, 7, 9);
my $k = 2;
my %in_array;
@in_array{ @N } = 0 .. $#N;
for (@N) {
say join ', ', @in_array{ $k + $_, $_ }
if exists $in_array{ $k + $_ };
}
```

## K^{th} Permutation Sequence

Write a script to accept two integers **n** (>=1) and **k** (>=1). It should print the **k-th permutation** of **n** integers.
For example, **n=3** and **k=4**, the possible permutation sequences are listed below:

123
132
213
231
312
321

The script should print the **4**^{th} permutation sequence **231**.

The straightforward way is to generate all the permutations in the correct order and then output the k^{th} one. To generate them, we can use recursion: To get all the permutations of **n** elements, start with each element and extend it with all the permutations of the remaining elements.

## Rotate Matrix

Write a script to rotate the following matrix by given **90/180/270 degrees** clockwise.
[ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]

For example, if you rotate by 90 degrees then expected result should be like below

[ 7, 4, 1 ]
[ 8, 5, 2 ]
[ 9, 6, 3 ]

The easiest way to work with multidimensional data in Perl is PDL. Interestingly, I haven’t found a direct method to rotate a matrix in this way.

What I have found, though, was a method to *transpose* a matrix, which means to switch the columns and rows. The result for the sample input is

## Stepping Numbers

Write a script to accept two numbers between 100 and 999. It should then print all **Stepping Numbers** between them.
A number is called a stepping number if the adjacent digits have a difference of 1. For example, 456 is a stepping number but 129 is not.

The naive approach would be to iterate over all the numbers from 100 to 999 and check the difference between each adjacent digits.

```
#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
NUMBER: for my $n (100 .. 999) {
my @digits = split //, $n;
for my $i (1 .. $#digits) {
next NUMBER
unless 1 == abs($digits[$i - 1] - $digits[$i]);
}
say $n;
}
```

In fact, for the given range this is enough. But if we try to print all the stepping numbers of length 7 (1_000_000 .. 9_999_999), it takes more than 10 seconds.