Advent of Code 2023 Day 21: Step Counter

Cover Photo

Foto de Capa gerada por IA

Após arrumar as máquinas, a areia está sendo produzida na Desert Island!

Enquanto espera, os elfos ouviram que você é bom em resolver desafios e resolvem te pedir ajuda com outro desafio: Um dos elfos usa um contador de passos e quer saber até onde ele conseguirá chegar em seu jardim caso ande apenas os passos faltantes do dia: 64.

Contexto específico

Seu input é o mapa do jardim mostrando o ponto inicial do elfo e quantas pedras existem no mesmo. Seu desafio é encontrar quais são todos os passos que ele pode dar vertical e horizontalmente em seu jardim, andando sempre 1 passo de cada vez.

Vale mencionar que ele não pode andar para espaços que contenham pedras e a cada “rodada” é preciso considerar todas as opções possíveis de movimentação.

Resolução Parte 1

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

Visto que temos um “mapa” novamente escolhi usar o Square() que foi usado em outros desafios (e pode ser visto neste arquivo do GitHub).

A ideia central da solução é criar uma lista de pontos (x, y) que o elfo poderia estar e iterar a cada passo sobre essa lista, encontrando todos os próximos pontos para serem colocados nessa lista, novamente.

Algumas funções auxiliares foram criadas para ajudar nessa tarefa:

isValidPositionOfSquare() - uma high-order function (HOF) que retorna uma função que valida se os pontos são ou não uma pedra (#)
customItemCallbackFn() - salva o STARTING_POINT, quando encontrado no mapa

const customItemCallbackFn = ({ item, coordinates }) => {
  if (item === STARTING_POSITION) {
    STARTING_POINT = coordinates
  }

  return item
}

const isValidPositionOfSquare = (square) => (point) => {
  const [i, j] = point

  return square[i][j] !== ROCK
}

O código para a solução se baseia na lista de pontos e adicionando pontos nessa lista das posições como mostrado a seguir

let count = STARTING_STEPS_PART_1
let possiblePositions = [STARTING_POINT]

while (count !== 0) {
  let nextPossibleSteps = []

  for (const possiblePosition of possiblePositions) {
    const adjascentPoints =
      gardenPlots.getLineAndColumnAdjascentPoints(possiblePosition)

    adjascentPoints.forEach((point) => {
      const pointStr = point.join(',')
      if (isValidPosition(point) && !nextPossibleSteps.includes(pointStr)) {
        nextPossibleSteps.push(pointStr)
      }
    })
  }

  possiblePositions = nextPossibleSteps.map((point) => {
    const [i, j] = point.split(',')
    return [Number(i), Number(j)]
  })
  count -= 1
}

Ao final, o tamanho da lista possiblePositions é a solução do desafio. E novamente a parte dois fica disponível: segundo o elfo o mapa é “infinito” para todos os lados, repetindo o mapa informado pelo input e o número de passos faltantes são 26501365.

Nota: Ainda estou resolvendo a segunda parte desse 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: