Advent of Code 2023 Day 12: Hot Springs

Cover Photo

Foto de Capa gerada por IA

Finalmente você e o Elfo pesquisador chegam as águas termais! Entretanto, descobrem que pela falta de Lava eles estão fechados.

Ao questionar sobre a Gear Island e as peças faltando na Desert Island, o Elfo que trabalha nas águas termais menciona que talvez consiga colocar todo o fluxo de Lava para uma única piscina de água termal e pode te “lançar” até a Gear Island.

Porém, você precisa descobrir uma piscina que funcione antes para ter certeza que vai dar certo.

Contexto específico

Existe um relatório feito a respeito do estado das piscinas(springs) de águas termais, mas ele está danificado. Porém, apenas uma das partes está danificada, a outra está intacta!

No relatório existem 2 partes:

  • a primeira que informam quais springs estão danificadas (#) ou operacionais (.)
  • a segunda que informa quantas springs estão danificadas (#) naquela linha
#.#.### 1,1,3

Na primeira parte é onde se encontram os problemas visto que alguns caracteres do seu input foram substituídos por ? e podem ser springs danificadas ou operacionais. Para descobrir, a segunda parte da linha menciona os grupos que estão danificados, sendo que eles são separados sempre por uma spring funcional.

Seu desafio é descobrir a soma total de possibilidades de arranjos de cada linha tornando a primeira parte válida.

Resolução Parte 1

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

Em um primeiro momento pensei em abordar cada linha como bits (0s e 1s) e até comecei a esboçar uma solução nessa direção. Então, chegou um momento onde eu estava cada vez mais confuso com as possibilidades e como iria resolver cada detalhe e optei por novamente, primeiro fazer a solução simples funcionar.

Para tal, decidi que iria

  • gerar todas as possíveis combinações
  • filtrar apenas as que tivessem a mesma combinação de grupos de springs da segunda parte da linha
const lines = data.split('\n').slice(0, -1)

const springsData = buildSpringsData(lines)

let possibleSpringsOptions = 0
for (const springsDataLine of springsData) {
  const options = buildSpringOptions({ springsLine: springsDataLine })

  const { damagedSizesList } = springsDataLine

  const validOptions = filterValidOptions({ damagedSizesList, options })
  possibleSpringsOptions += validOptions.length
}

Usando as funções auxiliares buildSpringOptions() e filterValidOptions() foi possível realizar as duas tarefas e apesar do tempo de execução ficar próximo dos 10 segundos, a solução do desafio foi obtida.

A implementação das funções auxiliares está neste arquivo do repositório no GitHub.

Assim que a parte 2 fica disponível é relatado que na verdade o registro dos springs estava “dobrado” e que cada linha de springs é na realidade 5 vezes maior!

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: