CS50-MCZ

Lab 6: World Cup

Você pode colaborar com um ou dois colegas de classe neste laboratório, embora seja esperado que todos os alunos em qualquer grupo contribuam igualmente para o trabalho.

Escreva um programa para executar simulações da Copa do Mundo FIFA.

$ python tournament.py 2018m.csv
Belgium: 20.9% chance of winning
Brazil: 20.3% chance of winning
Portugal: 14.5% chance of winning
Spain: 13.6% chance of winning
Switzerland: 10.5% chance of winning
Argentina: 6.5% chance of winning
England: 3.7% chance of winning
France: 3.3% chance of winning
Denmark: 2.2% chance of winning
Croatia: 2.0% chance of winning
Colombia: 1.8% chance of winning
Sweden: 0.5% chance of winning
Uruguay: 0.1% chance of winning
Mexico: 0.1% chance of winning

Contexto

Na Copa do Mundo de futebol, a fase de mata-mata consiste em 16 equipes. Em cada rodada, cada equipe joga contra outra equipe e as equipes perdedoras são eliminadas. Quando apenas duas equipes permanecem, o vencedor da partida final é o campeão.

No futebol, as equipes recebem classificações FIFA, que são valores numéricos que representam o nível de habilidade relativa de cada equipe. Classificações FIFA mais altas indicam resultados de jogos anteriores melhores e, dado as classificações FIFA de duas equipes, é possível estimar a probabilidade de que uma das equipes vença um jogo com base em suas classificações atuais. As classificações FIFA de duas Copas do Mundo anteriores estão disponíveis como os Classificações FIFA de Homens de maio de 2018 e as Classificações FIFA de Mulheres de março de 2019.

Usando essa informação, podemos simular o torneio inteiro repetidamente simulando rodadas até que reste apenas uma equipe. E se quisermos estimar o quão provável é que qualquer equipe dê a volta por cima no torneio, podemos simular o torneio muitas vezes (por exemplo, 1000 simulações) e contar quantas vezes cada equipe vence um torneio simulado. 1000 simulações podem parecer muitas, mas com o poder de processamento de hoje, podemos realizar essas simulações em questão de milissegundos. No final deste laboratório, vamos experimentar o quão vantajoso pode ser aumentar o número de simulações que executamos, dada a compensação de tempo de execução.

Sua tarefa neste laboratório é fazer exatamente isso usando Python!

Começando

Abra o VS Code.

Comece clicando dentro da janela do terminal e, em seguida, execute cd por si só. Você deve encontrar que seu "prompt" se assemelha ao abaixo.

Clique dentro dessa janela de terminal e execute

wget https://cdn.cs50.net/2022/fall/labs/6/world-cup.zip

digite Enter para baixar um arquivo ZIP chamado world-cup.zip em seu espaço de códigos. Tenha cuidado para não ignorar o espaço entre wget e a URL seguinte, ou qualquer outro caractere!

Agora execute

unzip world-cup.zip

para criar uma pasta chamada world-cup. Você não precisa mais do arquivo ZIP, então pode executar

rm world-cup.zip

e responda com "y" seguido de Enter no prompt para remover o arquivo ZIP que você baixou.

Agora digite

cd world-cup

seguido de Enter para entrar (ou seja, abrir) nesse diretório. Seu prompt agora deve se parecer com o abaixo.

world-cup/ $

Se tudo foi bem sucedido, você deve executar

ls

e você deve ver os seguintes arquivos:

answers.txt  2018m.csv  2019w.csv  tournament.py

Se você encontrar algum problema, siga os mesmos passos novamente e veja se consegue determinar onde errou!

Entendendo

Comece dando uma olhada no arquivo 2018m.csv. Este arquivo contém os 16 times na rodada de mata-mata da Copa do Mundo Masculina de 2018 e as classificações de cada time. Observe que o arquivo CSV possui duas colunas, uma chamada team (representando o nome do país do time) e outra chamada rating (representando a classificação do time).

A ordem em que os times estão listados determina quais times jogarão uns contra os outros em cada rodada (na primeira rodada, por exemplo, o Uruguai jogará contra Portugal e a França jogará contra a Argentina; na próxima rodada, o vencedor do jogo Uruguai-Portugal jogará contra o vencedor do jogo França-Argentina). Portanto, certifique-se de não editar a ordem em que os times aparecem neste arquivo!

Em Python, podemos representar cada time como um dicionário que contém dois valores: o nome do time e a classificação. O Uruguai, por exemplo, gostaríamos de representar em Python como {"team": "Uruguai", "rating": 976}.

Em seguida, dê uma olhada no arquivo 2019w.csv, que contém dados formatados da mesma maneira para a Copa do Mundo Feminina de 2019.

Agora, abra o arquivo tournament.py e veja que já escrevemos algum código para você. A variável N na parte superior representa quantas simulações da Copa do Mundo devem ser executadas: neste caso, 1000.

A função simulate_game aceita dois times como entradas (lembre-se de que cada time é um dicionário contendo o nome do time e a classificação do time) e simula um jogo entre eles. Se o primeiro time vencer, a função retorna True; caso contrário, a função retorna False.

A função simulate_round aceita uma lista de times (em uma variável chamada teams) como entrada e simula jogos entre cada par de times. A função retorna uma lista de todos os times que venceram a rodada.

Na função main, observe que primeiro garantimos que len(sys.argv) (o número de argumentos de linha de comando) seja 2. Usaremos argumentos de linha de comando para informar ao Python qual arquivo CSV de times usar para executar a simulação do torneio. Em seguida, definimos uma lista chamada teams (que eventualmente será uma lista de times) e um dicionário chamado counts (que associará nomes de times ao número de vezes que o time venceu um torneio simulado). Agora, ambos estão vazios, portanto, preenchê-los é com você!

Finalmente, no final de main, classificamos os times em ordem decrescente de quantas vezes venceram as simulações (de acordo com counts) e imprimimos a probabilidade estimada de que cada time vença a Copa do Mundo.

O preenchimento de teams e counts e a escrita da função simulate_tournament são deixados para você!

Detalhes de Implementação

Complete a implementação do arquivo tournament.py, de forma que simule uma série de torneios e exiba a probabilidade de cada time vencer.

Primeiramente, na função main, leia os dados dos times a partir do arquivo CSV e armazene-os na memória do programa, adicionando cada time à lista teams.

O arquivo a ser utilizado será fornecido como argumento de linha de comando. Você pode acessar o nome do arquivo através de sys.argv[1].
Lembre-se que é possível abrir um arquivo com o comando open(filename), onde filename é uma variável que armazena o nome do arquivo.
Uma vez que você tenha o arquivo f, é possível usar csv.DictReader(f) para obter um "leitor": um objeto em Python que pode ser iterado para ler o arquivo linha a linha, tratando cada linha como um dicionário.
Por padrão, todos os valores lidos do arquivo serão strings. Portanto, certifique-se de converter o rating de cada time para um valor inteiro (int). Você pode utilizar a função int do Python para isso.
Por fim, adicione o dicionário de cada time à lista teams. A chamada da função teams.append(x) adiciona o dicionário x à lista teams.
Lembre-se de que cada time deve ser representado por um dicionário contendo o nome do time (team) e o seu rating (rating).

Em seguida, implemente a função simulate_tournament. Esta função deve aceitar como entrada uma lista de equipes e simular repetidamente as rodadas até restar apenas uma equipe. A função deve retornar o nome dessa equipe.

Você pode chamar a função simulate_round, que simula uma única rodada, aceitando uma lista de equipes como entrada e retornando uma lista de todos os vencedores.
Lembre-se de que, se x é uma lista, você pode usar len(x) para determinar o comprimento da lista.
Você não deve assumir o número de equipes no torneio, mas pode assumir que será uma potência de 2.

Finalmente, dentro da função main, execute N simulações de torneio e mantenha o controle de quantas vezes cada equipe vence no dicionário counts.

Por exemplo, se o Uruguai venceu 2 torneios e Portugal venceu 3 torneios, então seu dicionário counts deve ser {"Uruguai": 2, "Portugal": 3}.
Você deve usar sua função simulate_tournament para simular cada torneio e determinar o vencedor.
Lembre-se de que, se counts é um dicionário, a sintaxe como counts[team_name] = x associará a chave armazenada em team_name com o valor armazenado em x.
Você pode usar a palavra-chave in em Python para verificar se um dicionário já possui uma chave específica. Por exemplo, if "Portugal" in counts: irá verificar se "Portugal" já possui um valor existente no dicionário counts.

Dicas

Ao ler o arquivo, você pode achar útil essa sintaxe, com filename como o nome do seu arquivo e file como uma variável.
```
  with open(filename) as file:
      reader = csv.DictReader(file)
```
In Python, to append to the end of a list, use the .append() function.

Testando

O seu programa deve se comportar de acordo com os exemplos abaixo. Como as simulações possuem aleatoriedade, é provável que a sua saída não corresponda perfeitamente aos exemplos abaixo.

$ python tournament.py 2018m.csv
Belgium: 20.9% chance of winning
Brazil: 20.3% chance of winning
Portugal: 14.5% chance of winning
Spain: 13.6% chance of winning
Switzerland: 10.5% chance of winning
Argentina: 6.5% chance of winning
England: 3.7% chance of winning
France: 3.3% chance of winning
Denmark: 2.2% chance of winning
Croatia: 2.0% chance of winning
Colombia: 1.8% chance of winning
Sweden: 0.5% chance of winning
Uruguay: 0.1% chance of winning
Mexico: 0.1% chance of winning

$ python tournament.py 2019w.csv
Germany: 17.1% chance of winning
United States: 14.8% chance of winning
England: 14.0% chance of winning
France: 9.2% chance of winning
Canada: 8.5% chance of winning
Japan: 7.1% chance of winning
Australia: 6.8% chance of winning
Netherlands: 5.4% chance of winning
Sweden: 3.9% chance of winning
Italy: 3.0% chance of winning
Norway: 2.9% chance of winning
Brazil: 2.9% chance of winning
Spain: 2.2% chance of winning
China PR: 2.1% chance of winning
Nigeria: 0.1% chance of winning

Você pode estar se perguntando o que realmente aconteceu nas Copas do Mundo de 2018 e 2019! No torneio masculino, a França ganhou, derrotando a Croácia na final. A Bélgica derrotou a Inglaterra pela terceira posição. No torneio feminino, os Estados Unidos ganharam, derrotando a Holanda na final. A Inglaterra derrotou a Suécia pela terceira posição.

Número de Simulações

Depois de ter certeza de que seu código está correto, vamos brincar com o valor de N, a constante no topo do nosso arquivo, para ajustar o número de vezes que simulamos o torneio. Mais simulações do torneio nos darão previsões mais precisas (por quê?), ao custo de tempo.

Podemos medir o tempo dos programas, adicionando "time" antes da execução deles na linha de comando. Por exemplo, com o valor de N ajustado para 1000 (o valor padrão), execute

time python tournament.py 2018m.csv

time python tournament.py 2019w.csv

que deve produzir algo como

real    0m0.037s
user    0m0.028s
sys     0m0.008s

embora seus próprios tempos possam variar.

Preste atenção à métrica real, que é o tempo total que levou para tournament.py ser executado. E observe que você é dado o tempo em minutos e segundos, com precisão até milésimos de segundo.

No arquivo answers.txt, mantenha o registro de quanto tempo leva para tournament.py simular...

10 (dez) torneios
100 (cem) torneios
1000 (mil) torneios
10000 (dez mil) torneios
100000 (cem mil) torneios
1000000 (um milhão) torneios

Cada vez que você ajustar N, registre o tempo real no TODO apropriado em answers.txt usando o mesmo formato 0m0.000s. Após cronometrar cada cenário, responda às duas perguntas de acompanhamento, sobrescrevendo o respectivo TODO:

Quais previsões, se houver, se mostraram incorretas ao aumentar o número de simulações?
Suponha que você seja cobrado por cada segundo de tempo de computação que seu programa usa. Após quantas simulações você consideraria as previsões "suficientemente boas"?

Veja um arquivo answers.txt formatado corretamente

Times:

10 simulations: 0m0.028s
100 simulations: 0m0.030s
1000 simulations: 0m0.041s
10000 simulations: 0m0.139s
100000 simulations: 0m1.031s
1000000 simulations: 0m11.961s

Questions:

Which predictions, if any, proved incorrect as you increased the number of simulations?:

With a small number of simulations...

Suppose you're charged a fee for each second of compute time your program uses.
After how many simulations would you call the predictions "good enough"?:

It seems like the predictions stabilized after about...

Como Testar Seu Código

Execute o código abaixo para avaliar a correção do seu código usando check50. Mas certifique-se de compilar e testá-lo por si mesmo também!

check50 cs50/labs/2023/x/worldcup

Execute o código abaixo para avaliar o estilo do seu código usando style50.

style50 tournament.py

Como enviar

No seu terminal, execute o seguinte para enviar seu trabalho.

submit50 cs50/labs/2023/x/worldcup