Day 5: Print Queue

by @KacperFKorban

Puzzle description

https://adventofcode.com/2024/day/5

Solution Summary

We can treat the data as a graph, where:

• the ordering rules represent directed edges in the graph
• each update represents a subset of the nodes

As a common part of the solution, we will:

• parse the input into a list of ordering rules (Int, Int) and a list of updates List[List[Int]]
• represent the rules as an adjacency list Map[Int, List[Int]]

1. Part 1:
   • For every update, we iterate over its elements (while keeping track of the visited nodes) and for each node check that none of its successors were visited before it.
   • We only keep the updates that don't violate the ordering rules.
   • We compute the middle number of the valid updates.
   • The solution is the sum of the middle numbers of the valid updates.
2. Part 2:
   • Similarily to part 1, we iterate over the updates and check if the ordering rules are violated, but this time we only keep the updates that do violate the ordering rules.
   • To fix the ordering for each update:
     • We find the nodes that have no incoming edges.
     • Then, we run a BFS starting from these nodes, making sure that we only enqueue nodes when all of their incoming edges have been visited or enqueued.

Common part

For both parts of the solution, we will parse the input into an adjacency list and a list of updates.

def parseRulesAndupdates(input: String): (Map[Int, List[Int]], List[List[Int]]) =
  val ruleRegex: Regex = """(\d+)\|(\d+)""".r
  val Array(rulesStr, updatesStr) = input.split("\n\n")
  val rules: Map[Int, List[Int]] =
    ruleRegex.findAllMatchIn(rulesStr).map { m =>
      m.group(1).toInt -> m.group(2).toInt
    }.toList.groupMap(_._1)(_._2)
  val updates: List[List[Int]] =
    updatesStr.linesIterator.map(_.split(",").map(_.toInt).toList).toList
  (rules, updates)

We first split the input into two parts. Then, for rules we convert them into a list of pairs (Int, Int) using a regex and group them by the first element. For updates, we simply split them by commas and convert the elements to Ints.

Part 1

To check if an update is valid, we iterate over the elements of the update and check if none of the neighbors of the current node were visited before it.

This can be done in several ways, for example by using a recursive function:

def isValid(rules: Map[Int, List[Int]])(update: List[Int]): Boolean =
  def rec(update: List[Int], visited: Set[Int] = Set.empty): Boolean = update match
    case Nil => true
    case updateNo :: rest =>
      !rules.getOrElse(updateNo, List.empty).exists(visited.contains)
        && rec(rest, visited + updateNo)
  rec(update)

another alternative is using boundary-break with a for:

def isValid(rules: Map[Int, List[Int]])(update: List[Int]): Boolean =
  boundary:
    var visited = Set.empty[Int]
    for updateNo <- update do
      visited += updateNo
      if rules.getOrElse(updateNo, List.empty).exists(visited.contains) then
        break(false)
    true

or a forall with a local mutable state:

def isValid(rules: Map[Int, List[Int]])(update: List[Int]): Boolean =
  var visited = Set.empty[Int]
  update.forall { updateNo =>
    visited += updateNo
    !rules.getOrElse(updateNo, List.empty).exists(visited.contains)
  }

Using the isValid function, we can filter the updates and compute the middle number of the valid updates:

def part1(input: String) =
  val (rules, updates) = parseRulesAndupdates(input)
  updates.filter(isValid(rules)).map(us => us(us.size / 2)).sum

Part 2

We start Part 2 by parsing and filtering the updates that violate the ordering rules, very similarly to Part 1:

val (rules, updates) = parseRulesAndupdates(input)
val invalidupdates = updates.filter(!isValid(rules)(_))

Next, to fix a single update, we first construct local adjacency lists for the relevant nodes and an inverse adjacency list to keep track of the incoming edges:

def fixUpdate(update: List[Int]): List[Int] =
  val relevantRules = rules
    .filter((k, vs) => update.contains(k) && vs.exists(update.contains))
    .mapValues(_.filter(update.contains)).toMap
  val prevsMap = relevantRules
    .map { case (k, vs) => vs.map(_ -> k) }
    .flatten.groupMap(_._1)(_._2)

The relevantRules are only those that only use the nodes from update, and the prevsMap is a map from a node to its direct predecessors.

Then, we start with nodes that have no incoming edges and run a BFS to fix the ordering:

val startNodes = update.filter(k => !relevantRules.values.flatten.toList.contains(k))

The BFS function takes a set of visited nodes, a queue of nodes to visit, and a list of nodes in the correct order:

  def bfs(queue: Queue[Int], visited: Set[Int] = Set.empty, res: List[Int] = List.empty): List[Int] = queue.dequeueOption match
    case None => res
    case Some((node, queue1)) =>
      val newVisited = visited + node
      val newRes = res :+ node
      val newQueue = relevantRules.getOrElse(node, List.empty)
        .filter { n =>
          val notVisited = !newVisited.contains(n)
          val notInQueue = !queue1.contains(n)
          val allPrevVisited = prevsMap.getOrElse(n, List.empty).forall(p => newVisited.contains(p) || queue1.contains(p))
          notVisited && notInQueue && allPrevVisited
        }
        .foldLeft(queue1)(_.appended(_))
      bfs(newVisited, newQueue, newRes)

The BFS works as follows:

• If the queue is empty, we return the result

• Otherwise, we dequeue a node and add it to the visited set and the result list. We enqueue all neighbors of the node that:

  • have not been visited yet
  • and are not in the queue
  • and have all of their incoming edges visited or enqueued.

  We then call the BFS function recursively with the updated queue, visited set, and result list.

The result of the fixUpdate function is call to the bfs function with the startNodes in the queue.

The solution for part2 is then a sum of the middle numbers of the fixed updates:

invalidUpdates.map(fixUpdate).map(us => us(us.size / 2)).sum

The full solution for Part 2 looks like this:

def part2(input: String) =
  val (rules, updates) = parseRulesAndupdates(input)
  val invalidUpdates = updates.filter(!isValid(rules)(_))

  def fixUpdate(update: List[Int]): List[Int] =
    val relevantRules = rules
      .filter((k, vs) => update.contains(k) && vs.exists(update.contains))
      .mapValues(_.filter(update.contains)).toMap
    val prevsMap = relevantRules
      .map { case (k, vs) => vs.map(_ -> k) }
      .flatten.groupMap(_._1)(_._2)
    val startNodes = update.filter(k => !relevantRules.values.flatten.toList.contains(k))
    def bfs(queue: Queue[Int], visited: Set[Int] = Set.empty, res: List[Int] = List.empty): List[Int] = queue.dequeueOption match
      case None => res
      case Some((node, queue1)) =>
        val newVisited = visited + node
        val newRes = res :+ node
        val newQueue = relevantRules.getOrElse(node, List.empty)
          .filter { n =>
            val notVisited = !newVisited.contains(n)
            val notInQueue = !queue1.contains(n)
            val allPrevVisited = prevsMap.getOrElse(n, List.empty).forall(p => newVisited.contains(p) || queue1.contains(p))
            notVisited && notInQueue && allPrevVisited
          }
          .foldLeft(queue1)(_.appended(_))
        bfs(newQueue, newVisited, newRes)
    bfs(Queue.from(startNodes))

  invalidUpdates.map(fixUpdate).map(us => us(us.size / 2)).sum

Solutions from the community

• Solution by Spamegg
• Solution by Raphaël Marbeck
• Solution by scarf
• Solution by Raymond Dodge
• Solution by nichobi
• Solution by Philippus Baalman
• Solution by Maciej Gorywoda
• Solution by Guillaume Vandecasteele
• Solution by itsjoeoui
• Solution by Antoine Amiguet
• Solution by jnclt
• Solution by Roland Tritsch
• Solution of Jan Boerman
• Solution by Georgi Krastev
• Solution by Joshua Portway
• Solution by Bulby

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