I’ve been doing the Weekly
Challenges. The
latest
involved string rearrangements and rational numbers. (Note that this
ends today.)
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.
This be done with regular expressions, but in the spirit of not
automatically using them everywhere I also built a character by
character match version. Each loop iterates through the string looking
for an "01" pattern; if it finds one, it increments the counter by two
and puts "10" to the output string, otherwise it sends the character
to output unchanged and increments the counter.
With regexps, in Crystal:
def rearrangebinarystring(a0)
Initialise the loop count.
ct = 0
Copy the input.
a = a0
Loop infinitely.
while true
Replace all instances of the character combination:
b = a.gsub("01", "10")
If no changes, drop out with the count we have (which might be zero).
if b == a
break
else
Otherwise, reload the input, increment the count, and go round again.
a = b
ct += 1
end
end
ct
end
Without regexps, in Rust:
fn rearrangebinarystring(a0: &str) -> usize {
let mut ct = 0;
let mut a = a0.to_owned().clone();
loop {
let mut dirty = false;
let mut b = String::new();
Loop through the characters and do the substitutions.
let c = a.chars().collect::<Vec<char>>();
let mut ci = 0;
while ci < c.len() {
if c[ci] == '0' && ci + 1 < c.len() && c[ci + 1] == '1' {
b.push('1');
b.push('0');
ci += 2;
dirty = true;
} else {
b.push(c[ci]);
ci += 1;
}
}
Check whether we actually did any substitutions.
if dirty {
ct += 1;
a = b.clone();
} else {
break;
}
}
ct
}
Task 2: Rational Numbers
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.
I wrote this as a parser with four possible terms, matched greedily:
- (Element symbol)(number) - a count of atoms.
- (Element symbol) - implicitly the next thing is not a number or we'd
have matched type 1. One atom.
- (open parenthesis) - start a new multiplication group.
- (close parenthesis)(number) - end that multiplication group.
And an element symbol is an upper-case letter followed by zero or more
lower-case letters.
So I initialise an empty counter and go through the input string token
by token. (1) and (2) add an item to the current counter; (3) pushes a
new empty counter onto the stack; and (4) multiplies up the counter at
the top of the stack, removes it, and adds its contents to the counter
below.
(There are no examples in the tests of a close parenthesis without a
number, and in this format the only purpose of the parentheses is to
indicate multiplication so there's no reason to expect it.)
Then it's just a matter of formatting the counter for the desired
output. In Perl:
sub atomscount($a) {
Initialise index into string, and stack.
my $i = 0;
my @stack = ({});
Loop through the string. (In each case the index will be incremented
based on the length of the match. Perhaps a more Perlish way would be
to add (.*)$ at the end of each regexp.)
while ($i < length($a)) {
We're working only with the input starting at $i.
my $as = substr($a, $i);
Case 1, an element and a number. Add to the counter on top of the
stack.
if ($as =~ /^([A-Z][a-z]?)([0-9]+)/) {
my $element = $1;
my $ct = $2;
$stack[-1]{$element} += $ct;
$i += length($element) + length($ct);
Case 2, an element and no number. Add to the counter on top of the
stack.
} elsif ($as =~ /^([A-Z][a-z]?)/) {
my $element = $1;
$stack[-1]{$element} += 1;
$i += length($element);
Case 3, open parenthesis. Push a new counter onto the stack.
} elsif ($as =~ /^\(/) {
push @stack, {};
$i += 1;
Case 4, close parenthesis and number. Pop off the top of the stack,
multiply each element by the number, and add them to the counter below.
} elsif ($as =~ /^\)([0-9]+)/) {
my $ct = $1;
my $oc = pop @stack;
while (my ($k, $v) = each %{$oc}) {
$stack[-1]{$k} += $v * $ct; }
$i += length($ct) + 1;
}
}
Run through the outermost counter (which will be all that's left,
barring syntax errors) in alphabetical order.
my $outstr;
foreach my $k (sort keys %{$stack[0]}) {
Add the item, and if there's more than one of it, the count, to the
output string.
$outstr .= $k;
if ($stack[0]{$k} > 1) {
$outstr .= $stack[0]{$k};
}
}
$outstr;
}
Full code in all tagged languages (except that I didn't do part 2 in
PostScript as the lack of pattern matching made it look like hard
work) is on
codeberg.