Perl Weekly Challenge: Regex Man Hates Atom Man

Posted on by

Perl Weekly Challenge 387‘s tasks are “Rearrange Binary String” and “Atoms Count”.

When I saw that one of this week’s tasks was counting atoms, I thought “This is a job for PARTICLE MAN!!!“

Task 1: Rearrange Binary String

You are given a binary string string.

Write a script to re-arrange the given binary string that all occurrences of “01” are simultaneously replaced with “10” until no occurrences of “01” exist. Finally return the total steps needed.

Example 1

Input: $str = "111000"
Output: 0

The string already has all 1s on the left and 0s on the right.
There are no occurrences of "01", so zero step needed.

Example 2

Input: $str = "00011"
Output: 4

Step 1: "00101"
Step 2: "01010"
Step 3: "10100"
Step 4: "11000"

Example 3

Input: $str = "01011"
Output: 3

Step 1: "10101"
Step 2: "11010"
Step 3: "11100"

Example 4

Input: $str = "010101"
Output: 3

Step 1: "101010"
Step 2: "110100"
Step 3: "111000"

Example 5

Input: $str = "00001"
Output: 4

Step 1: "00010"
Step 2: "00100"
Step 3: "01000"
Step 4: "10000"

Approach

I saw this and immediately thought of regular expressions. First we use the regex /^1+0+$/ to check whether we’ve reached the stopping condition, then the regex s/01/10/g to replace all the occurrences of “01” with “10”. We keep looping until we meet the stopping condition, and we keep track of how many times we looped.

Raku

Of course, if I want to reproduce the “steps” output in the examples, the easiest way is to just keep all the steps in list, and then use the list to count how many steps I took.

