Advent of Code 2023 Day 03: Gear Ratios

Foto de Capa gerada por IA

Depois de uma longa caminhada você chega a uma Estação de Teleféricos e que é possível chegar a fonte de água que está com problemas. Entrando na estação, os Teleféricos estão parados pois há um problema com os motores.

O Elfo Engenheiro que está trabalhando te explica o problema e você se oferece para ajudar: Existem engrenagens faltando no motor mas ninguém consegue encontrar o que é. Por sorte existe um mapa do motor que é seu input, e com ele é simples descobrir quais engrenagens estão faltando.

Contexto específico

Para resolver o problema é preciso descobrir a soma de todos os números que são adjascentes a um símbolo no mapa. Os números que não são adjascentes a nenhum símbolo devem ser desconsiderados. E claro: o símbolo “ponto” não deve ser considerado um símbolo válido para soma dos números adjascentes.

Vale notar que os números podem estar conectados em qualquer um dos seus dígitos, e em qualquer uma das extremidades. Como alguns números possuem mais de um dígito, pode ser que apenas um deles esteja conectado a um símbolo e isso torna o número válido.

Nota: Este também é o primeiro desafio que seu input é um grande “mapa” do ano: Todas as linhas possuem a mesma quantidade de dígitos.

Resolução Parte 1

Caso queira resolver antes de ler a respeito de minha solução, esse é o momento!

Enquanto ponderava entre opções resolução, essas pareciam promissoras:

• Encontrar todos os símbolos e analisar quais números eram adjascentes a eles
• Passar nos dígitos, um a um e analisando se ele se conectava a um símbolo mantendo um estado que guarda essa informação, retroativamente

Como nos dois casos seria necessário passar por todos os itens do mapa resolvi seguir com a segunda alternativa. Encadeei dois loops baseado nos tamanhos das linhas e das colunas e fui “montando” os números com os dígitos encontrados, caso encontrasse algum que não fosse um “ponto” ou símbolo. Também fiz uso do estado local shouldSum se deveria somar o número baseado no encontro de um símbolo adjascente.

let totalSum = 0

for (let i = 0; i < COL_SIZE; i++) {
  const line = lines[i]
  let shouldSum = false
  let actualValue = 0

  for (let j = 0; j < ROW_SIZE; j++) {
    const lineItem = line[j]

    if (lineItem !== DOT && isNumber(lineItem)) {
      actualValue = Number(`${actualValue}${lineItem}`)
      shouldSum = shouldSum || hasAdjascentSymbols({ lines, point: [i, j] })
      continue
    }

    if (shouldSum) {
      totalSum += Number(actualValue)
    }
    shouldSum = false
    actualValue = 0
  }

  if (actualValue > 0 && shouldSum) {
    totalSum += Number(actualValue)
  }
}

É possível notar funções auxiliares como isNumber() e hasAdjascentSymbols(). Enquanto a primeira é simples a segunda constrói uma lista de pontos adjascentes baseado no tamanho mínimo e máximo da linha e da coluna e itera sobre esses pontos para validar a existência de um símbolo. Caso encontre, retorna true e caso não, retorna false.

const isNumber = (value) => !isNaN(Number(value))

const getAdjascentPoints = (point) => {
  const [i, j] = point
  const allPossibleAdjascentPoints = [
    [i - 1, j - 1],
    [i - 1, j],
    [i - 1, j + 1],
    [i, j - 1],
    [i, j + 1],
    [i + 1, j - 1],
    [i + 1, j],
    [i + 1, j + 1],
  ]

  const adjascentPoints = []

  for (const adjascentPoint of allPossibleAdjascentPoints) {
    const [x, y] = adjascentPoint
    if (x >= 0 && x < ROW_SIZE && y >= 0 && y < COL_SIZE) {
      adjascentPoints.push(adjascentPoint)
    }
  }

  return adjascentPoints
}

const hasAdjascentSymbols = ({ lines, point }) => {
  const adjascentPoints = getAdjascentPoints(point)

  for (const adjascentPoint of adjascentPoints) {
    const [i, j] = adjascentPoint
    if (!/(\d|\.)/.test(lines[i][j])) {
      return true
    }
  }

  return false
}

