Balance chemical equations!

Question

Bernd is a highschool student who has some problems in chemistry. In class he has to design chemical equations for some experiments they are doing, such as the combustion of heptane:

C₇H₁₆ + 11O₂ → 7CO₂ + 8H₂O

Since mathematics isn't exactly Bernds strongest subject, he often has a hard time finding the exact ratios between the pro- and educts of the reaction. Since you are Bernds tutor, it is your job to help him! Write a program, that calculates the amount of each substance needed to get a valid chemical equation.

Input

The input is a chemical equation without amounts. In order to make this possible in pure ASCII, we write any subscriptions as ordinary numbers. Element names always start with a capital letter and may be followed by a minuscule. The molecules are seperated with + signs, an ASCII-art arrow -> is inserted between both sides of the equation:

Al+Fe2O4->Fe+Al2O3

The input is terminated with a newline and won't contain any spaces. If the input is invalid, your program may do whatever you like.

You may assume, that the input is never longer than 1024 characters. Your program may either read the input from standard input, from the first argument or in an implementation defined way at runtime if neither is possible.

Output

The output of your program is the input equation augmented with extra numbers. The number of atoms for each element must be the same on both sides of the arrow. For the example above, a valid output is:

2Al+Fe2O3->2Fe+Al2O3

If the number for a molecule is 1, drop it. A number must always be a positive integer. Your program must yield numbers such that their sum is minimal. For instance, the following is illegal:

40Al+20Fe2O3->40Fe+20Al2O3

If there is no solution, print

Nope!

instead. A sample input that has no solution is

Pb->Au

Rules

• This is code-golf. The shortest code wins.
• Your program must terminate in reasonable time for all reasonable inputs.

Testcase

Each testcase has two lines: An input and a correct output.

C7H16+O2->CO2+H2O
C7H16+11O2->7CO2+8H2O

Al+Fe2O3->Fe+Al2O3
2Al+Fe2O3->2Fe+Al2O3

Pb->Au
Nope!

Answer 1

Python, 880 chars

import sys,re
from sympy.solvers import solve
from sympy import Symbol
from fractions import gcd
from collections import defaultdict

Ls=list('abcdefghijklmnopqrstuvwxyz')
eq=sys.argv[1]
Ss,Os,Es,a,i=defaultdict(list),Ls[:],[],1,1
for p in eq.split('->'):
 for k in p.split('+'):
  c = [Ls.pop(0), 1]
  for e,m in re.findall('([A-Z][a-z]?)([0-9]*)',k):
   m=1 if m=='' else int(m)
   a*=m
   d=[c[0],c[1]*m*i]
   Ss[e][:0],Es[:0]=[d],[[e,d]]
 i=-1
Ys=dict((s,eval('Symbol("'+s+'")')) for s in Os if s not in Ls)
Qs=[eval('+'.join('%d*%s'%(c[1],c[0]) for c in Ss[s]),{},Ys) for s in Ss]+[Ys['a']-a]
k=solve(Qs,*Ys)
if k:
 N=[k[Ys[s]] for s in sorted(Ys)]
 g=N[0]
 for a1, a2 in zip(N[0::2],N[1::2]):g=gcd(g,a2)
 N=[i/g for i in N]
 pM=lambda c: str(c) if c!=1 else ''
 print '->'.join('+'.join(pM(N.pop(0))+str(t) for t in p.split('+')) for p in eq.split('->'))
else:print 'Nope!'

Tests:

python chem-min.py "C7H16+O2->CO2+H2O"
python chem-min.py "Al+Fe2O4->Fe+Al2O3"
python chem-min.py "Pb->Au"

Output:

C7H16+11O2->7CO2+8H2O
8Al+3Fe2O4->6Fe+4Al2O3
Nope!

Could be much less than 880, but my eyes are killing me already...

Answer 2

C, 442 505 chars

// element use table, then once parsed reused as molecule weights
u,t[99];

// molecules
char*s,*m[99]; // name and following separator
c,v[99][99]; // count-1, element vector

i,j,n;

// brute force solver, n==0 upon solution - assume at most 30 of each molecule
b(k){
    if(k<0)for(n=j=0;!n&&j<u;j++)for(i=0;i<=c;i++)n+=t[i]*v[i][j]; // check if sums to zero
    else for(t[k]=0;n&&t[k]++<30;)b(k-1); // loop through all combos of weights
}

main(int r,char**a){
    // parse
    for(s=m[0]=a[1];*s;){
        // parse separator, advance next molecule
        if(*s==45)r=0,s++;
        if(*s<65)m[++c]=++s;
        // parse element
        j=*s++;
        if(*s>96)j=*s+++j<<8;            
        // lookup element index
        for(i=0,t[u]=j;t[i]-j;i++);
        u+=i==u;
        // parse amount
        for(n=0;*s>>4==3;)n=n*10+*s++-48;
        n+=!n;
        // store element count in molecule vector, flip sign for other side of '->'
        v[c][i]=r?n:-n;
    }
    // solve
    b(c);
    // output
    for(i=0,s=n?"Nope!":a[1];*s;putchar(*s++))s==m[i]&&t[i++]>1?printf("%d",t[i-1]):0;
    putchar(10);
}

Run as:

./a.out "C7H16+O2->CO2+H2O"
./a.out "Al+Fe2O4->Fe+Al2O3"
./a.out "Pb->Au"

Results:

C7H16+11O2->7CO2+8H2O
8Al+3Fe2O4->6Fe+4Al2O3
Nope!

Answer 3

Mathematica 507

I employed the augmented chemical composition matrix approach described in

L.R.Thorne, An innovative approach to balancing chemical - reaction equations : a simplified matrix - inverse technique for determining the matrix null space. Chem.Educator, 2010, 15, 304 - 308.

One slight tweak was added: I divided the transpose of the null-space vector by the greatest common divisor of the elements to ensure integer values in any solutions. My implementation does not yet handle cases where there is more than one solution to balancing the equation.

b@t_ :=Quiet@Check[Module[{s = StringSplit[t, "+" | "->"], g = StringCases, k = Length, 
  e, v, f, z, r},
e = Union@Flatten[g[#, _?UpperCaseQ ~~ ___?LowerCaseQ] & /@ s];v = k@e;
s_~f~e_ := If[g[s, e] == {}, 0, If[(r = g[s, e ~~ p__?DigitQ :> p]) == {}, 1, 
   r /. {{x_} :> ToExpression@x}]];z = k@s - v;
r = #/(GCD @@ #) &[Inverse[Join[SparseArray[{{i_, j_} :> f[s[[j]], e[[i]]]}, k /@ {e, s}], 
Table[Join[ConstantArray[0, {z, v}][[i]], #[[i]]], {i, k[#]}]]][[All, -1]] &
   [IdentityMatrix@z]];
Row@Flatten[ReplacePart[Riffle[Partition[Riffle[Abs@r, s], 2], " + "], 
   2 Count[r, _?Negative] -> " -> "]]], "Nope!"]

Tests

b["C7H16+O2->CO2+H2O"]
b["Al+Fe2O3->Fe+Al2O3"]
b["Pb->Au"]

Analysis

It works by setting up the following chemical composition table, consisting of chemical species by elements, to which an addition nullity vector is added (becoming the augmented chemical composition table:

The inner cells are removed as a matrix and inverted, yielding.

The left-most column is extracted and transformed, yielding:

{-(1/8), -(11/8), 7/8, 1}

Each element in the vector is divided by the gcd of the elements (1/8), giving:

{-1, -11, 7, 8}

where the negative values will be placed on the left side of the equal sign. The absolute values of these are the numbers needed to balance the original equation: