Perl Weekly Challenge: Parenthetically Uncommon

Posted on by

Perl Weekly Challenge 385‘s tasks are “Uncommon Words” and “Outermost Parentheses”.

I thought I remembered one of my favored artists doing a song featuring “uncommon”, and the first one that popped up in my music collection was Carole King: An Uncommon Love.

Task 1: Uncommon Words

You are given two sentences.

Write a script to return list of all uncommon words, order is not important.

Example 1

Input: $sentence1 = "apple banana apple"
       $sentence2 = "banana orange"
Output: ("orange")

Example 2

Input: $sentence1 = "cat dog"
       $sentence2 = "bird fish"
Output: ("cat", "dog", "bird", "fish")

Example 3

Input: $sentence1 = "the quick brown fox"
       $sentence2 = "the quick"
Output: ("brown", "fox")

Example 4

Input: $sentence1 = "hello"
       $sentence2 = "hello"
Output: ()

Example 5

Input: $sentence1 = "blue blue red"
       $sentence2 = "red green green yellow"
Output: ("yellow")

Approach

I think it’s amusing that this task is so much like PWC 735 Task 1 , and I picked Carole King for that challenge as well.

But back in May, the challenge was to count strings that appeared once in each of two input arrays. In this task, we’re finding words that appear once across two arrays, since we’re splitting the sentence strings on whitespace into effectively two arrays.

Raku

Of course, we’re using my favorite data structure, the Bag. It’s a single statement broken up into multiple lines for clarity. First we concatenate the two sentences together into a single string, then we split that string on whitespace into a list of words. Then we push the list into a Bag, filter out any keys in the Bag that have a value other than 1, and then we return the keys. The task says the order isn’t important (which is great, because a Bag doesn’t preserve order), but I’m sorting the output so every time I run the script, the output is the same.

