Skip to main content

Day 17: Clumsy Crucible

by @stewSquared

Puzzle description​

https://adventofcode.com/2023/day/17

Solution Summary​

This is a classic search problem with an interesting restriction on state transformations.

We will solve this using Dijkstra's Algorithm to find a path through the grid, using the heat loss of each position as our node weights. However, the states in our priority queue will need to include more than just position and accumulated heat loss, since the streak of forward movements in a given direction affects which positions are accessible from a given state.

Since the restrictions on state transformations differ in part 1 and part 2, we'll model them separately from the base state transformations.

Framework​

First, we will need a Grid class to represent the possible positions, and store the heat at each position. It will be represented by a 2D vector:

case class Grid(grid: Vector[Vector[Int]]):
  val xRange = grid.head.indices
  val yRange = grid.indices

We can parse the input and store it in the Grid class. Each line is treated as a row, and each character in the row is treated as a single column, and required to be a digit:

def loadGrid(input: String): Grid =
  Grid:
    Vector.from:
      for line <- input.split("\n")
      yield line.map(_.asDigit).toVector

We can define some accessors to make it more convenient to work with a Grid that is available in the context.

def grid(using Grid) = summon[Grid].grid
def xRange(using Grid) = summon[Grid].xRange
def yRange(using Grid) = summon[Grid].yRange

Second, for convenience, let's introduce a class for presenting direction:

enum Dir:
  case N, S, E, W

  def turnRight = this match
    case Dir.N => E
    case Dir.E => S
    case Dir.S => W
    case Dir.W => N

  def turnLeft = this match
    case Dir.N => W
    case Dir.W => S
    case Dir.S => E
    case Dir.E => N

Since moving forward, turning left, and turning right are common operations, convenience methods for each are included here.

Third, a class for position:

case class Point(x: Int, y: Int):
  def inBounds(using Grid) =
    xRange.contains(x) && yRange.contains(y)

  def heatLoss(using Grid) =
    if inBounds then grid(y)(x) else 0

  def move(dir: Dir) = dir match
    case Dir.N => copy(y = y - 1)
    case Dir.S => copy(y = y + 1)
    case Dir.E => copy(x = x + 1)
    case Dir.W => copy(x = x - 1)

Here we provide some convenience methods for checking if a point is inBounds on the grid, and the heatLoss of a point on the grid.

Search State​

Now we want to be able to model our state as we're searching. The state will track our position (pos). To know what transitions are possible, we need to keep track of our streak of movements in a given direction (dir). Later, we'll also keep track of the heat lost while getting to a state.

case class State(pos: Point, dir: Dir, streak: Int):

Next let's define some methods for transitioning to new states. We know that we can chose to move forward, turn left, or turn right. For now, we won't consider the restrictions from Part 1 or Part 2 on whether or not you can move forward:

  def straight: State =
    State(pos.move(dir), dir, streak + 1)

  def turnLeft: State =
    val newDir = dir.turnLeft
    State(pos.move(newDir), newDir, 1)

  def turnRight: State =
    val newDir = dir.turnRight
    State(pos.move(newDir), newDir, 1)

Note that the streak resets to one when we turn right or turn left, since we also move the position forward in that new direction.

Dijkstra's Algorithm​

Finally, let's lay the groundwork for an implementation of Dijkstra's algorithm.

Since our valid state transformations vary between part 1 and part 2, let's parameterize our search method by a function:

import collection.mutable.{PriorityQueue, Map}

type StateTransform = Grid ?=> State => List[State]

def search(next: StateTransform)(using Grid): Int =

The algorithm uses Map to track the minimum total heat loss for each state, and a Priority Queue prioritizing by this heatloss to choose the next state to visit:

  val minHeatLoss = Map.empty[State, Int]

  given Ordering[State] = Ordering.by(minHeatLoss)
  val pq = PriorityQueue.empty[State].reverse

  var visiting = State(Point(0, 0), Dir.E, 0)
  minHeatLoss(visiting) = 0

As we generate new states to add to the priority Queue, we need to make sure not to add suboptimal states. The first time we visit any state, it will be with a minimum possible cost, because we're visiting this new state from an adjacent minimum heatloss state in our priority queue. So any state we've already visited will be discarded. This is what our loop will look like:

  val end = Point(xRange.max, yRange.max)
  while visiting.pos != end do
    val states = next(visiting).filterNot(minHeatLoss.contains)
    states.foreach: s =>
      minHeatLoss(s) = minHeatLoss(visiting) + s.pos.heatLoss
      pq.enqueue(s)
    visiting = pq.dequeue()

  minHeatLoss(visiting)

Notice how minHeatLoss is always updated to the minimum of the state we're visiting from plus the incremental heatloss of the new state we're adding to the queue.

We can then provide a framework for calling the search function using the input with solve. It parses the input to a Grid, defining it as a given instance.

def solve(input: String, next: StateTransform): Int =
  given Grid = loadGrid(input)
  search(next)

Part 1​

Now we need to model our state transformation restrictions for Part 1. We can typically move straight, left, and right, but we need to make sure our streak while moving straight never exceeds 3:

// Inside case class State:
  def nextStates(using Grid): List[State] =
    List(straight, turnLeft, turnRight).filter: s =>
      s.pos.inBounds && s.streak <= 3

This will only ever filter out the forward movement, since moving to the left or right resets the streak to 1.

We can then call solve with nextStates from our entry point for part1:

def part1(input: String): Int =
  solve(input, _.nextStates)

Part 2​

Part 2 is similar, but our streak limit increases to 10. Furthermore, while the streak is less than four, only a forward movement is possible:

// Inside case class State:
  def nextStates2(using Grid): List[State] =
    if streak < 4 then List(straight)
    else List(straight, turnLeft, turnRight).filter: s =>
      s.pos.inBounds && s.streak <= 10

And we call solve with nextStates2 to solve part2:

def part2(input: String): Int =
  solve(input, _.nextStates2)

Final Code​

import collection.mutable.{PriorityQueue, Map}

def part1(input: String): Int =
  solve(input, _.nextStates)

def part2(input: String): Int =
  solve(input, _.nextStates2)

def loadGrid(input: String): Grid =
  Grid:
    Vector.from:
      for line <- input.split("\n")
      yield line.map(_.asDigit).toVector

case class Grid(grid: Vector[Vector[Int]]):
  val xRange = grid.head.indices
  val yRange = grid.indices

enum Dir:
  case N, S, E, W

  def turnRight = this match
    case Dir.N => E
    case Dir.E => S
    case Dir.S => W
    case Dir.W => N

  def turnLeft = this match
    case Dir.N => W
    case Dir.W => S
    case Dir.S => E
    case Dir.E => N

def grid(using Grid) = summon[Grid].grid
def xRange(using Grid) = summon[Grid].xRange
def yRange(using Grid) = summon[Grid].yRange

case class Point(x: Int, y: Int):
  def inBounds(using Grid) =
    xRange.contains(x) && yRange.contains(y)

  def heatLoss(using Grid) =
    if inBounds then grid(y)(x) else 0

  def move(dir: Dir) = dir match
    case Dir.N => copy(y = y - 1)
    case Dir.S => copy(y = y + 1)
    case Dir.E => copy(x = x + 1)
    case Dir.W => copy(x = x - 1)

case class State(pos: Point, dir: Dir, streak: Int):
  def straight: State =
    State(pos.move(dir), dir, streak + 1)

  def turnLeft: State =
    val newDir = dir.turnLeft
    State(pos.move(newDir), newDir, 1)

  def turnRight: State =
    val newDir = dir.turnRight
    State(pos.move(newDir), newDir, 1)

  def nextStates(using Grid): List[State] =
    List(straight, turnLeft, turnRight).filter: s =>
      s.pos.inBounds && s.streak <= 3

  def nextStates2(using Grid): List[State] =
    if streak < 4 then List(straight)
    else List(straight, turnLeft, turnRight).filter: s =>
      s.pos.inBounds && s.streak <= 10

type StateTransform = Grid ?=> State => List[State]

def solve(input: String, next: StateTransform): Int =
  given Grid = loadGrid(input)
  search(next)

def search(next: StateTransform)(using Grid): Int =

  val minHeatLoss = Map.empty[State, Int]

  given Ordering[State] = Ordering.by(minHeatLoss)
  val pq = PriorityQueue.empty[State].reverse

  var visiting = State(Point(0, 0), Dir.E, 0)
  minHeatLoss(visiting) = 0

  val end = Point(xRange.max, yRange.max)
  while visiting.pos != end do
    val states = next(visiting).filterNot(minHeatLoss.contains)
    states.foreach: s =>
      minHeatLoss(s) = minHeatLoss(visiting) + s.pos.heatLoss
      pq.enqueue(s)
    visiting = pq.dequeue()

  minHeatLoss(visiting)

Run it in the browser​

Run Part 1​

Run Part 2​

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