Advent of Code 2023 Day 11: Cosmic Expansion

Cover Photo

Foto de Capa gerada por IA

Enquanto seguia os passos para as águas termais, você encontra um observatório! Ao se aproximar você encontra um Elfo pesquisador que aceita te levar para as águas termais. Ele só precisa encerrar uma parte da pesquisa dele relacionada a Expansão Cósmica.

Para acelerar as coisas você decide ajudar ele nessa pesquisa. Todos os dados compilados por ele estão em uma única imagem gigante, que é seu input. Ela contém espaços vazios e galáxias.

Contexto específico

A ideia por trás do desafio de hoje é que o espaço está expandindo constantemente e as leituras feitas já estão “defasadas”. Caso a linha ou a coluna do input tenha apenas espaços vazios, e por consequência nenhuma galáxia, esses dados na verdade devem ser “re-calculados”, expandidos.

Para encontrar a solução é preciso também calcular a distância entre as galáxias considerando essa expansão e somar todas as distâncias.

A respeito da leitura, as galáxias são os caracteres # e os espaços vazios são os caracteres ..

Resolução Parte 1

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

Novamente o uso do input como um “mapa” me inclinou a utilizar o Módulo Square(), mencionado na solução dia 10 com seu código nesse arquivo.

Usando essa abstração, bastava passar por todos os espaços e caso a linha/coluna fosse apenas de espaços vazios, duplicar a mesma. Na sequência, remonta-se o input, agora com os espaços expandidos, monta-se uma lista de galáxias e calcula-se as distâncias entre elas!

O código em questão foi refatorado para que atendesse também as necessidades da parte 2, que ficou aberta assim que a primeira parte foi concluída.

Para a parte 2, ao mostrar o resultado ao Elfo ele percebe que existe algo errado: As galáxias são muito mais antigas do que ele havia estimado! Agora, cada espaço expandido deveria ser substituído por 1000000 (um milhão!) espaços vazios.

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!

Percebi que minha implementação não seria a melhor abordagem visto que o número de colunas/linhas seria muito grande e a visualização seria ruim. Decidi então modificar a abordagem para caso a linha/coluna seja um espaço expandido ela seria substituida por um vórtice (0) e todas as medições que passassem por ele teriam adicionados a sua distância o valor de 1000000 (um milhão).

const expandedSpaceWithVortexData = expandSpaceWithVortex(data)

const spaceWithVortex = Square({
  data: expandedSpaceWithVortexData,
  itemCallbackFn: buildCosmicEntityWithVortex,
})

let sumOfShortestPaths = 0
for (let i = 0; i < galaxiesListWithVortex.length; i++) {
  for (let j = i + 1; j < galaxiesListWithVortex.length; j++) {
    const sumBetween = getCosmicDistanceBetweenWithVortex({
      space: spaceWithVortex,
      galaxyA: galaxiesListWithVortex[i],
      galaxyB: galaxiesListWithVortex[j],
      vortexSize: PART_2_VORTEX_SIZE,
    })

    sumOfShortestPaths += sumBetween
  }
}

O código final fica dessa forma:

Expande-se o espaço substituindo espaços por vórtices onde faz sentido
Cria-se o mapa (Square()) enquanto se preenche a lista de galáxias (galaxiesListWithVortex)
Encontra-se as distâncias entre cada galáxia da lista
É feita a soma de todas as distâncias

A soma final encontrada é a solução para o desafio! E com a solução de vórtice é possível usar qualquer tamanho de expansão, sendo possível usar o mesmo código para a parte 1 e a parte 2 do desafio. Se faz necessária a ressalva de apenas passar o tamanho vortexSize para a função de soma getCosmicDistanceBetweenWithVortex()!

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:

split()