14 Dec 2023

Solución Advent of Code 2023 día 3

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

Parte 1

En este problema tenemos un mapa bidimensional, es decir una simulación de un espacio de dos dimensiones. Lo que hay que hacer es encontrar los números que se encuentren adyacentes a los símbolos y sumar esos números.

Para este problema no vi necesario declarar una función input, debido a que no necesité formatear el texto, decidí iterar caracter por caracter en búsqueda de símbolos y con un poco de matematica determinar la ubicación de los vecinos de los símbolos.

require "utils"

local input = readFile("03input.txt")
local partNumberFound = {} -- lista de números encontrados
local down = #splitString(input, lineDelimiter)[1] + 1 -- se suma el salto de línea
local up = -down
local adjacents = {-1, up - 1, up, up + 1, 1, down + 1, down, down - 1}

Con el array “adjacents” iteraré en cada simbolo encontrado para buscar números vecinos.

Intentaré explicarlo con una imagen de bajo presupuesto que hice:

Cuando encontramos un simbolo en un index del string dado, es facil saber el caracter a la izquierda está mas cerca del inicio por lo que es el mismo “index - 1”, el caracter de la derecha está mas lejos del inicio por lo que sería “index + 1”, el vecino de arriba está una fila mas arriba, cada fila contiene una cantidad de caracteres (ancho), por lo que el caracter de arriba sería “index - ancho”, a la inversa el caracter de abajo sería “index + ancho”. Es importante tomar en cuenta que el mapa contiene saltos de línea (\n), por lo que cuenta también como un caracter.

La esquina superior izquierda se puede calcular como “index - ancho - 1”, la esquina superior derecha sería “index - ancho + 1”, la esquina inferior izquierda sería “index + ancho - 1” y la esquina inferior derecha sería “index + ancho + 1”.

Por este motivo, la variable local down la declaré como la cantidad de caracteres en la primera fila (ancho), aprovechando que el mapa tiene un ancho fijo.

Ahora si a iterar por cada caracter.

local function answer1()
    partNumberFound = {} -- importante restablecer para evitar inconvenientes en la parte 2
    local char = ""
    local total = 0
    for i = 1, #input do
        char = input:sub(i, i)
        --Buscamos caracter por caracter hasta encontrar un símbolo que no sea número, punto o salto de línea
        if tonumber(char) == nil and char ~= "." and char ~= "\n" then
            -- Una vez encontrado el simbolo, pasamos a buscar la suma de las partes adjacentes
            total = total + getSumOfParts(i)
        end
    end
    return total
end

La idea principal en getSumOfParts es encontrar cada dígito vecino al símbolo, luego, una vez encontrado un dígito debemos expandir a la izquierda y derecha para descubrir el número entero.

Otro ejemplo de bajo presupuesto:

local function getSumOfParts(index)
    local char = ""
    local isNumber = false
    -- la idea con left y right es si encontramos un dígito
    -- expandimos hacia la izquierda y derecha para descubrir todo el número
    -- luego agregamos el mismo número en el index desde left a right en partNumberFound para evitar
    -- contar el mismo número varias veces
    local left = 0
    local right = 0
    local number = 0
    local total = 0

    for i = 1, #adjacents do
        if adjacents[i] + index > 0 and adjacents[i] + index <= #input then
            char = input:sub(adjacents[i] + index, adjacents[i] + index)
            isNumber = tonumber(char) ~= nil
            if isNumber then
                -- verificamos si el index que estamos revisando no está registrado en la lista
                if partNumberFound[adjacents[i] + index] == nil then
                    -- readNumberOfIndex buscará el número completo expandiendose de izquierda a derecha
                    number, left, right = readNumberOfIndex(adjacents[i] + index)
                    -- una vez tenemos el número lo agregamos en cada index desde la ubicación izquierda
                    -- hasta la ubicación derecha para evitar sumar números repetidos
                    for j = left, right do
                        partNumberFound[j] = true
                    end
                    total = total + number
                end
            end
        end
    end
    return total
end

local function readNumberOfIndex(index)
    local left = index
    local right = index
    local number = 0
    -- Revisamos a la izquierda, siempre que el siguiente caracter sea un número
    -- continuamos expandiendo
    while tonumber(input:sub(left - 1, left - 1)) ~= nil do
        left = left - 1
        number = tonumber(input:sub(left, right))
        if number == nil then
            -- si el número es inválido, recuperamos el index anterior y continuamos
            left = left + 1
            break
        end
    end
    -- ahora revisamos a la derecha
    while tonumber(input:sub(right + 1, right + 1)) ~= nil do
        right = right + 1
        number = tonumber(input:sub(left, right))
        if number == nil then
            -- si el número es inválido, recuperamos el index anterior y continuamos
            right = right - 1
            break
        end
    end
    -- por último devolvemos el número descubierto y el index de su inicio(izq) y fin(der)
    return tonumber(input:sub(left, right)), left, right
end

Parte 2

En la segunda parte nos piden hacer algo similar, pero con diferentes condiciones, buscar solo en los símbolos “*” que tengan exactamente 2 números.

Por lo que nos sirve casi todo el código que ya tenemos, solo vamos a agregar estas condiciones, modificando el getSumOfParts quedaría así.

-- con solo agregar un booleano (gears) podemos diferenciar la parte 1 de la 2
local function getSumOfParts(index, gears)
    local char = ""
    local isNumber = false
    local left = 0
    local right = 0
    local number = 0
    local total = 0
    -- agregamos una lista para almacenar los números de gears
    local gearParts = {}

    for i = 1, #adjacents do
        if adjacents[i] + index > 0 and adjacents[i] + index <= #input then
            char = input:sub(adjacents[i] + index, adjacents[i] + index)
            isNumber = tonumber(char) ~= nil
            if isNumber then
                if partNumberFound[adjacents[i] + index] == nil then
                    number, left, right = readNumberOfIndex(adjacents[i] + index)
                    for j = left, right do
                        partNumberFound[j] = true
                    end
                    -- Aqui esta la diferencia, en la segunda parte añadimos el número al array
                    if gears then
                        table.insert(gearParts, number)
                    else
                        total = total + number
                    end

                end
            end
        end
    end
    if gears then
        -- devolvemos la multiplicación solo si hay 2 partes, si no devolvemos cero
        if #gearParts == 2 then
            return gearParts[1] * gearParts[2]
        else
            return 0
        end
    else
        return total
    end
end

Ahora solo quedaría obtener la solución

local function answer1()
    partNumberFound = {}
    local char = ""
    local total = 0
    for i = 1, #input do
        char = input:sub(i, i)
        if tonumber(char) == nil and char ~= "." and char ~= "\n" then
            total = total + getSumOfParts(i, false)
        end
    end
    return total
end

local function answer2()
    partNumberFound = {}
    local char = ""
    local total = 0
    for i = 1, #input do
        char = input:sub(i, i)
        if char == "*" then
            total = total + getSumOfParts(i, true)
        end
    end
    return total
end

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

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