PHPGangsta - Der praktische PHP Blog

Bis heute morgen wurden von 18 Lesern 19 Lösungen zur vorgestrigen Array-Umbau-Aufgabe eingereicht, und ich habe alle Funktionen durchlaufen lassen mit einem Testarray. Nun möchte ich hier einige Werte zur Korrektheit und Laufzeit veröffentlichen.

Dazu habe ich ein Testscript erstellt, welches auf GitHub einsehbar ist, und wo ich alle Funktionen mit einem 29358 Elemente großen Array laufen lasse und dann die Laufzeit und Korrektheit der Umwandlungen überprüfe.

Hier die sortierbare Tabelle:
Weiterlesen »

Eine kleine Aufgabe, die es zu lösen gibt. Ich habe folgendes Ausgangsarray, das nur positive ganze Zahlen enthält, die nur einmal vorkommen:

$numbers = array(13,81,80,79,78,77,76,19,40,41,42,43,44,45,48);

und möchte:

$numbers = array(13,"81-76",19,"40-45",48);

Es sollen also alle zusammenhängenden Arrayelemente zusammengefasst werden, um das Array kleiner zu machen (weniger Speicherplatz/Traffic).

In einem zweiten Schritt soll dann dieses Array wieder zurück umgewandelt werden in das Original:

$numbers = array(13,81,80,79,78,77,76,19,40,41,42,43,44,45,48);

Die Reihenfolge soll beibehalten werden, sodass es möglich ist das Array vor- und zurück umzuwandeln.

Wer hat die schönste und einfachste Lösung für die beiden Funktionen? Lösungen per Gist oder Pastie etc. posten.

Heute kam mir eine nette kleine Programmieraufgabe zu Ohren, und da dachte ich gleich an euch. Das könnte eine interessante Aufgabe sein um zu zeigen wie mit unterschiedlichen Vorgehensweisen das Problem gelöst werden kann.

Die Aufgabe: Die Zahlen 1 bis 10.000 sollen der Reihe nach ausgeschrieben werden, getrennt durch einen Umbruch. So sieht die Ausgabe dann aus:

eins
zwei
drei
vier
fünf
......
eintausendzweihundertdreizehn
eintausendzweihundertvierzehn
....
zehntausend

Ich hoffe die Aufgabe ist verständlich. Mich würde vor allem die Codelänge interessieren, ich glaube die Laufzeit oder Speicherverbrauch sind relativ uninteressant bzw. sehr ähnlich.

Programmiersprachen: Natürlich PHP, aber auch gern andere Sprachen zum Vergleich.

Edit: Eine sehr schöne Zusammenfassung der Ergebnisse hat Rodney Rehm geschrieben, Danke!

Vor 2 Wochen hatte ich ja dazu aufgerufen ein algorithmisches Problem zur Berechnung eines Spielplan zu lösen. Es gab in den Kommentaren einige gute Ansätze und auch eine gültige Lösung wenn ich es richtig gesehen habe, und wie versprochen werde ich heute meine Lösung veröffentlichen.

Vielleicht sollten wir uns nochmal das Grundproblem ins Gedächtnis rufen:

Wir haben folgende Ausgangslage: X Spieler möchten ein Turnier veranstalten, wobei jeweils einer gegen einen spielt (Duelle, deshalb sollte X gerade sein). Dabei soll jedoch niemand mehrfach gegen den selben Spieler antreten und es soll niemand ein Spielbrett zweimal benutzen dürfen. Es gibt X/2 Spielbretter, also auch für jeden Spieler X/2 Duelle.

Meine erste Lösung war recht schnell und auf den ersten Blick coole Lösung, ABER auch dieser Code hat das Problem dass es doppelte Paarungen gibt. Dieses Problem hatten fast alle Lösungen aus den Kommentaren auch.
Grundsätzlich funktioniert der Algorithmus wie folgt (bei 10 Spielern): Ich fülle am Anfang ein 5*5 Array, worin jede Zelle alle Spielernummern (0-9) enthält. Dann ziehe ich aus dem ersten Feld 2 zufällige Spieler, lösche alle anderen Einträge aus dieser Zelle und lösche diese beiden gezogenen Spieler auch aus der restlichen Zeile und Spalte. So stelle ich sicher dass ein Spieler nur einmal pro Runde und einmal auf jedem Spielfeld spielt. Das mache ich nun so lange bis ich eine Zelle finde wo es keine 2 Spieler mehr gibt, dann resette ich zum Anfangsarray ($startGrid) und beginne von vorn.

<?php
$player = 10;

$rounds = $player/2;
$startGrid = array();

$startTime = microtime(true);

for ($i=0; $i<$rounds; $i++) {
    for ($j=0; $j<$rounds; $j++) {
        $startGrid[$i][$j] = range(0, $player-1);
    }
}

while (true) {
    $grid = $startGrid;

    for ($j=0; $j<$rounds; $j++) {
        for ($i=0; $i<$rounds; $i++) {
            if (count($grid[$i][$j]) < 2) {
                continue 3;
            }

            $randomEntries = array_rand($grid[$i][$j], 2);

            $first = $grid[$i][$j][$randomEntries[0]];
            $second = $grid[$i][$j][$randomEntries[1]];

            $grid[$i][$j] = array($first => $first, $second => $second);

            for ($z=0; $z<$rounds; $z++) {
                if ($z != $i) {
                    unset($grid[$z][$j][$first]);
                    unset($grid[$z][$j][$second]);
                }
            }
            for ($z=0; $z<$rounds; $z++) {
                if ($z != $j) {
                    unset($grid[$i][$z][$first]);
                    unset($grid[$i][$z][$second]);
                }
            }
        }
    }

    outputPlan($grid);
    echo "\n".round((microtime(true)-$startTime), 2)." seconds\n";
    exit;
}

function outputPlan($grid) {
    global $rounds;

    for ($i=0; $i<$rounds; $i++) {
        for ($j=0; $j<$rounds; $j++) {
            echo str_pad(join('-', $grid[$i][$j]), 25);
        }
        echo "\n";
    }
}

Nachdem ich das Problem mit den doppelten Paarungen entdeckt hatte musste ich also nochmal überlegen und bin zu folgenden Code gekommen, der deutlich langsamer ist, aber (glaube ich) gültige Ergebnisse ausspuckt. Ich habe einen ähnlichen Ansatz wie beim ersten Versuch, speichere in jeder Zelle jedoch nicht alle Spieler, sondern alle Spielpaarungen.

<?php
$player = 10;

$rounds = $player/2;

$startTime = microtime(true);

$gameTable = array();
for ($i=0; $i<$player; $i++) {
    for ($j=$i+1; $j<$player; $j++) {
        $gameTable[] = array($i, $j);
    }
}

$startGrid = array();
for ($i=0; $i<$rounds; $i++) {
    for ($j=0; $j<$rounds; $j++) {
        $startGrid[$i][$j] = range(0, count($gameTable)-1);
    }
}

while (true) {
    $grid = $startGrid;

    for ($j=0; $j<$rounds; $j++) {
        for ($i=0; $i<$rounds; $i++) {
            if (count($grid[$i][$j]) == 0) {
            	echo "Abbruch in $i/$j\n";
                continue 3;
            }

            // Randomly pick one game
            $randomEntryIndex = array_rand($grid[$i][$j]);
            // remove all others in that cell
            $grid[$i][$j] = $randomEntryIndex;

            // remove all games from rest of row which have players in it we picked above
            for ($z=$i+1; $z<$rounds; $z++) {
                foreach ($grid[$z][$j] as $game) {
                	if (in_array($gameTable[$randomEntryIndex][0], $gameTable[$game]) ||
                		in_array($gameTable[$randomEntryIndex][1], $gameTable[$game])) {
                		unset($grid[$z][$j][$game]);
                	}
                }
            }

        	for ($z=$j+1; $z<$rounds; $z++) {
                foreach ($grid[$i][$z] as $game) {
                	if (in_array($gameTable[$randomEntryIndex][0], $gameTable[$game]) ||
                		in_array($gameTable[$randomEntryIndex][1], $gameTable[$game])) {
                		unset($grid[$i][$z][$game]);
                	}
                }
            }

            // remove all occurences of that exact match
            for ($k=0; $k<$rounds; $k++) {
        		for ($l=0; $l<$rounds; $l++) {
        			if (!($k==$i && $l==$j)) {
        				unset($grid[$k][$l][$randomEntryIndex]);
        			}
        		}
        	}

        }
    }

    outputPlan($grid);
    echo "\n".round((microtime(true)-$startTime), 2)." seconds\n";
    exit;
}

function outputPlan($grid) {
    global $rounds, $gameTable;

    for ($i=0; $i<$rounds; $i++) {
        for ($j=0; $j<$rounds; $j++) {
            echo str_pad(join('-', $gameTable[$grid[$i][$j]]), 25);
        }
        echo "\n";
    }
} 

Ja, ich weiß, nicht schön („global“ etc.), aber funktioniert, wenn auch langsamer als Fabians Lösung aus den Kommentaren des Aufruf-Artikels. Er sagte mir dass er mehrere Abende daran gesessen hat und die Lösung sein achter oder neunter Ansatz gewesen sei. Wirklich respektabel wie er sich da reingearbeitet und diese schöne Lösung erstellt hat.

Tüftler aufgepasst, ich habe eine neue Aufgabe, die es möglichst effektiv zu lösen gilt. In der Vergangenheit hatte ich bereits nach Wegberechnungen auf einem Spielfeld für ein Browsergame gefragt, heute soll es um einen Spielplan gehen den es zu errechnen gilt.

Wir haben folgende Ausgangslage: X Spieler möchten ein Turnier veranstalten, wobei jeweils einer gegen einen spielt (Duelle, deshalb sollte X gerade sein). Dabei soll jedoch niemand mehrfach gegen den selben Spieler antreten und es soll niemand ein Spielbrett zweimal benutzen dürfen. Es gibt X/2 Spielbretter, also auch für jeden Spieler X/2 Duelle.

Die Ergebnistabelle ähnelt etwas einer Sudoku-Lösung: Jede Zahl darf nur einmal pro Zeile und einmal pro Spalte vorkommen.

Beispiel: 6 Spieler, 3 Spielfelder

Für 4 Spieler und 2 Spielfelder gibt es keine Lösung.

Nun sollen gültige Lösungen für beliebig viele Spieler gefunden werden, in meinem Realbeispiel benötigten wir einen Turnierplan für 10 und 12 Spieler. Ich habe vor ca. einem Jahr ein Script geschrieben welches dafür ca. 20 Stunden gebraucht hat, gestern habe ich einen anderen Ansatz gewählt und habe in unter einer Sekunde eine Lösung.

Ihr sollt nun ein Script schreiben das bei einer Eingabe der Spieleranzahl von 20 eine gültige Lösung ausspuckt. Die Lösung dann bitte hier, im eigenen Blog, bei Pastie.org oder sonstwo veröffentlichen (Script + Ergebnis). Mein Script hat 58 Zeilen, ist zufallsbasiert (also keine Rekursion, kein geordnetes Brute-Forcing) und ich werde es in 2 Wochen (6.7.2010) veröffentlichen. Es benötigt für 20 Spieler im Durchschnitt ca. 60 Sekunden (da zufallsbasiert dauert es mal 4 Sekunden, mal 250 Sekunden).

Bin gespannt auf eure unterschiedlichen Lösungen, vielleicht ist ja eine sehr gute und schnelle Lösung dabei! Aber auch erste Ideen und langsame Scripte sind eine gute Basis, sie vorzustellen und zu verbessern.

Das ist auch eine gute Möglichkeit, sich mit Freunden, Bekannten und Arbeitskollegen zu messen 😉