Skip to main content

Day 24: Blizzard Basin

Puzzle description​

https://adventofcode.com/2022/day/24

Solution​

Today's problem is similar to Day 12, where we need to find our way through a maze. It's made more challenging by impassable blizzards moving through the maze. We can use a similar approach to that of Day 12 still, but we'll improve a little bit further by using A* search instead of a standard breadth first search.

We'll need some kind of point and a few functions that are useful on the 2d grid. A simple tuple (Int, Int) will suffice, and we'll add the functions as extension methods. We'll use Manhattan distance as the A* heuristic function, and we'll need the neighbours in cardinal directions.

type Coord = (Int, Int)
extension (coord: Coord)
  def x = coord._1
  def y = coord._2
  def up = (coord.x, coord.y - 1)
  def down = (coord.x, coord.y + 1)
  def left = (coord.x - 1, coord.y)
  def right = (coord.x + 1, coord.y)
  def cardinals = Seq(coord.up, coord.down, coord.left, coord.right)
  def manhattan(rhs: Coord) = (coord.x - rhs.x).abs + (coord.y - rhs.y).abs
  def +(rhs: Coord) = (coord.x + rhs.x, coord.y + rhs.y)

Before we get to the search, let's deal with the input.

case class Blizzard(at: Coord, direction: Coord)

def parseMaze(in: Seq[String]) =
  val start = (in.head.indexOf('.'), 0) // start in the empty spot in the top row
  val end = (in.last.indexOf('.'), in.size - 1) // end in the empty spot in the bottom row
  val xDomain = 1 to in.head.size - 2 // where blizzards are allowed to go
  val yDomain = 1 to in.size - 2
  val initialBlizzards =
    for
      y <- in.indices
      x <- in(y).indices
      if in(y)(x) != '.' // these aren't blizzards!
      if in(y)(x) != '#'
    yield in(y)(x) match
      case '>' => Blizzard(at = (x, y), direction = (1, 0))
      case '<' => Blizzard(at = (x, y), direction = (-1, 0))
      case '^' => Blizzard(at = (x, y), direction = (0, -1))
      case 'v' => Blizzard(at = (x, y), direction = (0, 1))

  ??? // ...to be implemented

Ok, let's deal with the blizzards. The blizzards move toroidally, which is to say they loop around back to the start once they fall off an edge. This means that, eventually, the positions and directions of all blizzards must loop at some point. Naively, after xDomain.size * yDomain.size minutes, every blizzard must have returned to it's original starting location. Let's model that movement and calculate the locations of all the blizzards up until that time. With it, we'll have a way to tell us where the blizzards are at a given time t, for any t.

def move(blizzard: Blizzard, xDomain: Range, yDomain: Range) =
  blizzard.copy(at = cycle(blizzard.at + blizzard.direction, xDomain, yDomain))

def cycle(coord: Coord, xDomain: Range, yDomain: Range): Coord = (cycle(coord.x, xDomain), cycle(coord.y, yDomain))

def cycle(n: Int, bounds: Range): Int =
  if n > bounds.max then bounds.min // we've fallen off the end, go to start
  else if n < bounds.min then bounds.max // we've fallen off the start, go to the end
  else n // we're chillin' in bounds still

We can replace the ??? in parseMaze now. And we'll need a return type for the function. We can cram everything into a Maze case class. For the blizzards, we actually only need to care about where they are after this point, as they'll prevent us from moving to those locations. We'll throw away the directions and just keep the set of Coords the blizzards are at.

case class Maze(xDomain: Range, yDomain: Range, blizzards: Seq[Set[Coord]], start: Coord, end: Coord)

def parseMaze(in: Seq[String]): Maze =
  /* ...omitted for brevity... */
  def tick(blizzards: Seq[Blizzard]) = blizzards.map(move(_, xDomain, yDomain))
  val allBlizzardLocations = Iterator.iterate(initialBlizzards)(tick)
      .take(xDomain.size * yDomain.size)
      .map(_.map(_.at).toSet)
      .toIndexedSeq

  Maze(xDomain, yDomain, allBlizzardLocations, start, end)

But! We can do a little better for the blizzards. The blizzards actually cycle for any common multiple of xDomain.size and yDomain.size. Using the least common multiple would be sensible to do the least amount of computation.

def gcd(a: Int, b: Int): Int = if b == 0 then a else gcd(b, a % b)
def lcm(a: Int, b: Int): Int = a * b / gcd(a, b)
def tick(blizzards: Seq[Blizzard]) = blizzards.map(move(_, xDomain, yDomain))
val allBlizzardLocations = Iterator.iterate(initialBlizzards)(tick)
    .take(lcm(xDomain.size, yDomain.size))
    .map(_.map(_.at).toSet)
    .toIndexedSeq

Great! Let's solve the maze.

import scala.collection.mutable
case class Step(at: Coord, time: Int)

def solve(maze: Maze): Step =
  // order A* options by how far we've taken + an estimated distance to the end
  given Ordering[Step] = Ordering[Int].on((step: Step) => step.at.manhattan(maze.end) + step.time).reverse
  val queue = mutable.PriorityQueue[Step]()
  val visited = mutable.Set.empty[Step]

  def inBounds(coord: Coord) = coord match
    case c if c == maze.start || c == maze.end => true
    case c => maze.xDomain.contains(c.x) && maze.yDomain.contains(c.y)

  queue += Step(at = maze.start, time = 0)
  while queue.head.at != maze.end do
    val step = queue.dequeue
    val time = step.time + 1
    // where are the blizzards for our next step? we can't go there
    val blizzards = maze.blizzards(time % maze.blizzards.size)
    // we can move in any cardinal direction, or chose to stay put; but it needs to be in the maze
    val options = (step.at.cardinals :+ step.at).filter(inBounds).map(Step(_, time))
    // queue up the options if they are possible; and if we have not already queued them
    queue ++= options
      .filterNot(o => blizzards(o.at)) // the option must not be in a blizzard
      .filterNot(visited) // avoid duplicate work
      .tapEach(visited.add) // keep track of what we've enqueued

  queue.dequeue

That's pretty much it! Part 1 is then:

def part1(in: Seq[String]) = solve(parseMaze(in)).time

Part 2 requires solving the maze 3 times. Make it to the end (so, solve part 1 again), go back to the start, then go back to the end. We can use the same solve function, but we need to generalize a bit so we can start the solver at an arbitrary time. This will allow us to keep the state of the blizzards for subsequent runs. We actually only need to change one line!

def solve(maze: Maze, startingTime: Int = 0): Step =
  /* the only line we need to change is... */
  queue += Step(at = maze.start, time = startingTime)

Then part 2 requires calling solve 3 times. We need to be a little careful with the start/end locations and starting times.

def part2(in: Seq[String]) =
  val maze = parseMaze(in)
  val first = solve(maze)
  val second = solve(maze.copy(start = maze.end, end = maze.start), first.time)
  solve(maze, second.time).time

That's Day 24. Huzzah!

Solutions from the community​

Share your solution to the Scala community by editing this page.