O quinto dia do Advent of Code foi ontem 05/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2, Dia 3, e Dia 4!

Classifiquei o quinto problema como fácil (parte 1) e médio (parte 2).

Dicas#

  • O problema tem duas entradas, uma lista de regras e uma lista de atualizações.

  • As páginas presentes na lista de regras (X) devem ser impressas antes das páginas (Y). Como a mesma página X pode ter várias Y, as regras são um dicionário com chaves do tipo int e listas também do tipo int.

  • As atualizações são listas de inteiros simples.

  • Para verificar se as regras foram respeitadas, verifique se toda página presente na atualização obedece as regras.

  • Uma forma de ver a validação é verificar se a lista antes da página sendo verificada tem alguma outra página listada nas regras da mesma página. Você pode utilizar as regras de fatiamento de listas para criar uma sub-lista com os elementos anteriores da lista.

Por exemplo:

>>> L = [7, 8, 9]
>>> L[1:]
[8, 9]
>>> L[:2]
[7, 8]
>>> L[:1] + L[2:]
[7, 9]
>>>

Releia a parte de fatiamento de listas no capítulo 7 se necessário.

  • A reordenação pode ser feita da mesma forma. Quando um elemento fora de ordem for encontrado, retire-o da lista, trocando a ordem do elemento errado com o elemento do livro de regras que deveria aparecer antes.

Exemplo com uma lista pequena:

>>> REGRA = {8: [7]}
>>> atualização = [7, 8, 9]
# Como p é o segundo elemento, índice 1, podemos trocar a ordem:
>>> REORDENADO = atualização[:0] + [8] + [atualização[0]] + atualização[2:]
[8, 7, 9]

  • Este tipo de problema confunde, pois a ordenação por ordem crescente prevalece e mesmo respeitando as regras, você pode ter a impressão que está incorreto.

  • Você pode utilizar uma função recursiva para reordenar a lista, uma vez que ao mudar um elemento, as regras devem ser novamente verificadas.

  • Parte 1: Fácil - exige um pouco de criatividade para combinar listas e dicionários.

  • Parte 2: Médio - a reordenação recursiva não é tão evidente.

Quanto de Python você precisa saber?#

Os capítulos se referem ao meu livro Introdução à Programação com Python.

  • Listas, Dicionários - Capítulo 6
  • Funções recursivas - Capítulo 8

Resposta# 

from auxiliares import string_para_matriz_int, uma_lista_por_linha

ORDEM = """47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13"""

TESTE = """
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47
"""


def constrói_regras(restrições: list[list[int]]) -> dict[int, list[int]]:
    regras = {}
    for x, y in restrições:
        regras[x] = regras.get(x, []) + [y]
    return regras


def constrói_restrições(ordem: str) -> list[list[int]]:
    return string_para_matriz_int(ordem, separador="|")


def verifica_ordem(regras: dict[int, list[int]], atualização: list[int]) -> bool:
    for p, pagina in enumerate(atualização):
        if pagina in regras:
            anteriores = atualização[:p]
            for anterior in anteriores:
                if anterior in regras[pagina]:
                    return False
    return True


def reordena(regras: dict[int, list[int]], atualização: list[int]) -> bool:
    for p, pagina in enumerate(atualização):
        if pagina in regras:
            anteriores = atualização[:p]
            for i, anterior in enumerate(anteriores):
                if anterior in regras[pagina]:
                    return reordena(
                        regras,
                        anteriores[:i]
                        + [pagina]
                        + anteriores[i:]
                        + atualização[p + 1 :],
                    )
    return atualização


def soma_paginas_do_meio(regras, atualizações):
    s = 0
    for atualização in atualizações:
        if verifica_ordem(regras, atualização):
            meio = (len(atualização)) // 2
            s += atualização[meio]
    return s


# Parte 1
regras_teste_parte_1 = constrói_regras(constrói_restrições(ORDEM))
m_teste = string_para_matriz_int(TESTE, ",")

teste_parte_1 = soma_paginas_do_meio(regras_teste_parte_1, m_teste)
print("Teste parte 1:", teste_parte_1)
assert teste_parte_1 == 143

regras_parte_1 = constrói_regras(uma_lista_por_linha("05/regras.txt", separador="|"))
atualizações_parte_1 = uma_lista_por_linha("05/atualizacoes.txt", separador=",")

parte_1 = soma_paginas_do_meio(regras_parte_1, atualizações_parte_1)
print("Parte 1:", parte_1)
assert parte_1 == 5268

# Parte 2

soma_teste_parte_1 = soma_paginas_do_meio(
    regras_teste_parte_1,
    [
        reordena(regras_teste_parte_1, atualização)
        for atualização in m_teste
        if not verifica_ordem(regras_teste_parte_1, atualização)
    ],
)
print("Soma dos elementos do meio, parte 2 vetor de teste:", soma_teste_parte_1)
assert soma_teste_parte_1 == 123

soma_parte_2 = soma_paginas_do_meio(
    regras_parte_1,
    [
        reordena(regras_parte_1, atualização)
        for atualização in atualizações_parte_1
        if not verifica_ordem(regras_parte_1, atualização)
    ],
)
print("Soma dos elementos do meio, parte 2:", soma_parte_2)
assert soma_parte_2 == 5799

# Saída
# Teste parte 1: 143
# Parte 1: 5268
# Soma dos elementos do meio, parte 2 vetor de teste: 123
# Soma dos elementos do meio, parte 2: 5799