Still working on getting into the swing of weekly blogging again. Nothing jumped out at me for a musical theme this week, so I just picked King Crimson’s Cat Food off the top of my head. Having three cats sleeping all around me probably had something to do with it.

So before I need to feed these cats, let’s jump into Perl Weekly Challenge 318.

Task 1: Group Position

You are given a string of lowercase letters.

Write a script to find the position of all groups in the given string. Three or more consecutive letters form a group. Return “” if none found.

Example 1

Input: $str = "abccccd"
Output: "cccc"

Example 2

Input: $str = "aaabcddddeefff"
Output: "aaa", "dddd", "fff"

Example 3

Input: $str = "abcdd"
Output: ""

Approach

This feels like a regular expression to me. Match an alphabetic character, then look for two or more of the same character immediately following it.

Raku

I had to re-familiarize myself with Raku’s regex syntax, because I’ve only been using Raku for the Weekly Challenge, but it was pretty easy. :i is the adverb to make the regex case-insensitive, and :c is the adverb to have the regex repeat the match later in the string if it occurs again.

sub groupPosition($str) {
  my @groups;
  while ( $str ~~ m:i:c/ ((<[a..z]>)$0$0+) / ) {
    @groups.push($0);
  }
  if (@groups) {
    return @groups.map({ qq/"$_"/ }).join(", ")
  }
  else {
    return qq/""/;
  }
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = "abccccd"
Output: "cccc"

Example 2:
Input: $str = "aaabcddddeefff"
Output: "aaa", "dddd", "fff"

Example 3:
Input: $str = "abcdd"
Output: ""

Perl

I remembered Perl’s regex syntax pretty well, but I did go through the docs and reminded myself that v5.10.0 added a way to capture the match without a performance penalty: ${^MATCH} paired with /p.

sub groupPosition($str) {
  my @groups;
  while ( $str =~ /([a-z])\1\1+/gip ) {
    push @groups, ${^MATCH};
  }
  if (@groups) {
    return join(", ", map { qq/"$_"/ } @groups);
  }
  else {
    return qq/""/;
  }
}

View the entire Perl script for this task on GitHub.

Python

Python doesn’t support nested capture groups in regexes, so we have to match each group individually, then remove each occurrence (and the characters before it) from the string and then loop until we’ve processed the entire string.

import re

def groupPosition(str):
  # python doesn't support nested groups,
  # so let's match just the first occurence
  hasGroups = re.compile(r"([a-z])\1\1+", re.I)
  groups = []

  match = hasGroups.search(str)
  while match:
     # push the occurrence onto a list of groups
     # the 0th group is the entire match
     groups.append(match.group(0))
     # then remove from the start of the string to
     # the end of the first occurence
     str = str[match.end():]
     # and match against the new string
     match = hasGroups.search(str)

  if groups:
    return ', '.join([ f'"{s}"' for s in groups ])
  else:
    return '""'

View the entire Python script for this task on GitHub.

Elixir

Elixir, on the other hand, has some pretty neat regular expression handling tools to make short work of this problem. Oh, and I finally remembered the shorthand for anonymous functions!

  def groupPosition(str) do
    # will return a list of [entire_match, matching_char]
    # tuples for each group matched
    groups = Regex.scan(~r/([a-z])\1\1+/i, str)
    if Enum.empty?(groups) do
      "\"\""
    else
      groups
        # grab the entire match from each group tuple
        # and wrap it in quotes
        |> Enum.map(&( "\"#{ List.first(&1) }\"" ))
        |> Enum.join(", ")
    end
  end

View the entire Elixir script for this task on GitHub.

Task 2: Reverse Equals

You are given two arrays of integers, each containing the same elements as the other.

Write a script to return true if one array can be made to equal the other by reversing exactly one contiguous subarray.

Example 1

Input: @source = (3, 2, 1, 4)
       @target = (1, 2, 3, 4)
Output: true

Reverse elements: 0-2

Example 2

Input: @source = (1, 3, 4)
       @target = (4, 1, 3)
Output: false

Example 3

Input: @source = (2)
       @target = (2)
Output: true

Approach

I’m sure there’s a clever way to do this, but I’m tired and I feel like the brute force way is easiest; just loop through all the possible subarrays and see if reversing any of them makes the two arrays equal. We should also check to see if the arrays are already in the same order or if they’re of different lengths.

Raku

I thought there was a method for comparing lists in Raku, but I couldn’t find one, so I figured “Why not just join the lists with a comma and compare that? I did make it a separate function because I’m using it twice, and it makes the code more readable.

sub arrayEquals(@a, @b) {
  return @a.join(',') eq @b.join(',');
}

sub reverseEquals(@source, @target) {
  # deal with the trivial cases
  if (@source.elems != @target.elems) {
    # @source and @target are different lengths
    return (False, "");
  }
  if (arrayEquals(@source, @target)) {
    # they're already the same
    return (True, "");
  }
  # ok, now we start checking subarrays
  for 0..@source.end - 1 -> $i {
    for $i+1..@source.end -> $j {
      my @reversed;
      @reversed = @source[0..$i-1] if $i > 0;
      @reversed.append(@source[$i..$j].reverse);
      @reversed.append(@source[$j+1..@source.end])
        if $j < @source.end;
      return (True, "$i-$j") if arrayEquals(@reversed, @target);
    }
  }
  return (False, "");
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @source = (3, 2, 1, 4)
       @target = (1, 2, 3, 4)
Output: True

Reverse elements: 0-2

Example 2:
Input: @source = (1, 3, 4)
       @target = (4, 1, 3)
Output: False

Example 3:
Input: @source = (2)
       @target = (2)
Output: True

Perl

The big thing I needed to do here was, because I was passing two arrays around, pass them as references.

sub arrayEquals($a, $b) {
  return join(',', @$a) eq join(',', @$b);
}

sub reverseEquals($source, $target) {
  # deal with the trivial cases
  if (@$source != @$target) {
    # @source and @target are different lengths
    return ("False", "");
  }
  if (arrayEquals($source, $target)) {
    # they're already the same
    return ("True", "");
  }
  # ok, now we start checking subarrays
  foreach my $i ( 0 .. $#{$source} - 1 ) {
    foreach my $j ( $i+1 .. $#{$source} ) {
      my @reversed;
      @reversed = @$source[0..$i-1] if $i > 0;
      push @reversed, reverse @$source[$i..$j];
      push @reversed, @$source[$j+1..$#{$source}]
        if $j < $#{$source};
      return ("True", "$i-$j") if arrayEquals(\@reversed, $target);
    }
  }
  return ("False", "");
}

View the entire Perl script for this task on GitHub.

Python

Python, on the other hand, does have list comparison, so that part is slightly easier. I just needed to make sure I used .extend() to add elements to my list so I didn’t get the sublists that .append would give me if I added from a list.

def reverseEquals(source, target):
  # deal with the trivial cases
  if len(source) != len(target):
    # @source and @target are different lengths
    return (False, "")

  if source == target:
    # they're already the same
    return (True, "")

  # ok, now we start checking subarrays
  for i in range(len(source)-1):
    for j in range(i+1, len(source)):
      rev = []
      if i > 0:
        rev = source[0:i]
      rev.extend(list(reversed(source[i:j+1])))
      if j < len(source)-1:
        rev.extend(source[j+1:])
      if rev == target:
        return (True, f'{i}-{j}')

  return (False, "")

View the entire Python script for this task on GitHub.

Elixir

Since Elixir really isn’t built to iterate over lists, we do this with recursion. It’s actually surprisingly easy. One thing we can also be thankful for is that list equality checking is built in. We take care of our trivial cases in lines 34-38 by using two guards on the reverseEquals/2 function definition (one to check if the lists are different lengths, one to check if the lists are already equal), and then if we get past those guards, we make a recursive call to reverseEquals/4 with initial values of i and j of 0 and 1.

Then we check to see if reversing from i to j yields the target list; if it does, we return truth with the i-j range for output. If it doesn’t, we test to see if we’re at the end of the nested loop simulation; if we are, we return falsity. Otherwise, we increment the appropriate i or j value and make the recursive call for the next iteration.

  def reverseEquals(source, target, i, j) do
    reversed = [] ++ if i > 0 do
      Enum.slice(source, 0 .. i-1)
    else
      []
    end
    reversed = reversed ++ Enum.reverse(Enum.slice(source, i..j))
    reversed = reversed ++ if j < length(source)-1 do
      Enum.slice(source, j+1 .. length(source)-1)
    else
      []
    end
    cond do
      reversed == target ->
        { true, "#{i}-#{j}" }
      # we've reached the end of the nested loops,
      # so there's no solution
      i == length(source)-2 and j == length(source)-1 ->
        { false, "" }
      # we're at the last j value, so let's increment i
      # and set j = i+1
      j == length(source)-1 ->
        reverseEquals(source, target, i+1, i+2)
      # just increment j
      true ->
        reverseEquals(source, target, i, j+1)
    end
  end

  def reverseEquals(source, target)
    when length(source) != length(target), do: { false, "" }

  def reverseEquals(source, target)
    when source == target, do: { true, "" }

  def reverseEquals(source, target) do
    reverseEquals(source, target, 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/master/challenge-318/packy-anderson

Packy’s Place

Packy's just 'zis guy, you know?

Perl Weekly Challenge: Group the Reverse Position

Task 1: Group Position

Approach

Raku

Perl

Python

Elixir

Task 2: Reverse Equals

Approach

Raku

Perl

Python

Elixir

Related

Leave a ReplyCancel reply