21 August 2026

Challenge 387

Binary Chemistry

Task 1: Rearrange Binary String
Task 2: Atoms Count

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"

Solution

Actually performing the transformation steps seems to be the simplest way to solve this task.

Perl

use strict;
use warnings;

sub rearrange ($str) {
    my $count = 0;
    $count++ while $str =~ s/01/10/g;
    $count;
}

See the full solution to task 1.

J

This is a slightly different procedure:

replace 01 with 10 as long as the result changes
collect all intermediate results (including the initial string)
count these
decrement by one

require 'regex'
rearrange =: <: @ # @ (('01';'10')&rxrplc^:a:)

Example 5:

   rearrange '00001'
4

See the full solution.

Task 2: Atoms Count

Submitted by: Mohammad Sajid Anwar

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)

Solution

Starting with some assumptions:

Elements are named with an upper case letter optionally followed by a single lower case letter.
Repetition counts are strictly greater than zero, i.e. a count of one is allowed in the input.
The same element may appear multiple times at the same level, at different levels or in different groups. Examples are ammonium nitrate NH4NO3, diammonium hydrogen phosphate (NH4)2HPO4 or the monomere of a polyamid NH(CH2)6NHCO(CH2)4CO
A formula may contain any number of elements and any number of parenthesized sub-formulas optionally followed by repetition counts in any order.

Perl

The given formula then must be matched by the following (recursive) regular expression:

m{
    ^
    (?<group>
        (?:
            \p{Lu}\p{Ll}?+
            (?&REP)
        |
            \(
            (?&group)
            \)
            (?&REP)
        )++
    )
    $
    (?(DEFINE)
        (?<REP>(?:[1-9]\d*+)?+)
    )
}x

This regex will never cause backtracking: either the whole formula matches greedily or it does not match at all.

By defining some capturing sub-expressions and inserting code hooks into this regex, the elements’ count can be accumulated while the string is being recursively matched. This is a top-down process in contrast to the bottom-up description in the task.

Elements are counted in a stack of hashes. The current level is always the top of the stack.
The match starts at level zero with an empty hash.
Whenever an element (and its repetition factor) is matched, the count is added to its already accumulated count at the current level.
An opening parenthesis starts a new level by pushing a new empty hash onto the stack.
A closing parenthesis (with its repetition factor) ends the current level:
- The top level is popped from the stack.
- All element counts from the old top level are multiplied with the group’s repetition factor and are added to their already accumulated counts in the new current level.
A repetition factor may be empty. An additional code hook provides the default factor of one for this case, which is accessible in $^R after a match.

There is no need to localize a level as backtracking will not occur.

Using a few helper functions to reduce the code inside the regular expression to improve readability.

After a successful match, there is only one level left that holds the total count for each element in the formula.

Sorting by element and omitting the factor “one” finalizes the task.

use v5.26;    # non-experimental lexical subs
use warnings;
use experimental 'signatures';

sub molecular_formula {
    # push an empty hash onto the stack and return the ref
    state sub push_h :prototype(\@) ($st) {
        push @$st, {};
        $st->[-1];
    }
    # pop the top hash from the stack and return old and new top
    state sub pop_h :prototype(\@) ($st) {
        (pop(@$st), $st->[-1]);
    }
    # multiply values in %$y by $f and add these to the values in
    # %$x
    state sub add_mult ($x, $y, $f) {
        while (my ($k, $v) = each %$y) {
            $x->{$k} += $v * $f;
        }
    }
    # format molecular formula
    state sub print_mol ($h) {
        join '',
        map +($_, $h->{$_} x ($h->{$_} > 1)),
        sort keys %$h;
    }
    my @stack;
    my $cur = push_h @stack;
    shift =~ m{
        ^
        (?<group>
            (?:
                (?<elem>\p{Lu}\p{Ll}?+)
                (?&REP)
                (?{ $cur->{$+{elem}} += $^R; })
            |
                \(
                (?{ $cur = push_h @stack; })
                (?&group)
                \)
                (?&REP)
                (?{ (my $top, $cur) = pop_h @stack;
                    add_mult($cur, $top, $^R);
                })
            )++
        )
        $
        (?(DEFINE)
            (?<REP>
                ((?:[1-9]\d*+)?+)
                (?{ $+ || 1 })
            )
        )
    }x && print_mol $cur;
}

See the full solution to task 2.

J

For obvious reasons there is no support for (?{*code*}) in J’s regex implementation, which was essential in the recursive Perl solution. Therefore I’ll follow the bottom-up process from the description.

require 'regex'
molecular_formula =: verb define
    NB. compile some regexes:
    NB. match elements or closing parentheses without a factor
    hnorm =. rxcomp '(?:\p{Lu}\p{Ll}?+|\))(?!\d)'
    NB. identify isolated '1's
    hdenorm =. rxcomp '(?<!\d)1(?!\d)'
    NB. match repeated digits
    hdigit =. rxcomp '\d++'
    NB. identify parenthesized leaf groups and their factor and
    NB. match both
    hgroup =. rxcomp '\(([^()]++)\)(\d++)'

    NB. apply or remove factors '1':
    NB. normalize '(H2O)' => '(H2O1)1'
    NB. normalize inv '(H2O1)1' => '(H2O)'
    normalize =. hnorm&(,&'1' rxapply) :. ((hdenorm;'')&rxrplc)

    NB. split string of XnYm... into a N x 2 array of boxed
    NB. element / factor pairs or re-join using "split inv"
    split =. (_2 (]\) ] rxcut~ hdigit rxmatches ]) :. (;@,)

    NB. open and convert to numeric (has an inverse: convert to character and box)
    num =. ".@>

    NB. multiply all factors in y by x:
    NB. 2 mol_mult 'H2O1' => 'H4O2'
    mol_mult =. ({.@] , [ *&.(a:`num) {:@])"1&.(a:`split)

    NB. resolve a leaf group:
    NB. resolve_group '(H2O1)2' => 'H4O2'
    resolve_group =. [: (".@] mol_mult [)&>/ ] rxfrom~ (hgroup;1 2) rxmatch ]

    NB. resolve leaf groups repeatedly until no group remains
    resolve_all =. hgroup&(resolve_group rxapply)^:_

    NB. sort split list by element 
    sort_by_elem =. ] /: {."1

    NB. cumulate counts by element in split list
    cumulate_by_elem =. {."1 ([ , (+/)&.:num@])/.. {:"1

    NB. normalize, resolve all groups, split, sort, cumulate, join and
    NB. denormalize on y
    (cumulate_by_elem@sort_by_elem&.split)@resolve_all&.normalize y
)

The above mentioned monomer:

   molecular_formula 'NH(CH2)6NHCO(CH2)4CO'
C12H22N2O2

I modified rxapply to use it on a locally defined operand. Otherwise I had to define some internal verbs at global scope.

[Update]
This has been fixed in J9.8.

NB. overwrite from 'regex'
rxapply=: 1 : 0
:
if. L. x do. 'pat ndx'=. x else. pat=. x [ ndx=. ,0 end.
if. 1 ~: #$ ndx do. 13!:8[3 end.
mat=. ({.ndx) {"2 pat rxmatches y
r=. u.&.> mat rxfrom y
r mat rxmerge y
)

The Bear's Den

Enter at your own risk

Binary Chemistry

Task 1: Rearrange Binary String

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Perl

J

Task 2: Atoms Count

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Perl

J