Programmieraufgabe zur Nacht

[onemorenerd]

Ich konnte halt letzte Nacht nicht früher hier reinschauen und das Ausdenken der Aufgabe hat auch noch eine Weile gedauert. Heute morgen hat dann der Server rumgemuckt. Aber wie gesagt gibt es kein Zeitlimit. Wer Angst hat, vom plötzlichen Ende überrascht zu werden, kann ja kurz bekannt geben, dass er an der Aufgabe sitzt. Dann hab ich eine Übersicht und warte bis alle Lösungen da sind.
Ansonsten kündige ich einfach irgendwann (nicht vor morgen früh) an, dass ich in einer Stunde den Gewinner küre. Wer in dieser Stunde noch eine Lösung bringt, ist mit im Rennen.

Hier noch ein paar Testfälle, die letzte Zahl ist wieder das Ergebnis:
1,2,3,4,5,10,1 => 1*(2-3)+4*5/10=1
1,3,11,13,121,104 => ((121-13)*3-(11+1))/3=104
3,7,14,28,13 => 7+(3/14)*28=13
7,9,63,567 => (63/7)*9*7=567

EDIT:

---

weitere Testfälle hinzugefügt

---

[case]

mensch ist das unfair...

ich habe auch schon richtig lust darauf, mich da mal dran zu setzen aber ich muss noch soooo lange arbeiten

[PHP-Desaster]

Bin auf der Arbeit, aber habe mal kurz die Mittagspause genutzt und das hier zusammengeknüppelt:

<?php
    
    function OneMoreNerd( $input, $max=1000, &$iteration=0, $delta=5 ) {
        if( is_string( $input ) ) {
            $input = explode( ',', $input );
        }
        
        $result = array_pop( $input );
        $n = count( $input );
        $operators = array( '+', '-', '*', '/' );
        $intervalBottom = $result - $delta;
        $intervalTop = $result + $delta;
        
        do {
            $try = '';
            
            for( $i=0; $i<$n-1; $i++ ) {
                $try .= $input[$i];
                $try .= $operators[rand( 0, count( $operators )-1 )];
            }
            $try .= end( $input );
            if( ($iteration++)>$max ) {
                return( null );
            }
            
            $tryRes = eval( 'return '.$try.';' );
        }
        while( $tryRes < $intervalBottom || $tryRes > $intervalTop );
        
        return( $try );
    }
    
    $iteration = 0;
    $result = OneMoreNerd( $argv[1], $argv[2], $iteration, $argv[3] );
    if( is_null( $result ) ) {
        echo 'found no solutions';
    }
    else {
        echo 'found '.$result.' after '.$iteration.' iterations';
    }
    
?>

Verwendet keine Klammersetzung und ich nutze jede Ziffer nur einmal, ist also noch keine hübsche Lösung. Will das aber trotzdem schon mal loswerden

[combie]

Es kann sich sehr wohl eine Division durch null ergeben!

4/(3-3)

[PHP-Desaster]

Es kann sich sehr wohl eine Division durch null ergeben!

4/(3-3)

Richtig. Aber bei einer Division durch Null wird "lediglich" eine Warnung ausgelöst, die kannst du in diesem Falle ausnahmsweise ignorieren

[onemorenerd]

PHP-Desasters Funktion produziert für die selbe Eingabe unterschiedliche Ergebnisse.

Das ist nicht schlimm, kein Fehler. Aber ich werde die Testroutine so umschreiben, dass sie eure Lösungen für jede Eingabe mehrmals aufruft und so eine mittlere Genauigkeit feststellt. Außerdem werde ich die maximal Abweichung in die Bewertung mit einbeziehen.

@PHP-Desaster: Deine Formeln sind erstaunlich kurz. Respekt. Um das korrekte Ergebnis zu bekommen, müsste ich $max auf unendlich und $delta auf 0 setzen. Allerdings gibt es schon bei $delta = 1 überhaupt kein Ergebnis mehr (ich habs ca. 100 mal probiert).
Für die Bewertung dieser Lösung werde ich übrigens die Defaults der Parameter verwenden, also 1000 und 5.

[TheFish511]

Ok, dann mach ich auch mal mit. Wollte eigentlich eine Funktion(bzw. Funktionen) schreiben, die viel mehr Varianten durchspielen, aber keine Lust.
Solange die Zahlen nicht zu groß werden, bzw. solange es eine kleine Zahl gibt, ist es recht genau und schnell.

class math
{
    public $ergebnis = 0;
    public $rechnung;
    public function oneMoreNerd()
    {
        $zahlen = func_get_args();
        $erg = array_pop($zahlen);
        $min = min($zahlen);
        $this->calc($min, $erg);
        for ($i = 0; $i < count($zahlen); $i++)
            $this->rechnung .= '(' . $zahlen[$i] . ' - ' . $zahlen[$i] . ')';
    }

    private function calc($min, $erg)
    {
        if ($this->ergebnis < $erg) {
            $maximum = $this->ergebnis + $min - $erg;
            $minimum = $this->ergebnis - $erg;
            $maximum < 0 ? $maximum *= -1 : $maximum;
            $minimum < 0 ? $minimum *= -1 : $minimum;
            if ($maximum < $minimum) {
                $this->ergebnis += $min;
                $this->rechnung .= $min . ' + ';
                $this->calc($min, $erg);
            }
        }
    }
}

$m = new math();
$m->oneMoreNerd(4, 6, 5);
echo $m->rechnung . ' = ' . $m->ergebnis; 

[unset]

In 12 Minuten nach der Raucherpause runtergeballert. Die Klammerung habe ich noch nicht berücksichtigt, das mache ich dann zuhause. Ich hab mich extra in Pause gebucht

<?php

    // Testcase = ((8*16)/(5-1))*3 = 96
    
    echo nerdize(array(1, 4, 3, 8, 16, 96));

    function nerdize($aList) {
        // Liste kopieren
        $aListCopy = $aList;
    
        // Hilfsfunktion in Funktion deklarieren (JA DAS GEHT ;))
        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;

        // 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] = '+';
        }

        // Durchlaufen und testen ;)
        // Wir machen den Durchlauf zweimal, und versuchen beim zweiten mal Klammern
        // mit einzubeziehen
        $bKlammern = false;
        for($i = 0; $i < 2; $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);
            }

            // Das nächste (und letzte mal) mit Klammersetzung
            $bKlammern = true;
        }

        return 'Beste Formel: '. $sBesteFormel.'='. $iBestesErgebnis;
    }

?>

[onemorenerd]

@TheFish511: Dein $m->rechnung läßt sich nicht eval'n. Bisher 0 Punkte. Aber es ist noch viel Zeit um es zu verbessern.

[onemorenerd]

@unset: Wow, extrem kurze Formeln! Leider nicht immer exakt. Bei 7,9,63,567 kommst du auf 574.

[unset]

Die Funktion gibt auch nur die beste gefundene Formel aus. Im Grunde Bruteforce ich die Operationen zwischen den übergebenen Werten

[combie]

Original geschrieben von PHP-Desaster
Richtig. Aber bei einer Division durch Null wird "lediglich" eine Warnung ausgelöst, die kannst du in diesem Falle ausnahmsweise ignorieren

Achso, es dreht sich gar nicht um mathematisch korrekte Ergebnisse....
Dann ist die Aufgabe ja einfach zu lösen.

Dann wird mir auch klar, wieso die erste Medallie .......

[unset]

Ich denke eine Formel, die durch 0 teilt, wird nicht gewertet ... obwohl Sie auch gar kein Ergebnis auswerfen dürfte.

[onemorenerd]

Original geschrieben von combie
Achso, es dreht sich gar nicht um mathematisch korrekte Ergebnisse....

Was nicht mathematisch korrekt ist, kann ich nicht eval'n. Das gilt übrigens auch für die Division durch Null. Was sich nicht eval'n läßt, wird mit 0 Punkten bewertet.

Dann wird mir auch klar, wieso die erste Medallie .......

... an mich ging? Ich war selbst überrascht, zumal eine Funktion erwartet wurde, die einen Timestamp bekommt. Aber ich kann zumindest nachträglich zeigen, dass meine Lösung mit wenigen Änderungen korrekt ist. Dazu packe ich sie in eine Funktion und setze bei jedem date(), das bisher keinen 2. Parameter hatte den Funktionsparameter ein. Aus dem echo wird ein return und fertig.

function getDay($t) {
    return(($i=eval('for($l=date("z",$t)
    +date("w",0),$i=date("Y",$t)-1;$i>=date("Y",0);
    $i--,$l+=date("z",mktime(0,0,0,12,31,$i))+1);
    return$l;')%8)==3?'Bumsday':$i<3?date('l',$t):
    date('l',mktime(0,0,0,1,date('w',0)+$i-1,date('Y',0))));
} 

Das gibt es auch in lesbar.

function getDay($t) {
    // Tage des angebrochenen Jahres 
    // + Offset des 1.1.1970 (war ein Donnerstag)
    $l = date("z", $t) + date("w", 0);

        // + Tage aller Jahre von 71 bis heute
    // (date berücksichtigt Schaltjahre)
    for ($i = date("Y", $t) - 1; $i >= date("Y", 0); $i--)
        $l+=date("z", mktime(0, 0, 0, 12, 31, $i)) + 1;
    
    return ( 
        ($i = $l % 8) == 3 
        ? 'Bumsday'
        : $i < 3 
            ? date('l', $t)
            : date('l', mktime(0, 0, 0, 1, date('w', 0) + $i - 1, date('Y', 0)))
    );
} 

Da fehlt jetzt das eval(), aber ansonsten ist es genau der selbe Code, nur etwas hin und her geschoben.

[TheFish511]

Darf man mathematisch korrekte Umformungen verwenden? Also darf man statt 6+6+6, 3*6 ausgeben?