Бернд - ученик средней школы, у которого есть проблемы с химией. В классе он должен разработать химические уравнения для некоторых экспериментов, которые они проводят, таких как сжигание гептана:

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

Поскольку математика не является самым сильным предметом Бернда, ему часто бывает трудно найти точные соотношения между продуктами и продуктами реакции. Поскольку вы наставник Бернда, ваша работа - помочь ему! Напишите программу, которая рассчитывает количество каждого вещества, необходимое для получения правильного химического уравнения.

вход

Ввод представляет собой химическое уравнение без количеств. Чтобы сделать это возможным в чистом ASCII, мы пишем любые подписки как обычные числа. Имена элементов всегда начинаются с заглавной буквы и могут сопровождаться крошечной. Молекулы разделены +знаками, стрелка ASCII-art ->вставлена ​​между обеими сторонами уравнения:

Al+Fe2O4->Fe+Al2O3

Ввод завершается новой строкой и не содержит пробелов. Если ввод неверен, ваша программа может делать все что угодно.

Вы можете предположить, что ввод никогда не будет длиннее 1024 символов. Ваша программа может либо прочитать входные данные из стандартного ввода, из первого аргумента, либо заданным реализацией способом во время выполнения, если это невозможно.

Выход

Результатом вашей программы является входное уравнение, дополненное дополнительными числами. Количество атомов для каждого элемента должно быть одинаковым с обеих сторон стрелки. Для приведенного выше примера допустимый вывод:

2Al+Fe2O3->2Fe+Al2O3

Если число для молекулы - 1, отбросьте это. Число всегда должно быть положительным целым числом. Ваша программа должна выдавать числа такие, чтобы их сумма была минимальной. Например, следующее недопустимо:

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

Если решения не существует, распечатайте

Nope!

вместо. Пример ввода, который не имеет решения

Pb->Au

правила

• Это код-гольф. Самый короткий код выигрывает.
• Ваша программа должна завершиться в разумные сроки для всех разумных вводов.

Тестовые случаи

Каждый тестовый пример имеет две строки: вход и правильный выход.

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

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

Pb->Au
Nope!

C 442 505 символов

// 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);
}

Беги как:

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

Полученные результаты:

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

Mathematica 507

Я использовал матричный подход с расширенным химическим составом, описанный в

Л.Р.Торн, Инновационный подход к уравновешиванию уравнений химических реакций: упрощенная матрично-обратная техника для определения нулевого пространства матрицы. Chem.Educator , 2010, 15, 304 - 308.

Был добавлен один небольшой трюк: я разделил транспонирование пустого вектора на наибольший общий делитель элементов, чтобы обеспечить целочисленные значения в любых решениях. Моя реализация еще не обрабатывает случаи, когда существует более одного решения для уравновешивания уравнения.

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!"]

тесты

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

Анализ

