Perl Weekly Challenge: Rising in Num

Posted on by

Each week, I’m playing word association with the tasks to pick the musical theme. Originally, this started because one of the tasks was literally a line from a musical. This week, Perl Weekly Challenge 340 was more difficult with the tasks “Duplicate Removals” and “Ascending Numbers”.

But it didn’t take long. I couldn’t think of anything with “duplicate” in it, but “ascending” made me think of “rising”, and I landed on David Roth‘s Rising in Love.

Task 1: Duplicate Removals

You are given a string, $str, consisting of lowercase English letters.

Write a script to return the final string after all duplicate removals have been made. Repeat duplicate removals on the given string until we no longer can.

A duplicate removal consists of choosing two adjacent and equal letters and removing them.

Example 1

Input: $str = 'abbaca'
Output: 'ca'

Step 1: Remove 'bb' => 'aaca'
Step 2: Remove 'aa' => 'ca'

Example 2

Input: $str = 'azxxzy'
Output: 'ay'

Step 1: Remove 'xx' => 'azzy'
Step 2: Remove 'zz' => 'ay'

Example 3

Input: $str = 'aaaaaaaa'
Output: ''

Step 1: Remove 'aa' => 'aaaaaa'
Step 2: Remove 'aa' => 'aaaa'
Step 3: Remove 'aa' => 'aa'
Step 4: Remove 'aa' => ''

Example 4

Input: $str = 'aabccba'
Output: 'a'

Step 1: Remove 'aa' => 'bccba'
Step 2: Remove 'cc' => 'bba'
Step 3: Remove 'bb' => 'a'

Example 5

Input: $str = 'abcddcba'
Output: ''

Step 1: Remove 'dd' => 'abccba'
Step 2: Remove 'cc' => 'abba'
Step 3: Remove 'bb' => 'aa'
Step 4: Remove 'aa' => ''

Approach

This task looks an awful lot like PWC 330‘s Task 1, which was “remove all digits by removing the first digit and the closest non-digit character to its left”. The solution I used that time was a regular expression substitution repeatedly applied until it doesn’t match anymore, and there’s no reason to stray from that approach for an essentially identical task.

But this task also looks a bit like PWC 328‘s Task 2 because it’s looking for duplicate characters, and this reminded me of two things: regular expression backreferences in Raku can be tricky, and I can use recursion to do my looping for me, which will really help when I’m doing the Elixir solution.

Raku

In Raku, in order to do a backreference in a regular expression, you need to embed a code block after the captured match so the variable will be available later.

sub duplicateRemoval($str is copy) {
  return $str
    unless $str ~~ s/(<lower>) {} $0//;
  duplicateRemoval($str);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = 'abbaca'
Output: 'ca'

Example 2:
Input: $str = 'azxxzy'
Output: 'ay'

Example 3:
Input: $str = 'aaaaaaaa'
Output: ''

Example 4:
Input: $str = 'aabccba'
Output: 'a'

Example 5:
Input: $str = 'abcddcba'
Output: ''

Perl

The Perl solution is the same, except getting the backreference is easier.

sub duplicateRemoval($str) {
  return $str
    unless $str =~ s/([a-z])\g1//;
  duplicateRemoval($str);
}

View the entire Perl script for this task on GitHub.

Python

In Python, using backreferences is similarly easy. Doing the match and the replacement in the same statement is less easy, but it’s simple enough to do them separately.

import re

def duplicate_removal(strval):
  m = re.search(r'([a-z])\1', strval)
  if not m: return strval
  return duplicate_removal(
    strval.replace(m.group(0), '', count=1)
  )

View the entire Python script for this task on GitHub.

Elixir

And in Elixir, we use the same match/replace/recurse pattern I’m using in Python.

  def duplicate_removal(str) do
    match = Regex.run(~r/(\p{L})\1/, str, capture: :first)
    if match do
      String.replace(str, match, "", global: false)
      |> duplicate_removal
    else
      str
    end
  end

View the entire Elixir script for this task on GitHub.

Task 2: Ascending Numbers

You are given a string, $str, is a list of tokens separated by a single space. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.

Write a script to check if all the numbers in the given string are strictly increasing from left to right.

Example 1

Input: $str = "The cat has 3 kittens 7 toys 10 beds"
Output: true

Numbers 3, 7, 10 - strictly increasing.

Example 2

Input: $str = 'Alice bought 5 apples 2 oranges 9 bananas'
Output: false

Example 3

Input: $str = 'I ran 1 mile 2 days 3 weeks 4 months'
Output: true


Example 4
Input: $str = 'Bob has 10 cars 10 bikes'
Output: false

Example 5

Input: $str = 'Zero is 0 one is 1 two is 2'
Output: true

Approach

The description of the string in the task would be necessary if we needed to do anything with the tokens that weren’t positive numbers. We could alternately describe the string as positive numbers consisting of digits 0-9 with no leading zeros separated by non-numeric digits. All we need to do is match the numeric digits, put them in a list, and then make sure the list is strictly increasing.

Raku

Fortunately, in Raku there’s a fabulous routine for this: .comb. It returns a Seq of everything in the invocant that matches the regular expression passed.

sub ascendingNum($str) {
  my @list = $str.comb(/\d+/);
  while (@list.elems > 1) {
    return False if @list[0] >= @list[1];
    @list.shift;
  }
  return True;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $str = 'The cat has 3 kittens 7 toys 10 beds'
Output: True

Example 2:
Input: $str = 'Alice bought 5 apples 2 oranges 9 bananas'
Output: False

Example 3:
Input: $str = 'I ran 1 mile 2 days 3 weeks 4 months'
Output: True

Example 4:
Input: $str = 'Bob has 10 cars 10 bikes'
Output: False

Example 5:
Input: $str = 'Zero is 0 one is 1 two is 2'
Output: True

Perl

Really $str.comb(/\d+/) in Raku is just $str =~ /(\d+)/g in Perl.

sub ascendingNum($str) {
  my @list = $str =~ /(\d+)/g;
  while (@list > 1) {
    return 'false' if $list[0] >= $list[1];
    shift @list;
  }
  return 'true';
}

View the entire Perl script for this task on GitHub.

Python

For my Python example, though, the definition as a set of tokens separated by whitespace helped, because that wound up being the easiest way to process it: generating a list of n for n in strval.split() (which splits the string on whitespace) if n.isnumeric(). But then I noticed that the result for example 1 was “false”… and I realized that’s because Python is typed, and "3" < "7" < "10" isn’t true, because they’re strings. 

  list = [ int(n) for n in strval.split() if n.isnumeric() ]
  while len(list) > 1:
    if list[0] >= list[1]: return False
    list.pop(0)
  return True

View the entire Python script for this task on GitHub.

Elixir

As usual with Elixir, the lack of a while loop means we need to use recursion to do our looping. The Regex.scan/3 gives us a list of results, but each result is itself a list, so we need to pipe it through List.flatten/1 to flatten it. I learned my lesson from Python, so I then pipe that list through Enum.map/2 to convert the strings into integers, and then I pipe the numeric list to my ascending/1 function.

def ascending(list) when is_list(list) and length(list) == 1,
  do: "true"

def ascending([head | list]) do
  if head < List.first(list) do
    ascending(list)
  else
    "false"
  end
end

def ascending_num(str) do
   Regex.scan(~r/\d+/, str, capture: :first)
   |> List.flatten
   |> Enum.map(fn n -> String.to_integer(n) end)
   |> ascending
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-340/packy-anderson