Algorithmus-Wettbewerb Teil 2: Spielplan errechnen
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
| Spielbrett 1 | Spielbrett 2 | Spielbrett 3 | |
|---|---|---|---|
| Runde 1 | 1-2 | 3-4 | 5-6 |
| Runde 2 | 3-5 | 1-6 | 2-4 |
| Runde 3 | 4-6 | 2-5 | 1-3 |
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 😉
Bis wann sollen die Skripte dich denn spätestens erreichen?
Klingt auf jeden Fall interessant und ich werde mich bei Zeit mal ransetzen.
Patrick
22 Jun 10 at 12:24
Coole Idee, da mache ich doch mit. Morgen oder übermorgen poste ich mal meinen Code.
Sascha Presnac
22 Jun 10 at 12:42
Eine Lösung für 6 Spieler hätte ich, die braucht 0.03sek., aber darüber wird es wieder kniffelig und es zerhaut mir den Spielplan. Ich muss mal meinen Ansatz überdenken. Ist nicht leicht, die Aufgabe, obwohl es einfach aussieht. Und das mitten in meiner Prüfungsvorbereitung *uff* 🙂
Sascha Presnac
23 Jun 10 at 09:25
Kannst ja dem Prüfer sagen dass es wichtigeres gibt im Leben eines Programmierers…
Michael Kliewe
23 Jun 10 at 10:00
@Michael: Ich denk mal, der Prof wird mir was husten, gelinde gesagt #g
Sascha Presnac
23 Jun 10 at 13:54
Interessante Aufgabe! 😉 *bastel*
Kannst du vll. noch die Lösung für 8 Spieler posten, damit ich mir diese Basis nicht selber erstellen muss um zu prüfen ob mein Script funktioniert!?
IchBinIch
23 Jun 10 at 19:55
Hmm…sowas wie das hier oder hab ich da irgendwie nen Fehler drin? 😀
http://www.faketheworld.net/_work/xy.php?gamer=20
Max. Wert = 100
tjado
23 Jun 10 at 20:16
Okay, erster Fehler erkannt und verbessert 🙂
tjado
23 Jun 10 at 20:38
@tjado: Nette Idee, sieht auf den ersten Blick auch gut aus, aber bei genauerem Hinsehen sieht man dass alle Duelle doppelt vorhanden sind, sprich „3 vs 13“ kommt doppelt vor. Bedingung ist jedoch dass niemand mehrfach gegen den selben Gegner spielen darf.
Aber die beiden anderen Bedingungen (niemand spielt doppelt auf einem Feld und niemand spielt doppelt in einer Runde) sind erfüllt.
Michael Kliewe
23 Jun 10 at 23:09
jo hab ich auch schon gesehen xD
tjado
23 Jun 10 at 23:30
Na dann möchte ich mal mein Vorschlag präsentieren:
http://pastebin.com/BtHiAnxp
Shiftyy
24 Jun 10 at 13:07
@Shiftyy: Spieler 16 spielt immer gegen Spieler 19. Irgendwas passt da noch nicht, ähnliches Problem wie bei tjado. Kein Spieler darf mehrfach gegen den selben Gegner spielen.
Außerdem bekam ich eine Notice „Undefined variable: numPlayers in Zeile 40“
Michael Kliewe
24 Jun 10 at 13:33
Erinnert mich irgendwie an die Eiweiß-Knickerei von BOINC. Meine Lösung funktioniert, ist aber noch sehr langsam. Bei 12 Spielern braucht es zwischen 8 und 29 sekunden.
Sascha Presnac
24 Jun 10 at 14:25
Na, dann wage ich es mal, hier meine Lösung:
http://softwareentwickler.blogspot.com/2010/06/algorithmus-wettbewerb-meine-losung.html
Nicht schnell, nicht schön, aber es funktioniert irgendwie. Ich werde das ganze versuchen zu optimieren, mir fallen da auch spontan 2 schrauben ein, an denen man drehen kann, aber für heute habe ich keine Zeit mehr.
Evtl. inspiriert es ja den einen oder anderen…
Sascha Presnac
24 Jun 10 at 15:10
Hier ist meine Lösung: http://pastie.org/1022197
Schnell und schön 😉
Der Algorithmus arbeitet zweigeteilt. Ein Teil für eine ungerade Brettanzahl und einer für eine gerade Brettanzahl. Beide haben nur eine quadratische Laufzeit.
GuBiMe
28 Jun 10 at 20:48
@GuBiMe Sieht sehr nett aus der Code! ABER: Ich habe ihn gerade mit 10 Playern laufen lassen, und im Ergebnis kommt das Duell 13-06 doppelt vor. Die komplette Runde 5 und Runde 10 scheinen gleich zu sein, nur etwas verschoben. Es spielen also Gegner doppelt gegeneinander was nicht erlaubt ist.
Da muss also noch etwas gefeilt werden, aber bisher der schönste Code würde ich sagen, OO mit PHPDoc… 🙂
Michael Kliewe
28 Jun 10 at 23:10
Tipp für’s nächste Mal: Wenn es ein Wettbewerb sein soll setze wenigstens eine grobe Frist…
Das macht die Aufgabe zwar interessant, aber ich frage mich: Gibt es dafür einen realen Anwendungsfall?
Gast
29 Jun 10 at 20:11
@Gast: Ein richtiger Wettbewerb ist es ja eigentlich auch nicht, ich habe keinen Gewinn oder ähnliches zu vergeben, es ist einfach nur ein Wettstreit um den schönsten, elegantesten und schnellsten Code, der das Problem löst.
Mein realer Anwendungsfall ist ein Table-Top-Turnier „Warhammer 40k“. Wir haben X Spieler und X/2 Spielplatten auf denen wir spielen. Damit niemand durch das Terrain einen Vor- oder Nachteil hat soll jeder exakt einmal jede Spielplatte bespielen, und zwar gegen wechselnde Gegner, und alle sollen immer parallel spielen, niemand soll aussetzen müssen.
Michael Kliewe
29 Jun 10 at 22:18
[…] etwa 2 Wochen hat der PHP Gangsta zu einem neuen Wettbewerb aufgerufen. Es sollen Spielpläne nach einem bestimmten Schema errechnet […]
PHP: Algorithmus-Wettbewerb: Spielplan errechnen | LocalDev
10 Jul 10 at 07:37
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
Christoph
10 Jul 10 at 09:45
@Christoph: Und genau das geht nicht, denn spätestens nach der Hälfte der Runden treffen die Spieler aus der 1. Runde wieder aufeinander wenn man so rotiert.
Kannst ja mal ausprobieren, so einfach ist es leider nicht 😉
Michael Kliewe
10 Jul 10 at 10:06
@Michael: Doch, es ist so einfach.
Wäre X bspw 10 und die folgenden Zahlen jewiels nur die Indizes, dann gäbe sich folgende Paarungen:
R1:1-2,3-4.5-6,7-8,9-10
R2:9-4,1-6,3-8,5-10,7,2
R3:7-6,9-8,1-10,3-2,5-4
R4:5-8,7-10,9-2,1-4,3-6
R5:3-10,5-2,7-4,9-6,1-8
Bedingungen erfüllt: Jede Runde ein anderer Tisch, Keine doppelten Paarungen.
Diese Tabelle wäre quasi fest. Nur die Spieler wären durch das vorherige Zusammenwürfeln jeweils anders.
Kann mir kaum vorstellen, dass in richtigen Events ein anderes Verfahren genutzt wird (als das vorherige Auslosen der Kontrahenten). Alles andere wäre recht ineffektiv!
Die eigentliche „Schierigkeit“ in dieser Methode liegt darin, zu Anfang möglichst effektiv das Xer Array ohne Duplikate zu füllen, aber auch das ist mit ner for- und ner while, sowie 2 Zeilen Code zu erfüllen; wenn man das ganze noch etwas unleserlich macht, kann man sogar mit den beiden Schleifen und einer Zeile Code auskommen.
—–
OT: Funktionsrümpfe würde ich übrigens nicht zu LOC zählen, da diese, wie Kommentare der Lesbarkeit dienen.
Christoph
10 Jul 10 at 11:10
@Christoph: Die Lösung funktioniert nur für ungerade Rundenanzahlen. Probier dein Verfahren mal mit 8 oder 12 Spielern (sprich 4 oder 6 Runden). Dann werden sich in der 3. bzw. 4. Runde die Paarungen wiederholen.
Siehe hier, habe es nach deiner Anleitung gemacht:
R1:1-2,3-4.5-6,7-8
R2:7-4,1-6,3-8,5-2
R3:5-6,7-8,1-2,3-4
1 wandert jede Runde einen Platz nach rechts, 2 immer nach links. Eine gerade Tischanzahl lässt die beiden wieder aufeinandertreffen.
Deine Lösung probiert fast jeder den ich bisher gefragt habe als erstes aus, funktioniert aber leider nicht immer.
Bin gespannt auf deine nächste Lösung 🙂
Michael Kliewe
10 Jul 10 at 11:29
Mist, war da tatsächlich n kleiner Denkfehler drin, aber auch der ist recht einfach behoben.
Die Grundidee bleibt gleich:
1) Vorheriges Würfeln
2) den linken Spieler einen Tisch weiterrücken lassen
—-
Neuer Verteilungsansatz: Die Paarungen werden „vorher“ festgelegt
X/2*X/2 Matrix:
1|2|3|…|X/2 (Die linken Spieler)
X/2+1|X/2+2|…|X (die rechten Spieler, die in der Verteilungsmatrix jeweils einen weiterrutschen)
X|X/2+1|X/2+2…|X-1
X-1|X|X/2+1|X/2+2…|X-2
…
Diese Verteilungsmatrix muss nun nur noch entsprechend 2) eingefügt werden 😉
Ich zappel mal flink den Code dahin; das ist fast noch einfacher, als dir vorherige Idee
Christoph
10 Jul 10 at 12:07
ich revidiere vorerst, war doch noch n denkfehler drin
Christoph
10 Jul 10 at 12:10
@Christoph: Bin gespannt!
Wäre natürlich toll wenn es eine einfache Lösung gibt. Martin (siehe oben LocalDev) hat ein sehr schönes Script geschrieben das das Problem zu lösen scheint, und das auch in annehmbarer Zeit, bin noch dabei die Lösung zu verstehen, ist trotz sehr guter Dokumentation nicht gerade einfach zu durchblicken 😉
Ich musste meine Lösung auch nochmals anpassen letzte Woche, es ist nun wieder recht langsam, aktuell scheint Martin die Nase vorn zu haben…
Michael Kliewe
10 Jul 10 at 12:16
Tach, bin grade durch PHPperformance auf dein Blog aufmerksam geworden. Da ich gerne tüftle, hier mein Beitrag:
http://smel.de/playmatch.php?player=20
Jackflash
14 Jul 10 at 04:48
Selber Fehler, wie bei mir.
Siehe RUnde 8, zweimal PG=7
Christoph
14 Jul 10 at 08:18
Kommt da noch was? Wann veröffentlich Gangsta seine Lösung?
Braunbär
4 Aug 10 at 10:55
Könnte ich eigentlich mal machen, habe den Artikel schon vorbereitet, aber derzeit komme ich zu nichts irgendwie. Und wie gesagt die schnellste Lösung scheint Martin zu haben, meine ist langsamer 😉
Michael Kliewe
4 Aug 10 at 11:06
[…] etwa 2 Wochen hat der PHP Gangsta zu einem neuen Wettbewerb aufgerufen. Es sollen Spielpläne nach einem bestimmten Schema errechnet […]
PHP: Algorithmus-Wettbewerb: Spielplan errechnen | local:/dev
2 Jan 13 at 17:47
Wahrscheinlich ist das Thema längst erledigt und nicht mehr aktuell. Dennoch, ich habe mich in den letzten Tagen auch damit beschäftigt und eine Anleihe bei den mathematischen Graphentheoretikern mit (glaube ich zumindest) Erfolg umgesetzt.
Siehe:
http://www.ulibecker.eu/homepage/index.php?option=com_spielplan&view=code
Schöne Grüße aus Wiesloch,
Uli Becker
Uli Becker
7 Mrz 13 at 20:55
Hi Uli,
deine Spieltage sind alle gleich… Irgendwas ist da schief gelaufen…
Wichtige Bedingung ist übrigens noch dass ein Spieler nie zweimal auf der selben Spielplatte spielen soll
Michael Kliewe
7 Mrz 13 at 21:55
Hallo Michael,
bin jetzt ein wenig verwirrt, muss ich sagen 😉
Unter unten stehendem Link habe ich es zig mal ausgetestet, und es ist durchgerattert – bin dabei weder auf gleiches Spieltage noch auf mehrfach am selben Spieltag angetretene Teams gestoßen.
Einfach zeilenweise die Teams eintippen (also pro Zeile ein Team, beliebig viele (n < 100).
Gab es ein Missverständnis?
http://www.ulibecker.eu/homepage/index.php?option=com_spielplan&view=demo
Viele Grüße,
Uli
Uli Becker
8 Mrz 13 at 15:26
Hi Uli,
jetzt bin ich auch verwirrt. Wo soll ich etwas zeilenweise eingeben?
So sieht es bei mir aus:
http://picload.org/image/aoaadrd/screenshot2013-0.png
Alle Spieltage sind gleich, keine Eingabebox irgendwo…
Michael
Michael Kliewe
8 Mrz 13 at 15:38
Hallo Michale,
wenn Du dem unteren Link folgst, solltes Du doch auf meiner Internetseite landen und dort ein Formular vorfinden – findest du da nix?
http://www.ulibecker.eu/homepage/index.php?option=com_spielplan&view=demo
Upps..ich mache mir gerade Sorgen, habe meine Seite bislang nur unter Firefox getestet, und da taucht auch meine Eingabebox auf….
Uli Becker
8 Mrz 13 at 15:53
Hi,
jetzt sehe ich da eine Textarea.
So sah es bei mir aus, „nur“ der Artikel zu sehen, und da sind alle Spieltage in der Tabelle gleich…
http://picload.org/image/aoaadcc/ulibecker.eu_201.png
Michael
Michael Kliewe
8 Mrz 13 at 16:00
Hallo Michael, klar, jetzt ist das Mißverständnis, glaube ich, aufgeklärt.
Dein Bild zeigt meine Erläuterungen, da habe ich mit Copy und Paste gefuscht und per Hand falsche Beispiel-Partien eingegeben, das sind keine generierten Spiele, sondern nur statischer HTML-Code, den ich falsch eingetippt habe.
Aber trotzdem solltest du doch mit dem angegebenen Link auf der Seite mit der Eingabebox landen?!
Zwei Screenshots, siehst du wenigstens die (ansonsten muss ich glaube ich zum Arzt ;-)?
http://www.ulibecker.eu/homepage/screenshot2.png
http://www.ulibecker.eu/homepage/screenshot.png
dir ein schönes Wochenende,
Uli
Uli Becker
8 Mrz 13 at 16:28
Hi Uli,
ja, schrieb ich ja, jetzt sehe ich die Textarea, und es funktioniert auch, ich sehe die generierten Partien wenn ich auf Senden klicke.
Allerdings möchte ich nach wie vor auf das Problem mit den „Tischen“ hinweisen. Es handelte sich dabei um ein Brettspiel, und niemand sollte zwei Mal an dem selben Tisch spielen. Gerade dies macht das Problem relativ schwer.
Bei 4 Spielern erhalte ich bei dir folgende Partien:
1. Spieltag
2 – 1
3 – 4
2. Spieltag
1 – 4
3 – 2
3. Spieltag
3 – 1
4 – 2
Nehmen wir an dass die erste Zeile eines jeden Spieltags immer „Tisch 1“ ist, und die zweite Zeile ist „Tisch 2“. Dann spielt Spieler Nummer 1 beispielsweise immer an Tisch 1.
Deshalb gibt es auch oben in der Aufgabenstellung die Begrenzung auf X/2 Spieltage, denn bei X Spielern hat man X/2 Partien, d.h. X/2 Tische. Und wenn niemand zweimal an einem Tisch spielen soll, dann dürfen nur X/2 Partien gespielt werden.
Bitte noch einmal oben die Aufgabenstellung genau durchlesen, und dann den Algorithmus anpassen, du wirst merken dass es dann plötzlich viel schwerer wird…
Michael
Michael Kliewe
8 Mrz 13 at 16:47
Ok, das ist natürlich wieder ein anderes Problem, muss zugeben, dass ich die Aufgabenstellung nicht wirklich gelesen habe, sorry. War eben nur mit meiner „einfachen“ Aufgabe beschäftigt.
Die Randbedingung verändert natürlich die Lage 😉
So oder so erst mal danke, mir wäre nie aufgefallen, dass ich in meiner Beschreibung nach paste & copy vergessen habe, die Einträge für die Spiele zu ändern.
Werde mich dann mal bei nächster Gelegenheit in die verschärfte Aufgabenstellung hinein vertiefen und verfolge interessiert was sich diesbezüglich hier so nocht tut,
Uli
Uli Becker
8 Mrz 13 at 17:03