Advent of Code 2023 Day 09: Mirage Maintenance
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: