"Calculation is taking too long. And here's why."

[inker]

I knew you'd run into this message sooner or later 😜

Currently, in order to find the first possible group, the algorithm conducts the virtual draw behind the scenes to check if placing the picked team in a certain group would result in a possible outcome. The problem with this approach is that for the Europa League there's at most 12!⁴ ≈ 5.3×10³⁴ possible outcomes. Sounds almost like a transcomputational problem.

If you have any ideas how to speed up the algorithm, please share it here. Your contribution would be highly appreciated!

[bersbersbers]

Sooo... How does UEFA do it?

[InNOutJimmy]

Hello,

I need to do the calculations, but I'm pretty sure that whatever the draw outcome for the first 2 pots (just using rules and random selections), there are always possible outcomes from the 3rd and 4th pots resulting in a possible outcome (because there are more teams and more diverse nations than the Champions League). So maybe you can just drop the calculations for checking the possible outcome for the first 2 pots. If you do that, checking only 3rd and 4th pots would be a lot easier.

Champions League regulations are a bit stricter than Europa League, so I'm not sure if same theory holds for that competition as well (possibly it does).

[mikezks]

Please see the section on "paired":
https://www.uefa.com/uefaeuropaleague/news/newsid=2568277.html

Does this help?

Thanks for this fabulous web app! 😉

[mikezks]

Teams are drawn only, not groups.
So after each drawn team the computer determines which group is possible.

E.g.: remaining teams of pot 4:

• Slavia
• Akhisarspor
• Düdelingen

Groups with open spots:

• Group A: any team
• Group F: Fenerbahce
• Group L: Besiktas

If Slavia is drawn first: Group F

If Akhisarspor is drawn: Group A

If Düdelingen is drawn...

• first: Group F
• second and after Slavia: Group L
• second and after Akhisarspor: Group F
• third: Group L

[inker]

@mikezks For each case you have to perform the complete remaining part of the draw in order to check if placing certain team in certain group is possible or not. That's why a computer is needed for this kind of task. This is what's inside the engine of this draw simulator.

@InNOutJimmy No, that's not true. Some teams are paired with each other to avoid going into the same half & technically both teams can be in the first pot (e.g. Arsenal & Chelsea this year). So tree traversal is always needed. There was even an edge case a couple of years ago when there were 4 teams from 4 different countries in the first pot & it was required that each 2 of them went into the opposite halves. See this post.

@bersbersbers I guess they're either cheating or using a big-ass cluster to perform the calculations. I suspect both. And they're definitely not using JavaScript.

[mikezks]

No it's not. It's really only straight forward from group A to L.

The magic is, that you need to divide the possible set of groups by two if you have a second team of the same country.

E.g. Salzburg was drawn from pot 1 to group B, so for Rapid from pot 2 group G to L are the only possible.

You just need to take the previous pots and the current in consideration.

Try it out. It works. Respectivly rewatch the UEFA draw.

Edit: and of course the algo checks if enough spots for the remaining teams are free. So the algo needs to check if the remaining teams are allowed to be drawn to any of the remaining spots if Rapid is put in group G. Otherwise Rapid changes to H and the algo checks again.

Nevertheless this is much more performant than checking all possibilities.

You just need to check the teams of the current pot based on the known set of pot 1, but do NOT take pot 3 and 4 into consideration at this moment.

[mikezks]

The pairs are just to respect TV timeframes for teams of the same country. A nice side effect: you reduce complexitiy so that Salzburg and Rapid may not be drawn in the same group. There is no further magic.

Just try it out - this also works with JavaScript.

[inker]

@mikezks This is exactly how the program handles it, we're talking about the same thing.

Suppose, Salzburg goes to group D. Fast forward to Rapid Wien drawn out after 2 balls from its pot have been drawn out (went to, say, groups A & B). So first of all, the program checks if group C is possible by first scanning if Salzburg is in the half. It is (i.e. a deadlock), so it skips the first half & goes to checking group G.

[bersbersbers]

@mikezks I believe you are missing a main point (or I am missing completely what you are saying). Consider this simple example of 4 teams to be drawn into 2 groups, with one pair to be put into separate groups (for whatever reasons - time frame, same country, RUS-UKR, ...).

Let's call the teams in pot 1, X1 and Y, and in pot2, X2 and Z. X1-X2 is the pair to be put separately. The groups are A and B.

You draw team X1 from pot 1, have groups A and B available. Let's say you draw group B.
You draw team Y from pot 1, have only group A available.

So after pot 1, you have:
Group A: Y
Group B: X1
So far, so good.

Now you draw team Z from pot 2. Which groups do you have available? Naively, you would say "A and B", but this could lead to a deadlock - why? Assume you draw group A:
Group A: Y, Z
Group B: X1, ?

Then, for the next team from pot 2, which is X2, you only have group B available, but X1 and X2 must not be in the same group. This is the deadlock we are about to avoid. Therefore, team Z can only go in group B.

This is a simple example. What this means in general terms is that, even for the very first team of the second pot, one has to determine carefully which groups are available, even if all groups look like they are possible, considering only the team that was just drawn.

Edit, reacting to "much more performant than checking all possibilities": if you happen to come across a group for a team that is indeed impossible, you need to be sure of that. In fact, you can only verify that by enumerating all possibilities (you don't have check each individual one, as some may be similar and can be considered together), but in the worst case, this can take a long time.

[mikezks]

In this example Rapid is not allowed to go to group A to F, but G to L only.

Now you already reduce complexity by splitting in two halves.

So you just need to check whether the remaining teams of pot 2 have at least one allowed spot in G to L. If not, Rapid moves to H and check reruns. If G is OK check is finished.

Furthermore pot 2 has other teams too, that may only be allowed to go to group A to F and therefore are not required to be checked.

[mikezks]

@bersbersbers You have 12 groups if we talk about Europa League and 8 in case of the Champions League.

The pairings are the only thing you know before taking the first team out of pot 1.

Let's say this team is Leverkusen. Leverkusen is not paired, only Leipzig and Frankfurt are.

So the algo tries to put Leverkusen in group A and checks whether all other teams of pot 1 have at least one free spot. If they have, check successfully finished, if not, try B.

You just repeat these steps and that's all.

[mikezks]

@bersbersbers:

Regarding your example: we do not draw groups, just teams. So it is not possible to draw X1 to group B. This would only be possible if Y has a constraint that it is not allowed to go to B.

If X1 is in group A and paired with X2, then Z is only allowed to go to group B. This is part of the instant check.

The trick is: not all groups are possible. That is a wrong consideration and part of the check.