Advent of Code 2023 Day 08: Haunted Wasteland

Cover Photo

Foto de Capa gerada por IA

Algumas horas a dentro da viagem uma tempestade de areia se aproximava no horizonte. Ao tentar avisar a Elfa a respeito, ela havia sumido! A Elfa tinha acabado de avisar sobre os perigos de fantasmas nessa região.

Assim que você começa a olhar nas bolsas junto ao camelo, você percebe uma com nome de maps e resolve dar uma olhada. Os dados ali contidos seriam seu input:um dos documentos contém uma lista de instruções e os outros contém informações sobre um tipo de “rede” com nomes para cada um dos nodos da rede.

Contexto específico

Como mencionado, as instruções são de dois tipos: L ou R indicando que você precisa virar para a esquerda ou direita, respectivamente. Já os documentos com a rede de nodos possui uma sequência no formato:

<actual-node>: (<left-node> <right-node>)

Seu desafio é contar quantos movimentos você precisa fazer seguindo as instruções e repetindo elas ao chegar no fim dos mesmos para ir do nodo AAA ao nodo ZZZ.

Resolução Parte 1

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

Para a primeira parte pensei em resolver de forma simples: começar pelo nodo AAA iterando sobre o mapa de nodos contando os movimentos (moves) até chegar no nodo ZZZ.

const START = 'AAA'
const END = 'ZZZ'
const MOVES = { left: 'L', right: 'R' }
const countMovesToEnd = ({ nodeMap, instructions }) => {
  const instructionsList = instructions.split('')

  let actualNode = START
  let moves = 0
  let i = 0
  while (actualNode !== END) {
    const { left, right } = nodeMap.get(actualNode)

    actualNode = instructionsList[i] === MOVES.left ? left : right

    i = (i + 1) % instructionsList.length

    moves += 1
  }

  return moves
}

Para minha surpresa, essa abordagem completou a primeira parte do desafio!

Porém, ao finalizar as instruções você praticamente não se moveu do seu ponto inicial no deserto. Nesse momento você recorda da Elfa falando dos fantasmas e percebe que o mapa pode ser na verdade para fantasmas e não para humanos!

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!

Enquanto passava o olho pelo mapa, você percebe que o número de nodos terminados em A é o mesmo que os terminados em Z e imagina que se você for um fantasma você poderia começar em todos os nodos terminados em A e iterar até chegar em todos os nodos terminados em Z! (Afinal, fantasmas não respeitam as leis da física não é mesmo?)

Para resolver a segunda parte do desafio escrevi uma variação do código da parte um que iterava em todos os nodos terminados em A até os terminados em Z. Ao rodar o programa, fiquei olhando para tela e pensando que essa ideia talvez não fosse a mais performática…

Passados mais ou menos 10 segundos de execução, interrompi e rascunhei algumas opções. Percebi então que no exemplo mostrado pelo site o resultado de passos era 6 e as ocorrências dos nodos terminados em Z era de 2 em 2 e 3 em 3. Existia uma correlação entre esses valores e o resultado 6: 2 * 3 = 6!

E se eu rodar a simulação até achar o número de passos de cada nodo inicial até o nodo final e multiplicar esses valores?

Implementei uma versão desse código e ao multiplicar fui surpreendido por um número em notação float que provavelmente ultrapassou o número máximo de representação numérico possível: Number.MAX_SAFE_INTEGER que é 9007199254740991 (em minha máquina).

Ao pensar um pouco mais a respeito, percebi que talvez poderia multiplicar apenas os Mínimo Múltiplo Comuns (MMC ou LCM em inglês) dos números encontrados. Foi então que implementei os cálculos e coloquei dentro do diretório de utils/ com os nomes de arquivo array.js e number.js.

Modifiquei também um pouco a função de contagem de movimentos até o passo final para receber os parâmetros startingNode e isEndNodeValidationCallbackFn responsáveis por fornecer o nodo inicial e a validação de nodo final.

const countMovesToEnd = ({
  nodeMap,
  instructions,
  startingNode = START,
  isEndNodeValidationCallbackFn = isEndNode,
}) => {
  // ...
}

const countGhostMovesToEnd = ({ nodeMap, instructions }) => {
  const startingNodes = getGhostStartingNodes(nodeMap)
  const allNodeMoves = []

  for (const startingNode of startingNodes) {
    const nodeMoves = countMovesToEnd({
      nodeMap,
      instructions,
      startingNode,
      isEndNodeValidationCallbackFn: isGhostEndingNode,
    })

    allNodeMoves.push(nodeMoves)
  }

  const movesToEnd = leastCommonMultipleBetweenList(allNodeMoves)

  return movesToEnd
}

Com essa implementação foi criada uma lista de movimentos até o último nodo (movesToEnd) passada para a função leastCommonMultipleBetweenList() para encontrar o MMC dos valores da mesma.

A solução para a parte dois do desafio foi justamente o MMC resultante!

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: