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
- Solution of @tOverney.
- Solution of Jan Boerman.
- Solution of @FlorianCassayre.
Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format