Algorithmus Wettbewerb: Meine Lösung

Eine super Idee hat Michael in seinem Blog: Eine Programmier-Aufgabe, die es wirklich in sich hat.

Die Aufgabe findet ihr unter dem Link, hier findet sich meine Lösung.

28.06.2010
Das ganze muss auch eine mathematische Lösbarkeit haben, hier mal meine bisherigen Überlegungen:
x = Anzahl der Spieler
p1 = Anzahl der möglichen Platzierungen ohne Partiedopplung (also ohne das ein Spieler mehrfach gegen einen anderen antritt), Brettdopplung nicht berücksichtigt:
p1 = (x²-x)/2 = Summe 1 bis (x-1)

Memo an mich: Mehrfach-Matrix mit Substitution erstellen, Speicherbedarf testen!

24.06.2010

Erste Lösung, nicht hochperformant, aber funktioniert.
Die echo „.“ Angaben und die variable $neustarts sind nur für mich und könnten in einer finalen Fassung entfernt werden

$startzeit = microtime(1);
if ($_SERVER['argv'][1]%2!=0)
die("Nur gerade Eingaben!\n");
$spieler = $_SERVER['argv'][1];
//$spieler = 8;
$bretter = $spieler/2;
$spielplan = array();
$neustarts=0;
$abbruch = $spieler ^ 3;
for ($runde=1; $runde<=$bretter; $runde++)
{
$rundensatz = -1;
$count = 0;
while ($rundensatz == -1)
{
$count++;
if ($count > $abbruch)
{
$count=0;
for ($x=1;$x<=($spieler/2);$x++)
$spielplan[$x] = null;
$runde=0;
$neustarts++;
echo "."; flush();
break;
}
$spielerstack = generiereSpielerStack($spieler);
$rundensatz = besetzeRunde($spielplan,$runde,$spielerstack);
}
if ($rundensatz==-1) continue;
$spielplan[$runde] = $rundensatz;
}

print_r($spielplan);

$endzeit=microtime(1);
printf("Spieler: %u\n",$spieler);
printf("Bretter/Runden: %u\n",$bretter);
echo 'Benoetigte Zeit: '.($endzeit-$startzeit).'s'."\n";
printf('Benoetigte Neustarts: %s',$neustarts);

exit;

function generiereSpielerStack($spieler)
{
$stack=array();
for ($i=1;$i<=$spieler;$i++)
array_push($stack,$i);
shuffle($stack);
return $stack;
}

function besetzeRunde($spielplan,$runde,$spielerstack)
{
$bretter = count($spielerstack)/2;
$aktuellerSpieler = array_shift($spielerstack);
while (count($spielerstack)>0 && is_numeric($aktuellerSpieler))
{
if ($brett>$bretter)
{
return -1;
}
for ($brett=1;$brett<=$bretter;$brett++)
{
$opp=0;
if (brettBesetzt($brett,$runde,$spielplan))
continue;

if (hatGespieltAufBrett($aktuellerSpieler,$brett,$spielplan))
continue;

if (is_numeric($spielplan[$runde][$brett][0])
&&
hatGespieltGegen($aktuellerSpieler,$spielplan[$runde][$brett][0],$spielplan))
continue;

if (is_numeric($spielplan[$runde][$brett][0]))
$opp=1;

$spielplan[$runde][$brett][$opp]=$aktuellerSpieler;
$aktuellerSpieler = array_shift($spielerstack);
if (is_null($aktuellerSpieler))
{
return $spielplan[$runde];
}
$brett=0;
}
}
if (is_numeric($aktuellerSpieler))
return -1;
else
return $spielplan[$runde];
}

function brettBesetzt($brett,$runde,$spielplan)
{
return (is_numeric($spielplan[$runde][$brett][0]) && is_numeric($spielplan[$runde][$brett][1]));
}

function hatGespieltGegen($spieler1, $spieler2, $spielplan)
{
for ($i=1;$i<=count($spielplan);$i++)
{
if ($spielplan[$i] == null)
return false;

for ($j=1;$j<=count($spielplan[$i]);$j++)
{
if ( ($spielplan[$i][$j][0] == $spieler1 && $spielplan[$i][$j][1] == $spieler2 )
||
($spielplan[$i][$j][0] == $spieler2 && $spielplan[$i][$j][1] == $spieler1 )
)
return true;
}
}
return false;
}

function hatGespieltAufBrett($spieler, $brett, $spielplan)
{
for ($i=1;$i<=count($spielplan);$i++)
{
if ($spielplan[$i] == null)
return false;

if ($spielplan[$i][$brett][0] == $spieler || $spielplan[$i][$brett][1] == $spieler )
return true;
}
return false;
}

Verbesserungsvorschläge überaus erwünscht 😉

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.