11
\$\begingroup\$

Backstory

You wake up dizzy in a chemistry laboratory, and you realize you have been kidnapped by a old mad chemist. Since he cannot see very well because of his age, he wants you to work for him and only then, you can escape the laboratory.

Task

It is your task to return the structural formulae of the molecules whose chemical formula will be given as input. Note that only the carbon (C), oxygen (O) and hydrogen (H) atoms will be used as input. Unlike in chemical formulas, a 0 is a valid quantifier and a 1 cannot be omitted (e.g. C1H4O0 is valid input, but CH4 isn't).

To prevent ambiguity, we assume double and triple bonds do not appear in the molecules. All carbon atoms need 4 single bonds, all oxygen atoms need 2, and hydrogen atoms need one. We also assume that O-O bonds do not exist as well. The molecule does not have to exist nor be stable.

The input will never contain more than 3 carbon atoms to ensure lightness in the output's display.

You only should display the molecules whose carbons atoms are arranged in a straight line without interruption. Ergo, no C-O-C bonds.

You must return all possible molecules not excluded by the previous rules. You do not need to handle invalid inputs.

The following example displays all the solutions you have to handle for that molecule.

A rotation by 180 degrees in the plane of the page of one of the molecule's formula is considered a redundancy and does not need to be displayed.

In the example below I'll show all of the possible formulae for a molecule, then point out the ones that do not need to be displayed.

Example

Input: C2H6O2

First, here are all the possible formulae for this input (Thank you to @Jonathan Allan)

01        H
          |
          O   H
          |   |
  H - O - C - C - H
          |   |
          H   H

02            H
              |
          H   O
          |   |
  H - O - C - C - H
          |   |
          H   H

03        H   H
          |   |
  H - O - C - C - O - H
          |   |
          H   H

04        H   H
          |   |
  H - O - C - C - H
          |   |
          H   O
              |
              H

05        H   H
          |   |
  H - O - C - C - H
          |   |
          O   H
          |
          H

12        H   H
          |   |
          O   O
          |   |
      H - C - C - H
          |   |
          H   H

13        H
          |
          O   H
          |   |
      H - C - C - O - H
          |   |
          H   H

14        H
          |
          O   H
          |   |
      H - C - C - H
          |   |
          H   O
              |
              H


15        H
          |
          O   H
          |   |
      H - C - C - H
          |   |
          O   H
          |
          H

23            H
              |
          H   O
          |   |
      H - C - C - O - H
          |   |
          H   H

24            H
              |
          H   O
          |   |
      H - C - C - H
          |   |
          H   O
              |
              H

25            H
              |
          H   O
          |   |
      H - C - C - H
          |   |
          O   H
          |
          H

34        H   H
          |   |
      H - C - C - O - H
          |   |
          H   O
              |
              H

35        H   H
          |   |
      H - C - C - O - H
          |   |
          O   H
          |
          H

45        H   H
          |   |
      H - C - C - H
          |   |
          O   O
          |   |
          H   H

And here are the formulae that should be in the output if we take out the rotations of 180° in the plane of the page :

01        H
          |
          O   H
          |   |
  H - O - C - C - H
          |   |
          H   H



03        H   H
          |   |
  H - O - C - C - O - H
          |   |
          H   H


12        H   H
          |   |
          O   O
          |   |
      H - C - C - H
          |   |
          H   H

13        H
          |
          O   H
          |   |
      H - C - C - O - H
          |   |
          H   H

14        H
          |
          O   H
          |   |
      H - C - C - H
          |   |
          H   O
              |
              H


 15      H
         |
         O   H      
         |   |
     H - C - C - H
         |   |
         O   H
         |
         H 

23            H
              |
          H   O
          |   |
      H - C - C - O - H
          |   |
          H   H



25            H
              |
          H   O
          |   |
      H - C - C - H
          |   |
          O   H
          |
          H



35        H   H
          |   |
      H - C - C - O - H
          |   |
          O   H
          |
          H

You do not need to output the labels of the formulae and you can output either of the rotations when two exist. For example you can output either 02 or 35.

Here are some valid inputs to test your code:

C3H8O2 C1H4O0 C2H6O2 C1H4O1 C2H6O2

The PC the chemist gave you to complete your task is quite old so you do not have a lot of memory on it to save your code, thus this is and the shortest amount of byte wins!

\$\endgroup\$
  • \$\begingroup\$ Do we need to handle cyclic molecules? \$\endgroup\$ – Luke Apr 27 '17 at 16:13
  • \$\begingroup\$ @Luke The inputs I gave cannot be cyclic so you do not need to handle that. But if you want to handle molecules that contains 4 C or more you can do it and earn bonus score :) Thanks for the edit by the way! english is not my native language ^^ \$\endgroup\$ – user68509 Apr 27 '17 at 16:17
  • 1
    \$\begingroup\$ The output you've suggested is missing a lot of potential molecules: you have two copies of propan-1,2-diol there, but is missing at least propan-1,1-diol, propan-1,3-diol, propan-2,2-diol, a large number of alcohol ethers, and various compounds where the two oxygen atoms connect to each other. Additionally, how specified is the output format? I can imagine molecules in which some of the bonds need to be drawn longer than others to fit everything in (e.g. dimethylpropane, which is apparently a real chemical). \$\endgroup\$ – user62131 Apr 27 '17 at 16:20
  • 2
    \$\begingroup\$ 1. Is it possible to have 2 OH groups on the same carbon? You seem to have excluded it from the examples, but I don't see anywhere in the spec that says we don't have to consider it (I know in reality these compounds exist in equilibrium with aldehydes) 2. Why is the HOCH2CH2OH with both OH groups pointing downards missing from the example? Isn't it a required output? \$\endgroup\$ – Level River St Apr 30 '17 at 3:35
  • 1
    \$\begingroup\$ 3. Is it acceptable to have the outputs with the carbon chain vertical instead of horizontal? \$\endgroup\$ – Level River St Apr 30 '17 at 3:36
3
+50
\$\begingroup\$

Ruby, 275

->s{(k=4<<2*c=s[1].to_i).times{|i|z=" "*8
t=("  H|O|"[i%2*2,4]+"C|"*c+"O|H   "[i>>c&2^2,4]).chars.map{|j|z+j+z}
(c*2).times{|j|t[4+j&-2][j%2*10,7]="    H - O - H    "[[i>>j/2-1&4,-7-(i>>c*2-j/2-1&4)][j%2],7]}
i*(k+1)>>c+1&k-1<i||("%b"%i).sum%16!=s[5].to_i||i%7>c*3||puts(t)}}

Combined formulas for left and right sidechains and eliminated variable h

Ruby, 279

->s{(k=1<<h=2+2*c=s[1].to_i).times{|i|t=("  H|O|"[i%2*2,4]+"C|"*c+"O|H   "[i>>c&2^2,4]).chars.map{|j|(z=" "*8)+j+z}
c.times{|j|t[4+j*2][0,7]="    H - O -"[i>>j-1&4,7]
t[4+j*2][10,7]="- O - H    "[i>>h-j-3&4^4,7]}
i*(k+1)>>h/2&k-1<i||("%b"%i).sum%16!=s[5].to_i||i%7>c*3||puts(t)}}

Ungolfed in test program

f=->s{
  (k=1<<h=2+2*c=s[1].to_i).times{|i|                       #c=number of C atoms. h=number of H (calculated)
                                                           #iterate i from 0 to (k=1<<h)-1

  t=("  H|O|"[i%2*2,4]+"C|"*c+"O|H   "[i>>c&2^2,4]).       #compose a backbone string H-C...C-H. Insert O at the top where bit 0 of i set, and O at the bottom where bit c+1 of i set
  chars.map{|j|(z=" "*8)+j+z}                              #convert string to an array of characters, pad each character left and right with 8 spaces

  c.times{|j|t[4+j*2][0,7]="    H - O -"[i>>j-1&4,7]       #overwrite spaces on left with H or HO according to bits 1 up to c
             t[4+j*2][10,7]="- O - H    "[i>>h-j-3&4^4,7]} #overwrite spaces on right with H or OH according to bits h-1 down to c+1

  i*(k+1)>>h/2&k-1<i||                                     #rotate the bits of i by h/2. if this is less than i, do not output the structure (eliminates rotations by 180deg by outputtng the lexically highest)
  ("%b"%i).sum%16!=s[5].to_i||                             #if the number of 1's in i differs from the number of O's indicated in the input, do not output
  i%7>c*3||                                                #if i%7>c*3, do not output (empirical solution to avoid 90deg rotations for C=1)
  puts(t)                                                  #if the above are all false, output the current structure.
  }
}

f[gets]

Output

Spacing is as per question output. Backbone vertical instead of horizontal allowed per comments. Rotations of the entire display through 90 or 180 degrees considered equivalent.

C2H6O2
        H
        |
        O
        |
H - O - C - H
        |
    H - C - H
        |
        H



        H
        |
        O
        |
    H - C - H
        |
H - O - C - H
        |
        H





        H
        |
H - O - C - H
        |
H - O - C - H
        |
        H



        H
        |
        O
        |
    H - C - H
        |
    H - C - H
        |
        O
        |
        H



        H
        |
H - O - C - H
        |
    H - C - H
        |
        O
        |
        H



        H
        |
    H - C - H
        |
H - O - C - H
        |
        O
        |
        H



        H
        |
H - O - C - H
        |
    H - C - O - H
        |
        H





        H
        |
    H - C - H
        |
H - O - C - O - H
        |
        H





        H
        |
    H - C - O - H
        |
H - O - C - H
        |
        H
\$\endgroup\$
  • \$\begingroup\$ Nice I'll run it when I get back at my computer :) \$\endgroup\$ – user68509 May 1 '17 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy