O nono dia do Advent of Code foi ontem 09/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, Dia 4, Dia 5, Dia 6, Dia 7 e Dia 8.

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

Dicas#

  • Lembre-se que strings em Python são imutáveis

  • Se você precisa alterar os caracteres de uma string, você pode transformá-la em uma lista de caracteres e reconvertê-la quando terminar.

  • Listas podem ser manipuladas por faixas. Você pode extrair vários elementos de uma lista de uma vez, assim como alterar vários elementos usando a notação de faixas.

  • zip combina dois iteráveis e é útil, por exemplo, para percorrer duas listas simultaneamente.

  • Você pode alterar dois elementos usando tuplas em Python:

a, b = b, a

  • Listas são passadas por referência. Se sua função alterar a lista, estas alterações serão visíveis fora da função.

  • Os ids são inteiros e serão bem maiores que números de um dígito. Ao expandir o mapa, use inteiros para representar cada id. Isto pode explicar o porquê de seu “checksum” não funcionar.

  • Na parte 1 do problema, vá passo a passo. Escreva uma função que expanda o mapa, outra que ache os espaços livres e uma para executar a reorganização. Use os valores de teste dados pelo problema para testar cada função.

  • A parte 2 é um pouco mais complexa, pois como o mapa é maior e a reorganização mais complexa, a solução não pode ser quadrática (O(n²)). Ou seja, se você precisar gerar a lista de espaços em branco desde o início a cada arquivo, ficará muito lento. Use a notação de listas para poder trocar vários elementos de uma vez.

  • Na parte 2, se você precisar manter uma lista de espaço livre, lembre-se que pode eliminar elementos da lista, quando o espaço é completamente usado. Se o espaço não for totalmente usado, lembre-se de atualizar a lista de espaço livre.

Quanto de Python você precisa saber?#

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

  • Listas, tuplas - Capítulo 6
  • Strings - Capítulo 7
  • Geradores, itertools - Capítulo 8

Resposta# 

from auxiliares import le_arquivo_sem_linhas_em_branco

DISK_MAP = "2333133121414131402"
DISK_MAP_EXPANDED = "00...111...2...333.44.5555.6666.777.888899"
DISK_MAP_REARRANGED = "0099811188827773336446555566.............."
DISK_MAP_REARRANGED_2 = "00992111777.44.333....5555.6666.....8888.."


def lista_para_string(lista):
    return "".join(lista)


def expanda_mapa(mapa_do_disco: str) -> str:
    expandido = []
    modo = True
    id = 0
    for código in mapa_do_disco:
        if modo:
            expandido += [str(id)] * int(código)
            id += 1
        else:
            expandido += ["."] * int(código)
        modo = not modo
    return expandido


def livre(disco: list[str]) -> int:
    for posição, c in enumerate(disco):
        if c == ".":
            yield posição


def usado_da_direita(disco: list[str]) -> int:
    posição = len(disco) - 1
    while posição >= 0:
        if disco[posição] != ".":
            yield posição
        posição -= 1


def troca(disco: list[str], a: int, b: int, tamanho: int = 1):
    disco[a : a + tamanho], disco[b : b + tamanho] = (
        disco[b : b + tamanho],
        disco[a : a + tamanho],
    )


def rearrange(disco: list[str]):
    for esquerda, direita in zip(livre(disco), usado_da_direita(disco)):
        if direita <= esquerda:
            break
        troca(disco, esquerda, direita)


def livre_continuo(disco: list[str]) -> (int, int):
    u = -1
    for p, c in enumerate(disco):
        if c == "." and u == -1:
            u = p
        elif c != "." and u != -1:
            yield u, p - 1
            u = -1


def usado_da_direita_continuo(disco: list[str]) -> (int, int):
    posição = len(disco) - 1
    while posição >= 0:
        if disco[posição] != ".":
            fim = posição
            while disco[posição] == disco[fim] and posição >= 0:
                posição -= 1
            posição += 1
            if posição >= 0:
                yield posição, fim
        posição -= 1


def rearrange_parte_2(disco: list[str]):
    espaço_livre = list(livre_continuo(disco))
    for inicio, fim in usado_da_direita_continuo(disco):
        tamanho = fim - inicio + 1
        for i, (inicio_livre, fim_livre) in enumerate(espaço_livre):
            if fim_livre >= inicio:
                break
            if fim_livre - inicio_livre + 1 >= tamanho:
                troca(disco, inicio_livre, inicio, tamanho)
                if fim_livre - inicio_livre + 1 == tamanho:
                    espaço_livre.pop(i)
                else:
                    espaço_livre[i] = (inicio_livre + tamanho, fim_livre)
                break


def checksum(disco: list[str]) -> int:
    s = 0
    for posição, id in enumerate(disco):
        s += posição * int(id) if id != "." else 0
    return s


# Teste
expandido = expanda_mapa(DISK_MAP)
assert lista_para_string(expandido) == DISK_MAP_EXPANDED
rearrange(expandido)
assert lista_para_string(expandido) == DISK_MAP_REARRANGED
check = checksum(expandido)
print("Teste - parte 1:", check)
assert check == 1928

# Parte 1
entrada = le_arquivo_sem_linhas_em_branco("09/input.txt")
expandido = expanda_mapa(entrada)
rearrange(expandido)
check = checksum(expandido)
print("Parte 1:", check)
assert check == 6283170117911

# Teste - Parte 2
expandido = expanda_mapa(DISK_MAP)
rearrange_parte_2(expandido)
assert lista_para_string(expandido) == DISK_MAP_REARRANGED_2
check = checksum(expandido)
print("Teste - Parte 2:", check)
assert check == 2858

# Parte 2
expandido = expanda_mapa(entrada)
rearrange_parte_2(expandido)
check = checksum(expandido)
print("Parte 2:", check)
assert check == 6307653242596

# Saída:
# Teste - parte 1: 1928
# Parte 1: 6283170117911
# Teste - Parte 2: 2858
# Parte 2: 6307653242596