Perl Weekly Challenge: They run and hide their heads / They might as well be dead…

Posted on by

Perl Weekly Challenge 377‘s tasks are “Reverse Existence” and “Prefix Suffix”.

Hmmm. Reverse. What does “reverse” make me think of musically? The existence of this song.

Task 1: Reverse Existence

You are given a string.

Write a script to find whether any substring of length 2 is also present in the reverse of the given string.

Example 1

Input: $str = "abcba"
Output: true

Reverse of given string is "abcba".
The substring "ab" in original string is also present in the reverse string too.

Example 2

Input: $str = "racecar"
Output: true

The substring "ce" is present in both.

Example 3

Input: $str = "abcd"
Output: false

Example 4

Input: $str = "banana"
Output: true

The substring "an" is present in both.

Example 5

Input: $str = "hello"
Output: true

The substring "ll" is present in both.

Approach

There’s probably a clever way to do this, but I’m just going to brute-force it: generate a reversed string, $trs, and then take all the two-character slices of $str and see if any are found in $trs. Worst case, for a string of length N, I’m doing N-1 lookups.

Raku

I really wanted to use an experimental extension of .comb that’s in the long-awaited Raku 6.e:

The rotor pair indicates the number of characters to fetch as the key (the “size”), and the number of “steps” forward to take afterwards. Its main intended use is to provide a way to create N-grams from strings in an efficient manner. By default only strings of the specified size will be produced.

so I decided to use the v6.e.PREVIEW version. With that, "racecar".comb(2 => -1) yields the list ["ra", "ac", "ce", "ec", "ca", "ar"], making short work of generating two-character substrings. Raku’s index returns Nil if the substring isn’t found, so I use .defined to determine if the substring was found.

use v6.e.PREVIEW; # so I can use .comb with a rotor pair

