PHPGangsta - Der praktische PHP Blog

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.