So, umgeschrieben, und nun findet die Funktion irgendwann aufjedenfall eine Formel, die korrekt auflöst. Wird nur nicht unbedingt die kürzeste sein. Hab das mit der Klammerung irgendwie stark unterschätzt:
PHP-Code:
<?php
// Testcase = (1*2)-(2*3)+(4-5)-(5+6)
$sTest = '(5*6)+(7*8)+(4-5)-(9+10)';
eval('$iCaseResult = '. $sTest.';');
echo $sTest ."=". $iCaseResult;
echo "<br />";
echo nerdize(array(7,9,63,567));
function nerdize($aList) {
// Liste kopieren
$aListCopy = $aList;
// Hilfsfunktion in Funktion deklarieren (JA DAS GEHT <img src="images/smilies/wink.gif" border="0" alt="">)
function setMatrixElement($iIndex, &$aMatrix) {
// Wenn die Operation eine Division ist, und wir nicht beim
// ersten Element sind, wird das Vorgängerelement erhöht, und
// das aktuelle wieder auf + gesetzt
if($aMatrix[$iIndex] == '/' AND $iIndex != 0) {
$aMatrix[$iIndex] = '+';
setMatrixElement($iIndex-1, &$aMatrix);
} else {
// Andernfalls wird das Element einfach auf den nächsten Operator gesetzt
switch($aMatrix[$iIndex]) {
case '+':
$aMatrix[$iIndex] = '-';
break;
case '-':
$aMatrix[$iIndex] = '*';
break;
case '*':
$aMatrix[$iIndex] = '/';
break;
}
}
}
// Integrität des Array prüfen
if(
!is_array($aList)
OR
count($aList) <= 1
) {
// Zu wenig Elemente
return false;
}
foreach($aList as $mIndex => $mItem) {
if(!is_numeric($mItem)) {
// Nicht numerisch
return false;
} else {
// Auf int casten, Dezimalzahlen fuck off
$aList[$mIndex] = (int) $mItem;
}
}
// Ergebnis entfernen und vorhalten
$iZielErgebnis = array_pop($aListCopy);
$iTrash = array_pop($aList);
// Rechenoperationen:
// + - * /
$iOperatoren = 4;
// Durchlaufen und testen <img src="images/smilies/wink.gif" border="0" alt="">
// Wir machen den Durchlauf zweimal, und versuchen beim zweiten mal Klammern
// mit einzubeziehen
// Scheiß auf Klammerung. Wir bauen uns die verfügbaren Zahlen hinten dran,
// wenn das Beste Ergebnis kleiner ist, als das gewünschte Ergebnis! Das gibt
// dann zwar lange Formeln, aber wenigstens das richtige Ergebnis - irgendwann
$bPhilsStone = false;
$iRounds = 0;
while(!$bPhilsStone) {
// Wenn die Lösung nicht gefunden, Anzahl der zur Verfügung stehenden Zahlen
// verändern
if($iRound > 0) {
// Das war mehr als der erste Durchgang
// Wir nehmen uns die Zahl, dessen Index der Durchlaufnummer entspricht minus eins
$aList[] = $aList[$iRound-1];
}
// Anzahl Elemente
$iOperationen = count($aList) - 1;
// Maximale Durchgänge ermitteln
$iMaxRunden = pow($iOperatoren, $iOperationen);
// Matrix erstellen
$aMatrix = array();
for($i = 0; $i < $iOperationen; $i++) {
$aMatrix[$i] = '+';
}
for($i = 0; $i < $iMaxRunden; $i++) {
// Formel erzeugen
$sFormel = '';
foreach($aList as $iIndex => $iZahl) {
// Zahl
$sFormel.= $iZahl;
// Operator
if(isset($aMatrix[$iIndex])) {
$sFormel.= $aMatrix[$iIndex];
}
}
// Formel evaluieren
eval(
'
$iErgebnis = '. $sFormel.';
'
);
if($bKlammern) {
// Klammerung
} else {
// Hatten wir schonmal ein Ergebnis?
if(isset($sBesteFormel)) {
// Ja
// Aktuelle Differenz ermitteln
$iDifferenz = abs(($iErgebnis - $iZielErgebnis));
if($iDifferenz == 0 OR $iDifferenz < $iBesteDifferenz) {
$sBesteFormel = $sFormel;
$iBesteDifferenz = abs(($iErgebnis - $iZielErgebnis));
$iBestesErgebnis = $iErgebnis;
}
} else {
// Nein
// Speichern
$sBesteFormel = $sFormel;
$iBesteDifferenz = abs(($iErgebnis - $iZielErgebnis));
$iBestesErgebnis = $iErgebnis;
}
}
// Matrix für den nächsten Durchlauf modifizieren
setMatrixElement(count($aMatrix) - 1, &$aMatrix);
}
if($iBestesErgebnis == $iZielErgebnis) {
$bPhilsStone = true;
} else {
$iRound++;
flush();
}
}
return 'Beste Formel: '. $sBesteFormel.'='. $iBestesErgebnis;
}
?>
Kommentar