Weekly Challenge: Ascending Regex to remove the Duplicates

Weekly Challenge 340

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Duplicate Removals

Task

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.

My solution

Thanks to regular expressions this is relatively straight forward. We can use the expression (.)\1 to get two of the same character. . will match any single letter, () will capture it, and \1 will use the capture.

For the Python solution, I run the regexp on the input_string and store it in a variable called new_string. If it is the same, I return it. If it is different (because we removed two characters), I reset input_string and call the loop again.

def duplicate_removals(input_string: str) -> str:
    while True:
        new_string = re.sub(r'(.)\1', '', input_string)
        if new_string == input_string:
            return new_string
        input_string = new_string

In Perl, calling the s function returns the number of substitutions made. Therefore the Perl solution uses this feature rather than using the new_string variable. The loop will exit when no substitutions are made.

sub main ($input_string) {
    my $changes = 1;
    while ($changes) {
        $changes = ($input_string =~ s/(.)\1+//g);
    }

    say "'$input_string'";
}

Examples

$ ./ch-1.py abbaca
'ca'

$ ./ch-1.py azxxzy
'ay'

$ ./ch-1.py aaaaaaaa
''

$ ./ch-1.py aabccba
'a'

$ ./ch-1.py abcddcba
''

Task 2: Ascending Numbers

Task

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.

My solution

The first thing I do is extract the numbers from input_string (str is a reserved word in Python). For this I use list comprehension, along with a regular expression to return words that contain digits only.

def ascending_numbers(input_string: str) -> bool:
    number_list = [int(n) for n in input_string.split() if re.match(r'^\d+$', n)]

Perl doesn't have list comprehension, but the same functionality can be achieved by using the grep function.

sub main ($input_string) {
    my @number_array = grep { /^\d+$/ } split /\s+/, $input_string;

It's then a matter of checking that the list (array in Perl) is sorted correctly. For this I have a loop with the variable i. It starts at 1, to one less than the length of the number_list list. For each iteration, I check that the number at the position i-1 is less than the number at position i. If it isn't, I return False. If the loop is exhausted, I return True.

    for i in range(1, len(number_list)):
        if number_list[i-1] >= number_list[i]:
            return False

    return True

The Perl code follows a similar pattern.

    foreach my $i ( 1 .. $#number_array ) {
        if ( $number_array[ $i - 1 ] >= $number_array[$i] ) {
            say "false";
            return;
        }
    }
    say "true";

Examples

$ ./ch-2.py "The cat has 3 kittens 7 toys 10 beds"
True

$ ./ch-2.py 'Alice bought 5 apples 2 oranges 9 bananas'
False

$ ./ch-2.py 'I ran 1 mile 2 days 3 weeks 4 months'
True

$ ./ch-2.py 'Bob has 10 cars 10 bikes'
False

$ ./ch-2.py 'Zero is 0 one is 1 two is 2'
True