ASCII stoichiometry P82060


Statement
 

pdf   zip

thehtml

The future is now! And proof of it is that recent advances in quantum mechanics and digital signal processing have allowed the construction of sophisticated electronic microscopes. It ‍is now possible to see chemical reactions as they happen, at the molecular level of detail, and in the way that they were meant to be seen: as ASCII art.

For instance, it is possible to see the combustion of a molecule of CH4 (methane) in the presence of O2 (oxygen), giving CO2 (carbon dioxide) and H2O (water), as text:

...H.......O-O.......    ...H.H....O-C-O.H....
...|...O-O...........    ...|.|..........|....
.H-C-H...........C...    .H-O.H-O......H-C-H..
...|...H..O-Ca...|... -> ..H......O-Ca...|....
...H...|.......H-H-H.    ..|.............H....
.....H-C-H.Ca-O..|...    H-C-H-H..Ca-O........
.O-O...|.........H...    ..............O-O....
.......H.............    .....................

Note too the presence of lime CaO, which is unaffected by the reaction. After looking at these images, it is obvious that the reaction which is happening, in its correct stoichiometrical proportions, has to be CH4+2O2->CO2+2H2O.

Given the captures of substances in change, can you write the reactions that are happening?

Input

Input consists of several cases. Every case starts with the height h and width w of the ASCII captures generated by the microscope. Two blocks of h lines of w characters each follow, with the before and after conditions. Both h and w are between 1 and 100.

In the diagrams, dots denote empty spaces. Atoms of the same molecule are connected horizontally or vertically by exactly one ‘-’ or ‘’. Atom names consist of one uppercase letter followed by at most one lowercase letter. Every molecule has a tree structure.

The same atoms will be present before and after, and only full molecules will be present (i.e., there will be no clipping of the picture at the edges).

Output

For every case, print its chemical reaction, with the involved molecules before and after separated by “->”. No given reaction will be empty. Isomery is a hoax (like climate change), so molecules are defined just by the count of its atoms, not by their internal connections.

Inside each molecule, sort atoms in alphabetical order (for exemple, “C” comes before “Ca”), and follow each atom by its count if it is greater than one. Similarly, display molecules in each side of the reaction using the default string lexicographical order, and precede molecules by their counts if greater than one. Separate molecules by ‘+’.

Finally, good stoichiometry requires that molecule counts have no common factors.

Public test cases
  • Input

    8 21
    
    ...H.......O-O.......
    ...|...O-O...........
    .H-C-H...........C...
    ...|...H..O-Ca...|...
    ...H...|.......H-H-H.
    .....H-C-H.Ca-O..|...
    .O-O...|.........H...
    .......H.............
    
    ...H.H....O-C-O.H....
    ...|.|..........|....
    .H-O.H-O......H-C-H..
    ..H......O-Ca...|....
    ..|.............H....
    H-C-H-H..Ca-O........
    ..............O-O....
    .....................
    
    5 14
    
    .Ca.O-O.Ca.H.O
    ..|.....|....|
    ..Sb-H.Sb-Ca.O
    ..|.......|...
    .Ca..W.W..H..H
    
    .Ca-W..Ca-W..H
    O..H-Sb..O-O.|
    |...........Sb
    O...Ca-H......
    .........Ca-H.
    
    1 30
    
    .H-H....H....H-H...H..H-H..H-H
    
    H-H...H..H...H....H.H..H.H..H.
    

    Output

    CH4+2O2->CO2+2H2O
    Ca2HSb+H+W->CaH+CaW+HSb
    H2->2H
    
  • Information
    Author
    Edgar Gonzalez
    Language
    English
    Official solutions
    C++
    User solutions
    C++