The weekly challenge 387 - Task 2: Rational Numbers

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-387/#TASK2
  3 #
  4 # Task 2: Rational Numbers
  5 # ========================
  6 #
  7 # You are given a chemical formula with elements, numbers, and parentheses.
  8 #
  9 # Write a script to count the total number of each type of atom by expanding
 10 # all grouped multipliers. Then, format and return the final inventory as a
 11 # single string sorted alphabetically by element name, including the total
 12 # count only if it is greater than 1.
 13 #
 14 ## Example 1
 15 ##
 16 ## Input: $formula = "((N2O)3(H2O)2)2"
 17 ## Output: "H8N12O10"
 18 ##
 19 ## Step 1: Expand the innermost parentheses
 20 ##     (N2O)3 => N = 2*3 = 6, O = 1*3 = 3 => N6O3
 21 ##     (H2O)2 => H = 2*2 = 4, O = 1*2 = 2 => H4O2
 22 ##
 23 ## Step 2: Combine inside the outer parentheses
 24 ##     Formula becomes: (N6O3 H4O2)2
 25 ##     Sum up identical elements inside: (N6 H4 O5)2
 26 ##
 27 ## Step 3: Apply the outer multiplier
 28 ##     N = 6*2 = 12
 29 ##     H = 4*2 = 8
 30 ##     O = 5*2 = 10
 31 ##
 32 ## Step 4: Sort alphabetically and format
 33 ##     Alphabetical order: H, N, O
 34 ##     Counts: H: 8, N: 12, O: 10
 35 #
 36 ## Example 2
 37 ##
 38 ## Input: $formula = "Mg3(PO4)2"
 39 ## Output: "Mg3O8P2"
 40 ##
 41 ## Step 1: Parse ungrouped elements
 42 ##     Mg3 => Mg = 3
 43 ##
 44 ## Step 2: Expand parentheses (PO4)2
 45 ##     P = 1*2 = 2
 46 ##     O = 4*2 = 8
 47 ##
 48 ## Step 3: Total up counts
 49 ##     Mg = 3
 50 ##     P  = 2
 51 ##     O  = 8
 52 ##
 53 ## Step 4: Sort alphabetically and format
 54 ##     Alphabetical order: Mg, O, P
 55 ##     Counts: Mg: 3, O: 8, P: 2
 56 #
 57 ## Example 3
 58 ##
 59 ## Input: $formula = "(((H)2)3)4"
 60 ## Output: "H24"
 61 ##
 62 ## Step 1: Expand innermost level (H)2
 63 ##     H = 1*2 = 2 => formula becomes ((H2)3)4
 64 ##
 65 ## Step 2: Expand middle level (H2)3
 66 ##     H = 2*3 = 6 => formula becomes (H6)4
 67 ##
 68 ## Step 3: Expand outer level (H6)4
 69 ##     H = 6*4 = 24
 70 ##
 71 ## Step 4: Sort alphabetically and format
 72 ##     Single element: H: 24
 73 #
 74 ## Example 4
 75 ##
 76 ## Input: $formula = "NaCl3(O2(S10)2)2Mg"
 77 ## Output: "Cl3MgNaO4S40"
 78 ##
 79 ## Step 1: Expand innermost parentheses (S10)2
 80 ##     S = 10*2 = 20 => inner formula becomes => O2S20
 81 ##
 82 ## Step 2: Expand outer parentheses (O2S20)2
 83 ##     O = 2*2  = 4
 84 ##     S = 20*2 = 40
 85 ##
 86 ## Step 3: Combine all parts
 87 ##     Ungrouped start: Na (Na = 1), Cl3 (Cl = 3)
 88 ##     Expanded middle: O = 4, S = 40
 89 ##     Ungrouped end: Mg (Mg = 1)
 90 ##
 91 ## Step 4: Sort alphabetically and format
 92 ##     Alphabetical order: Cl (3), Mg (1), Na (1), O (4), S (40)
 93 ##     Omit the number 1 for Mg and Na.
 94 #
 95 ## Example 5
 96 ##
 97 ## Input: $formula = "Z2Y3(X2W)2"
 98 ## Output: "W2X4Y3Z2"
 99 ##
100 ## Step 1: Parse ungrouped elements
101 ##     Z2 => Z = 2
102 ##     Y3 => Y = 3
103 ##
104 ## Step 2: Expand parentheses (X2W)2
105 ##     X = 2*2 = 4
106 ##     W = 1*2 = 2
107 ##
108 ## Step 3: Total up counts
109 ##     W = 2, X = 4, Y = 3, Z = 2
110 ##
111 ## Step 4: Sort alphabetically and format
112 ##     Alphabetical order: W (2), X (4), Y (3), Z (2)
113 #
114 ############################################################
115 ##
116 ## discussion
117 ##
118 ############################################################
119 #
120 # As long as the formula still contains "(" and ")\d+" with
121 # no "(" or ")" in between, we calculate the replacement
122 # for that part. Once all of that is done, we calculate how
123 # often each element appears in this result and sort by
124 # element name.
125 
126 use v5.36;
127 
128 rational_numbers("((N2O)3(H2O)2)2");
129 rational_numbers("Mg3(PO4)2");
130 rational_numbers("(((H)2)3)4");
131 rational_numbers("NaCl3(O2(S10)2)2Mg");
132 rational_numbers("Z2Y3(X2W)2");
133 
134 sub rational_numbers($formula) {
135    say "Input: \"$formula\"";
136    while($formula =~ m/\([^\(\)]*\)\d+/) {
137       my $found = $&;
138       my $replacement = $found;
139       $replacement =~ s/\(//;
140       my ($elements, $count) = split /\)/, $replacement;
141       $replacement = "";
142       while($elements =~ m/([A-Z][a-z]{0,1})(\d*)/) {
143          my $next_elem = $&;
144          my ($elem_name, $elem_count) = ($1, $2);
145          $elements =~ s/\Q$&\E//;
146          $replacement .= "$elem_name";
147          if(length($elem_count)) {
148             $replacement .= ( $count * $elem_count );
149          } else {
150             $replacement .= $count;
151          }
152       }
153       $formula =~ s/\Q$found\E/$replacement/;
154    }
155    my $all_elems = {};
156    while($formula =~ m/([A-Z][a-z]{0,1})(\d*)/) {
157       my $next_elem = $&;
158       my ($elem_name, $elem_count) = ($1, $2);
159       $elem_count ||= 1;
160       $formula =~ s/\Q$&\E//;
161       $all_elems->{$elem_name} += $elem_count;
162    }
163    print "Output: \"";
164    foreach my $key (sort keys %$all_elems) {
165       print $key;
166       print $all_elems->{$key} if $all_elems->{$key} > 1;
167    }
168    say "\"";
169 }