printf(" SaltwaterC ");

S-a găsit Google Reader să mă scoată cu nasul din shell cu următoarea problemă, dată pe undeva pe aici. Practic rezolvarea problemei:

AB + CD + AC + BD = 100

Ca orice “nerd” ce se respectă, am pus mâna pe Eclipse pentru a rezolva problema, nu pe o foaie de hârtie, din moment ce prin natura ei există 10⁴ ( da, 10.000) soluții posibile, dar doar 25 sunt corecte, considerând faptul că A, B, C pot lua valoarea 0. De fapt, am scris soluția ca pe una configurabilă pentru a-i servi și alt input dacă nu am nimerit-o și A, B, C încep de la 1. Oricum, muncă de 5 minute, dar i-am dat un refactor, să moară dușmanii de ciudă, fără număr la bandă.

Din moment ce propria pacoste de motan mi-a servit drept inspirație, codul e scris lolstyle (dar totuși câtuși de cât profesionist). Ca idee, I_can_has_numbers este clasa ce se ocupă de toate chestiile, iar fișierul I_can_has_everything.php este cel apelabil, fie din browser, pentru cei cu o stivă PHP instalată, fie folosind PHP CLI.

Cod: PHP5/OOP

Download: I_can_has_Makavelis_numbers.zip

Pentru cei născuți cu lene de a mai rula cod, acestea sunt soluțiile:

Number of solutions: 25

A = 0; B = 0; C = 8; D = 6; 0 + 86 + 8 + 6 = 100
A = 0; B = 1; C = 7; D = 6; 1 + 76 + 7 + 16 = 100
A = 0; B = 2; C = 6; D = 6; 2 + 66 + 6 + 26 = 100
A = 0; B = 3; C = 5; D = 6; 3 + 56 + 5 + 36 = 100
A = 0; B = 4; C = 4; D = 6; 4 + 46 + 4 + 46 = 100
A = 0; B = 5; C = 3; D = 6; 5 + 36 + 3 + 56 = 100
A = 0; B = 6; C = 2; D = 6; 6 + 26 + 2 + 66 = 100
A = 0; B = 7; C = 1; D = 6; 7 + 16 + 1 + 76 = 100
A = 0; B = 8; C = 0; D = 6; 8 + 6 + 0 + 86 = 100
A = 1; B = 0; C = 6; D = 7; 10 + 67 + 16 + 7 = 100
A = 1; B = 1; C = 5; D = 7; 11 + 57 + 15 + 17 = 100
A = 1; B = 2; C = 4; D = 7; 12 + 47 + 14 + 27 = 100
A = 1; B = 3; C = 3; D = 7; 13 + 37 + 13 + 37 = 100
A = 1; B = 4; C = 2; D = 7; 14 + 27 + 12 + 47 = 100
A = 1; B = 5; C = 1; D = 7; 15 + 17 + 11 + 57 = 100
A = 1; B = 6; C = 0; D = 7; 16 + 7 + 10 + 67 = 100
A = 2; B = 0; C = 4; D = 8; 20 + 48 + 24 + 8 = 100
A = 2; B = 1; C = 3; D = 8; 21 + 38 + 23 + 18 = 100
A = 2; B = 2; C = 2; D = 8; 22 + 28 + 22 + 28 = 100
A = 2; B = 3; C = 1; D = 8; 23 + 18 + 21 + 38 = 100
A = 2; B = 4; C = 0; D = 8; 24 + 8 + 20 + 48 = 100
A = 3; B = 0; C = 2; D = 9; 30 + 29 + 32 + 9 = 100
A = 3; B = 1; C = 1; D = 9; 31 + 19 + 31 + 19 = 100
A = 3; B = 2; C = 0; D = 9; 32 + 9 + 30 + 29 = 100
A = 5; B = 0; C = 0; D = 0; 50 + 0 + 50 + 0 = 100

Update: F (nu o să îi dezvălui numele din moment ce a decis să se semneze doar cu F ) a atras antețina asupra faptului că am făcut brute-force în soluția mea sofisticată, deci vin în întâmpinare cu un algoritm bazat pe modelarea matematică a soluției. Algoritmul rezolvă problema în numărul minim de pași (24), plus adăugarea soluției iregulate (unde trișez, este hardcoded). Numărul de bucle s-a redus la două cu număr minim de pași (4 pentru A, inițial 9 pentru B, după care scade, C și D sunt deduse).

Download: I_can_has_Makavelis_numbers_v0.2.zip

Update: din moment ce primii doi algoritmi sunt de cacao (fără o), primul e pur brute-force iar al doilea nu reprezintă o modelare matematică ce să includă toate soluțiile, revin pe scenă cu ultima soluție (finală) a problemei de mai sus.

Sursa algoritmului propriu zis:

for ($a = 0; $a < = 5; $a++)
{
	$double_a = 2 * $a;
	$end_b = 8 - $double_a;
	$d = $a + 6;
	for ($b = 0; $b <= $end_b; $b++)
	{
		$c = (8 - $double_a) - $b;

		if ($d % 10 === 0)
		{
			$a++;
			$d = 0;
		}

		$this->solutions[] = array
		(
			'a' => $a,
			'b' => $b,
			'c' => $c,
			'd' => $d,
		);
	}
}

Download: I_can_has_Makavelis_numbers_v0.3.zip