O Advent of Code é um desafio de programação que acontece entre os dias 1 e 25 de dezembro de cada ano. O de 2024, é a décima edição do evento que é independente de linguagem de programação, você pode usar as ferramentas que você quiser.

Todo dia, a partir do dia primeiro de dezembro, um novo problema é disponibilizado. Embora o nome seja Advent of Code (Advento é um evento cristão que antecede o Natal), os problemas não envolvem necessariamente religião, mas são problemas divertidos com os duendes de Papai Noel.

Esta tradição em conheci na Bélgica, pois as crianças ganhavam calendários com um chocolate para cada dia do mês de dezembro, até o Natal. E eles pequenos ficavam olhando o enorme tablete com vários chocolates, mas só podiam comer um por dia :-D. Uma foto para se ter uma ideia:

Foto de Nick Fewings on Unsplash

Os problemas tem vários níveis de dificuldade, eu vou classificá-los em três níveis:

Nível Fácil: precisa apenas de Python Básico para ser resolvido. Lógica de programação, conjuntos, listas, dicionários, ordenação, etc. Se você leu todos os capítulos do meu livro, deve conseguir resolver os problemas de nível fácil.

Nível Médio: já precisa de mais conhecimentos sobre estruturas de dados, algoritmos de busca e mesmo grafos.

Nível Difícil: aqui já começam a aparecer problemas mais complexos, que podem ser resolvidos com programação dinâmica, backtracking, etc. Costumam aparecer lá pelo dia 9 ou 10. Este problemas exigem heurísticas ou uma boa escolha dos algoritmos para serem completados em um tempo razoável (menor de 10 minutos). Eles estimulam a busca de soluções mais eficientes.

Um exemplo do problema apresentado no dia 01/12/24 - Nível fácil:

— Dia 1: Histeria do Historiador —

O Chefe Historiador está sempre presente para o grande lançamento do trenó de Natal, mas ninguém o viu em meses! A última vez que alguém ouviu falar dele, ele estava visitando locais que são historicamente significativos para o Polo Norte; um grupo de Historiadores Seniores pediu que você os acompanhe enquanto eles verificam os lugares que acham que ele provavelmente visitou.

À medida que cada local é verificado, eles o marcarão em sua lista com uma estrela. Eles acham que o Chefe Historiador deve estar em um dos primeiros cinquenta lugares que irão procurar, então, para salvar o Natal, você precisa ajudá-los a obter cinquenta estrelas em sua lista antes de Santa partir em 25 de dezembro.

Colete estrelas resolvendo puzzles. Dois puzzles estarão disponíveis em cada dia do calendário de Advento; o segundo puzzle é desbloqueado quando você completa o primeiro. Cada puzzle concede uma estrela. Boa sorte!

Você nem sequer saiu ainda e o grupo de Historiadores Seniores Elvish já encontrou um problema: sua lista de locais para verificar está atualmente vazia. Eventualmente, alguém decide que o melhor lugar para verificar primeiro seria o escritório do Chefe Historiador.

Ao vasculhar o escritório, todos confirmam que o Chefe Historiador está de fato em lugar nenhum. Em vez disso, os Elfos descobrem uma variedade de notas e listas de locais historicamente significativos! Isso parece ser o planejamento que o Chefe Historiador estava fazendo antes de sair. Talvez essas notas possam ser usadas para determinar quais locais procurar?

Ao longo do escritório do Chefe, os locais historicamente significativos estão listados não pelo nome, mas por um número único chamado ID do local. Para se certificarem de que não vão perder nada, os Historiadores se dividem em dois grupos, cada um vasculhando o escritório e tentando criar sua própria lista completa de IDs do local.

Há apenas um problema: ao segurar as duas listas lado a lado (sua entrada de puzzle), rapidamente fica claro que as listas não são muito semelhantes. Talvez você possa ajudar os Historiadores a reconciliar suas listas?

Por exemplo:

3 4
4 3
2 5
1 3
3 9
3 3

Talvez as listas estejam apenas um pouco diferentes! Para descobrir, pareie os números e meça quão distantes estão. Pareie o menor número na lista esquerda com o menor número na lista direita, então o segundo menor número esquerdo com o segundo menor número direito, e assim por diante.

Dentro de cada par, descubra quão distantes estão os dois números; você precisará somar todas essas distâncias. Por exemplo, se você pareia um 3 da lista esquerda com um 7 da lista direita, a distância entre eles é 4; se você pareia um 9 com um 3, a distância entre eles é 6.

Na lista de exemplo acima, os pares e distâncias seriam os seguintes:

O menor número na lista esquerda é 1, e o menor número na lista direita é 3. A distância entre eles é 2.

O segundo menor número na lista esquerda é 2, e o segundo menor número na lista direita é outro 3. A distância entre eles é 1.

O terceiro menor número em ambas as listas é 3, então a distância entre eles é 0.

Os próximos números a serem pareados são 3 e 4, uma distância de 1.

Os quintos menores números em cada lista são 3 e 5, uma distância de 2.

Finalmente, o maior número na lista esquerda é 4, enquanto o maior número na lista direita é 9; esses estão a uma distância de 5 aparte.

Para encontrar a distância total entre a lista esquerda e a lista direita, some as distâncias entre todos os pares que você encontrou. Na lista de exemplo acima, isso é 2 + 1 + 0 + 1 + 2 + 5, uma distância total de 11!

Suas listas esquerda e direita reais contêm muitos IDs de local. Qual é a distância total entre suas listas?

Para começar, obtenha sua entrada de puzzle.

Se você não lê em inglês, lembre-se que o seu browser provavelmente tem uma opção para traduzir o texto. Caso contrário, não hesite em pedir ao Google ou um site de inteligência artificial para traduzi-lo. Eu usei o Claude.ai para traduzir o problema. Nos outros dias, eu vou postar apenas o link para o problema original.

Os problemas tem partes bem estruturadas, normalmente começam com uma pequena história para colocar a vítima no espírito do evento :-D. Logo depois, um vetor de teste é descrito. O vetor de teste é um exemplo de entrada onde o problema é demonstrado no formato: entrada e saída. Ou seja, entra tais dados e devem sair tais resultados. Esta parte é muito importante, pois é como você vai começar a resolver o problema.

O que eu normalmente faço e escrever um pequeno programa que usa o mesmo vetor de testes (como entrada) e começo a escrever um programa para gerar o resultado (saída). Quando meu programa começa a passar nos testes, eu troco o vetor de teste pela entrada do problema em si. A entrada você tem que pegar no site, eu acredito que ela mude de um usuário para outro, para não deixar que as respostas sejam divulgadas rapidamente e manter a competição honesta. Uma parte do Advent of Code que não recomendo, é a competição de programação. Quem compete fica esperando o programa sair de madrugada para ser o primeiro a resolver e publicar a resposta. Quanto mais cedo você posta a resposta correta, mais pontos você ganha, mas já aviso que duro, os “feras” resolvem esses problemas em menos de 10 minutos.

Uma vez que você tem os resultados para entrada do problema, você pode postá-la no site. Ao submeter sua resposta, o site indica se esta está correta ou não, às vezes dando alguma dica, como número muito grande ou muito pequeno. Você pode submeter quantas respostas quiser até acertar, mas tem que esperar um minuto caso erre. A ideia é que você entenda o problema, corrija o problema e calcule uma nova resposta.

Enviando a primeira resposta correta, o site apresentará uma segunda parte do problema. A segunda parte normalmente modifica a primeira. Os duendes normalmente descobrem que fizeram algo errado e mudam o cálculo do seu algoritmo. Esta mudança às vezes é bem simples, mas pode exigir que uma` nova solução seja elaborada.

A cada parte correta, você ganha uma estrela, duas por dia. Cada dia completo libera um desenho da árvore de Natal.

Dicas#

Se for a primeira vez que você participa, eu recomendo que combine com amigos e colegas para resolverem os problemas juntos. Existem forums na internet para este fim, como o Advent of Code Subreddit. Mas tente resolver sozinho e se precisar olhar a resposta, tente entender o que precisa ser feito.

Não se preocupe se atrasar um dia ou dois, o importante é voltar e continuar a fazer. Eu sempre esqueço depois de alguns dias, este ano vou tentar fazer até o final, postando minhas soluções no dia seguinte ou depois. Se a coisa apertar, use o grupo do Telegram do meu livro para pedir ajuda (endereço no livro :-D). Não esqueça que alguns problemas são realmente difíceis e tem algumas pegadinhas, não desanime se não conseguir resolver, procure a solução e veja quais algoritmos foram aplicados.

Organize o código em funções, pois é muito frequente reutilizar rotinas, principalmente de leitura do arquivo de entrada ou que transforma a entrada em lista ou dicionário. Você vai acabar criando rotinas para exibir os dados e ajudar com o debug na tela (alguns problemas geram gráficos em modo texto…). É uma boa oportunidade para conhecer a bibliteca rich do Python.

Resposta do Dia 01/12/24#

from auxiliares.arquivos import le_arquivo_sem_linhas_em_branco

ENTRADA_EXEMPLO = """
3   4
4   3
2   5
1   3
3   9
3   3
"""

ENTRADA_PROBLEMA = le_arquivo_sem_linhas_em_branco("01/input.txt")


def gera_listas(entradas):
    lista_esquerda = []
    lista_direita = []
    for entrada in entradas.splitlines():
        le, ld = entrada.split()
        lista_esquerda.append(int(le))
        lista_direita.append(int(ld))
    return lista_esquerda, lista_direita


def calcula_distancia(lista_esquerda, lista_direita):
    return [
        abs(le - ld) for le, ld in zip(sorted(lista_esquerda), sorted(lista_direita))
    ]


def conta_ocorrencias(lista: list[int]) -> dict[int, int]:
    ocorrencias: dict[int, int] = {}
    for elemento in lista:
        if elemento not in ocorrencias:
            ocorrencias[elemento] = lista.count(elemento)
    return ocorrencias


def similarity_score(lista_esquerda, lista_direita):
    ocorrencias = conta_ocorrencias(lista_direita)
    return sum([elemento * ocorrencias.get(elemento, 0) for elemento in lista_esquerda])


# Teste do problema
le, ld = gera_listas(ENTRADA_EXEMPLO)
distancia_exemplo = sum(calcula_distancia(le, ld))
assert distancia_exemplo == 11
print("Distancia exemplo:", distancia_exemplo)

# Resposta do problema
le, ld = gera_listas(ENTRADA_PROBLEMA)
distancia_problema = sum(calcula_distancia(le, ld))
print("Distancia problema:", distancia_problema)

# Parte 2

# Teste do problema
le, ld = gera_listas(ENTRADA_EXEMPLO)
score_exemplo = similarity_score(le, ld)
print("Score exemplo:", score_exemplo)
assert score_exemplo == 31

# Resposta do problema
le, ld = gera_listas(ENTRADA_PROBLEMA)
score_problema = similarity_score(le, ld)
print("Score problema:", score_problema)

# Saída:
# Distancia exemplo: 11
# Distancia problema: 936063
# Score exemplo: 31
# Score problema: 23150395

Módulo: auxiliar.arquivos

def le_arquivo(nome_arquivo: str) -> str:
    with open(nome_arquivo, "r") as f:
        return f.read()


def le_arquivo_sem_linhas_em_branco(nome_arquivo: str) -> str:
    return "\n".join(
        zz
        for linha in le_arquivo(nome_arquivo).splitlines()
        if len(zz := linha.strip()) > 0
    )


def uma_lista_por_linha(nome_arquivo: str) -> list[str]:
    return [
        [int(l) for l in linha.split()]
        for linha in le_arquivo_sem_linhas_em_branco(nome_arquivo).splitlines()
    ]

No meu caso, eu crio um diretório para cada dia e coloco tanto o programa quantos os arquivos de entrada o mesmo lugar. Para realizar os testes, eu estou usando o comando assert do Python. Ele simplesmente causa uma exceção no programa caso retorne falso. O assert é excelente, principalmente quando você começa a modificar o programa, para ter certeza que não criou um bug tentando resolver outro.

E essa é a resposta do primeiro dia. Eu já resolvi o de hoje (dia 02/12/24), se tiver tempo (amanhã é meu aniversário :-D), posto amanhã ou quarta-feira.