Pular para conteúdo

Projetos

Simulador de Copa

GitHub DaviAMSilva/PI-Copa

Foi o meu primeiro grande projeto em grupo no primeiro semestre da minha graduação na Doctum. O objetivo geral do projeto foi:

Desenvolver um programa capaz de simular a realização de um torneio (copa). Pode-se utilizar o modelo atual utilizado pela FIFA para organizar a copa do mundo de futebol.

O contexto era de um organizador de eventos que desejasse inserir os resultados de um tornamento, conforme ele ia acontecendo, de tal maneira que o sistema calculasse e gerasse automaticamente o resultado de cada jogo, fase e do campeonato inteiro.

A minha versão suportava a quantidade de gols e cartões amarelos e vermelhos recebidos por cada time e para cada jogo. Também conseguia calcular todas as fases do torneio, desde a fase de grupos até a final, conforme as regras básicas da Copa do Mundo da FIFA. O usuário tinha também a opção de aleatorizar os resultados dos jogos, principalmente útil para testar o programa.

O projeto foi desenvolvido em C e compilado usando a ferramenta make para facilitar a compilação e execução do programa. Essa experiência foi uma das razões que motivaram a minha ideia para o projeto integrador 2, que foi o Arcade Mania.

Esse programa foi, principalmente na segunda fase, construído utilizando-se o sistema operacional Microsoft Windows 10 e a biblioteca windows.h para manipular o console do Windows. Por causa disso eu nem consigo mais testar o programa no meu sistema Linux atual. Mesmo ferramentas como o wine não conseguem exibir corretamente o console do Windows, apesar de conseguirem rodar o programa e gerar o resultado correto.

Um resultado típico do programa, ao selecionar todas as opções aleatórias, é o seguinte:

Saída do Terminal
            ___________
       .---'::'        `---.
      (::::::'              )
    __|`-----._______.-----'|__
   /  |              :::::::|  \
  |   |               ::::::|   |
  |   |                :::::|   |
   \  |               ::::::|  /
    \ |    Copa do Mundo   :| /
     \|       da FIFA   ::::|/
      |               ::::::|
      |              .::::::|
      \             :::::::|
       \            ::::::/
        `.        .:::::::'
          `-._  .::::::-'
              |  """|"
              |  :::|
              |   ::|
             /     ::\
        __.-'      :::`-.__
       (_           ::::::_)
         `"""---------"""'

      GANHADOR:
      Brasil
Arquivo de Resultado
O campeão da Copa do Mundo da FIFA foi o time:
> Brasil <

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━┓
┃            COPA DO MUNDO DA FIFA             ┃             Gols            ┃        Cartões       ┃
┣━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┯━━━━━━━━╋━━━━━━━━━━┯━━━━━━━━━━┯━━━━━━━╋━━━━━━━━━━┯━━━━━━━━━━━┫
┃ Nº ┃          Nome do Time          │ Pontos ┃ Marcados │ Sofridos │ Saldo ┃ Amarelos │ Vermelhos ┃
┣━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┿━━━━━━━━╋━━━━━━━━━━┿━━━━━━━━━━┿━━━━━━━╋━━━━━━━━━━┿━━━━━━━━━━━┫
┃ 01 ┃ Brasil                         │ 18     ┃ 34       │ 21       │ +13   ┃ 37       │ 2         ┃
┃ 02 ┃ Croácia                        │ 15     ┃ 23       │ 25       │ -2    ┃ 35       │ 4         ┃
┃ 03 ┃ Japão                          │ 15     ┃ 35       │ 29       │ +6    ┃ 41       │ 2         ┃
┃ 04 ┃ Egito                          │ 13     ┃ 29       │ 17       │ +12   ┃ 37       │ 4         ┃
┃ 05 ┃ Marrocos                       │ 9      ┃ 20       │ 12       │ +8    ┃ 16       │ 2         ┃
┃ 06 ┃ Senegal                        │ 9      ┃ 23       │ 18       │ +5    ┃ 28       │ 2         ┃
┃ 07 ┃ Alemanha                       │ 9      ┃ 20       │ 19       │ +1    ┃ 26       │ 4         ┃
┃ 08 ┃ Islândia                       │ 7      ┃ 17       │ 15       │ +2    ┃ 25       │ 3         ┃
┃ 09 ┃ Rússia                         │ 7      ┃ 11       │ 6        │ +5    ┃ 20       │ 3         ┃
┃ 10 ┃ Austrália                      │ 6      ┃ 18       │ 14       │ +4    ┃ 18       │ 1         ┃
┃ 11 ┃ Costa Rica                     │ 6      ┃ 10       │ 8        │ +2    ┃ 16       │ 2         ┃
┃ 12 ┃ Portugal                       │ 6      ┃ 14       │ 14       │ +0    ┃ 19       │ 2         ┃
┃ 13 ┃ Sérvia                         │ 6      ┃ 7        │ 8        │ -1    ┃ 16       │ 3         ┃
┃ 14 ┃ Bélgica                        │ 6      ┃ 14       │ 20       │ -6    ┃ 21       │ 1         ┃
┃ 15 ┃ Panamá                         │ 6      ┃ 21       │ 28       │ -7    ┃ 23       │ 4         ┃
┃ 16 ┃ Dinamarca                      │ 6      ┃ 8        │ 16       │ -8    ┃ 31       │ 3         ┃
┃ 17 ┃ México                         │ 6      ┃ 14       │ 14       │ +0    ┃ 21       │ 3         ┃
┃ 18 ┃ Nigéria                        │ 4      ┃ 11       │ 10       │ +1    ┃ 15       │ 1         ┃
┃ 19 ┃ Irã                            │ 4      ┃ 10       │ 14       │ -4    ┃ 12       │ 0         ┃
┃ 20 ┃ Colômbia                       │ 3      ┃ 7        │ 2        │ +5    ┃ 5        │ 0         ┃
┃ 21 ┃ Inglaterra                     │ 3      ┃ 6        │ 3        │ +3    ┃ 3        │ 0         ┃
┃ 22 ┃ Peru                           │ 3      ┃ 12       │ 10       │ +2    ┃ 12       │ 1         ┃
┃ 23 ┃ Tunísia                        │ 3      ┃ 19       │ 19       │ +0    ┃ 20       │ 3         ┃
┃ 24 ┃ França                         │ 3      ┃ 11       │ 11       │ +0    ┃ 8        │ 2         ┃
┃ 25 ┃ Suécia                         │ 3      ┃ 8        │ 9        │ -1    ┃ 9        │ 1         ┃
┃ 26 ┃ Polônia                        │ 3      ┃ 14       │ 17       │ -3    ┃ 21       │ 2         ┃
┃ 27 ┃ Coreia do Sul                  │ 3      ┃ 13       │ 17       │ -4    ┃ 25       │ 3         ┃
┃ 28 ┃ Arábia Saudita                 │ 3      ┃ 2        │ 6        │ -4    ┃ 19       │ 2         ┃
┃ 29 ┃ Argentina                      │ 2      ┃ 9        │ 10       │ -1    ┃ 14       │ 3         ┃
┃ 30 ┃ Espanha                        │ 1      ┃ 6        │ 12       │ -6    ┃ 14       │ 3         ┃
┃ 31 ┃ Suíça                          │ 0      ┃ 6        │ 15       │ -9    ┃ 18       │ 2         ┃
┃ 32 ┃ Uruguai                        │ 0      ┃ 0        │ 13       │ -13   ┃ 14       │ 0         ┃
┗━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━┻━━━━━━━━━━┷━━━━━━━━━━┷━━━━━━━┻━━━━━━━━━━┷━━━━━━━━━━━┛
  • em Projetos
  • 1 min de leitura

TileableNoise.js

GitHub DaviAMSilva/TileableNoise.js

TileableNoise.js é uma simples biblioteca na forma de uma classe que ajuda a criar imagens de ruídos que se conectam perfeitamente.

Essa biblioteca usa a ideia de pegar o resultado de uma função de ruído, andando em volta de um círculo, para que o valor inicial seja igual ao valor final, permitindo ruído conectável em 1D e 2D.

Usando dois círculos em um espaço de ruído 4D é possível criar ruído repetível em um ambiente 2D.

Eu tirei minha inspiração de um vídeo do Daniel Shiffman's: Coding Challenge #136.1: Polar Perlin Noise Loops, do canal The Coding Train.

Imagem feita com a biblioteca. As linhas vermelhas marcam o local da repetição. Imagem feita com a biblioteca. As linhas vermelhas marcam o local da repetição.

  • em Projetos
  • 1 min de leitura

Pontos Mais Próximos

GitHub DaviAMSilva/Pontos-mais-proximos Website Pontos Mais Próximos

Esse foi um algoritmo bem simples que eu desenvolvi cujo o objetivo é encontrar os dois pontos mais próximos dentro de uma coleção qualquer utilizando o algoritmo de divisão e conquista.

Tradicionalmente o algoritmo de par de pontos mais próximos tem tempo de execução representado por \(O\left(n^2\right)\), mas utilizando a estratégia acima é possível reduzir o tempo necessário para \(O\left(n \log n\right)\), sendo muito mais eficiente.

Eu desenvolvi esse algoritmo enquanto estava cursando o curso PENSAMENTO COMPUTACIONAL, PROGRAMAÇÃO E APLICAÇÕES EM MATEMÁTICA ofertada pelo ProMO 2019 por ter sido premiado por uma medalha de prata na OBMEP 2018.

  • em Projetos
  • 1 min de leitura

Mosaico de Fotos

GitHub DaviAMSilva/Mosaico_de_Fotos

Mosaico de Fotos é um programa escrito em Python para criar mosaicos de fotos a partir de uma imagem principal e várias imagens fontes.

O caso de uso original foi pegar várias imagens de família e juntá-las para formar uma única imagem composta especial. Apesar disso, o fato de o programa trabalhar exclusivamente com peças quadradas o torna particularmente interessante para redesenhar imagens utilizando blocos do jogo Minecraft.

Exemplo de uso utilizando blocos de Minecraft na pintura Abaporu da pintora Tarsila do Amaral:

Pintura Abaporu original comparada com a versão criada usando blocos de Minecraft

  • em Projetos
  • 3 min de leitura

Tabuleiro Bacana

Website Tabuleiro Bacana

Quando eu participei da prova do terceiro nível da segunda fase da OBMEP 2019 a questão 5 foi uma que me deixou muito intrigado se a solução que eu desenvolvi durante o teste estava correta. Por causa disso logo após terminar a prova eu fiquei curioso e decidi escrever um algoritmo capaz de resolver o problema.

Essa edição específica da olimpíada foi a minha última aonde eu conquistei minha terceira medalha de ouro.

O problema em questão envolve tabuleiros bacanas, descritos como:

Um tabuleiro preenchido com as letras A, B, C e D é bacana se essas quatro letras aparecem em qualquer quadriculado 2×2 do tabuleiro. Por exemplo, dos tabuleiros abaixo, o da esquerda é bacana e o da direita não é bacana.

\[ \begin{array}{|c|c|c|} \hline \text{C}&\text{D}&\text{C}\\ \hline \text{A}&\text{B}&\text{A}\\ \hline \text{C}&\text{D}&\text{C}\\ \hline \end{array} \\ \space\space\space\space\space \begin{array}{|c|c|c|} \hline \text{C}&\text{B}&\text{C}\\ \hline \text{C}&\text{D}&\text{A}\\ \hline \text{A}&\text{C}&\text{B}\\ \hline \end{array} \]
Prova e Solução

Especificamente a letra c) da questão 5 pergunta Quantos tabuleiros bacanas 8×8 existem?. Eu não irei entrar em detalhes sobre a solução matemática, visto que a solução oficial acima é similar à minha.

O algoritmo que eu desenvolvi para resolver esse problema envolve o uso dos métodos de força bruta e recursividade. Basicamente cada quadrado, da esquerda para a direita, de cima para baixo, é visitado uma vez para cada uma das letras e calcula recursivamente quantos casos possíveis existem para o próximo quadrado para cada letra, desde ela seja válida. No final todos os casos possíveis retornam 1 e são somados para gerar o resultado.

Como se pode imaginar esse algoritmo não é eficiente, mas esse não foi um objetivo meu de qualquer jeito. Percebe-se que o algoritmo precisa percorrer tantos níveis de recursão quanto quadrados no tabuleiro e que para cada quadrado há 4 casos possíveis e para cada caso é necessário criar uma cópia do tabuleiro.

Por causa disso eu acredito que a complexidade temporal desse algoritmo é \(O\left(4^{n^2}\right)\), enquanto a complexidade espacial é \(O\left(n^2 \times 4^{n^2}\right)\). É claro que isso se aplicaria apenas para o pior caso possível, sendo que na prática a maioria das possibilidades se tornarão inválidas e a recursão interrompida antes de completar todo o tabuleiro, mesmo assim isso demonstra a ineficiência desse algoritmo.

Após terminar esse projeto eu pude verificar que minha solução estava de acordo com o resultado gerado pelo meu algoritmo e depois da liberação das repostas respostas oficiais eu tive a confirmação de que eu respondi corretamente todas as letras dessa questão.