Skip to main content

Day 11: Dumbo Octopus

by @tgodzik

Puzzle description​

https://adventofcode.com/2021/day/11

Final Solution​

trait Step:
  def increment: Step
  def addFlashes(f: Int): Step
  def shouldStop: Boolean
  def currentFlashes: Int
  def stepNumber: Int

case class MaxIterStep(currentFlashes: Int, stepNumber: Int, max: Int) extends Step:
  def increment = this.copy(stepNumber = stepNumber + 1)
  def addFlashes(f: Int) = this.copy(currentFlashes = currentFlashes + f)
  def shouldStop = stepNumber == max

case class SynchronizationStep(
    currentFlashes: Int,
    stepNumber: Int,
    maxChange: Int,
    lastFlashes: Int
) extends Step:
  def increment = this.copy(stepNumber = stepNumber + 1)
  def addFlashes(f: Int) =
    this.copy(currentFlashes = currentFlashes + f, lastFlashes = currentFlashes)
  def shouldStop = currentFlashes - lastFlashes == maxChange

case class Point(x: Int, y: Int)
case class Octopei(inputMap: Map[Point, Int]):

  @tailrec
  private def propagate(
      toVisit: Queue[Point],
      alreadyFlashed: Set[Point],
      currentSituation: Map[Point, Int]
  ): Map[Point, Int] =
    toVisit.dequeueOption match
      case None => currentSituation
      case Some((point, dequeued)) =>
        currentSituation.get(point) match
          case Some(value) if value > 9 && !alreadyFlashed(point) =>
            val propagated =
              Seq(
                point.copy(x = point.x + 1),
                point.copy(x = point.x - 1),
                point.copy(y = point.y + 1),
                point.copy(y = point.y - 1),
                point.copy(x = point.x + 1, y = point.y + 1),
                point.copy(x = point.x + 1, y = point.y - 1),
                point.copy(x = point.x - 1, y = point.y + 1),
                point.copy(x = point.x - 1, y = point.y - 1)
              )
            val newSituation = propagated.foldLeft(currentSituation) {
              case (map, point) =>
                map.get(point) match
                  case Some(value) => map.updated(point, value + 1)
                  case _       => map
            }
            propagate(
              dequeued.appendedAll(propagated),
              alreadyFlashed + point,
              newSituation
            )
          case _ =>
            propagate(dequeued, alreadyFlashed, currentSituation)
  end propagate

  def simulate(step: Step) = simulateIter(step, inputMap)

  @tailrec
  private def simulateIter(
      step: Step,
      currentSituation: Map[Point, Int]
  ): Step =
    if step.shouldStop then step
    else
      val incremented = currentSituation.map { case (point, value) =>
        (point, value + 1)
      }
      val flashes = incremented.collect {
        case (point, value) if value > 9 => point
      }.toList
      val propagated = propagate(Queue(flashes*), Set.empty, incremented)
      val newFlashes = propagated.collect {
        case (point, value) if value > 9 => 1
      }.sum
      val zeroed = propagated.map {
        case (point, value) if value > 9 => (point, 0)
        case same            => same
      }
      simulateIter(step.increment.addFlashes(newFlashes), zeroed)
  end simulateIter

end Octopei

def part1(input: String) =
  val octopei = parse(input)
  val step = MaxIterStep(0, 0, 100)
  octopei.simulate(step).currentFlashes

def part2(input: String) =
  val octopei = parse(input)
  val step = SynchronizationStep(0, 0, octopei.inputMap.size, 0)
  octopei.simulate(step).stepNumber

Run it in the browser​

Part 1​

Part 2​

Run it locally​

You can get this solution locally by cloning the scalacenter/scala-advent-of-code repository.

$ git clone https://github.com/scalacenter/scala-advent-of-code
$ cd scala-advent-of-code

You can run it with scala-cli.

$ scala-cli 2021 -M day11.part1
The answer is: 1673

$ scala-cli 2021 -M day11.part2
The answer is: 279

You can replace the content of the input/day11 file with your own input from adventofcode.com to get your own solution.

Solutions from the community​

Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format