Perl Weekly Challenge: Go hang a salami, I’m a lasagna hog!

Posted on by

Perl Weekly Challenge 392‘s tasks are “Convert Palindrome” and “Words Length Product”.

If we want music with palindromes, you can’t do much better than “Weird Al” Yankovic’s Bob.

Task 1: Convert Palindrome

You are given a string.

Write a script to convert the given string to palindrome by adding characters in front of it.

Example 1

Input: $str = "pinnipeds"
Output: "sdepinnipeds"

Example 2

Input: $str = "abcd"
Output: "dcbabcd"

Example 3

Input: $str = "bananas"
Output: "sananabananas"

Example 4

Input: $str = "dissident"
Output: "tnedissident"

Example 5

Input: $str = "cailliachs"
Output: "shcailliachs"

Approach

Since we’re adding characters in front of the given string, the characters added will just be the characters from the end of the string, reversed. But there’s a portion of the string that’s already a palindrome, even if it’s just one character. So I’m going to pull characters off the end of the string until the remaining string is a palindrome, then add those characters to the beginning of the string.

Raku

As I started implementing this, I realized that I was reversing the characters I was pulling off the end of the string as I was keeping track of what I would need to add to the front, so I needed to reverse them when I added them back to the end of the string. I could have made sure to build the list in the same order they were in the original string, but then I’d have to flip them when I was adding them to the beginning of the string, so there was going to be flipping on one end or the other, and flipping the re-add at the end meant building the list was slightly easier.

Knowing I would probably be using recursion in my Elixir solution, I opted for using recursion to check whether a string is a palindrome in Raku. If the string has 1 or fewer characters, it’s a palindrome; otherwise if the first and last characters match and the string without those characters is a palindrome, the entire string is a palindrome.

sub isPalindrome($str) {
  return True  if $str.chars <= 1;
  return $str.substr(0,1) eq $str.substr(*-1)
      && isPalindrome($str.substr(1,*-1));
}

sub convertPalindrome($str is copy) {
  my $add = "";
  while (! isPalindrome($str)) {
    $add ~= $str.substr(*-1);
    $str.substr-rw(*-1) = "";
  }
  return $add ~ $str ~ $add.flip;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = "pinnipeds"
Output: "sdepinnipeds"

Example 2:
Input: $str = "abcd"
Output: "dcbabcd"

Example 3:
Input: $str = "bananas"
Output: "sananabananas"

Example 4:
Input: $str = "dissident"
Output: "tnedissident"

Example 5:
Input: $str = "cailliachs"
Output: "shcailliachs"

Example 6:
Input: $str = "gohangasalamiimalasagnahog"
Output: "gohangasalamiimalasagnahog"

Perl

As usual, the Perl version is an easy translation from the Raku version.

sub isPalindrome($str) {
  return true if length($str) <= 1;
  return substr($str,0,1) eq substr($str,-1)
      && isPalindrome(substr($str,1,-1));
}

sub convertPalindrome($str) {
  my $add = "";
  while (! isPalindrome($str)) {
    $add .= substr($str,-1);
    substr($str,-1) = "";
  }
  return $add . $str . reverse($add);
}

View the entire Perl script for this task on GitHub.

Python

And the Python translation was also fairly straightforward.

def is_palindrome(s):
  if len(s) <= 1: return True
  return s[0:1] == s[-1] and is_palindrome(s[1:-1])

def convert_palindrome(string):
  add = ""
  while not is_palindrome(string):
    add += string[-1]
    string = string[0:-1]
  return add + string + add[::-1]

View the entire Python script for this task on GitHub.

Elixir

Rather than try to operate on individual characters in a string, I first converted the string into a list of characters, which made targeting individual characters much easier. I also selectively imported modules in functions when I found myself using several functions from that module on the same line, thus reducing some line length.

I was particularly proud of using list |> tl |> pop_at(-1) |> elem(1) to return the list with the first and last elements removed: Kernel.tl/1 returns the “tail” of a list—the list without its first element, List.pop_at/3 returns a tuple of the item being popped off the list (-1 means it’s the last element from the list) and the list with that item removed, and Kernel.elem/2 returns the specified element of a tuple (in this case, the list from pop_at/3).

def is_palindrome(list) when length(list) <= 1, do: true
def is_palindrome(list) do
  import List
  first(list) == last(list) and
    is_palindrome(list |> tl |> pop_at(-1) |> elem(1))
end

def convert_palindrome(str, add) do
  if is_palindrome(str) do
    {add, str}
  else
    {last, str} = List.pop_at(str, -1)
    convert_palindrome(str, add ++ [last])
  end
end

def convert_palindrome(str) do
  {add, str} = convert_palindrome(String.codepoints(str), [])
  import Enum
  join(add) <> join(str) <> join(reverse(add))
end

View the entire Elixir script for this task on GitHub.

Task 2: Words Length Product

You are given an array of strings.

Write a script to return the maximum value of len($words[i]) * len($words[j]) where the two words do not share common letters. If no such two words exist, return 0.

Example 1

Input: @words = ("a", "ab", "abc", "d", "de", "def")
Output: 9

Two words are "abc" and "def".

Example 2

Input: @words = ("a", "aa", "aaa", "aaaa")
Output: 0

Since no two words can be chosen without sharing letters, the result is 0.

Example 3

Input: @words = ("meet", "app", "code", "sky", "bold")
Output: 16

Two words are "meet" and "bold".

Example 4

Input: @words = ("a", "ab", "abc", "abcd", "efghi")
Output: 20

Two words are "abcd" and "efghi".

Example 5

Input: @words = ("xyz", "w", "abcdefg", "hij")
Output: 21

Two words are "abcdefg" and "hij".

Approach

I think the way to do this is to first sort the entries by length, then eliminate entries with shared letters, and once we have two entries without shared letters, stop and return the product of their lengths.

My brain is telling me that I should use a Bag to determine if two words have shared letters, because I can loop through the keys of one bag and test for membership in the other bag.

Raku

This was easy to do in Raku. It has the .Bag coercer to turn the list of characters returned from calling .comb on the string with no matcher, and I’m able to test for existence of a key in a bag by using ∈.

Rather than eliminating entries with shared letters, I just skipped them so if I had a list like ["abcdefgh", "efgh", "abcd"] I wouldn’t eliminate the second and third elements and wind up with only one element left. By skipping the second and third elements when comparing them to the first, I can then determine that the first element has common characters with all the remaining elements, and then wind up skipping that instead.

Rather than doing a next to a label on the loop on line 16, I split out the testing whether there’s common characters into it’s own function. This makes the code on line 17 easier to read, and I don’t have to jump to a label, which I knew would be trickier in Python and Elixir.

sub common($first, $second) {
  my %bag1 = $first.comb.Bag;
  my %bag2 = $second.comb.Bag;
  for %bag1.keys -> $c {
    return True if $c ∈ %bag2;
  }
  return False;
}

sub wlp(@words is copy) {
  @words = @words.sort: {$^b.chars cmp $^a.chars || $^b cmp $^a};
  for 0 .. @words.end - 1 -> $i {
    for $i+1 .. @words.end -> $j {
      next if common(@words[$i], @words[$j]);
      return @words[$i].chars * @words[$j].chars;
    }
  }
  return 0;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @words = ("a", "ab", "abc", "d", "de", "def")
Output: 9

Example 2:
Input: @words = ("a", "aa", "aaa", "aaaa")
Output: 0

Example 3:
Input: @words = ("meet", "app", "code", "sky", "bold")
Output: 16

Example 4:
Input: @words = ("a", "ab", "abc", "abcd", "efghi")
Output: 20

Example 5:
Input: @words = ("xyz", "w", "abcdefg", "hij")
Output: 21

Perl

The Perl version was pretty much a straight translation of the Raku version. split // for .comb, List::MoreUtils’ frequency for .Bag, and exists for ∈.

use List::MoreUtils qw( frequency );

sub common($first, $second) {
  my %bag1 = frequency split //, $first;
  my %bag2 = frequency split //, $second;
  for my $c (keys %bag1) {
    return true if exists $bag2{$c};
  }
  return false;
}

sub wlp(@words) {
  @words = sort {length($b) cmp length($a) || $b cmp $a} @words;
  for my $i (0 .. $#words - 1) {
    for my $j ($i+1 .. $#words) {
      next if common($words[$i], $words[$j]);
      return length($words[$i]) * length($words[$j]);
    }
  }
  return 0;
}

View the entire Perl script for this task on GitHub.

Python

In Python, I always use the collections module’s Counter datatype for bags. Python sorting, however, does the comparison behind the scenes, relying on us to define a key and direction for the sort.

from collections import Counter

def common(first, second):
  bag1 = Counter([ c for c in first])
  bag2 = Counter([ c for c in second])
  for c in bag1.keys():
    if c in bag2:
      return True
  return False

def wlp(words):
  words.sort(key=lambda k: (len(k), k), reverse=True)
  end = len(words)-1
  for i in range(end):
    for j in range(i+1, end+1): 
      if not common(words[i], words[j]):
        return len(words[i]) * len(words[j])
  return 0

View the entire Python script for this task on GitHub.

Elixir

Elixir’s Enum.sort_by/3 works on the same principle: define a key and direction for the sort. Rather than try to work out how to bail out of an Enum.reduce_while/3 loop early when we found a result, I just went with my usual Elixir solution: recursion.

I wind up defining common/2 three separate times, but Elixir knows which one to call based on what the first argument is: the one on line 4 is called when the first argument is an empty list, the one on lines 6-9 is called when the first argument is a list, and the one on lines 11-15 is called when the first argument is a bitstring. Initially, I had a when is_bitstring(first) guard on line 11, but I later realized I didn’t need it because Elixir already knew the difference.

def common([], _), do: false

def common([c | rest], bag2) do
  if Map.has_key?(bag2, c), do: true,
  else: common(rest, bag2)
end

def common(first, second) do
  bag1 = String.codepoints(first)  |> Enum.frequencies
  bag2 = String.codepoints(second) |> Enum.frequencies
  common(Map.keys(bag1), bag2)
end

def wlp(words, i, j) do
  first  = Enum.at(words, i)
  second = Enum.at(words, j)
  if not common(first, second) do
    String.length(first) * String.length(second)
  else
    last = length(words)-2
    cond do
      j <= last -> wlp(words, i, j+1)
      i < last  -> wlp(words, i+1, i+2)
      true      -> 0
    end
  end
end

def wlp(words) do
  wlp(Enum.sort_by(words, &{byte_size(&1), &1}, :desc), 0, 1)
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-392-packy-anderson/challenge-392/packy-anderson

Leave a Reply