Programmieraufgabe zur Nacht

[unset]

Ok, ich denke, es kommt nix mehr rein. Herzlichen Glückwunsch onemorenerd, hier ist deine Medaille , und du bist dran, mit der nächsten Aufgabe

[onemorenerd]

Meine Aufgabe ist eher was für Knobler.

Gegeben sei eine Liste (Array) mit beliebig vielen natürlichen Zahlen (ohne 0). Das letzte Element der Liste ist das Ergebnis einer Berechnung der anderen Listenelemente mit den Grundoperationen +, -, * und /.
Gesucht ist eine Formel, die jedes Listenelement 1...n-1 mindestens einmal enthält und mit den Grundoperationen so anordnet, dass das Ergebnis der Formel das Listenelement n ist oder zumindest so gut wie möglich annähert.

Ein Beispiel:
Eingabe 2,56,10,4711,90
Ausgabe (4711 / 56) + 10 - 2 = 92.125

Es gewinnt die Lösung mit der besten Annäherung an das Ergebnis und der kürzesten Formel.

[combie]

// zahlen =  34,33,23,4,27

echo (34-33)*23+4; 

[unset]

Liste: 1,2,3
Formel: 1+2=3


Ich glaube aber auch, die Aufgabenstellung nicht ganz verstanden zu haben

[Griecherus]

@unset: Meinem Verständnis der Aufgabenstellung nach müsstest du damit gewonnen haben

Grüße

[unset]

Nein ...

Liste: 1,1
Formel: 1=1

[Griecherus]

Da ist jetzt aber keine einzige Operation mehr vorhanden. Setzen - 6!

[onemorenerd]

Hm, ist die Aufgabe wirklich so unverständlich? Dann versuche ich es nochmal.

Es gilt ein Script zu schreiben, dem man z.B. als GET-Parameter ?in=2,56,10,4711,90 übergibt. Die letzte Zahl in dieser Reihe ist das Ergebnis einer Berechnung aus den anderen Zahlen und den Grundrechenoperationen.

Das Script soll versuchen, aus der Eingabe die ursprüngliche Berechnung zu rekonstruieren. Von dieser Berechnung ist bekannt, dass sie beliebig oft die Zeichen +, -, *, /, (, ), außerdem jede der Zahlen aus der Eingabe mindestens einmal, jedoch die letzte Zahl der Eingabe genau einmal und genau ein = enthielt.

Einige Beispiele, zuerst ein ganz einfaches:
1,2,3 => Ausgabe "1+2=3"
Das nächste Beispiel zeigt, dass jede Zahl (außer die letzte, die ist ja das Ergbnis) beliebig oft verwendet werden kann:
2,3 => Ausgabe "2+2/2=3"
Im dritten Beispiel kommen Klammern vor:
5,9,3,4,2 => Ausgabe "5+9-(3*4)=2"

Ich werde gleich noch den Code posten, mit dem ich die Lösungsvorschläge teste und bewerte. Sobald ich ihn fertig habe.
Spätestens dann sollte jeder die Aufgabe verstehen können.

[unset]

Autsch. Und dafür Zeit bis Morgen früh?

[combie]

Das ist doch ***** !!!

1. Das setzen der Klammern
2. Die Mehrfachverwendung der Zahlen

Treiben Rechenzeit ins Unermessliche!
Die Anzahl möglicher Kombinationen ist unbegrenzt.
Permanent muß man auf eine div durch null aufpassen.

[eintrachtemil]

Quick & Dirty. Aber ohne Nährung, immer mit dem exakten Ergebnis nach den Vorgaben

<?php
$zahlen   = explode(',', $_GET['in']);
$ergebnis = $zahlen[count($zahlen)-1];

$reihe = implode(' + ', array_splice($zahlen, 0, count($zahlen)-1));

$berechnung = array();
for($i = 1; $i <= $ergebnis; $i++){
    $berechnung[] = "($reihe) / ($reihe)";        
}

echo  implode(' + ', $berechnung).' = '.$ergebnis;
?>

[onemorenerd]

Hier die Testroutine. Ich werde mir natürlich verschiedene Testformeln ausdenken.
Beim Aufruf eurer Lösung komme ich euch entgegen. Ihr müsst die Eingabe nicht über GET holen. Ich schau mir euren Code an und fummel mir das zurecht.

<?php
header('Content-Type: text/plain');

