Perl Weekly Challenge: Week 387
Challenge 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"
I'll show the Perl version first.
We define some storage for the number of steps taken.
my $steps = 0;
Then we repeatedly substitute 01 with 10 using the /g or global flag to make as many substitutions in one go as possible.
while($str =~ s/01/10/g) {
Each time we do this, we increment $steps.
$steps++;
}
When we cannot make any more substitutions, the loop will end and we can just print
out $steps.
say $steps;
To emulate the Perl version we must give $str the is copy attrivute so its'
underlying value is not considered immutable. The rest is exactly the same.
my $steps = 0;
while $str ~~ s:g/01/10/ {
$steps++;
}
say $steps;
Challenge 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)
I think this would have been better done using Raku's grammar feature to parse the formula but unfortunately I didn't have a lot of time this week so I banged out a solution as best as I could.
MAIN() is very simple.
We define a variable to keep track of the position in $formula we are parsing.
It starts off at 0 i.e. the beginning of the string.
my $position = 0;
We call the parseGroup() function (explained belowe) passing it $formula and
the position. It will return a Hash whose keys are elements and values the number
of atoms of each element.
my %atoms = parseGroup($formula, $position);
We take the .keys() of %atoms...
%atoms
.keys
...and .sort() them into ascending alphabetical order....
.sort
...then for each element, append the number of atoms of it if there were more than 1. If there was only 1, we just keep the element name...
.map({ $_ ~ (%atoms{$_} > 1 ?? %atoms{$_} !! q{}) })
...then we .join() all the elements together into one string...
.join
...and print the results.
.say;
parseGroup() parses an atom count definition within parentheses. It is passed
the $formula and the current $position in the formula. As it will be updating
the position and possibly calling itself recursively, $position needs to be mutable.
But unlike in the previous challenge we don't want a copy of it passed to the function.
So we use the is rw attribute which only removes it's immutable nature.
It should be noted that I am assuming a valid formula was input and I'm not checking
for unmatched parentheses, invalid element names, or trailing unparsed characters etc.
Obviously a production quality script would have to do extensive validation to prevent
auch errors.
sub parseGroup ($formula, $position is rw) {
We create the %atoms hash which will be returned by this function.
my %atoms;
While we haven't reached the end of $formular and the character at the current
position isn't a closing parenthesis...
while $position < $formula.chars && $formula.substr($position, 1) ne q{)} {
...we create a Hash to store details about the current group.
my %group;
If the character at the current position is an opening parenthesis...
if $formula.substr($position, 1) eq q{(} {
...we neeed to advance the position and recursively call parseGroup() again.
Afterwards, we advance the position one more time.
$position++;
%group = parseGroup($formula, $position);
$position++;
Otherwise we read in an element name and store it in %group assing it an
initial count of 1.
} else {
my $start = $position++;
while $position < $formula.chars &&
$formula.substr($position, 1) ~~ /<[a..z]>/ {
$position++;
}
my $element = $formula.substr($start, $position - $start);
%group{$element} = 1;
}
To get the proper count we need to call parseNumber() (see below) to get a
number. We multiply the counts of every element in %group by that number. The
results are added to %atoms.
my $multiplier = parseNumber($formula, $position);
for %group.keys -> $key {
%atoms{$key} += %group{$key} * $multiplier;
}
}
Finally, %atoms is returned.
return %atoms;
}
parseNumber() also takes $formula and $position as its' parameters. It reads
in digits and stops when their are no more or the end of formula has been reached.
sub parseNumber ($formula, $position is rw) {
my $start = $position;
while $position < $formula.chars && $formula.substr($position, 1) ~~ /\d/ {
$position++
}
If no digits were found, it returns 1 or otherwise, the string of digits.
return $position == $start
?? 1
!! $formula.substr($start, $position - $start);
}
The Perl version mostly works the same way except $position has to be passed
around by reference and derefenced whenever it is used which is a bit awkward to
read.
my $position = 0;
my $atoms = parseGroup($formula, \$position);
say join q{}, map { $_ . ($atoms->{$_} > 1 ? $atoms->{$_} : q{}) }
sort keys %{$atoms};
sub parseNumber ($formula, $position) {
my $start = ${$position};
while (${$position} < length($formula) &&
substr($formula, ${$position}, 1) =~ /\d/) {
${$position}++
}
return ${$position} == $start
? 1
: substr($formula, $start, ${$position} - $start);
}
sub parseGroup ($formula, $position) {
my %atoms;
while (${$position} < length($formula) &&
substr($formula, ${$position}, 1) ne q{)}) {
my %group;
if (substr($formula, ${$position}, 1) eq q{(}) {
${$position}++;
%group = %{parseGroup($formula, $position)};
${$position}++;
} else {
my $start = ${$position}++;
while (${$position} < length($formula) &&
substr($formula, ${$position}, 1) =~ /[a-z]/) {
${$position}++;
}
my $element = substr($formula, $start, ${$position} - $start);
$group{$element} = 1;
}
my $multiplier = parseNumber($formula, $position);
for (keys %group) {
$atoms{$_} += $group{$_} * $multiplier;
}
}
return \%atoms;
}