sub uncommonWords($sentence1, $sentence2) {
  ($sentence1 ~ " " ~ $sentence2) # make two sentences one
  .split(/\s+/)            # split on whitespace
  .Bag                     # count occurrences of each word
  .grep({ $_.value == 1 }) # filter for words that happen once
  .Bag                     # .grep returns a Seq, make it a Bag
  .keys                    # return just the keys
  .sort;             # but sort so the answer's always the same
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $sentence1 = "apple banana apple"
       $sentence2 = "banana orange"
Output: ("orange")

Example 2:
Input: $sentence1 = "cat dog"
       $sentence2 = "bird fish"
Output: ("bird", "cat", "dog", "fish")

Example 3:
Input: $sentence1 = "the quick brown fox"
       $sentence2 = "the quick"
Output: ("brown", "fox")

Example 4:
Input: $sentence1 = "hello"
       $sentence2 = "hello"
Output: ()

Example 5:
Input: $sentence1 = "blue blue red"
       $sentence2 = "red green green yellow"
Output: ("yellow")

Perl

As usual, I’m using List::MoreUtil’s frequency to make my Bag in Perl. It’s split into two statements because I need to be able to reference the %bag variable we’re assigning in the first statement in the second statement. Each statement handles about half of what the Raku statement handles, and the order winds up being reversed.

use List::MoreUtils qw( frequency );

sub uncommonWords($sentence1, $sentence2) {
  my %bag = frequency    # count occurrences of each word
  split /\s+/,           # split on whitespace
  $sentence1 . " " . $sentence2; # make two sentences one
  sort                   # sort so the answer's always the same
  grep { $bag{$_} == 1 } # filter for words that happen once
  keys %bag;             # return just the keys          
}

View the entire Perl script for this task on GitHub.

Python

As usual, the Python version of a Bag is a Counter. It’s a single statement again, but the order is kinda inside-out. The comments help keep the correlation between the commands between versions.

from collections import Counter

def uncommon_words(sentence1, sentence2):
  return sorted([     # sort so the answer's always the same
    k for k,v in      # return just the keys
    Counter(          # count occurrences of each word
      (sentence1 + " " + sentence2) # make two sentences one
      .split()        # split on whitespace
    ).items() if v == 1 # filter for words that happen once
  ])

View the entire Python script for this task on GitHub.

Elixir

As I noted back in PWC 735, because Enum.filter/2 produces a List of tuples instead of a Map, we need to pipe it through Map.new/1 to make it a Map again. Again, this is a single statement, piping the output of one function call into the next.

def uncommon_words(sentence1, sentence2) do
  sentence1 <> " " <> sentence2 # make two sentences one
  |> String.split           # split on whitespace
  |> Enum.frequencies       # count occurrences of each word
  |> Enum.filter(fn {_, v} -> v == 1 end) # filter for words that happen once
  |> Map.new                # Enum.filter yields list of tuples
  |> Map.keys               # return just the keys
  |> Enum.sort           # sort so the answer's always the same
end

View the entire Elixir script for this task on GitHub.

Task 2: Outermost Parentheses

You are given a valid parentheses string.

Write a script to return the string after removing the outermost parentheses of every primitive string in the primitive decomposition of the given string.

Example 1

Input: $str = "()()()"
Output: ""

Primitive Decomposition: "()" + "()" + "()"

Example 2

Input: $str = "(((())))"
Output: "((()))"

Primitive Decomposition: "(((())))"

Example 3

Input: $str = "(()())(())"
Output: "()()()"

Primitive Decomposition: "(()())" + "(())"

Example 4

Input: $str = "()((()))()"
Output: "(())"

Primitive Decomposition: "()" + "((()))" + "()"

Example 5

Input: $str = "(()(()))(()())"
Output: "()(())()()"

Primitive Decomposition: "(()(()))" + "(()())"

Approach

Really, the “removing the outermost parentheses” part of this isn’t the most work. These strings are just parenthesis, and the primitive strings each begin and end with parentheses. So for each primitive, all we have to do is strip off the first and last character.

The challenge, as it were, is to split the string into primitives. We’re just walking through the string, maintaining a count of opening and closing parentheses, and when we balance out the opening and closing parens, we break off a primitive. It would be more challenging if there was anything else in the strings besides parentheses.

Raku

One of the decisions I made was I wanted to return the list of primitives from the function so they could be printed in the output, but whenever I tried returning ($output, @primitives) from the first example, I wound up getting [["()", "()", "()"],]. I didn’t want a list of lists, I wanted just a list. After a while of trying to flatten the list without success, I decided to just pass an empty list into my function and then populate that.

I knew I would need my primitives function to be recursive once I got my Elixir solution, so I made it recursive to begin with, even though it’s just making a single one-direction pass through the string.

sub primitives($str is copy,       $prim is copy = "",
               $count is copy = 0, @primitives = []) {
  my $char = $str.substr(0,1); # first char
  $str = $str.substr(1);       # remaining string
  $prim ~= $char;             # append char to current primative

  if ($char eq ')') {
    $count--;                  # decrease paren count
    if ($count == 0) {         # we found the end of a primative
      @primitives.push($prim); # add to primative list
      $prim = "";              # clear current primative
    }
  }
  else {
     $count++; # increase paren count
  }
  return @primitives if $str eq ""; # we've finished the string

  # recursively call to process rest of string
  return primitives($str, $prim, $count, @primitives);
}

sub outermostParentheses($str, @primitives) {
  @primitives = primitives($str);
  @primitives.map({ $_.substr(1, *-1)}).join;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $str = "()()()"
Output: ""

Primitive Decomposition: "()" + "()" + "()"

Example 2:
Input: $str = "(((())))"
Output: "((()))"

Primitive Decomposition: "(((())))"

Example 3:
Input: $str = "(()())(())"
Output: "()()()"

Primitive Decomposition: "(()())" + "(())"

Example 4:
Input: $str = "()((()))()"
Output: "(())"

Primitive Decomposition: "()" + "((()))" + "()"

Example 5:
Input: $str = "(()(()))(()())"
Output: "()(())()()"

Primitive Decomposition: "(()(()))" + "(()())"

Perl

The Perl solution is just like the Raku one, except I’m passing in a reference to an array instead of an array, since in Perl, if you want to modify a parameter inside a function and you want to preserve those modifications outside the function, you have to pass your parameters by reference.

sub primitives($str, $prim, $count, $primitives) {
  my $char = substr $str,0,1; # first char
  $str = substr $str, 1;      # remaining string
  $prim .= $char;             # append char to current primative
  if ($char eq ')') {
    $count--;                   # decrease paren count
    if ($count == 0) {          # we found the end of a primative
      push @$primitives, $prim; # add to primative list
      $prim = "";               # clear current primative
    }
  }
  else {
     $count++; # increase paren count
  }
  return if $str eq ""; # we've finished the string

  # recursively call to process rest of string
  primitives($str, $prim, $count, $primitives);
}

sub outermostParentheses($str, $primitives=[]) {
  primitives($str, "", 0, $primitives);
  join '', map { substr $_, 1, -1 } @$primitives;
}

View the entire Perl script for this task on GitHub.

Python

In Python, parameters are passed “by assignment”, which is like passing by reference but the behavior depends on whether the reference is to a mutable object or not. Everything in Python is an object, but things like integers and strings are immutable objects, so any changes made from within a function result in a new object being created; but things like lists and dicts are mutable objects, so adding elements to a list result in the original object being modified.

Which means that in my code that calls the function, I’m creating an empty list to pass in:

primitives = []
output = outermost_parentheses(string, primitives)

def find_primitives(string, prim, count, primitives):
  char   = string[0:1] # first char
  string = string[1:]  # remaining string
  prim   += char       # append char to current primative

  if char == ')':
    count -= 1                # decrease paren count
    if count == 0:            # we found the end of a primative
      primitives.append(prim) # add to primative list
      prim = ""               # clear current primative
  else:
     count += 1 # increase paren count

  if string == "": return  # we've finished the string

  # recursively call to process rest of string
  find_primitives(string, prim, count, primitives)

def outermost_parentheses(string, primitives):
  find_primitives(string, "", 0, primitives)
  return "".join([ p[1:-1] for p in primitives ])

View the entire Python script for this task on GitHub.

Elixir

Elixir, on the other hand, doesn’t allow you to modify variables inside a control structure and have those modifications survive, so if I want to be able to return a list from a function, I need to pass the list out as a return value. Fortunately, returning a tuple of a string value and a list makes this really easy (and is what I was trying to do in Raku to being with).

Not being able to modify a variable from within a control structure and have that modification survive the structure is why the cond do structure from lines 12-25 returns a tuple of {prim, count, primitives}: because even though I’m only modifying prim and primitives in one of the three branches, we need to return the unmodified variables from the other two branches so we can get the modified variables from the one.

def find_primitives(str, _, _, primitives) when str == "",
  do: primitives

def find_primitives(str, prim, count, primitives) do
  char = String.slice(str, 0, 1)   # first char
  str  = String.slice(str, 1, 100) # remaining string
  prim = prim <> char       # append char to current primative

  {prim, count, primitives} = cond do
    char == ")" and count == 1 ->
      {
        "",                  # clear current primative
        0,                   # clear paren count
        primitives ++ [prim] # add to primative list
      }
    char == ")" and count > 1 ->
      # decrease paren count
      {prim, count - 1, primitives}
    true ->
      # increase paren count
      {prim, count + 1, primitives}
  end

  # recursively call to process rest of string
  find_primitives(str, prim, count, primitives)
end

def outermost_parentheses(str) do
  primitives = find_primitives(str, "", 0, [])
  {
    primitives
    |> Enum.map(&( String.slice(&1, 1, String.length(&1)-2) ))
    |> Enum.join,
    primitives
  }
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-385-packy-anderson/challenge-385/packy-anderson

Leave a Reply