"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.

[bersbersbers]

@mikezks my final cents for today:

1. I must say, sorry, I am growing a little tired of your high-frequency posting and editing, this is not what an issue is for. (This is not a chat.) If I do post here again, this will not be before tomorrow to give you some time to converge to some stable output.
2. What do you want to say by "12 groups if we talk about Europa League and 8 in case of the Champions League". Are you inferring my example is too simple? Are you inferring my point does not apply to more groups? I don't get that.
3. I have no idea what you mean by "we do not draw groups". We sure do draw groups: namely, from the bowl in which we place all possible groups for the team just drawn. This fact, however, has nothing to do with the fact that "it is not possible to draw X1 to group B" (we both agree on that). In addition, I have no idea what your constraint on team Y would change: in my example, team Y is not in group B, so what would that constraint add?
4. Finally, the "checks whether all other teams of [some pot] have at least one free spot" are exactly what can take a lot of time. This is what this issue is about.

[mikezks]

Same additional things:

• You do not need to check all possibilities.
• Just the ones from A to L in a sequence (resp. A to F or G to L).
• You just need to verify that if team 1 is in group A and team 2 is in group B, that teams 3 to 12 have ONE free spot each in group C to L.
• If team 3 is put in group C and this results in one of the teams 4 to 12 to have no spot in D to L, then 3 moves to D and the check reruns.

[inker]

@mikezks Of course, I meant G, not F. Sorry for the typo.

Please, check out this file to see that what you're saying has already been implemented. The EL draw's entry point for each picked team is the firstPossibleGroup function. Notice that in filterGroupsBasic, checks are not made against the 'dead' half - instead, it is simply removed from traversal following trivial checks in filterSomeGroups which determines that 'Rapid' cannot be drawn into the half where 'Salzburg' already is, so those branches are simply cut off from the tree.

[mikezks]

@bersbersbers:

I did not want to offend you. Of course I respect, that you do not agree with my posting frequency. I just wanted to help. As this does not seem to be helpful for you I will stop it now. Nevertheless all the best for your further actions on this issue.

[InNOutJimmy]

@inker that special case occurs because of the pairings. But if you check pairings correctly (it's an instant check for the computer even if there are many possible constraints) you'll already achieve the thing that you're talking about (2 teams for one half and 2 teams for the other half).

Case 1: Let's assume you have already drawn Barcelona and Chelsea to the red group in your first two draw. By red group I mean first half of the actual groups (A-B-C-D). And at a point you drew Bayern. At that point, your pairing algorithm should check only the pairing results. Because you drew Barcelona and Chelsea to the red group, only 2 teams left in the red group. But because of the pairings of the pot 2, you also know that 2 of the pot 2 teams that are paired should go to the red group, which closes red group to Bayern and Bayern should go to the blue group. It's same for Benfica as well. So by only checking pairings and same nation rule (also RUS-UKR case) you could finish 1st pot without a problem. And you can continue with the same manner for the remaining pots.

Case 2: Let's assume you draw 2 teams that are not the problematic teams (BAR-CHE-BAY-BEN). Because you may draw 3 teams in the same group and you deadlock the draw. However, because you'll do the pairing check at every step, you'll know that 2 of the red and blue groups are occupied (we don't know which groups, but we know that 2 groups are occupied). Therefore, you cannot draw 3 teams in the same group. In that case, even if BAR, CHE,BAY,BEN are drawn very late, it wouldn't be a problem.

Now you may ask it's a lot of check. However, pairing checks don't need a lot of time. And after each successful draw, the number of checks decreases dramatically. And in this particular drawing problem, creating the whole possibility tree is unnecessary.

You should only focus on the pairings and nation rule. Teams like Crvena Zvezda, Plzen, Galatasaray etc. (only teams from their country and has no special rule) don't have any role in this calculation.

And I'll finish my comment with some insight to the problem. Let's assume there were no rules, I mean no pairings, no same nation rule etc. In that case, how many possible groups can be achieved? It's the number that you gave before: 5.23x10^34. However, do we need to check all of these? No, because there are no rules, we don't need any check, just draw the teams. So actually we check NONE of these possibilites. What about only rule is to put Man Utd and Man City to different groups, and let's assume Man City in pot 1 and Man Utd in pot 2 (they could be in the same category though, I mean one in group A and one in group B)? Assuming there are 12 groups, the number would be: (5.23x10^34 - 9.16x10^24). Again, do we need to check every possibility? Or do we need to check that ridiculous number (that we just calculated) of possibilities? No. because there is only 1 constraint, and solving it would be enough to know that there are possible outcomes (solving it would cost just one check in this case). So this drawing problem is a constraint solving problem. If you manage to solve the contraints in an acceptable time, you're fine.

My english is not very fluent, so I'm sorry if I messed it up :)

[inker]

@InNOutJimmy

It is not trivial to do checks like these (that 4-team case is not visible to the unaided eye & initially even caused some confusion as you can see from the thread I linked), so eventually, we have to resort to tree traversal anyway.

Please define what you mean by successful draw. Is it the complete draw made by the user or just a complete journey to one of the tree's leaves? It looks like you are talking about memoization. I've made attempts to use it in my experimental engine (pseudo-pure functions + memoization), but the benefits turned out to be slim; on the contrary, the memory usage skyrocketed & each calculation started to take up to a minute, so I put it on the back burner. I nevertheless use it in the World Cup draw simulator, as it's not computationally expensive due to the absence of pairings.

Having said that, if you know the exact solution to the problem & you feel like it's better than the current one (assuming you've looked through the code), please don't hesitate to make alterations & send a PR. This project doesn't have any benchmark tests yet, but I will write them, so that we can compare your solution against mine.

[InNOutJimmy]

@inker sorry, as I said I'm not very fluent in English, I had to use a different word. By successful draw, I don'!t mean a complete draw but just a single step in the whole draw. For example, I choose a ball and it's Bayern, and I put Bayern to a suitable group, this is a successful draw in my case, not the whole draw process.

I'm talking about some tables, but I'm not sure it's a memoization table. It's more like a rule table. Before the start of the draw, you check pairings, nation rule and special cases (UKR-RUS) and you get some rules. Rules like the one you've mentioned; 2 of the BAR, BAY, BEN, CHE should go to red, 2 of them should go to blue category. The rules consist of closed spot number (2 of the red category and 2 of the blue category is closed, but again, we don't know which groups are closed) and the teams involved in that case, for this rule, teams involved are BAR, BAY, BEN, CHE. You continue for other inferred rules and you get your rules table. And then you start to draw teams and groups.

I actually started to work around the problem before, but unfortunately, lymphoma got me so my free quality time becomes less quality so I didn't do anything until I saw your simulation :) I guess in 3-4 months I'll get rid of lymphoma (most of the cutaneous wounds are gone, only one wound left) and start fresh to the problem. My main goal was not to make a successfull draw but calculate the draw outcomes (which requires successful complete draws :) ). A good mathematician could do it but it's a messy problem so I wanted to use programming instead. For example I want to see the probability of getting Man Utd and Juventus in the same group etc. Because of the constraints, these probabilities deviates a lot so some teams have a huge tendency to be in the same group etc.

When I start to work again, I'll share my algorithm with you. I'm comfortable with Java only, so probably I'll write my own code in Java.

[InNOutJimmy]

@inker @mikezks

Hello guys, could you write a message that you are on air! :)

I did my work for the problem today and come up with a solution if you are still interested.

[inker]

@InNOutJimmy Hi! Please fork this project & send a PR with your changes. Or, if it's just a concept, create a standalone repo.