// Testcase, von mir ausgedacht.
$formel = '5+9-(3*4)';
$ergebnis = eval('return '.$formel.';');

echo "Testcase   : $formel=$ergebnis\n\n";


// Eingabe für eure Scripte vorbereiten.
$zahlen = preg_split("/\+|\-|\*|\/|\(|\)|=/", $formel, -1, PREG_SPLIT_NO_EMPTY);
$zahlen = array_unique($zahlen);
shuffle($zahlen);
$eingabe = implode(',', $zahlen).','.$ergebnis;

echo "Eingabe    : $eingabe\n\n";


// Aufruf eures Scripts. Whitespace wird aus der Ausgabe entfernt.
$ausgabe = file_get_contents('http://localhost/deinScript.php?in='.$eingabe);
$ausgabe = str_replace(array(' ', "\t", "\r", "\n"), '', $ausgabe);

echo "Ausgabe    : $ausgabe\n\n";


// Ausgabe in Formel und Ergebnis zerlegen.
$teile = explode('=', $ausgabe);

// Prüfe Bedingung "genau ein =".
if (count($teile) !== 2) 
    die('FEHLER: Nicht genau ein "=".');

// Prüfe Bedingung "jede Zahl mindestens einmal".
$zahlen_ausgabe = preg_split("/\+|\-|\*|\/|\(|\)|=/", $teile[0], -1, PREG_SPLIT_NO_EMPTY);
if (count(array_diff($zahlen_ausgabe, $zahlen)) !== 0) 
    die('FEHLER: Nicht jede Zahl der Eingabe mindestens einmal verwendet oder unerlaubte Zeichen.');

// Prüfe Korrektheit der Lösung. Rundung auf 2 Nachkommastellen.
$ergebnis_ausgabe = round(eval('return '.$teile[0].';'), 2);
if ($ergebnis_ausgabe !== round($teile[1], 2)) 
    die('FEHLER: Ausgabe ist nicht korrekt.');

echo "Genauigkeit: ".($ergebnis - $ergebnis_ausgabe);    

?>

[onemorenerd]

Die Nacht ist übrigens schon vorbei. Also verlängern wir mal bis ... keine weiteren Lösungsvorschläge mehr zu erwarten sind.

Wegen Division durch Null muss niemand aufpassen. Die Eingabe besteht aus natürlichen Zahlen ohne 0.
Und ja, es stimmt, dass die Anzahl möglicher Lösungen i.A. unbegrenzt ist. Aber es sollen ja auch nicht alle sondern nur eine Lösung bestimmt werden.

Original geschrieben von combie
1. Das setzen der Klammern
2. Die Mehrfachverwendung der Zahlen

Treiben Rechenzeit ins Unermessliche!

Dann hast du den falschen Ansatz. Hier ist ein Lösung mit linearer Komplexität.

for ($i = 1; $i < end($in); $i++)
    $out .= '+'.$in[0].'/'.$in[0];
}
for ($i = 1; $i < count($in)-1; $i++) {
    $out .= '+('.$in[$i].'-'.$in[$i].')';
}
echo trim($out, '+').'='.end($in); 

Vielleicht ist der Code jetzt nicht ganz korrekt. Der Ansatz ist jedenfalls dieser:
1,2,3 => Ausgabe "1/1+1/1+1/1+(2-2)=3"
2,3 => Ausgabe "2/2+2/2+2/2=3"
5,9,3,4,2 => Ausgabe "5/5+5/5+(9-9)+(3-3)+(4-4)=2"

Diese Lösung ist zwar wunderschön linear in ihrer Laufzeit, aber leider auch in der Länge der Ausgabe, so dass man damit sicher keinen Blumentopf gewinnt. Aber es ist bewiesen, dass es geht. Und es ist auch nicht besonders schwierig.

[unset]

Ist ja doof, wenn du deine Aufgabe postest, wenn Leute die Arbeiten müssen schon im Bettchen sind, und die Lösung dann erwartest, wenn Leute die Arbeiten müssen ... arbeiten.

Poste mal ne Reihe von Testcases. Ich hab da ne Idee, die werde ich mir zuhause mal zusammenfrickeln

Wobei das echt ne harte Nuss ist. Wenn man nicht grade einen extrem großen Algorithmus zusammenschreiben will, muss man sich auf eine der beiden Kriterien konzentrieren: Exaktes Ergebnis oder kurze Formel.

[eintrachtemil]

...und der kürzesten Formel.

Shit, das habe ich ganz überlesen