Bernd jest uczniem szkoły średniej, który ma pewne problemy z chemią. W klasie musi zaprojektować równania chemiczne dla niektórych przeprowadzanych eksperymentów, takich jak spalanie heptanu:

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

Ponieważ matematyka nie jest najsilniejszym przedmiotem Bernda, często ma trudności ze znalezieniem dokładnych proporcji między pro- i eduktami reakcji. Ponieważ jesteś wychowawcą Bernda, Twoim zadaniem jest mu pomóc! Napisz program, który oblicza ilość każdej substancji potrzebną do uzyskania prawidłowego równania chemicznego.

Wkład

Dane wejściowe to równanie chemiczne bez ilości. Aby było to możliwe w czystym ASCII, zapisujemy wszelkie subskrypcje jako zwykłe liczby. Nazwy elementów zawsze zaczynają się od dużej litery, a po nich może być mała. Cząsteczki są oddzielone +znakami, po ->obu stronach równania wstawiona jest strzałka ASCII-art :

Al+Fe2O4->Fe+Al2O3

Wejście jest zakończone znakiem nowej linii i nie będzie zawierało spacji. Jeśli dane wejściowe są niepoprawne, twój program może zrobić co chcesz.

Można założyć, że dane wejściowe nigdy nie przekraczają 1024 znaków. Twój program może albo odczytać dane wejściowe ze standardowego wejścia, z pierwszego argumentu lub w sposób zdefiniowany w implementacji w czasie wykonywania, jeśli żadne z nich nie jest możliwe.

Wydajność

Dane wyjściowe Twojego programu to równanie wejściowe powiększone o dodatkowe liczby. Liczba atomów dla każdego elementu musi być taka sama po obu stronach strzałki. W powyższym przykładzie poprawnym wynikiem jest:

2Al+Fe2O3->2Fe+Al2O3

Jeśli liczba cząsteczki wynosi 1, upuść ją. Liczba musi zawsze być dodatnią liczbą całkowitą. Twój program musi podawać liczby tak, aby ich suma była minimalna. Na przykład następujące działania są nielegalne:

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

Jeśli nie ma rozwiązania, wydrukuj

Nope!

zamiast. Przykładowe dane wejściowe, które nie mają rozwiązania, to

Pb->Au

Zasady

• To jest golf golfowy. Najkrótszy kod wygrywa.
• Twój program musi zakończyć się w rozsądnym terminie dla wszystkich uzasadnionych danych wejściowych.

Przypadki testowe

Każdy przypadek testowy ma dwa wiersze: dane wejściowe i prawidłowe dane wyjściowe.

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

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

Pb->Au
Nope!

C, 442 505 znaków

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

Uruchom jako:

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

Wyniki:

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

Mathematica 507

Zastosowałem metodę rozszerzonej matrycy składu chemicznego opisaną w

LRThorne, Innowacyjne podejście do bilansowania równań chemicznych - reakcyjnych: uproszczona matryca - technika odwrotna do wyznaczania macierzy zerowej. Chem.Educator , 2010, 15, 304–308 .

Dodano jedną drobną poprawkę: transponowałem wektor zerowej przestrzeni przez największy wspólny dzielnik elementów, aby zapewnić wartości całkowite w dowolnych rozwiązaniach. Moja implementacja nie obsługuje jeszcze przypadków, w których istnieje więcej niż jedno rozwiązanie równoważenia równania.

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

Testy

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

Analiza

Działa poprzez utworzenie następującej tabeli składu chemicznego, składającej się z gatunków chemicznych według pierwiastków, do których dodawany jest wektor nieważności dodania (staje się tabelą rozszerzonego składu chemicznego:

Komórki wewnętrzne usuwa się jako matrycę i odwraca, uzyskując.

Wyodrębniona zostaje kolumna znajdująca się najbardziej z prawej strony, co daje:

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

Każdy element w wektorze jest podzielony przez gcd elementów (1/8), co daje:

{-1, -11, 7, 8}

gdzie wartości ujemne zostaną umieszczone po lewej stronie strzałki. Ich wartości bezwzględne to liczby potrzebne do zrównoważenia pierwotnego równania:

Python, 880 znaków

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

Testy:

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

Wydajność:

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

Może być znacznie mniej niż 880, ale moje oczy już mnie zabijają ...

Python 2, 635 bajtów

poprzednie liczby bajtów: 794, 776, 774, 765, 759, 747, 735, 734, 720, 683, 658, 655, 654, 653, 651, 638, 637, 636 bajtów.

Drugi poziom wcięcia to tylko tabulator, trzeci to tabulator, a następnie spacja.

Szczerze mówiąc, to odpowiedź jadkik94, ale tyle bajtów zostało ogolonych, musiałem to zrobić. Powiedz mi, czy mogę ogolić jakieś bajty!

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 bajtów

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

To jest znacznie bardziej golfowa (dekady postaci!) Odpowiedź Kuilina. Może być niekonkurencyjny, ponieważ niektóre funkcje JS są datowane po wyzwaniu.

JavaScript, 705 bajtów

(niekonkurencyjne, niektóre funkcje dodają wyzwanie)

Wszystkie inne rozwiązania miały elementy brutalnego forsowania. Próbowałem zastosować bardziej deterministyczne podejście, przedstawiając równanie chemiczne jako zbiór równań liniowych, a następnie rozwiązując je za pomocą algorytmu Gaussa-Jordana, aby przyjąć postać tej macierzy o zmniejszonym układzie rzędów-rzędów. Aby wyodrębnić trywialny przypadek, w którym wszystko jest równe zero, zakładam, że jeden z elementów jest liczbą stałą - a liczba ta jest określona przez wszystkie liczby pomnożone razem, aby nie mieć ułamków. Następnie jako ostatni krok podzielimy każdy przez gcd, aby spełnić ostatni warunek.

Nie golfowany:

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"));

Grał w golfa

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"));