sub rearrangeBinaryString($str is copy) {
  my @steps;
  while ($str !~~ /^1+0+$/) {
    $str ~~ s:g/01/10/;
    @steps.push($str);
  }
  return @steps.elems, @steps;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = "111000"
Output: 0

Example 2:
Input: $str = "00011"
Output: 4

Step 1: "00101"
Step 2: "01010"
Step 3: "10100"
Step 4: "11000"

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

Step 1: "10101"
Step 2: "11010"
Step 3: "11100"

Example 4:
Input: $str = "010101"
Output: 3

Step 1: "101010"
Step 2: "110100"
Step 3: "111000"

Example 5:
Input: $str = "00001"
Output: 4

Step 1: "00010"
Step 2: "00100"
Step 3: "01000"
Step 4: "10000"

Perl

As usual, the Perl solution looks a lot like the Raku solution. Mostly I had to change how the regular expression substitution happened, rearrange how push worked, and use scalar to count the steps.

sub rearrangeBinaryString($str ) {
  my @steps;
  while ($str !~ /^1+0+$/) {
    $str =~ s/01/10/g;
    push @steps, $str;
  }
  return scalar(@steps), @steps;
}

View the entire Perl script for this task on GitHub.

Python

Python’s big difference is a decided to compile the stopping condition once, which provided an object I could name stop_condition and then call .match() on, making it read very nicely.

import re

stop_condition = re.compile(r'^1+0+$')

def rearrange_binary_string(string):
  steps = []
  while not stop_condition.match(string):
    string = re.sub(r'01', '10', string)
    steps.append(string)
  return len(steps), steps

View the entire Python script for this task on GitHub.

Elixir

As usual with Elixir, when I’ve got an unbounded loop, I’m doing it through recursion. If we don’t meet the stopping condition, we do a replacement once, and then recursively call ourselves with the new string and the appended list of steps.

def rearrange_binary_string(str, steps \\ []) do
  steps = if not Regex.match?(~r/^1+0+$/, str) do
    str = Regex.replace(~r/01/, str, "10")
    {_, steps} = rearrange_binary_string(str, steps ++ [str])
    steps
  else
    steps
  end
  {length(steps), steps}
end

View the entire Elixir script for this task on GitHub.

Task 2: Atoms Count

You are given a chemical formula with elements, numbers, and parentheses.

Write a script to count the total number of each type of atom by expanding all grouped multipliers. Then, format and return the final inventory as a single string sorted alphabetically by element name, including the total count only if it is greater than 1.

Example 1

Input: $formula = "((N2O)3(H2O)2)2"
Output: "H8N12O10"

Step 1: Expand the innermost parentheses
    (N2O)3 => N = 2*3 = 6, O = 1*3 = 3 => N6O3
    (H2O)2 => H = 2*2 = 4, O = 1*2 = 2 => H4O2

Step 2: Combine inside the outer parentheses
    Formula becomes: (N6O3 H4O2)2
    Sum up identical elements inside: (N6 H4 O5)2

Step 3: Apply the outer multiplier
    N = 6*2 = 12
    H = 4*2 = 8
    O = 5*2 = 10

Step 4: Sort alphabetically and format
    Alphabetical order: H, N, O
    Counts: H: 8, N: 12, O: 10

Example 2

Input: $formula = "Mg3(PO4)2"
Output: "Mg3O8P2"

Step 1: Parse ungrouped elements
    Mg3 => Mg = 3

Step 2: Expand parentheses (PO4)2
    P = 1*2 = 2
    O = 4*2 = 8

Step 3: Total up counts
    Mg = 3
    P  = 2
    O  = 8

Step 4: Sort alphabetically and format
    Alphabetical order: Mg, O, P
    Counts: Mg: 3, O: 8, P: 2

Example 3

Input: $formula = "(((H)2)3)4"
Output: "H24"

Step 1: Expand innermost level (H)2
    H = 1*2 = 2 => formula becomes ((H2)3)4

Step 2: Expand middle level (H2)3
    H = 2*3 = 6 => formula becomes (H6)4

Step 3: Expand outer level (H6)4
    H = 6*4 = 24

Step 4: Sort alphabetically and format
    Single element: H: 24

Example 4

Input: $formula = "NaCl3(O2(S10)2)2Mg"
Output: "Cl3MgNaO4S40"

Step 1: Expand innermost parentheses (S10)2
    S = 10*2 = 20 => inner formula becomes => O2S20

Step 2: Expand outer parentheses (O2S20)2
    O = 2*2  = 4
    S = 20*2 = 40

Step 3: Combine all parts
    Ungrouped start: Na (Na = 1), Cl3 (Cl = 3)
    Expanded middle: O = 4, S = 40
    Ungrouped end: Mg (Mg = 1)

Step 4: Sort alphabetically and format
    Alphabetical order: Cl (3), Mg (1), Na (1), O (4), S (40)
    Omit the number 1 for Mg and Na.

Example 5

Input: $formula = "Z2Y3(X2W)2"
Output: "W2X4Y3Z2"

Step 1: Parse ungrouped elements
    Z2 => Z = 2
    Y3 => Y = 3

Step 2: Expand parentheses (X2W)2
    X = 2*2 = 4
    W = 1*2 = 2

Step 3: Total up counts
    W = 2, X = 4, Y = 3, Z = 2

Step 4: Sort alphabetically and format
    Alphabetical order: W (2), X (4), Y (3), Z (2)

Approach

Ok, first, this task plays fast and loose with element abbreviations. There are no elements X or Z (there’s Xe, Zn, and Zr), and I have no idea if they’d bond with Tungsten or Yttrium, so we’re going to make an assumption: an element is a single upper-case letter followed by zero or one lower case letters.

So we need to take multiple passes through a string to pull out parenthetical atom groups and normalize them. I figure a regular expression that matches a left parenthesis, any number of characters that are not a right parenthesis, a right parenthesis, and the any number of numeric digits will do this. Once we have (atoms)num, we figure out what the atoms in atoms are, then multiply their quantities by num, and put that back in the original string.

Once we’ve eliminated all the parenthetical groups, we can count up all the atoms, sort them, make sure we don’t put counts after the atoms that only appear once, and output the string.

Raku

First, I wrote a normalizeAtoms helper function to take strings in the form "Xe3Y2Zr5" and break it up into a hash of element names and atom counts and then reconstitute that hash with the atoms sorted. As a bonus, on line 9, I have the atom count not only adding to the value of the existing atom count, so if the count doesn’t exist, it’s autovivified, but if it does exist, it adds to the existing value (thus allowing strings like "O2N2O2" to get broken down into {N => 2, O => 4}), but also taking a multiplier, so I could take a string like "(O2N2O2)2", pass it in as normalizeAtoms("O2N2O2", 2), produce a hash like {N => 4, O => 8}, and then return the string "N4O8".

Then I wrote the atomsCount() function. It loops over the formula and looks for parenthetical groups. Because my regex only matches non-paren characters inside the parentheses, this will wind up processing the innermost parentheses first.

I take note of the original substring that I’m normalizing so I can perform a substitution later (line 18). Then I use another regex to extract the string portion inside the parens and the count outside the parens (line 19). I pass these two values to the normalizeAtoms helper function to get back a normalized string, and then replace the substring with the normalized string. And I keep looping over the formula until there are no more parenthetical groups.

Then I pass the formula to normalizeAtoms one more time to group atoms together, and return the result.

sub normalizeAtoms($str, $multiplier = 1) {
  my (%atoms, $output);
  my $match = $str ~~ m:g/(<:Lu><:Ll>?)(\d*)/;
  for $match.list -> $m {
    my ($k, $v) = ($m[0], $m[1].Str || 1);
    %atoms{$k} += $v * $multiplier;
  }
  for %atoms.keys.sort -> $k {
    $output ~= %atoms{$k} == 1 ?? $k !! $k ~ %atoms{$k};
  }
  $output;
}

sub atomsCount($formula is copy) {
  # while we have parenthetical groups
  while (my $match = $formula ~~ m/(\(<-[\(\)]>+\)\d+)/) {
    my $orig = $match[0]; # save for later
    # grab values for ($str)$count
    my ($str, $count) = ($orig ~~ /\((.+)\)(\d+)/)[0,1];
    $str = normalizeAtoms($str, $count); # count atoms in string
    $formula ~~ s/$orig/$str/; # replace orig with normalized
  }
  normalizeAtoms($formula); # normalize one more time
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $formula = "((N2O)3(H2O)2)2"
Output: "H8N12O10"

Example 2:
Input: $formula = "Mg3(PO4)2"
Output: "Mg3O8P2"

Example 3:
Input: $formula = "(((H)2)3)4"
Output: "H24"

Example 4:
Input: $formula = "NaCl3(O2(S10)2)2Mg"
Output: "Cl3MgNaO4S40"

Example 5:
Input: $formula = "Z2Y3(X2W)2"
Output: "W2X4Y3Z2"

Perl

Besides the changes in regex syntax and regex matches not returning match objects, the other big change I noted I needed to make translating Raku to Perl was on line 23; because the original string I was replacing had parenthesis in it, I needed to run it through quotemeta to escape those parens before I could use it in the substitution regex.

sub normalizeAtoms($str, $multiplier = 1) {
  my (%atoms, $output);
  while ($str =~ m/(\p{Lu}\p{Ll}?)(\d*)/g) {
    my ($k, $v) = ($1, $2 || 1);
    $atoms{$k} += $v * $multiplier;
  }
  for my $k (sort keys %atoms) {
    $output .= $atoms{$k} == 1 ? $k : $k . $atoms{$k};
  }
  $output;
}

sub atomsCount($formula) {
  # while we have parenthetical groups
  while ($formula =~ m/(\([^\(\)]+\)\d+)/) {
    my $orig = $1; # save for later
    # grab values for ($str)$count
    my ($str, $count) = $orig =~ /\((.+)\)(\d+)/;
    $str = normalizeAtoms($str, $count); # count atoms in string
    $orig = quotemeta($orig); # quote the parens
    $formula =~ s/$orig/$str/; # replace orig with normalized
  }
  normalizeAtoms($formula); # normalize one more time
}

View the entire Perl script for this task on GitHub.

Python

In Python, I made some tweaks. Because everything is an object, and strings are non automatically converted to integers, I check to see if the multiplier passed into normalize_atoms is a str object, and if it is, convert it to an int (line 7). This allows me to take the result of my match for the string portion outside the parens and the count (line 20), and just pass that into normalize_atoms as-is (line 21). Also, because I’m passing in the original string into functions as a parameter and not using it in a regex substitution, I can just use match.group(1) instead of saving it off into a variable orig.

And I’m using a Counter instead of a straight dictionary because Counter objects return a zero count for missing items instead of raising a KeyError, simulating Raku/Perl’s autovivication.

import re
from collections import Counter

def normalize_atoms(string, multiplier = 1):
  if isinstance(multiplier, str): multiplier = int(multiplier)
  atoms  = Counter()
  output = ""
  for k, v in re.findall(r'([A-Z][a-z]?)(\d*)', string):
    v = 1 if v == "" else int(v)
    atoms[k] += v * multiplier
  for k in sorted(atoms.keys()):
    output += k + str(atoms[k]) if atoms[k] > 1 else k 
  return output

def atoms_count(formula):
  while match := re.search(r'(\([^\(\)]+\)\d+)', formula):
    # grab values for ($str)$count
    m = re.match(r'\((.+)\)(\d+)', match.group(1)) 
    string = normalize_atoms(*m.group(1,2)) # count atoms in string
    formula = formula.replace(match.group(1), string)
  return normalize_atoms(formula)

View the entire Python script for this task on GitHub.

Elixir

In Elixir, because the loop matching the parenthetical expressions is unbounded, I decided to use recursion to do the looping. atoms_count/1 checks to see if the formula has a parenthetical expression, and if it does, it normalizes it, replaces it in the formula, and then recursively calls atoms_count/1 until the formula no longer matches the regex. Then it calls normalize_atoms/2 one final time to produce the output string.

I’m passing some interesting options to Regex.run/3:

@has_parens ~r/(\([^\(\)]+\)\d+)/

def normalize_atoms(str, multiplier \\ 1) do
  multiplier = if is_integer(multiplier),
    do: multiplier, else: String.to_integer(multiplier)
  atoms = Regex.scan(~r/([A-Z][a-z]?)(\d*)/, str)
  |> Enum.reduce(%{}, fn [_, k, v], atoms ->
    v = if v == "", do: 1, else: String.to_integer(v)
    Map.put(atoms, k, Map.get(atoms, k, 0) + v * multiplier)
  end)
  sorted = Map.keys(atoms) |> Enum.sort
  Enum.reduce(sorted, "", fn k, output ->
    v = Map.get(atoms, k)
    output <> if v == 1, do: k, else: k <> Integer.to_string(v)
  end)
end

def atoms_count(formula) do
  formula = if Regex.match?(@has_parens, formula) do
    [match] = Regex.run(@has_parens, formula, capture: :first)
    [str, count] = Regex.run(~r/\((.+)\)(\d+)/, match,
      capture: :all_but_first)
    str = normalize_atoms(str, count) # count atoms in string
    atoms_count(String.replace(formula, match, str))
  else
    formula
  end
  normalize_atoms(formula)
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-387-packy-anderson/challenge-387/packy-anderson

Leave a Reply