Advento do Código 2025 - Dia 7

07 de dezembro de 2025

O primeiro domingo do Advento do Código. Eric Wastl, o criador, deve pensar que temos muito tempo no fim de semana para resolver quebra-cabeças de código o dia todo. Bem, certamente não, mas consegui passar. Veja como.

Confira minha solução completa para o dia 7 no GitHub.

Na verdade, não vou abordar parte por parte neste post de hoje. Refatorei muito código para a parte dois e adicionei novamente a lógica da parte um. Então, vamos voltar e começar com a parte dois.

Parte dois

Em ambas as partes, começamos com o seguinte espaço de problemas:

.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

Começamos no ponto S na grade e aponte um feixe para baixo. Se o feixe atingir um divisor (^), ele se divide em dois: um feixe à esquerda do divisor e um feixe à direita. Se o feixe não encontrar um divisor (.) ele apenas continua descendo até atingir a parte inferior da grade.

O quebra-cabeça torna as coisas mais difíceis do que são, introduzindo o conceito de um variedade de táquion quântico que divide o próprio tempo em cada divisor. Mas o que realmente importa é o seguinte: começando em Sencontre todos os caminhos exclusivos para a parte inferior da grade. E como o feixe se divide em dois em cada divisor (onde você pode escolher esquerda ou direita a cada vez, que é onde a ideia de quântico origina-se de) existem muitos caminhos, especialmente na entrada real.

Em outras palavras: não podemos nos dar ao luxo de recalcular partes do caminho várias vezes, pois isso simplesmente leva muito tempo. Isso significa que precisamos de uma maneira de armazenar resultados anteriores. Se uma posição da grade faz parte de um caminho que já possui um resultado, não precisaríamos calculá-lo novamente, mas sim recuperar o resultado correspondente de algum lugar.

É aqui que entra a magia da programação dinâmica. Deixe-me dar um exemplo do que é isso. Digamos que temos uma função que aceita um número como entrada e calcula seu quadrado:

Digamos que damos o número 3 como entrada, que retorna 9. Cada vez que damos 3 como entrada novamente, a função retornará 9 novamente (o que significa que a função é determinística). Em vez de recalcular sempre, podemos armazenar o resultado 9 para entrada 3 em algum lugar. Python facilita isso permitindo a implementação de um cache no topo da função, usando um atributo:

@lru_cache(maxsize=None)
def f(x):
    return x * x

Esse lru_cache O atributo garante que cada vez que chamarmos a função com uma entrada usada anteriormente, ele não recalculará o resultado, mas o recuperará do cache.

Podemos aplicar a mesma lógica ao nosso quebra-cabeça. Cada vez que tentamos encontrar um caminho a partir de uma posição na grade que já fez parte de outro caminho no passado, já sabemos qual será o resultado e podemos retorná-lo do cache.

A parte principal da lógica de hoje utiliza este princípio, juntamente com a continuação recursiva do caminho descendente. O código abaixo mostra que se chegarmos a um divisor (^), continuamos a olhar para baixo a partir de pontos na grade começando à esquerda e à direita deste divisor. Se chegarmos ao espaço vazio (.) apenas continuamos para baixo. Se chegarmos ao fundo da grade em um caminho, retornamos 1indicando que outro caminho foi concluído.

@lru_cache(maxsize=None)
def dp(sr: int, sc: int) -> int:
    if sr >= len(manifold):
        return 1
    
    if manifold(sr)(sc) == '^':
        return dp(sr, sc - 1) + dp(sr, sc + 1)
    else:
        return dp(sr + 1, sc)

Esta função recursiva eventualmente nos dá a resposta para a parte dois.

Parte um

Minha primeira implementação da primeira parte foi diferente. Você pode encontrá-lo em meu histórico do Git se estiver realmente curioso. O quebra-cabeça da primeira parte era um pouco diferente: só precisávamos contar quantas vezes uma viga seria dividida.

Resolvi isso adicionando um conjunto global ao qual adiciono cada divisor que encontro no meu caminho descendente a partir do ponto inicial:

Na mesma função que usei na parte dois, adiciono cada divisor que encontro a este conjunto:

if manifold(sr)(sc) == '^':
    if (sr, sc) not in SEEN_SPLITS:
        SEEN_SPLITS.add((sr, sc))

Com esta lógica, SEEN_SPLITS conterá todos os divisores no caminho apenas uma vez. Contar o número de itens neste conjunto dará a resposta à primeira parte.

Source link