Pular para conteúdo

2019

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.

CDCABACDC     CBCCDAACB
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(4n2), enquanto a complexidade espacial é O(n2×4n2). É 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.

10 PRINT MAZE

GitHub DaviAMSilva/10-print-maze OpenProcessing 10 PRINT MAZE Website 10 PRINT MAZE


O comando abreviado como 10 PRINT, ou a sua versão completa 10 PRINT CHR$(205.5+RND(1)); : GOTO 10, é originado no Commodore 64, escrito na linguagem BASIC. Ao executar esse simples comando nessa máquina o resultado é algo similar ao um labirinto, mas com resultado visual complexo e cheio de padrões interessantes de se observar.

Eu primeiro descobri esse padrão no vídeo Coding Challenge #76: 10PRINT in p5.js quase ao mesmo tempo que eu assistir o vídeo sobre o algoritmo de busca A* de nome A* Pathfinding Algorithm (Coding Challenge 51 - Part 1). Ambos foram postados pelo canal do YouTube educacional The Coding Train, que eu gosto bastante pelos seus vídeos que ensinam diversos tópicos sobre programação utilizando ferramentas gráficas, como o p5.js.

Eu fiquei fascinado como um comando tão simples tão curto um resultado tão interessante e, além disso, eu até hoje considero o A* como um dos meus algoritmos favoritos, devido ao fato de ser um algoritmo com uma lógica fácil de entender e cuja a utilidade prática é enorme.

O único problema é o fato de que devido à geometria do padrão, para cada entrada no labirinto existe uma única saída o que não é muito interessante. Por causa disso na minha versão apenas uma porcentagem dos símbolos é realmente criada e serve como obstáculo para o caminho.

Exemplo de uma solução do 10 PRINT MAZE

Na visualização acima é possível ver como os elementos são desenhados na tela, em que os pontos vermelhos são os caminhos já calculados (fechados) e os verdes são os possíveis caminhos a se analisar (abertos). Os dois pontos azuis são o ponto de início e fim, e a linha rosa representa o caminho atual sendo processado ou, após o término do algoritmo, o melhor caminho encontrado.

Eu gosto bastante da maneira como eu implementei o sistema de gride diagonal e o sistema de símbolos, pelo fato de que não é um gride diagonal real, mas sim um gride ortogonal em que metade dos pontos estão omissos. Já o sistema de símbolos é baseado na definição de pontos de intersecção dentro de um grid 5x5 e uma função que desenha tal forma. Isso permite que novas forma sejam adicionadas facilmente.

Em retrospectiva eu deveria ter utilizado classes para essa utilidade específica, permitindo uma possível herança de propriedades, mas na época eu ainda estava pouco familiarizado com os conceitos próprios de POO.

Lookups.js
var allSymbols = [];

var blank = [];
blank.draw = function () { }
allSymbols.push(blank);


var invSlash = [
    { x: 0, y: 0 },
    { x: 1, y: 1 },
    { x: 2, y: 2 },
    { x: 3, y: 3 },
    { x: 4, y: 4 }
];
invSlash.draw = function (x, y, size) {
    line(x, y, x + size, y + size);
}
allSymbols.push(invSlash);


var slash = [
    { x: 0, y: 4 },
    { x: 1, y: 3 },
    { x: 2, y: 2 },
    { x: 3, y: 1 },
    { x: 4, y: 0 },
];
slash.draw = function (x, y, size) {
    line(x, y + size, x + size, y);
}
allSymbols.push(slash);

DaviAMSilva.github.io

Static Badge Static Badge


É o primeiro site pessoal que eu criei e fui atualizando com o tempo. Ele é muito simples e atualmente apenas contém alguns links e demonstrações para os meus principais projetos. Embora seja obsoleto agora eu ainda me sinto nostalgia por ele. Provavelmente eu irei apenas atualiza-lo para redirecionar automaticamente para o novo site.

Game of Life

GitHub DaviAMSilva/Game-of-Life Website Game of Life


Esse foi um dos primeiros grandes projetos que eu criei quando eu comecei a aprender programação.

The Game of Life, ou o Jogo da Vida, foi criado pelo matemático John Conway em 1970, sendo um tipo de autômato celular.

Na época eu ainda tinha pouco conhecimento em como usar html e css, por isso vários dos projetos que eu criava usavam sketches do p5.js em páginas de tela cheia.

Por acaso a versão original separava os tipos de visualizações diferentes em arquivos .js diferentes e não permitir realizar a troca de maneira dinâmica. Apenas recentemente eu implantei essa opção.

Minha intenção foi expandir a versão simples do jogo da vida que eu tinha criado na Khan Academy (Conway's game of life v2.0) para incluir um nível a mais de complexidade. Eu imaginei o que aconteceria se as células contivessem informações sobre cores e como elas poderiam interagir entre si.

Eu acabei criando quatro versões do jogo da vida nesse projeto:

  • ORIGINAL

    A versão básica do jogo. Para todas os tipos o movimento do mouse torna as células vivas e o clique do mais limpa todo o tabuleiro. Além disso células nas bordas do tabuleiro são vizinhas das células na borda oposta.

  • RAINBOW

    Funcionalmente idêntico à versão ORIGINAL, mas utilizando as cores do espectro HSL.

  • RAINBOW-PHASING

    Funcionalmente idêntico à versão ORIGINAL, mas a tonalidade da células muda de acordo com o espectro HSL e a intensidade de acordo com a quantidade de vizinhos que cada célula possuí.

  • COLOR-BLEND

    Esse é o motivo principal que eu decidi criar todo esse projeto. Nessa versão quando uma nova célula nasce a sua cor é determinada pela média aritmética das cores das três células vizinhas que a criou. Além disso células mortas mantêm a cor que tinham ao morrer.

    O resultado foi aquilo que eu esperava, em que após algum tempo todo o tabuleiro tende a ser dominado por uma única cor, sendo ela diferente para cada instância da simulação, devido à aleatorização das células no início.