O motor agora funciona mas anda muito devagar. O Elfo menciona que apesar de funcionar ainda existe algo errado: Você precisa encontrar o que eles chamaram de gear ratio, ou: uma soma dos valores das engrenagens, e apenas delas. Uma engrenagem é apresentada no mapa do motor como um asterísco (*) com apenas dois números próximos e o valor de cada engrenagem a multiplicação desses dois números.

Resolução Parte 2

Novamente, Caso queira resolver a segunda parte antes de ler a respeito de minha solução, interrompa sua leitura aqui mesmo!

Nesse momento pensei que teria sido melhor ter optado por resolver a parte 1 do desafio com a outra abordagem considerada. Caso tivesse feito dessa forma já teria os símbolos todos com seus respectivos valores adjascentes e bastaria filtrar as engrenagens e multiplicar os valores.

Optei então por seguir com a abordagem de passar por todos pontos do input novamente e criar um mapa (chave-valor) usando a estrutura Map() do JavaScript para adicionar itens da seguinte forma:

const gears = new Map()

gears.set(`gear[i][j]`, [])

Assim, já teria todos os valores adjascentes as engrenagens e bastaria multiplicar aqueles que tem apenas 2 valores e somar tudo para obter o gear ratio.

const gears = new Map()

for (let i = 0; i < COL_SIZE; i++) {
  const line = lines[i]
  let gearPoint = []
  let actualValue = 0

  for (let j = 0; j < ROW_SIZE; j++) {
    const lineItem = line[j]

    if (lineItem !== DOT && isNumber(lineItem)) {
      actualValue = Number(`${actualValue}${lineItem}`)
      gearPoint = hasAdjascentGear({ lines, point: [i, j] }) ?? gearPoint
      continue
    }

    if (actualValue > 0 && gearPoint.length > 0) {
      addGearPointToGears({ gears, gearPoint, value: actualValue })
    }

    gearPoint = []
    actualValue = 0
  }

  if (actualValue > 0 && gearPoint.length > 0) {
    addGearPointToGears({ gears, gearPoint, value: actualValue })
  }
}

Vale notar que precisei passar e construir o número em todos os casos, mesmo que ele não estivesse adjascente a uma engrenagem pois não sabia se já existia uma engrenagem perto até passar por todos os pontos daquele número.

Também foi usado a função auxiliar isNumber() aqui e 2 outras: hasAdjascentGear() e addGearPointToGears(). A primeira busca especificamente por uma engrenagem adjascente enquanto a segunda adiciona ao Map() de forma segura o valor encontrado. Essa função só é executada se existe um valor e se existe uma engrenagem adjascente.

const hasAdjascentGear = ({ lines, point }) => {
  const adjascentPoints = getAdjascentPoints(point)

  for (const adjascentPoint of adjascentPoints) {
    const [i, j] = adjascentPoint
    if (/(\*)/.test(lines[i][j])) {
      return adjascentPoint
    }
  }

  return null
}

const addGearPointToGears = ({ gears, gearPoint, value }) => {
  const [x, y] = gearPoint
  const label = `gear[${x}${y}]`

  const values = gears.has(label) ? [...gears.get(label), value] : [value]

  gears.set(label, values)
}

Bastava então fazer a parte final de multiplicar e somar esses valores todos feitos na função findGearRatio(). Cheguei ao valor final e consegui completar o desafio.

const findGearRatio = (lines) => {
  const gears = populateGearsMap(lines)

  let gearRatio = 0

  for (const values of gears.values()) {
    if (values.length === 2) {
      const [v1, v2] = values
      gearRatio += v1 * v2
    }
  }

  return gearRatio
}

Referências

O código final esta disponível no repositório do GitHub. Esses são alguns links que podem te auxiliar a compreender melhor o código e cada detalhe que mencionei ou esqueci de comentar a respeito de minha solução:

• Método RegExp test()
• isNaN()
• Nullish coalescing operator (??)
• Map Object
• split()