Advent of Code 2023 Day 16: The Floor Will Be Lava

Cover Photo

Foto de Capa gerada por IA

Com o raio de luz completamente focado e usando todo o poder a Rena natalina agora conduz você ao Lava Production Facility: Uma caverna no coração da montanha.

Lá dentro existe uma “engenhoca” cheia de espelhos e refletores bidimensionais que está recebendo toda a luz que chega. É ali que a luz é convertida em calor!

Contexto específico

Seu input é uma estrutura 2d com os seguintes caracteres e suas respectivas representações:

  • . - espaço vazio
  • / e \ - espelhos
  • - e | - divisores

Cada raio que passa pelos espelhos ou divisores tem sua direção modificada. Para o caso dos divisores, ele é “separado” se sua entrada não for pelas pontas de saída (que fazem um bypass).

Já para os espelhos os raios de luz tem sua direção modificada em 90 graus, dependendo da origem que chegam.

Seu desafio é contar quantos espaços do mapa ficam iluminados pelo raio de luz considerando todas as voltas e modificações que podem vir a ocorrer com os espelhos e divisores.

Resolução Parte 1

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

Caso tenha acompanhado os outros desafios já deve imaginar a estrutura que será usada para iniciar a resolução desse desafio: o Módulo Square() (vide esse arquivo).

A ideia aqui é montar um mapa onde contamos quais itens tem o raio de luz passando por eles para então contar quantos desses itens estão iluminados. A estrutura do item fica da seguinte forma:

const contraptionItem = {
  energized: false,
  reflected: false,
  coordinates,
  item, // o caractere em questão
}

Para iterar nos itens, nos baseamos em uma fonte de luz (source) e uma direção (direction) de entrada no item. É criado um laço que fica responsável por

  • marcar o item atual como energizado
  • buscar a próxima fonte de luz baseado no item e na fonte de entrada atuais
  • validar se a fonte foi “dividida”
    • caso tenha sido dividida, validar se a luz já passou pelo item atual
    • caso não tenha passado ainda, marcar o item atual como refletido
    • chamar a função do laço para cada nova direção e aguardar a execução
    • interromper o laço mais externo e encerrar a execução
  • se a fonte não foi “dividida”
    • atualizar a fonte de luz atual e as coordenadas

Assim, evita-se que loops infinitos fiquem executando e conseguimos encontrar todos os pontos de luz. O código para esse algoritmo está no arquivo do repositório GitHub na função auxiliar de nome fireLightBeam().

Foram criadas também algumas estruturas para o auxílio na descoberta de onde o raio de luz iria incidir na próxima iteração. A função auxiliar getNextSourceDirection() foi criada e ela se baseia na sourceDirection atual e no mapItem que estamos iterando

const getNextSourceDirection = ({ sourceDirection, actualItem }) => {
  if (actualItem.item === ITEM.SPLITER_VERTICAL) {
    if (verticalLightSource.includes(sourceDirection.label)) {
      return [sourceDirection]
    }
    return [SOURCE_LIGHT.DOWN, SOURCE_LIGHT.UP]
  }

  if (actualItem.item === ITEM.SPLITER_HORIZONTAL) {
    if (horizontalLightSource.includes(sourceDirection.label)) {
      return [sourceDirection]
    }
    return [SOURCE_LIGHT.RIGHT, SOURCE_LIGHT.LEFT]
  }

  if ([ITEM.MIRROR_LEFT, ITEM.MIRROR_RIGHT].includes(actualItem.item)) {
    return MIRROR_NEXT_DIRECTIONS[actualItem.item][sourceDirection.label]
  }

  // default case: actualItem.item === ITEM.EMPTY_SPACE
  return [sourceDirection]
}

Com todos os itens agora “energizados”, é possível iterar sobre cada item e somar os que estão energizados para encontrar a solução do desafio

const sumEnergized = (square) =>
  square.reduce(
    (acc, line) =>
      acc + line.reduce((acc2, item) => (item.energized ? acc2 + 1 : acc2), 0),
    0
  )

Com a primeira parte do desafio pronta, a segunda parte fica habilitada e agora é necessario descobrir qual o ponto de entrada que vai resultar no maior número de itens energizados.

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!

Por sorte, já havia implementado a função de laço com a seguinte assinatura

const fireLightBeam = ({
  square,
  startingPoint = [0, 0],
  startingSourceDirection = SOURCE_LIGHT.RIGHT,
}) => { /* ... */ }

Para descobrir qual o melhor ponto de entrada, bastava então iterar sobre todos os pontos de entrada nas extremidades do mapa, tomando cuidado para passar o startingSourceDirection das extremidades das pontas com as duas possibilidades de entrada de luz.

const testFireLightBeam = ({
  data,
  startingPoint,
  startingSourceDirection,
}) => {
  const localContraption = Square({
    data,
    itemCallbackFn: buildContraptionItemsCallbackFn,
  })

  const localContraptionSquare = localContraption.getSquare()
  fireBeam({
    square: localContraptionSquare,
    startingPoint,
    startingSourceDirection,
  })

  return sumEnergized(localContraptionSquare)
}

Validando todos os pontos de entrada e todas as possibilidades de fonte de luz é possível chegar ao resultado final que será a soução do desafio!

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: