Advent 9 - Hilfe, Hilfe!

English translation follows the German text.

Hallo.
Hinter Türchen 9 wollte ich etwas wirklich Wunderschönes verstecken. Ich wollte nämlich ein Computer-Programm schreiben, das die Auslosung für die erste KO-Runde der diesjährigen Champions League simuliert. Ich habe es aber gerade geschrieben und es hat einen ziemlich schlimmen Fehler, dessen Schilderung ich jetzt anstelle des eigentlichen Programms Ihnen zum 9. Adventstag (ja, ist verspätet) schenken kann.

Bei der Auslosung werden 16 Teams in 8 Begegnungen sortiert.
Die Einschränkungen sind:
1) kein Team darf gegen das andere Team aus derselben Vorrundengruppe spielen. Es gibt 8 Gruppen mit jeweils 2 Teams.
2) kein Team darf gegen ein anderes Team aus demselben Land spielen.
3) Gruppenerste müssen gegen Gruppenzweite spielen.

Das war's. Heim und Auswärts sind auch kein Problem, denn die Gruppenersten immer das Rückspiel zu Hause spielen dürfen. Es klingt nicht so kompliziert und eigentlich ist es auch nicht.
Mein Programm "funktioniert" folgendermaßen.
Der erste Gruppenzweite wird zufällig ausgesucht und sein Gegner wird aus den Gruppenersten auch zufällig ausgesucht. Es wird dann überprüft, ob der Gruppenerste unter Berücksichtigung der Einschränkungen gegen den ausgesuchten Gruppenzweiten spielen darf. Wenn nicht, wird ein neuer Gruppenerster ausgesucht und überprüft, bis eine akzeptable Paarung gefunden worden ist.
Für die zweite (und dritte, vierte usw.) Begegnung wird derselbe Prozess durchgeführt, nur mit der zusätlichen Funktion, dass schon ausgesuchte Teams abgelehnt werden. In diesem Fall wird ein neues Team gezogen bis eins gefunden wird, das noch nicht genommen wurde.
Klingt alles okay, und es hat ein paar Mal geklappt, dass ich 8 zulässige Begegnungen bekam. Jedoch: manchmal kommt es zu einer solchen Auslosung:

Lyon - Chelsea
Marseille - Barcelona
AS Roma - Real Madrid
FC Kopenhagen - Schalke 04
Inter Mailand - Schachtar Donezk
AC Mailand - Bayern München
Arsenal -

Da hängt das Programm. Denn:
Nach den Regeln sind das alle an sich ganz akzeptable Spielpaarungen. Leider bleiben in diesem Falle nur englische Gruppenerste übrig (Man Utd und Tottenham Hotspur), weshalb kein Gegner für den FC Arsenal gefunden werden kann.
Da müsste man etwas Besseres ins Programm einbauen, um dies zu vermeiden. Es ist in der Tat (wenn ich mich nicht irre) nicht so einfach, wie ich dachte - dass man nicht einfach für jeden Verein einen passenden Gegner finden muss, sondern man muss gleichzeitig auf die übriggebliebenen Vereine aufpassen, dass aus denen noch zulässige Paarungen zu machen sind.
Ich habe dieses Problem noch nicht gelöst - ich war mit dem Schreiben des Massive Blogs beschäftigt - aber wenn ich's bis heute Abend hingekriegt habe, kriegen Sie dann das optimierte (funktionierende) Programm als 10. Adventsgeschenk.
Für Vorschläge zur Lösung des Problems bin ich natürlich offen.
Bis bald.



Hello.
Behind door number 9 I was looking to hide something really wonderful. You see, I wanted to write a computer programme which would simulate the draw for the first knock-out phase of this year's Champions League. But I've just written it and it has got a pretty heinous error, the description of which I am now going to give you on this 9th day of Advent (yes it's late) instead of the actual programme.
At the draw 16 teams are sorted into 8 matches.
The restrictions are:
1) no team is allowed to play against the other team from the same group-phase group. There are 8 groups each with 2 teams.
2) no team is allowed to play against a team from the same country.
3) group winners have to play group runners-up.
That's it. Home and away takes care of itself too, because group winners always play the second leg at home. It doesn't sound that complicated and it actually isn't. My programme "works" as follows.
The first runner-up is chosen at random and its opponent is then chosen at random from the group winners. It is then checked whether the group winner, according to the restrictions, is allowed to play against the runner-up selected. If not, a new group winner is chosen and checked, until an acceptable pairing has been found.
For the second (and third, fouth etc.) match-up the same process is carried out, just with the additional function, that teams which have already been selected are rejected. In this case, a new team is drawn until one is found which hasn't yet been chosen.
It all sounds okay and it did work a few times - so that I got 8 admissable match-ups. However: sometimes you get a draw like this:

Lyon - Chelsea
Marseille - Barcelona
Roma - Real Madrid
FC Copenhagen - Schalke 04
Inter Milan - Schakhtar Donetsk
AC Milan - Bayern Munich
Arsenal -

Then the programme freezes. Because:
According to the rules those are all in their own right acceptable match-ups. Unfortunately, you are left in this case with only English group-winners (Man Utd and Tottenham), for which reason no opponent can be found for Arsenal.
So something better has to be built into the programme to avoid this scenario. It is in fact (if I'm not mistaken) not as easy as I thought - that you can just look for a suitable opponent for each club. Instead you have to, at the same time, take care of who the left over clubs are, and that you can still build admissable pairings from them
I have not yet solved this problem - I've been busy writing the Massive Blog - but if I've solved it by this evening, then you can get the optimised (working) programme as the 10th Advent present.
I'm obviously open to suggestions as to how to solve the problem.
See you soon.