Advent of Code 2023 Day 06: Wait For It

Cover Photo

Foto de Capa gerada por IA

Usando a Balsa do dia anterior é possível chegar na próxima ilha Island Island. Após garimpar algumas informações foi possível observar um cartaz sobre uma competição de barcos que despertou seu interesse. Para sua felicidade a premiação seria uma viagem com tudo pago para onde você precisa ir: Desert Island!

Você se inscreve quase que instantaneamente e mal pode esperar por tentar a sorte.

Contexto específico

O Elfo responsável pela competição te informa que a mesma é “um pouco diferente” das competições tradicionais. Todos vão ganhar um pequeno barco com um botão que quando pressionado faz o barco “carregar” seu motor. Quando o botão é solto, o barco vai se mover a uma velocidade de 1 mm/ms (milimetros por segundo) para cada ms pressionado. O ganhador é o barco que for mais longe ao final do tempo disponível.

Também acontecerão um número n de “baterias”, onde você terá um tempo fixo para pressionar e para o barco se mover. Caso o tempo esgote e você ainda esteja pressionando o botão você vai ter o valor percorrido de distância de 0, como se não houvesse sequer pressionado o botão.

Seu input é uma lista com o tempo de cada bateria e o recorde para aquele tempo.

Para resolver o desfio, é preciso encontrar quantos ms são possíveis de pressionar o botão em cada bateria para que a distância recorde seja batida e multiplicar os valores entre si.

Resolução Parte 1

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

Pensando em opções, notei que poderia resolver esse desafio com:

  • Busca Binária para encontrar cada limite do intervalo [min, max] para cada bateria
  • “Força Bruta” para passar por todos os elementos validando suas distâncias

No começo optei por tentar pela primeira abordagem mas por 2 vezes esbarrei em complexidade na visualização do problema e resolvi partir para segunda opção: “Força Bruta”.

Primeiro precisei quebrar o input em corridas (races) com seus tempos e recordes

const fillRacesData = (lines) => {
  const raceTimes = lines[0].match(/\d+/g)
  const raceRecords = lines[1].match(/\d+/g)

  const races = []
  for (let i = 0; i < raceTimes.length; i++) {
    races.push([raceTimes[i], raceRecords[i]])
  }

  return races
}

Percebi que precisava isolar um pouco da lógica de um barco (Boat) e construi uma estrutura simples para isso que seria de grande ajuda durante a resolução do desafio.

const Boat = ({ buttonHoldTime }) => {
  return {
    speed: buttonHoldTime, // 1 mm / ms
    travelledDistance: (remainingRaceTime) =>
      remainingRaceTime * buttonHoldTime,
  }
}

Na sequência, iterando sobre essa lista bastava conseguir a lista de valores em ms que bateriam os recordes de cada corrida e multiplicar os valores dessa lista. Respectivamente a função findHoldTimesAboveRecord() e usada para conseguir os valores da lista holdTimesPerRace dentro da função getHoldTimesMultiplicationFromRaces().

const findHoldTimesAboveRecord = (race) => {
  const [time, record] = race

  const holdTimes = []
  for (let i = 0; i <= time; i++) {
    const boat = Boat({ buttonHoldTime: i })
    const distance = boat.travelledDistance(time - i)

    if (distance > record) {
      holdTimes.push(i)
    }
  }

  return holdTimes
}

const getHoldTimesMultiplicationFromRaces = (lines) => {
  const races = fillRacesData(lines)

  const holdTimesPerRace = []

  for (const race of races) {
    const holdTimes = findHoldTimesAboveRecord(race)

    holdTimesPerRace.push(holdTimes.length)
  }

  const holdTimesMultiplication = holdTimesPerRace.reduce(
    (acc, holdTimes) => acc * holdTimes,
    1
  )

  return holdTimesMultiplication
}

Ao final, bastava multiplicar os valores dos tamanhos de cada lista e usei o método Array.reduce() para isso.

Sabendo do valor e resolvendo o desafio o Elfo te informa que na verdade não eram tempos e recordes de corridas diferentes mas sim que os caracteres estavam espaçados de forma incorreta e existia apenas 1 corrida e 1 recorde, juntando todos os números ali presentes em cada linha do seu input.

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!

Como já havia tomado a liberdade de partir para a solução de “Força Bruta” na parte 1, resolvi tentar fazer o mesmo na parte 2 e confesso que me surpreendi. Apesar de ter que esperar cerca de 2 a 3 segundos para o resultado aparecer em minha tela (o que me deixou com um pouco de medo) o desafio foi resolvido também.

Ao invés de iterar sobre uma lista de valores, agora o valor final era apenas o tamanho de uma única lista. O demorado seria encontrar essa lista (que já estava implementado na parte 1!).

Assim, a função auxiliar getHoldTimesMultiplicationFromSingleRace() foi escrita e ela apenas quebra o input em uma única corrida e encontra os valores que batem o recorde:

const getHoldTimesMultiplicationFromSingleRace = (lines) => {
  const race = fillSingleRaceData(lines)

  const holdTimes = findHoldTimesAboveRecord(race)

  return holdTimes.length
}

Ao final, o tamanho dessa lista é a solução para a parte 2 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: