Perl Weekly Challenge: Whoa-oh-oh! Sing about parens!

Posted on by

With Perl Weekly Challenge 346‘s tasks being “Longest Parenthesis” and “Magic Expression”, I had a bunch of ideas for music, so I went with the first one that popped into my head: Billy Joel’s “The Longest Time“.

Who knows how much further I’ll be able to torture the intro before diving into PWC 346…

Task 1: Longest Parenthesis

You are given a string containing only ( and ).

Write a script to find the length of the longest valid parenthesis.

Example 1

Input: $str = '(()())'
Output: 6

Valid Parenthesis: '(()())'

Example 2

Input: $str = ')()())'
Output: 4

Valid Parenthesis: '()()' at positions 1-4.

Example 3

Input: $str = '((()))()(((()'
Output: 8

Valid Parenthesis: '((()))()' at positions 0-7.

Example 4

Input: $str = '))))((()('
Output: 2

Valid Parenthesis: '()' at positions 6-7.

Example 5

Input: $str = '()(()'
Output: 2

Valid Parenthesis: '()' at positions 0-1 and 3-4.

Approach

Let’s think a little bit about what makes a set of parenthesis “valid”. What we want is not just an equal number of opening and closing parenthesis, we want them to be of the form

<valid> ::= "()" | <valid> "()" | "()" <valid> | "(" <valid> ")"

That suggests that we want to use recursion to find valid strings of parenthesis, but another thing struck me: if you’re processing the string character by character, counting how many open sets of parenthesis you have, you know the string you’re processing is invalid if the count ever goes below zero, or if at the end the count is above zero. If we keep track of all the valid strings we encounter along the way, we won’t need to deal with the extra overhead of recursion.

Raku

sub longestParen($str) {
  my @found;
  for 0..$str.chars-2 -> $start {
    my $count = 0;
    for $start..$str.chars-1 -> $end {
      my $c = $str.substr($end, 1);
      my $substring = $str.substr($start..$end);
      if ($c eq "(") {
        $count++;
      }
      else {
        $count--;
      }
      # unbalanced left paren
      last if $count < 0;
      # we have exactly as many right parens as we've seen left
      @found.push($substring) if $count == 0;
    }
    # if we've reached the end of $str and we're at 0,
    # any valid paren strings we find in subsequent outer loop
    # iterations will be substrings
    last if $count == 0;
  }
  return (@found.sort: *.chars)[*-1].chars;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = '(()())'
Output: 6

Example 2:
Input: $str = ')()())'
Output: 4

Example 3:
Input: $str = '((()))()(((()'
Output: 8

Example 4:
Input: $str = '))))((()('
Output: 2

Example 5:
Input: $str = '()(()'
Output: 2

Perl

sub longestParen($str) {
  my @found;
  for my $start (0 .. length($str) - 2) {
    my $count = 0;
    for my $end ($start .. length($str) - 1) {
      my $c = substr($str, $end, 1);
      my $substring = substr($str, $start, $end-$start+1);
      if ($c eq "(") {
        $count++;
      }
      else {
        $count--;
      }
      # unbalanced left paren
      last if $count < 0;
      # we have exactly as many right parens as we've seen left
      push @found, $substring if $count == 0;
    }
    # if we've reached the end of $str and we're at 0,
    # any valid paren strings we find in subsequent outer loop
    # iterations will be substrings
    last if $count == 0;
  }
  return length((sort {length($a) <=> length($b)} @found)[-1]);

View the entire Perl script for this task on GitHub.

Python

def longest_paren(my_str):
  found = []
  for start in range(len(my_str)-1):
    count = 0
    for end in range(start, len(my_str)):
      c = my_str[end:end+1]
      substring = my_str[start:end+1]
      if c == "(":
        count += 1
      else:
        count -= 1
      # unbalanced left paren
      if count < 0: break
      # we have exactly as many right parens as we've seen left
      if count == 0: found.append(substring)
    # if we've reached the end of $str and we're at 0,
    # any valid paren strings we find in subsequent outer loop
    # iterations will be substrings
    if count == 0: break
  found.sort(key=len)
  return len(found[-1])

View the entire Python script for this task on GitHub.

Elixir

As usual, I’m simulating the loops with recursion in Elixir.

# we're at the end of the outer loop
def longest_paren(_, len, found, start, stop, _)
  when start == len and stop == len, do: found

# we're at the end of the inner loop, next outer loop iteration
def longest_paren(str, len, found, start, stop, _)
  when start < len and stop == len, do:
  longest_paren(str, len, found, start+1, start+1, 0)

def longest_paren(str, len, found, start, stop, count) do
  c = String.slice(str, stop, 1)
  substring = String.slice(str, start, stop-start+1)
  count = cond do
    c == "(" -> count + 1
    c == ")" -> count - 1
  end
  cond do
    # unbalanced left paren
    count < 0 ->
      longest_paren(str, len, found, start+1, start+1, 0)

    # if we've reached the end of $str and we're at 0,
    # any valid paren strings we find in subsequent outer loop
    # iterations will be substrings
    count == 0 and stop == len-1 ->
      found ++ [substring]

    # we have exactly as many right parens as we've seen left
    count == 0 ->
      longest_paren(str, len, found ++ [substring],
                    start, stop+1, count)

    # process the next inner loop iteration
    true ->
      longest_paren(str, len, found, start, stop+1, count)
  end
end

def longest_paren(str) do
  longest_paren(str, String.length(str), [], 0, 0, 0)
  |> Enum.sort(&(String.length(&1) >= String.length(&2)))
  |> List.first
  |> String.length
end

View the entire Elixir script for this task on GitHub.

Task 2: Magic Expression

You are given a string containing only digits and a target integer.

Write a script to insert binary operators +, - and * between the digits in the given string that evaluates to target integer.

Example 1

Input: $str = "123", $target = 6
Output: ("1*2*3", "1+2+3")

Example 2

Input: $str = "105", $target = 5
Output: ("1*0+5", "10-5")

Example 3

Input: $str = "232", $target = 8
Output: ("2*3+2", "2+3*2")

Example 4

Input: $str = "1234", $target = 10
Output: ("1*2*3+4", "1+2+3+4")

Example 5

Input: $str = "1001", $target = 2
Output: ("1+0*0+1", "1+0+0+1", "1+0-0+1", "1-0*0+1", "1-0+0+1", "1-0-0+1")

Approach

When I looked at the problem, at first I thought that there were three operators we needed to place between the characters in the string, but then I looked at the second output string for example 2 and I realized there was a fourth: the empty string. So what we want to do is find all the combinations of the digits and binary operators (and the empty string) that evaluate to the target integer. To me, that says that we want to use an eval to do the math.

Then I turned to the problem of creating all the combinations. This really felt like a tree traversal to me:

But since I couldn’t come up with a way to make the traversal work so it only visited each node once, I cheated by using a hash to store the solutions that evaluated to the target number.

Raku

In Raku, EVAL is discouraged enough that there’s a warning about using it unless a specific pragma is turned on:

In case the MONKEY-SEE-NO-EVAL pragma is not activated, the compiler will complain with EVAL is a very dangerous function!!!. And it is essentially right, since that will run arbitrary code with the same permissions as the program. You should take care of cleaning the code that is going to pass through EVAL if you activate the MONKEY-SEE-NO-EVAL pragma.

sub targetMatch($target, $str) {
  my $result;
  use MONKEY-SEE-NO-EVAL;
  EVAL "\$result = $str";
  $result == $target;
}

multi magicExpression($op, $target, @digits, @ops is copy, $pos,
                      %found) {
  @ops[$pos] = $op;
  my $str = (@digits Z~ (@ops,"").flat).join("");
  %found{$str} = 1 if $str !~~ /\D0\d+/
                   && targetMatch($target, $str);
  magicExpression($target, @digits, @ops, $pos+1, %found);
}

multi magicExpression($target, @digits, @ops, $pos, %found) {
  return if $pos > @ops.end; # terminate recusrion

  magicExpression("",  $target, @digits, @ops, $pos, %found);
  magicExpression("+", $target, @digits, @ops, $pos, %found);
  magicExpression("-", $target, @digits, @ops, $pos, %found);
  magicExpression("*", $target, @digits, @ops, $pos, %found);
}

multi magicExpression($target, $str) {
  my %found;
  my @digits = $str.comb;
  magicExpression($target, @digits, ""xx@digits.end, 0, %found);
  return %found.keys;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $str = "123", $target = 6
Output: ("1+2+3", "1*2*3")

Example 2:
Input: $str = "105", $target = 5
Output: ("10-5", "1*0+5")

Example 3:
Input: $str = "232", $target = 8
Output: ("2*3+2", "2+3*2")

Example 4:
Input: $str = "1234", $target = 10
Output: ("1*2*3+4", "1+2+3+4")

Example 5:
Input: $str = "1001", $target = 2
Output: ("1-0-0+1", "1-0*0+1", "1+0*0+1", "1-0+0+1", "1+0+0+1",
         "1+0-0+1")

Perl

In Perl, it’s easier to pass around references to arrays and hashes than it is to pass around arrays and hashes themselves, so I made that change. And there’s no multi, so I had to give the functions different names. And eval doesn’t require a pragma to work without a warning in Perl…

sub targetMatch($target, $str) {
  my $result;
  eval "\$result = $str";
  $result == $target;
}

sub magicExpression3($op, $target, $digits, $ops, $pos, $found){
  $ops->[$pos] = $op;
  my $str = join("", zip(@$digits, @{[@$ops,""]}));

  $found->{$str} = 1 if $str !~ /\D0\d+/
                   && targetMatch($target, $str);
  magicExpression2($target, $digits, $ops, $pos+1, $found);
}

sub magicExpression2($target, $digits, $ops, $pos, $found) {
  return if $pos >= @$ops; # terminate recusrion

  magicExpression3("",  $target, $digits, $ops, $pos, $found);
  magicExpression3("+", $target, $digits, $ops, $pos, $found);
  magicExpression3("-", $target, $digits, $ops, $pos, $found);
  magicExpression3("*", $target, $digits, $ops, $pos, $found);
}

sub magicExpression($target, $str) {
  my %found;
  my $digits = [ split //, $str ];
  my $ops = [ map { "" } 1 .. length($str)-1 ];
  magicExpression2($target, $digits, $ops, 0, \%found);
  return keys %found;
}

View the entire Perl script for this task on GitHub.

Python

Unfortunately, the zip function in Python yields tuples, so I needed to pull in itertools’ chain to flatten that out.

I did run into an odd problem, though: even though the re documentation says that the escape sequences \d and \D are valid, when I tried to use them on line 6, I got the following:

SyntaxWarning: invalid escape sequence '\D'
SyntaxWarning: invalid escape sequence '\d'

So I fell back and used an old-fashioned character set

from itertools import chain
import re

has_leading_zero = re.compile("[^0-9]0[0-9]+")

def to_str(digits, ops):
  return "".join(
    list( chain.from_iterable( zip(digits, ops+[""]) ) )
  )

def magic_expression3(op, target, digits, ops, pos, found):
  ops[pos] = op
  mystr = to_str(digits, ops)
  if not has_leading_zero.search(mystr) and target==eval(mystr):
    found[mystr] = 1
  magic_expression2(target, digits, ops, pos+1, found)

def magic_expression2(target, digits, ops, pos, found):
  if pos >= len(ops): return # terminate recusrion
  magic_expression3("",  target, digits, ops, pos, found)
  magic_expression3("+", target, digits, ops, pos, found)
  magic_expression3("-", target, digits, ops, pos, found)
  magic_expression3("*", target, digits, ops, pos, found)

def magic_expression(target, mystr):
  found = {}
  digits = list(mystr)
  ops = [ "" for x in range(len(mystr)-1)]
  magic_expression2(target, digits, ops, 0, found)
  return found.keys()

View the entire Python script for this task on GitHub.

Elixir

Because I’d done this in Raku not only with recursion but with a multi, coding this in Elixir was a cinch. There’s a new function that I don’t usually use, though, and that’s Code.eval_string/3. I wrote a little wrapper function for it because it returns a tuple, and the result we want is the first element of that tuple.

But I did change around the parameter order for magic_expression/6 so the first parameter was the found map; I did this so I could pipe the value of found being returned by the function into the next iteration (see lines 27-30).

def eval(str) do
  {result, _} = Code.eval_string(str)
  result
end

def magic_expression(found, op, target, digits, ops, pos) do
  ops = List.replace_at(ops, pos, op)
  str = Enum.zip(digits, ops++[""])
  |> Enum.flat_map(fn t -> Tuple.to_list(t) end)
  |> Enum.join
  found = cond do
    !Regex.run(~r/\D0\d+/,str) && target == eval(str) ->
      Map.put(found, str, 1)
    true ->
      found
  end
  magic_expression(target, digits, ops, pos+1, found)
end

def magic_expression(_, _, ops, pos, found)
  when pos >= length(ops), do: found

def magic_expression(target, digits, ops, pos, found) do
  magic_expression(found, "", target, digits, ops, pos)
  |> magic_expression("+", target, digits, ops, pos)
  |> magic_expression("-", target, digits, ops, pos)
  |> magic_expression("*", target, digits, ops, pos)
end

def magic_expression(target, str) do
  magic_expression(
    target,
    String.codepoints(str),
    List.duplicate("", String.length(str)-1),
    0,  # pos
    %{} # found
  )
  |> Map.keys
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-346/packy-anderson

Leave a Reply