Он работает, создавая следующую таблицу химического состава, состоящую из химических элементов по элементам, к которой добавлен вектор нулевой добавки (ставший таблицей дополненного химического состава:

Внутренние клетки удаляются в виде матрицы и переворачиваются, давая.

Самый правый столбец извлекается, давая:

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

Каждый элемент вектора делится на gcd элементов (1/8), давая:

{-1, -11, 7, 8}

где отрицательные значения будут размещены на левой стороне стрелки. Абсолютными значениями являются числа, необходимые для баланса исходного уравнения:

Питон, 880 символов

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!'

тесты:

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

Выход:

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

Может быть гораздо меньше, чем 880, но мои глаза уже убивают меня ...

Python 2, 635 байт

количество предыдущих байтов: 794, 776, 774, 765, 759, 747, 735, 734, 720, 683, 658, 655, 654, 653, 651, 638, 637, 636 байтов.

Второй уровень отступа - только вкладка, третий - вкладка, затем пробел.

Если честно, это ответ jadkik94, но побрилось так много байтов, что мне пришлось это сделать. Скажи мне, могу ли я сбрить байты!

from sympy import*
import sys,re
from sympy.solvers import*
from collections import*
P=str.split
L=map(chr,range(97,123))
q=sys.argv[1]
S,O,a,i,u,v=defaultdict(list),L[:],1,1,'+','->'
w=u.join
for p in P(q,v):
 for k in P(p,u):
     c=L.pop(0)
     for e,m in re.findall('([A-Z][a-z]*)(\d*)',k):
      m=int(m or 1)
      a*=m
      S[e][:0]=[c,m*i],
 i=-1
Y=dict((s,Symbol(s))for s in set(O)-set(L))
Q=[eval(w('%d*%s'%(c[1],c[0])for c in S[s]),{},Y)for s in S]+[Y['a']-a]
k=solve(Q,*Y)
if k:
 N=[k[Y[s]]for s in sorted(Y)]
 g=gcd(N[:1]+N[1::2])
 print v.join(w((lambda c:str(c)*(c!=1))(N.pop(0)/g)+str(t)for t in P(p,u))for p in P(q,v))
else:print'Nope!'

JavaScript, 682 байта

x=>{m=1;x.split(/\D+/g).map(i=>i?m*=i:0);e=new Set(x.replace(/\d+|\+|->/g,"").match(/([A-Z][a-z]*)/g));e.delete``;A=[];for(let z of e){t=x.split`->`;u=[];for(c=1;Q=t.shift();c=-1)Q.split`+`.map(p=>u.push(c*((i=p.indexOf(z))==-1?0:(N=p.substring(i+z.length).match(/^\d+/g))?N[0]:1)));A.push(u)}J=A.length;for(P=0;P<J;P++){for(i=P;!A[i][P];i++);W=A.splice(i,1)[0];W=W.map(t=>t*m/W[P]);A=A.map(r=>r[P]?r.map((t,j)=>t-W[j]*r[P]/m):r);A.splice(P,0,W)}f=e.size;if(!A[0][f])return"Nope!";g=m=-m;_=(a,b)=>b?_(b,a%b):a;c=[];A.map(p=>c.push(t=p.pop())&(g=_(g,t)));c.push(m);j=x.match(/[^+>]+/g);return c.map(k=>k/g).map(t=>(t^1?t:"")+(z=j.shift())+(z.endsWith`-`?">":"+")).join``.slice(0,-1);}

Это гораздо более удачный (десятилетия символов!) Ответ Куйлина. Может быть неконкурентоспособным, потому что некоторые функции JS устарели.

Javascript, 705 байт

(не конкурирует, некоторые функции устарели)

Все остальные решения имели элементы грубой силы. Я попытался использовать более детерминированный подход, представив химическое уравнение в виде набора линейных уравнений, а затем решив, используя алгоритм Гаусса-Джордана, чтобы получить приведенную форму ряда строк в этой матрице. Чтобы выделить тривиальный случай, когда все равно нулю, я предполагаю, что один из элементов является постоянным числом - и это число определяется только всеми числами, умноженными вместе, чтобы не иметь дробей. Затем в качестве последнего шага мы разделим каждый на gcd, чтобы выполнить последнее условие.

Ungolfed:

function solve(x) {
	//firstly we find bigNumber, which will be all numbers multiplied together, in order to assume the last element is a constant amount of that
	bigNumber = 1;
	arrayOfNumbers = new Set(x.split(/\D+/g));
	arrayOfNumbers.delete("");
	for (let i of arrayOfNumbers) bigNumber *= parseInt(i);
	
	//first actual step, we split into left hand side and right hand side, and then into separate molecules
	//number of molecules is number of variables, number of elements is number of equations, variables refer to the coefficients of the chemical equation
	//note, the structure of this is changed a lot in the golfed version since right is the same as negative left
	left = x.split("->")[0].split("+");
	righ = x.split("->")[1].split("+");
	molecules = left.length + righ.length;
	
	//then let's find what elements there are - this will also become how many equations we have, or the columns of our matrix minus one
	//we replace all the non-element characters, and then split based on the uppercase characters
	//this also sometimes adds a "" to the array, we don't need that so we just delete it
	//turn into a set in order to remove repeats
	elems = new Set(x.replace(/\d+|\+|->/g,"").match(/([A-Z][a-z]*)/g));
	elems.delete("");
	
	rrefArray = [];//first index is rows, second index columns - each row is an equation x*(A11)+y*(A21)+z*(A31)=A41 etc etc, to solve for xyz as coefficients
	//loop thru the elements, since for each element we'll have an equation, or a row in the array
	for (let elem of elems) {
		buildArr = [];
		//loop thru the sides
		for (let molecule of left) {
			//let's see how many of element elem are in molecule molecule
			//ASSUMPTION: each element happens only once per molecule (no shenanigans like CH3COOH)
			index = molecule.indexOf(elem);
			if (index == -1) buildArr.push(0);
			else {
				index += elem.length;
				numberAfterElement = molecule.substring(index).match(/^\d+/g);
				if (numberAfterElement == null) buildArr.push(1);
				else buildArr.push(parseInt(numberAfterElement));
			}
		}
		//same for right, except each item is negative
		for (let molecule of righ) {
			index = molecule.indexOf(elem);
			if (index == -1) buildArr.push(0);
			else {
				index += elem.length;
				numberAfterElement = molecule.substring(index).match(/^\d+/g);
				if (numberAfterElement == null) buildArr.push(-1);
				else buildArr.push(parseInt(numberAfterElement)*(-1));
			}
		}
		rrefArray.push(buildArr);
	}
	
	//Gauss-Jordan algorithm starts here, on rrefArray
	for (pivot=0;pivot<Math.min(molecules, elems.size);pivot++) {
		//for each pivot element, first we search for a row in which the pivot is nonzero
		//this is guaranteed to exist because there are no empty molecules
		for (i=pivot;i<rrefArray.length;i++) {
			row = rrefArray[i];
			if (row[pivot] != 0) {
				workingOnThisRow = rrefArray.splice(rrefArray.indexOf(row), 1)[0];
			}
		}
		//then multiply elements so the pivot element of workingOnThisRow is equal to bigNumber we determined above, this is all to keep everything in integer-space
		multiplyWhat = bigNumber / workingOnThisRow[pivot]
		for (i=0;i<workingOnThisRow.length;i++) workingOnThisRow[i] *= multiplyWhat
		//then we make sure the other rows don't have this column as a number, the other rows have to be zero, if not we can normalize to bigNumber and subtract
		for (let i in rrefArray) {
			row = rrefArray[i];
			if (row[pivot] != 0) {
				multiplyWhat = bigNumber / row[pivot]
				for (j=0;j<row.length;j++) {
					row[j] *= multiplyWhat;
					row[j] -= workingOnThisRow[j];
					row[j] /= multiplyWhat;
				}
				rrefArray[i]=row;
			}
		}
		//finally we put the row back
		rrefArray.splice(pivot, 0, workingOnThisRow);
	}
	
	//and finally we're done!
	//sanity check to make sure it succeeded, if not then the matrix is insolvable
	if (rrefArray[0][elems.size] == 0 || rrefArray[0][elems.size] == undefined) return "Nope!";
	
	//last step - get the results of the rref, which will be the coefficients of em except for the last one, which would be bigNumber (1 with typical implementation of the algorithm)
	bigNumber *= -1;
	gcd_calc = function(a, b) {
		if (!b) return a;
		return gcd_calc(b, a%b);
	};
	coEffs = [];
	gcd = bigNumber;
	for (i=0;i<rrefArray.length;i++) {
		num = rrefArray[i][molecules-1];
		coEffs.push(num);
		gcd = gcd_calc(gcd, num)
	}
	coEffs.push(bigNumber);
	for (i=0;i<coEffs.length;i++) coEffs[i] /= gcd;
	
	//now we make it human readable
	//we have left and right from before, let's not forget those!
	out = "";
	for (i=0;i<coEffs.length;i++) {
		coEff = coEffs[i];
		if (coEff != 1) out += coEff;
		out += left.shift();
		if (left.length == 0 && righ.length != 0) {
			out += "->";
			left = righ;
		} else if (i != coEffs.length-1) out += "+";
	}
	return out;
}
console.log(solve("Al+Fe2O4->Fe+Al2O3"));
console.log(solve("Al+Fe2O3->Fe+Al2O3"));
console.log(solve("C7H16+O2->CO2+H2O"));
console.log(solve("Pb->Au"));

Golfed

s=x=>{m=1;x.split(/\D+/g).map(i=>i!=""?m*=i:0);e=(new Set(x.replace(/\d+|\+|->/g,"").match(/([A-Z][a-z]*)/g)));e.delete("");A=[];for(let z of e){t=x.split("->");u=[];for(c=1;Q=t.shift();c=-1)Q.split("+").map(p=>u.push(c*((i=p.indexOf(z))==-1?0:(N=p.substring(i+z.length).match(/^\d+/g))?N[0]:1)));A.push(u)}J=A.length;for(P=0;P<J;P++){for(i=P;!A[i][P];i++);W=A.splice(i,1)[0];W=W.map(t=>t*m/W[P]);A=A.map(r=>!r[P]?r:r.map((t,j)=>t-W[j]*r[P]/m));A.splice(P,0,W)}f=e.size;if (!A[0][f])return "Nope!";g=m=-m;_=(a,b)=>b?_(b,a%b):a;c=[];A.map(p=>c.push(t=p.pop())&(g=_(g,t)));c.push(m);j=x.match(/[^+>]+/g);return c.map(k=>k/g).map(t=>(t==1?"":t)+(z=j.shift())+(z.endsWith("-")?">":"+")).join("").slice(0,-1);}

console.log(s("Al+Fe2O4->Fe+Al2O3"));
console.log(s("Al+Fe2O3->Fe+Al2O3"));
console.log(s("C7H16+O2->CO2+H2O"));
console.log(s("Pb->Au"));