PHP: Algorithmus-Wettbewerb: Spielplan errechnen

Vor etwa 2 Wochen hat der PHP Gangsta zu einem neuen Wettbewerb aufgerufen. Es sollen Spielpläne nach einem bestimmten Schema errechnet werden.

Folgende Regeln sind zu beachten:

  • Die Anzahl der Spieler muss gerade sein
  • Es gibt X/2 Bretter und Runden (bei 20 Spielern gibt es 10 Bretter die an 10 Runden bespielt werden)
  • Jede Spielpaarung darf nur einmal vorkommen
  • Jeder Spieler darf nur einmal in einer Runde und an einem Brett spielen (ähnlich Sodoku)

Wenn ihr euch den kompletten Beitrag anseht, findet ihr meine Lösung. Die Berechnung dauert zwischen 3 und 300 Sekunden, und hängt davon ab, wie gut der Zufall mitspielt. Wer das ganze gleich mal testen möchte, kann eines der Ausgabeskripte nehmen, die ihr unter dem Algorithmus findet.

Schaut euch den Code einmal an, vielleicht bekommt ihr ja Ideen für einen eigenen Algorithmus. Noch habt ihr Gelegenheit daran teilzunehmen, denn der PHP Gangsta hat seine Lösung noch nicht veröffentlicht.


Berechnung:

Ausgabe (Konsole):

Ausgabe (HTML):

Comments 7

  1. Christoph

    Kann mir schon fast denken, welches der Anfangs als optimalst angepriesene Algo ist:
    1) Man würfle die Spieler vorher durch (bspw in einem Array) (Zufallskomponente)
    2) Quasi fester Spielplan, in Gitter:
    [1-2][3-4]…[(x-1)-x]
    [(x-1)-…[..-2]
    Sprich die Die linken wandern ein Brett weiter, die rechten ein Brett zurück.

    So hätte man mit weit weniger, als 58 Zeilen eine Zufallsbasierte Lösung, die in weit weniger als einer Sekunde einen Spielplan berechnet 😉

    Keep it Simple, Keep it Stupid

  2. Fabian

    @Christoph: und schon bei 4 Brettern hast du alles voller doppelter Paarungen

    1-2 3-4 5-6 7-8
    7-4 1-6 3-8 5-2
    5-6 7-8 1-2 3-4
    3-8 5-2 7-4 1-6

  3. Pingback: Mein Spielplan-Algorithmus | PHP Gangsta - Der PHP Blog

  4. Pingback: PHP: Warum count() im Schleifenkopf langsam ist und foreach auch | LocalDev

    1. Post
      Author
      Fabian Martin

      Ich habe es nur kurz getestet, aber ich glaube mit dem dort beschriebenen Algorithmus lässt sich der Punkte “Jeder Spieler darf nur einmal in einer Runde und an einem Brett spielen (ähnlich Sodoku)” nicht erfüllen.

      1. Erik

        Naja gut, aber dafür wird sich ja wohl noch ein Algorithmus finden lassen 😉
        Als Informatiker/Mathematiker lässt sich da auf jeden Fall was errechnen, wenn man ein bisschen Zeit investiert.
        Ich hab sie momentan leider nicht, obwohl es mir gerade schon wieder in den Fingern juckt 😉

        Grüße

Hinterlasse eine Antwort

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