Advent of Code 2023 Day 22: Sand Slabs

Cover Photo

Foto de Capa gerada por IA

Com toda a areia que estava caindo da Desert Island finalmente será possível filtrar a água.

Como sempre, ainda restam alguns problemas: A areia está caíndo em grandes blocos que estão formando uma torre de areia. É necessário tomar cuidado com quais blocos remover para não causar nenhum acidente!

Contexto específico

O primeiro desafio que usa 3 coordenadas finalmente apareceu! Os blocos estão descritos no seu input no formato de

x,y,z~x,y,z

onde o primeiro grupo de 3 coordenadas fazem referência ao ponto inicial do bloco de areia e o segundo grupo é o ponto final do mesmo bloco. Porém, a leitura dos blocos foi feita quando eles ainda estavam caindo e você precisa descobrir quais blocos que podem ou não ser removidos baseado onde os blocos vão estar quando estiverem no chão e formando a torre.

Existem algumas regras específicas como: um bloco pode ser suportado por qualquer ourtro bloco desde que esteja encostando por pelo menos 1 ponto e não importando o tamanho dos mesmos.

Resolução Parte 1

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

Para o desafio de hoje eu estava com algumas ideias e tentei implementar de diferentes maneiras mas sempre esbarrava no problema de que para o caso de testes funcionava mas para o caso do input meu resultado era sempre algum valor muito absurdo.

Foi então que eu recorri a thread de soluções do subreddit e encontrei um video citado lá do canal HyperNeutrino. Após assistir o video para a primeira parte, entendi que estava cometendo alguns erros e foi interessante relembrar conceitos de sobreposição e como tirar proveito deles.

Em suma, a solução contempla:

  • ler o input
  • ordenar a lista de blocos por coordenada z, visto que ela é a altura
  • “assentar” todos os blocos até que nenhum bloco esteja flutuando
  • ordenar a lista novamente, visto que a ordem de altura dos blocos pode ter mudado
  • criar uma estrutura que mapeia quais blocos sustentam outros blocos e quais blocos são sustentados por um bloco específico
  • validar quais blocos são sustentados por mais de um bloco e por consequência, podem ser removidos

Talvez uma das coisas que possa ser citada e que eu estava errando é a forma de validar se existe uma sobreposição (overlap) entre dois elementos. Visto que minha solução se baseia em cada linha ser convertida para dois arrays [x,y,z] de começo e final daquele bloco, a função auxiliar checkOverlaps() foi escrita da seguinte forma:

const checkOverlaps = (brickA, brickB) => {
  const [startA, endA] = brickA
  const [startB, endB] = brickB

  return (
    Math.max(startA[0], startB[0]) <= Math.min(endA[0], endB[0]) &&
    Math.max(startA[1], startB[1]) <= Math.min(endA[1], endB[1])
  )
}

Outro ponto válido de mencionar é o uso de um Array de Set()s para identificar os blocos que suportam e que são suportados por outros blocos:

const supports = Array.from({ length: bricks.length }, () => new Set())
const isSupportedBy = Array.from({ length: bricks.length }, () => new Set())

Neste caso, minha alternativa tinha sido utilizar um Map() com listas e validar cada ponto interno na lista: Uma solução muito menos performática!

Por final, com a primeira parte solucionada (e aprendizados novos), a segunda parte do desafio foi liberada e agora é necessário saber a soma total de quantos blocos vão se mover caso cada bloco seja removido e os outros sejam mantidos.

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: