15 Dec 2023

Solución Advent of Code 2023 día 4

El problema puede encontrarse aquí: Advent of Code 2023 día 4.

Parte 1

Para resolver este problema solo se necesita buscar los números repetidos en la lista de números ganadores de cada tarjeta, el mayor inconveniente de esta parte es la estructuración de los datos.

Primero colocamos en un array la información de cada tarjeta, los números ganadores y los números del juego principalmente, no es del todo necesario almacenar el número del juego ya que está ordenado de menor a mayor y se puede usar el index del array para eso. En este caso particular, Lua inicia la indexación en 1, por lo que me ahorra algunos posibles problemas.

require "utils"

local function getInput()
    local input = readFile("04input.txt")
    local lines = splitString(input, lineDelimiter)
    local parts = {}
    local games = {}
    local numbers = {}
    local winners = {}

    for i, line in ipairs(lines) do
        line = line:gsub("|", ":") -- cambiar | por : para dividir el juego en 3 partes
        parts = splitString(line, colonDelimiter) -- 3 partes: parte 1: Card, parte 2: Numeros, parte 3: Numeros ganadores
        numbers = splitString(parts[2], spaceDelimiter)
        winners = splitString(parts[3], spaceDelimiter)
        games[i] = {
            numbers = {},
            winners = {}
        }

        for j = 1, #numbers do
            table.insert(games[i].numbers, tonumber(numbers[j])) -- importante cambiar string a números
        end

        for j = 1, #winners do
            table.insert(games[i].winners, tonumber(winners[j]))
        end
    end
    return games
end

Ahora podemos definir una función que compare un número con un array de números ganadores.

local function isWinner(number, winners)
    for _, winner in ipairs(winners) do
        if number == winner then
            return true
        end
    end
    return false
end

Ahora solo queda iterar por cada juego y por cada número y determinar los puntos que se obtiene en cada juego, importante iniciar la puntuación en cero, si encuentra un ganador pasa a 1, y si ya vale uno comienzas a multiplicar por 2, de esta manera cumple las condiciones requeridas.

local function answer1()
    local games = getInput()
    local points = 0
    local total = 0

    for _, game in ipairs(games) do
        points = 0

        for _, number in ipairs(game.numbers) do
            if isWinner(number, game.winners) then
                if points == 0 then
                    points = 1
                else
                    points = points * 2
                end
            end
        end

        total = total + points
    end
    return total
end

Parte 2

En esta parte te indican que cada tarjeta te hace ganar mas tarjetas, concretamente copias de las tarjetas, por tanto deberíamos poder aplicar un método recursivo aquí.

Con esto fue suficiente para resolver el ejercicio, en mi caso tardaba mas o menos un segundo para resolverlo, pero sabía que se podía hacer mas rápido, debido a que muchos cálculos se repiten por la misma recursión, se puede mejorar utilizando memoización.

Iterando desde el final hasta el inicio, es decir, al revés, podemos evitar recalcular las puntuaciones, esto debido a que las últimas tarjetas son las que debieran tener menos copias ganadas, guardar estos totales permite posteriormente recuperarlos cuando se necesite en la siguiente iteración.

local function getTotalScratchcards(index, cards)

    -- si el total ya fue calculado se devuelve directamente
    if cards[index].total ~= -1 then
        return cards[index].total
    end
    -- en caso contrario se calcula
    local total = 0

    for i = cards[index].points, 1, -1 do
        total = total + getTotalScratchcards(index + i, cards) + 1
    end
    -- se guarda el total calculado
    cards[index].total = total

    return total
end

El truco está en ir sumando 1 cada vez que la función recursiva es llamada de esta manera conseguimos conseguir el total de cada tarjeta, solo quedaría determinar los puntos, que la diferencia con la primera parte es que ahora va de 1 a 1.

local function answer2()
    local scratchcards = {}
    local totalScratchcards = 0
    local games = getInput()
    local points = 0
    local total = 0

    for _, game in ipairs(games) do
        points = 0

        for _, number in ipairs(game.numbers) do
            if isWinner(number, game.winners) then
                points = points + 1
            end
        end

        table.insert(scratchcards, {
            points = points,
            total = -1 -- iniciar con -1 ayuda a determinar que el total no ha sido calculado
        }) -- Casualmente Lua indexa desde 1, no desde 0
    end

    for i = #scratchcards, 1, -1 do
        totalScratchcards = totalScratchcards + getTotalScratchcards(i, scratchcards) + 1
    end

    return totalScratchcards
end

Con todo esto ya solo queda ejecutar el código

print("Parte 1:", answer1())
print("Parte 2:", answer2())

Puede encontrar mi código completo aquí: Github.