Advent of Code 2023 Day 09: Mirage Maintenance

Cover Photo

Foto de Capa gerada por IA

Ao chegar no local indicado pelo mapa e após a tempestade de areia passar você descobre que está em um Oasis! E ao olhar para o céu, perceve que existe uma ilha de metal.

Talvez é de lá que as peças faltantes das máquinas de areia que você precisa arrumar venham?

Como ainda é noite, para evitar que futuros viajantes se percam nas tempestades de areia você decide coletar algumas informações e usar o seu Sensor chamado OASIS (Oasis And Sand Instability Sensor). Ele coleta informações de forma discreta e sequencial durante o tempo em forma de parâmetros. Essas leituras são o seu input.

Contexto específico

Cada linha do seu input é referente a leitura de um parâmetro e por análise de padrões você deve descobrir (prever) qual será o próximo parâmetro que vai aparecer. Para isso, existe uma fórmula que pode ser usada para usar os valores ali presentes para prever as próximas leituras. A fórmula consiste em usar a a diferença entre os parâmetros lidos e as diferenças subsequentes.

Tomando por exemplo a linha 0 3 6 9 12 15, a diferença entre os valores é de 3 entre eles. Geramos então a linha 3 3 3 3 3, onde a diferença entre os valores agora é de 0 entre cada parâmetro. Extrapolando, chegamos ao seguinte caso:

0   3   6   9   12   15
  3   3   3   3    3
    0   0   0    0

O próximo valor (após o 15) dos parâmetros é a soma dos valores previstos anteriormente com o último valor da linha que está sendo prevista. Dessa forma, primeiro se deve prever o valor da linha contendo apenas 0 e somar ele ao último valor da linha anterior: 0 + 3 = 3.

Usando a mesma lógica, é somado o valor previsto anteriormente ao último valor da linha que queremos prever e temos o resultado 0 + 3 + 15 = 18.

// iteração 1
9   12   15
  3    3
0   [0] ->(0)

// iteração 2
9   12   15
  3    [3] ->(3)
0    0    [0]

// iteração 3
9   12   [15]->(18)
  3    3   [3]
0    0   [0]

Algo importante a notar é: Você só deve realizar a soma recursiva caso encontre uma linha completa preenchida de valores 0. Caso contrário, o algoritmo continua sua execução!

A solução para seu desafio é executar esse algoritmo para todas as leituras de parâmetros (linhas) e somar todos os "próximos" valores de cada linha.

Resolução Parte 1

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

Para esse desafio não percebi nenhuma otimização logo que iniciei. Fui então implementando cada passo do algoritmo para que pudesse obter a soma dos valores previstos nas sequências de cada linha

const findNextValue = (line) => {
  const values = line.match(/-?\d+/g).map((v) => Number(v))
 
  const allDifferences = findListOfDifferences(values)
 
  const nextValue = findNextValueBasedOnListOfDifferences(allDifferences)
 
  return nextValue
}

Primeiro, quebramos a linha em números. Na sequência é criada uma lista com as sequências de diferenças até atingir o critério de parada (uma lista contendo apenas valores 0) com a função auxiliar findListOfDifferences(). Essa lista é usada para somar prever o próximo parâmetro com a função auxiliar findNextValueBasedOnListOfDifferences().

Executamos a função findNextValue() para cada linha dentro da função buildListOfNextValues() e somamos os valores encontrados com uma função auxiliar sumListElements()

const buildListOfPreviousValues = (lines) => {
  const previousValues = []
  for (const line of lines) {
    const previousValue = findPreviousValue(line)
 
    previousValues.push(previousValue)
  }
 
  return previousValues
}
 
// ...
 
const nextValues = buildListOfNextValues(lines)
 
const sumOfNextValues = sumListElements(nextValues)

Por ser uma função de soma usando Array.reduce(), a função sumListElements() foi colocada no arquivo de utils array.js.

Nota: as funções auxiliares não mencionadas estão presentes no repositório do GitHub

Com a solução encontrada, a parte 2 do desafio é aberta. Para proporcionar mais informações no report de parâmetros, você decide extrapolar as leituras "para trás", prevendo valores anteriores aos lidos.

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!

Para a segunda parte, a decisão foi usar boa parte do código existente e apenas inverter a ordem dos parâmetros lidos de cada linha.

Como exemplo, a linha mencionada no exemplo anterior ficaria na seguinte ordem:

15  12  9  6  3  0

E usando a mesma função findNextValue() temos o código:

const findPreviousValue = (line) => {
  const reversedLine = line.split(' ').reverse().join(' ')
 
  return findNextValue(reversedLine)
}

Vale mencionar que o método Array.reverse() modifica o Array original. Porém, como o código está no meio de uma execução encadeada de conversão de String -> Array a linha original não é modificada!

A solução é a soma final encontrada após prever os valores, como na parte 1!

const previousValues = buildListOfPreviousValues(lines)
 
const sumOfPreviousValues = sumListElements(previousValues)

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étodos Array:

Métodos String: