Advent of Code 2023 Day 14: Parabolic Reflector Dish
Foto de Capa gerada por IA
Ao chegar no local onde todos os espelhos estavam apontando você percebe um refletor parabólico em formato de “prato”. Entretanto o refletor não parece estar funcionando visto que todos os seus espelhos refletores estão desajustados.
Para colocar cada refletor no seu devido lugar, você nota que é possível mover os espelhos refletores com algumas pedras que estão em uma plataforma interconectadas aos refletores. Ao mover uma pedra, os espelhos se movem!
Após analisar a fundo, a plataforma parece estar danificada e resolve calcular se a parte norte da plataforma vai aguentar a pressão das pedras se movendo e estando naquela posição.
Seu trabalho é achar a pressão depositada na parte norte pelas pedras, baseado no seu input que contém pedras arredondadas e pedras em formato cúbico (não se movem!).
Contexto específico
Seu input é constituído de um mapa da plataforma com indicações de onde estão cada pedra
- Arredondadas (
O) - Cúbicas (
#)
ou apenas é um espaço vazio (.).
Seu desafio é deslocar todas as pedras para a parte norte e avaliar a pressão ali depositada com um mapa de valores dependendo do quão perto da borda as pedras arredondadas estão. As pedras cúbicas não fazem pressão mas também não se movem e barram a rolagem das pedras arredondadas.
Seu input possui diversos terrenos (terrains) e você deve descobrir onde está posicionado o espelho que está refletindo exatamente o terreno.
O reflexo pode aparecer de forma horizontal ou vertical e dependendo de onde estiver podem existir linhas que “sobrem” ao final/início da linha/coluna. O importante é que todo o terreno refletido seja idêntico ao original.
Resolução Parte 1
Caso queira resolver antes de ler a respeito de minha solução, esse é o momento!
Novamente, por termos um mapa optei por usar o Módulo Square() (que pode ser visualizado nesse arquivo) enquanto tirava vantagem da função de callback que é possível ser passada.
Ao invés de realizar os movimentos todas as vezes e ter que passar por todos os items da plataforma, foi motada uma estrutura usando um Map() do JavaScript que contém todas as pedras e suas respectivas posições.
const columnName = ([i, j]) => `column[${j}]`
const columnRocks = new Map()
const buildColumnRocksMapCallbackFn = ({ item, coordinates }) => {
if (item !== TILES.EMPTY_SPACE) {
const name = columnName(coordinates)
const prevColumnRocks = columnRocks.has(name) ? columnRocks.get(name) : []
columnRocks.set(name, [...prevColumnRocks, { item, line: coordinates[0] }])
}
return item
}
Para “mover” as pedras para a extremidade norte, foi implementada uma função que passava em cada coluna e buscava as pedras da coluna de forma ordenada. Na sequência as pedras eram movidas (seus índices) para a extremidade norte, respeitando um offset prévio, caso existente que se movia conforme as pedras eram colocadas na parte norte ou uma pedra cúbica fosse encontrada.
const platform = Square({
data,
itemCallbackFn: buildColumnRocksMapCallbackFn,
})
const [maxRow, maxCol] = platform.getMaxLimits()
const MAX_LOAD = maxRow
const columnsLoad = new Map()
for (const [columnName, values] of columnRocks) {
const columnItemsLoad = []
let columnOffset = 0
for (const rock of values) {
const { item, line } = rock
if (item === TILES.ROUND_ROCKS) {
const columnLoad = MAX_LOAD - columnOffset
columnItemsLoad.push(columnLoad)
}
if (item === TILES.CUBE_ROCKS) {
columnOffset = line
}
columnOffset += 1
}
columnsLoad.set(columnName, columnItemsLoad)
}
Foi também criada uma lista que guardava a “carga” (load) que estava sendo aplicada na extremidade norte chamada columnLoad. Por final, bastava somar os elementos dessa lista e temos a solução do desafio!
Ao liberar a segunda parte do desafio, agora será necessário realizar um “giro” em todas as direções: norte, oeste, sul e leste! A solução é encontrar o valor de “carga” (load) das pedras na plataforma após a execução de 1000000000 ciclos.
O valor é realmente alto: um bilhão de ciclos.
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!
Ao ler o valor que teria de ciclos já percebe-se que rodar um laço for até lá pode realmente demorar. Porém, em casos como esse, onde existe um universo limitado e possivelmente pequeno de opções a cada ciclo já que estamos realizando o mesmo movimento sequencial, talvez exista um ciclo dentro dos resultados possíveis e eles se repetem!
Como assim?!?
Um bom exemplo para esse momento é o famoso Cubo de Rubik ou “Cubo Mágico”: Um cubo que tem cores em cada face quebrada em 9 cubos menores. Ao girar o mesmo você pode “bagunçar” o mesmo e existe um algoritmo para resolver.
A questão é: Se você pegar um cubo completo e girar apenas um dos lados 4 vezes, sem mover mais nenhum lado, você chega ao estado inicial do Cubo: Completo. O pulo do gato aqui é que não importa o estado do cubo (completo ou não) se você girar um lado sem mover mais nada por 4 vezes, o Cubo volta ao estado que tinha quando você começou a girar.
Extrapolando isso: é possível que ao mover a plataforma sequencialmente em 4 direções por muitas vezes(um bilhão de vezes, talvez) entramos em um ciclo onde a plataforma só irá gerar estados já conhecidos.
Como não sabemos se ao iniciar já estamos em um ciclo temos que partir da premissa de que não estamos até encontrarmos um estado repetido.
E se encontrarmos um estado repetido?
Bom, devemos continuar a execução até encontrar o mesmo estado repetido novamente. Caso ocorra, significa que “fechamos o ciclo”.
let northLoadAfterCycles = 0
let prevRocks = ALL_ROCKS
const resultsMap = new Map()
let cycleSize = 0
let startCycleAt = 0
let startCycleItemKey = ''
for (let i = 0; i < MAX_CYCLES; i++) {
const prevState = getRocksMap({
rocks: prevRocks,
maxLimits: [maxRow, maxCol],
})
// in case we already passed over this state
if (resultsMap.has(prevState)) {
if (startCycleAt > 0 && startCycleItemKey === prevState) {
cycleSize = i - startCycleAt
break
}
if (startCycleAt === 0) {
startCycleAt = i
startCycleItemKey = prevState
}
const { nextRocksState, northLoadValue } = resultsMap.get(prevState)
prevRocks = nextRocksState
northLoadAfterCycles = northLoadValue
continue
}
const finalState = spinCube() // code ommited!
const actualItemLoadsValue = getNorthLoadFromRocks({
rocks: finalState,
maxValue: maxRow,
})
northLoadAfterCycles = actualItemLoadsValue
if (!resultsMap.has(prevState)) {
resultsMap.set(prevState, {
nextRocksState: eastTiltRocks,
northLoadValue: actualItemLoadsValue,
})
}
prevRocks = eastTiltRocks
}
Caso nenhum ciclo seja encontrado, iremos gerar estados para cada uma das iterações. Caso um ciclo seja encontrado, devemos calcular qual será o estado final da plataforma baseado no ponto que paramos a execução!
if (cycleSize > 0) {
const leftIterations = MAX_CYCLES - startCycleAt
const totalFullIterations = Math.floor(leftIterations / cycleSize)
const stopItem = leftIterations - totalFullIterations * cycleSize - 1
let itemKey = startCycleItemKey
const { nextRocksState, northLoadValue } = resultsMap.get(itemKey)
let prevRocks = nextRocksState
let loadValue = northLoadValue
for (let i = 0; i < stopItem; i++) {
const prevState = getRocksMap({
rocks: prevRocks,
maxLimits: [maxRow, maxCol],
})
const { nextRocksState, northLoadValue } = resultsMap.get(prevState)
prevRocks = nextRocksState
loadValue = northLoadValue
}
northLoadAfterCycles = loadValue
}
Ainda será necessário executar do ponto inicial do ciclo e de onde a execução pausou previamente até o ponto final. A questão é que os estados nesse meio se repetem de forma sequencial e previsível!
Usando essa abordagem, não precisamos esperar até a última iteração e cortamos uma boa parte dessa execução apenas usando o conhecimento de um Cubo Mágico!
O resultado final é, assim como na primeira parte, a carga que vai incidir sobre a extremidade norte da plataforma. Para ela, já temos uma função de cálculo que pode ser reaproveitada da primeira parte.
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: