Sorteio dos 1/4, 1/2 e Final da Liga dos Campeões (Inter - Milan/Napoli)

[Jb3011]

Agora todo o mundo programa em Python?

É a melhor e mais versátil nos dias que correm, com big data, e AI

[EagleVision]

Depois de lançado o desafio pelo Hungry Alien, deixo aqui também as probabilidades para a solução exacta, juntamente com o código (talvez não tão elegante, mas corre em menos de um segundo ). Espero não me ter escapado nada!

import numpy as np
import pandas as pd
pd.options.display.float_format = "{:,.2f}".format

seeded = {0: "Bayern", 1: "Benfica", 2: "Chelsea", 3: "FCP", 4: "ManCity", 5: "Napoli", 6: "RealMadrid", 7: "Tottenham"}
unseeded = {0: "Brugge", 1: "Dortmund", 2: "Frankfurt", 3: "Inter", 4: "Leipzig", 5: "Liverpool", 6: "Milan", 7: "Paris"}

l = [[0,5,6,7], # Bayern
     [0,1,2,3,4,5,6], # Benfica
     [0,1,2,3,4,7], # Chelsea
     [1,2,3,4,5,6,7], # FCP
     [0,2,3,4,6,7], # ManCity
     [0,1,2,4,7], # Napoli
     [0,1,2,3,5,6,7], # RealMadrid
     [0,1,3,4,6,7]] # Tottenham

total = 0
keys = np.empty((8,0), dtype=np.int8)
for k0 in l[0]:
    for k1 in l[1]:
        for k2 in l[2]:
            for k3 in l[3]:
                for k4 in l[4]:
                    for k5 in l[5]:
                        for k6 in l[6]:
                            for k7 in l[7]:
                                key = [k0, k1, k2, k3, k4, k5, k6, k7]
                                if(len(key) == len(set(key))):
                                    # Only keys where all elements are different
                                    total += 1
                                    keys = np.append(keys, [[k0],[k1],[k2],[k3],[k4],[k5],[k6],[k7]], axis=1)
print(total)

probs = np.zeros([8,8], dtype=np.float32)
for i in range(8):
    team_keys = np.unique(keys[:][i])
    for j in team_keys:
        # Count the number of occurences of each key and convert to percentage
        probs[i][j] = np.sum(keys[:][i] == j) / total * 100

df = pd.DataFrame(probs)
display(df.rename(index=seeded, columns=unseeded))

** NOTA (EDIT) **: Jogo mais provável no sorteio será mesmo um Bayern x Liverpool (P~40%), enquanto que os possíveis adversários do Benfica são, muito grosseiramente falando, equiprováveis (P=[11,20]%).

Interessante. Uma boa forma de obter rapidamente uma boa aproximação das probabilidades, mas se reparares não são iguais às que alguem partilhou atrás,

https://github.com/eminga/cldraw

Esses valores são muito mais próximos dos meus que os teus. Por exemplo, para um Liverpool - Bayern tu tens 39,86%, eu tenho 36,95% e eles têm 37,12%.

E o código deles tem uma performance que depende muito das especificidades do sorteio, tanto pode demorar 1 décimo de segundo com pode demorar quase hora e meia, e usar mais de 5 GB de RAM. O meu método usa apenas cerca de 115 MB de RAM, e penso que não variará muito com as especificidadades de cada sorteio.

The memoization technique described above works better the more similar the teams are (e.g. the algorithm is faster if there are 2 runners-up and 2 winners from country A and 2 runners-up and 2 winners from country B, compared to 1 runner-up and 3 winners from country A and 2 runners-up and 1 winner from country B).

Tests with a Pentium G4600 using Node.js 10.13.0 yield computation times of 110ms for the CL draw 2017/18 and 2:02 minutes (310MB RAM usage) for the EL draw 2017/18. However, there are cases where the computation is much more expensive, like EL season 2014/15 where it takes 88 minutes and 5.3GB of RAM.

To bypass the long computation times, precomputed probabilities can be used in EL mode. With a gzipped filesize of 5MB all possible combinations of the first 4 or 6 draw steps can be stored. The probabilities for the remaining 26/28 teams are then computed locally which usually takes a couple of seconds / up to 1 minute.

Repara também que o meu código não está optimizado, foi feito entre ontem e hoje, e a minha única preocupação era que funcionasse. Pode talvez ser modificado para usar todos os cores do processador em vez de apenas 1.

A solução que apresentei é supostamente a solução exacta. A tua abordagem por Monte Carlo será sempre uma aproximação. No entanto, amanhã com mais calma vou dar uma olhadela à teoria por de trás dessa approach que enviaste

[sbremoved_42475]

Agora todo o mundo programa em Python?

É a melhor e mais versátil nos dias que correm, com big data, e AI

O que é ser melhor? A syntax, a vasta comunidade, e a compatibilidade? Se formos puramente pela performance é para o penoso...

[EagleVision]

Agora todo o mundo programa em Python?

É a melhor e mais versátil nos dias que correm, com big data, e AI

O que é ser melhor? A syntax, a vasta comunidade, e a compatibilidade? Se formos puramente pela performance é para o penoso...

Boa malha esse paper tuga! 

[Crente]

Agora todo o mundo programa em Python?

Hello, World!

[GTtdi_SLB]

pode ser um adversário de milão. obrigado.

[sbremoved_42475]

Agora todo o mundo programa em Python?

É a melhor e mais versátil nos dias que correm, com big data, e AI

O que é ser melhor? A syntax, a vasta comunidade, e a compatibilidade? Se formos puramente pela performance é para o penoso...

Boa malha esse paper tuga! 

Nâo conheço ninguém, mas estimo em saber que a maioria é da UMINHO 

[Jb3011]

Agora todo o mundo programa em Python?

É a melhor e mais versátil nos dias que correm, com big data, e AI

O que é ser melhor? A syntax, a vasta comunidade, e a compatibilidade? Se formos puramente pela performance é para o penoso...

A nível de versatilidade, porque essa merda bomba até num Tamagotchi. E também a quantidade absurda de tools e libraries que existem disponíveis.
Eu trabalho com C# e é de ir às lágrimas

[Hungry Alien]

Depois de lançado o desafio pelo Hungry Alien, deixo aqui também as probabilidades para a solução exacta, juntamente com o código (talvez não tão elegante, mas corre em menos de um segundo ). Espero não me ter escapado nada!

import numpy as np
import pandas as pd
pd.options.display.float_format = "{:,.2f}".format

seeded = {0: "Bayern", 1: "Benfica", 2: "Chelsea", 3: "FCP", 4: "ManCity", 5: "Napoli", 6: "RealMadrid", 7: "Tottenham"}
unseeded = {0: "Brugge", 1: "Dortmund", 2: "Frankfurt", 3: "Inter", 4: "Leipzig", 5: "Liverpool", 6: "Milan", 7: "Paris"}

l = [[0,5,6,7], # Bayern
     [0,1,2,3,4,5,6], # Benfica
     [0,1,2,3,4,7], # Chelsea
     [1,2,3,4,5,6,7], # FCP
     [0,2,3,4,6,7], # ManCity
     [0,1,2,4,7], # Napoli
     [0,1,2,3,5,6,7], # RealMadrid
     [0,1,3,4,6,7]] # Tottenham

total = 0
keys = np.empty((8,0), dtype=np.int8)
for k0 in l[0]:
    for k1 in l[1]:
        for k2 in l[2]:
            for k3 in l[3]:
                for k4 in l[4]:
                    for k5 in l[5]:
                        for k6 in l[6]:
                            for k7 in l[7]:
                                key = [k0, k1, k2, k3, k4, k5, k6, k7]
                                if(len(key) == len(set(key))):
                                    # Only keys where all elements are different
                                    total += 1
                                    keys = np.append(keys, [[k0],[k1],[k2],[k3],[k4],[k5],[k6],[k7]], axis=1)
print(total)

probs = np.zeros([8,8], dtype=np.float32)
for i in range(8):
    team_keys = np.unique(keys[:][i])
    for j in team_keys:
        # Count the number of occurences of each key and convert to percentage
        probs[i][j] = np.sum(keys[:][i] == j) / total * 100

df = pd.DataFrame(probs)
display(df.rename(index=seeded, columns=unseeded))

** NOTA (EDIT) **: Jogo mais provável no sorteio será mesmo um Bayern x Liverpool (P~40%), enquanto que os possíveis adversários do Benfica são, muito grosseiramente falando, equiprováveis (P=[11,20]%).

Interessante. Uma boa forma de obter rapidamente uma boa aproximação das probabilidades, mas se reparares não são iguais às que alguem partilhou atrás,

https://github.com/eminga/cldraw

Esses valores são muito mais próximos dos meus que os teus. Por exemplo, para um Liverpool - Bayern tu tens 39,86%, eu tenho 36,95% e eles têm 37,12%.

E o código deles tem uma performance que depende muito das especificidades do sorteio, tanto pode demorar 1 décimo de segundo com pode demorar quase hora e meia, e usar mais de 5 GB de RAM. O meu método usa apenas cerca de 115 MB de RAM, e penso que não variará muito com as especificidadades de cada sorteio.

The memoization technique described above works better the more similar the teams are (e.g. the algorithm is faster if there are 2 runners-up and 2 winners from country A and 2 runners-up and 2 winners from country B, compared to 1 runner-up and 3 winners from country A and 2 runners-up and 1 winner from country B).

Tests with a Pentium G4600 using Node.js 10.13.0 yield computation times of 110ms for the CL draw 2017/18 and 2:02 minutes (310MB RAM usage) for the EL draw 2017/18. However, there are cases where the computation is much more expensive, like EL season 2014/15 where it takes 88 minutes and 5.3GB of RAM.

To bypass the long computation times, precomputed probabilities can be used in EL mode. With a gzipped filesize of 5MB all possible combinations of the first 4 or 6 draw steps can be stored. The probabilities for the remaining 26/28 teams are then computed locally which usually takes a couple of seconds / up to 1 minute.

Repara também que o meu código não está optimizado, foi feito entre ontem e hoje, e a minha única preocupação era que funcionasse. Pode talvez ser modificado para usar todos os cores do processador em vez de apenas 1.

A solução que apresentei é supostamente a solução exacta. A tua abordagem por Monte Carlo será sempre uma aproximação. No entanto, amanhã com mais calma vou dar uma olhadela à teoria por de trás dessa approach que enviaste

A abordagem Monte Carlo é uma aproximação, mas com 5 milhões de simulaçóes fica muito próxima mesmo do real. A diferença para os resultados que obtive com 1 milhão de simulaçóes não é grande, o que indica convergência. E o outro tipo, por um método diferente, chegou a valores que chegam nalguns jogos a serem idênticos aos meus arredondados às centésimas, e noutros casos a diferença é de 1 ou 3 centásimas. Os teus valores é que são mais dispares.

Continuo a achar que a tua abordagem não leva em conta a natureza sequencial do sorteio. Algumas ocorrências serão um pouco mais prováveis do que outras porque poderão ser atingidas por um maior número de caminhos. Se reparares, no link do github ele também leva em conta a sequencialidade do sorteio, e usa teoria dos grafos. Como a formação de base é em economia, uma área onde se dá pouca atenção à matemática discreta, eu não tenho conhecimentos para entender plenamente o que ele faz (e também não sei java script).

[Dr. Captainous]

Mas por que raios é que este sorteio não é na 6a Feira como o habitual?!

Não vou poder ver!

Bolas quentes, bolas frias. E evitar a cagada em dois actos da época passada.

Campeões Europeus!!!

[Dr. Captainous]

Agora todo o mundo programa em Python?

É a melhor e mais versátil nos dias que correm, com big data, e AI

O que é ser melhor? A syntax, a vasta comunidade, e a compatibilidade? Se formos puramente pela performance é para o penoso...

Então e Programação de Java?

[Sá das Violas30]

Porque não assembly?

[futeboldelite]

os primeiros do grupo jogam o segundo jogo em casa

Muito bom.

É as equipas portuguesas ficarem em primeiro outra vez e estas regrinhas mudam todas

Por acaso há vantagem em ter o segundo jogo em casa

Claro que há. Por isso disse o que disse..

É uma dupla vantagem: jogam com os apurados teoricamente mais fracos e aindam jogam a partida decisiva em casa

[Vascolptt]

Como estava com algum tempo livre, pus-me a fazer um script em python para simular o serteio dos oitavos de final da Champions, levando em atenção todas as condicionantes. Depois usei esse script para fazer 5 milhões de simulações.

Esta tabela indica a frequência absoluta com que cada confronto surgiu na simulação:



e esta tabela mostra a mesma infomação mas em percentagem:



O resultado mais frequente, mas com apenas 1615 ocorrências em 5 milhões, foi:

Bayern - Brugges
Benfica - Leipzig
Chelsea - Inter
FCP - Liverpool
Man City - Frankfurt
Napoli - Paris SG
Real Madrid - Dortmund
Tottenham - Milan

Em spoiler estão histogramas com a as frequências relativas para cada uma das 16 equipas.

Spoiler

[fechar]

Quero ir a Milão

[Puches]

Vocês são doidos.