sub reverseExistence($str) {
  my $trs = $str.flip;
  for $str.comb(2 => -1) -> $substr {
    return 'true' if $trs.index($substr).defined;
  }
  return 'false';
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = "abcba"
Output: true

Example 2:
Input: $str = "racecar"
Output: true

Example 3:
Input: $str = "abcd"
Output: false

Example 4:
Input: $str = "banana"
Output: true

Example 5:
Input: $str = "hello"
Output: true

Perl

Perl, however, doesn’t have that, so I just looped over starting character positions from 0 to the penultimate character of the string, and then used substr() to generate the substring. Perl’s index returns -1 if the substring isn’t found, so I use >= 0 to determine if the substring was found. 

sub reverseExistence($str) {
  my $trs = reverse $str;
  foreach my $i ( 0..length($str)-2 ) {
    my $substr = substr($str, $i, 2);
    return 'true' if index($trs, $substr) >= 0;
  }
  return 'false';
}

View the entire Perl script for this task on GitHub.

Python

As I learned back in PWC 256, the fastest and most idiomatic way to reverse a string in Python is string[::-1]. Also, being able to use in to test to see if a substring is in a string makes this implementation quite neat.

def reverse_existence(string):
  gnirts = string[::-1]
  for i in range(len(string)-1):
    substr = string[i:i+2]
    if substr in gnirts: return "true"
  return "false"

View the entire Python script for this task on GitHub.

Elixir

Rather than looping, I’m using a Range to produce numbers from 0 to length(str)-2, then piping that through Enum.reduce/3 to produce a list of 2-character substrings, and then piping that list into a reverse_existence/2 that recursively calls itself to check if the reversed string contains any of the substrings.

def reverse_existence([], _), do: "false"
def reverse_existence([substr | tail], rts) do
  if String.contains?(rts, substr), do: "true",
  else: reverse_existence(tail, rts)
end

def reverse_existence(str) do
  0..String.length(str)-2
  |> Enum.reduce([],
       fn i, list -> list ++ [String.slice(str, i, 2)] end)
  |> reverse_existence(String.reverse(str))
end

View the entire Elixir script for this task on GitHub.

Task 2: Prefix Suffix

You are given an array of strings.

Write a script to find if the two strings (str1, str2) in the given array such that str1 is prefix and suffix of str2. Return the total count of such pairs.

Example 1

Input: @array = ("a", "aba", "ababa", "aa")
Output: 4

$array[0], $array[1]: "a" is a prefix and suffix of "aba"
$array[0], $array[2]: "a" is a prefix and suffix of "ababa"
$array[0], $array[3]: "a" is a prefix and suffix of "aa"
$array[1], $array[2]: "aba" is a prefix and suffix of "ababa"

Example 2

Input: @array = ("pa", "papa", "ma", "mama")
Output: 2

$array[0], $array[1]: "pa" is a prefix and suffix of "papa"
$array[2], $array[3]: "ma" is a prefix and suffix of "mama"

Example 3

Input: @array = ("abao", "ab")
Output: 0

Example 4

Input: @array = ("abab", "abab")
Output: 1

$array[0], $array[1]: "abab" is a prefix and suffix of "abab"

Example 5

Input: @array = ("ab", "abab", "ababab")
Output: 3

$array[0], $array[1]: "ab" is a prefix and suffix of "abab"
$array[0], $array[2]: "ab" is a prefix and suffix of "ababab"
$array[1], $array[2]: "abab" is a prefix and suffix of "ababab"

Example 6

Input: @array = ("abc", "def", "ghij")
Output: 0

Approach

This feels like a regex. We take str1, str2 and return true if str2 matches /^str1/ and /str1$/.

Raku

But why use a regex when Raku’s Str class has .starts-with and .ends-with methods? I could drop lines 6 and 14 if I didn’t also want to return the explanatory text.

sub prefixSuffix(@array) {
  my ($count, $explain) = (0, "");
  for 0 .. @array.end - 1 -> $i {
    my $istr = @array[$i];
    for $i+1 .. @array.end -> $j {
      my $jstr = @array[$j];
      next unless $jstr.starts-with($istr)
               && $jstr.ends-with($istr);
      $count++;
      $explain ~= qq{\n\$array[$i], \$array[$j]: "$istr" is }
                ~ qq{a prefix and suffix of "$jstr"};
    }
  }
  return $count, $explain;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @array = ("a", "aba", "ababa", "aa")
Output: 4

$array[0], $array[1]: "a" is a prefix and suffix of "aba"
$array[0], $array[2]: "a" is a prefix and suffix of "ababa"
$array[0], $array[3]: "a" is a prefix and suffix of "aa"
$array[1], $array[2]: "aba" is a prefix and suffix of "ababa"

Example 2:
Input: @array = ("pa", "papa", "ma", "mama")
Output: 2

$array[0], $array[1]: "pa" is a prefix and suffix of "papa"
$array[2], $array[3]: "ma" is a prefix and suffix of "mama"

Example 3:
Input: @array = ("abao", "ab")
Output: 0

Example 4:
Input: @array = ("abab", "abab")
Output: 1

$array[0], $array[1]: "abab" is a prefix and suffix of "abab"

Example 5:
Input: @array = ("ab", "abab", "ababab")
Output: 3

$array[0], $array[1]: "ab" is a prefix and suffix of "abab"
$array[0], $array[2]: "ab" is a prefix and suffix of "ababab"
$array[1], $array[2]: "abab" is a prefix and suffix of "ababab"

Example 6:
Input: @array = ("abc", "def", "ghij")
Output: 0

Perl

And I know I said regex, but it occurred to me I could implement starts_with and ends_with in Perl using index and rindex, and I wouldn’t need to incur the overhead of the full regex engine.

sub starts_with($str, $substr) { index($str, $substr) == 0; }

sub ends_with($str, $substr) {
  rindex($str, $substr) == length($str) - length($substr);
}

sub prefixSuffix(@array) {
  my ($count, $explain) = (0, "");
  for my $i ( 0 .. $#array - 1 ) {
    my $istr = $array[$i];
    for my $j ( $i+1 .. $#array ) {
      my $jstr = $array[$j];
      next unless starts_with($jstr, $istr)
               && ends_with($jstr, $istr);
      $count++;
      $explain .= qq{\n\$array[$i], \$array[$j]: "$istr" is }
                . qq{a prefix and suffix of "$jstr"};
    }
  }
  return $count, $explain;
}

View the entire Perl script for this task on GitHub.

Python

Really, it looks like of the languages I’m using, only Perl didn’t have a built-in .startswith and .endswith methods.

def prefix_suffix(array):
  count, explain = 0, ""
  for i in range(len(array)-1):
    istr = array[i]
    for j in range(i+1, len(array)):
      jstr = array[j]
      if not jstr.startswith(istr): continue
      if not jstr.endswith(istr): continue
      count += 1
      explain += f'\n$array[{i}], $array[{j}]: "{istr}" is '
      explain += f'a prefix and suffix of "{jstr}"'
  return count, explain

View the entire Python script for this task on GitHub.

Elixir

Part of the heavy lifting in the Elixir solution is that, just like in Perl, the return value of a function is the value of the last expression in the function. In each of the Enum.reduce/3 calls, the anonymous function winds up evaluating the tuple {count, explain} last, so that’s the return value, which is, in turn, the return value of the reduce call.

def prefix_suffix(array) do
  Enum.reduce(0..length(array)-2, {0, ""},
  fn i, {count, explain} ->
    Enum.reduce(i+1..length(array)-1, {count, explain},
    fn j, {count, explain} ->
      istr = Enum.at(array, i)
      jstr = Enum.at(array, j)
      cond do
        String.starts_with?(jstr, istr) &&
        String.ends_with?(jstr, istr) ->
          {
            count + 1,
            explain <> "\n$array[#{i}], $array[#{j}]: "
                    <> "\"#{istr}\" is a prefix and suffix "
                    <> "of \"#{jstr}\""
          }
        true -> {count, explain}
      end
    end)
  end)
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-377-packy-anderson/challenge-377/packy-anderson

Leave a Reply