Skip to main content

Day 3: Gear Ratios

by @bishabosha and @iusildra

Puzzle description​

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

Solution summary​

The solution models the input as a grid of numbers and symbols.

  1. Define some models to represent the input:
    • case class Coord(x: Int, y: Int) to represent one coordinate on the grid
    • case class Symbol(sym: String, pos: Coord) to represent one symbol and its location
    • case class PartNumber(value: Int, start: Coord, end: Coord) to represent one number and its starting/ending location
  2. Parse the input to create a sparse collection of symbols and numbers
  3. Separate the symbols from the numbers
  4. Then summarise the whole grid as follows:
    • in part1, find all numbers adjacent to a symbol, and sum the total of the resulting number values,
    • in part2,
      1. Find all numbers adjacent to a symbol whose char value is *
      2. Filter out the * symbol with less/more than 2 adjacent numbers
      3. For each * symbol remaining, take the product of its two number values
      4. Sum the resulting products
    • a symbol is adjacent to a number (and vice-versa) if that symbol is inside the number's bounding box on the grid at 1 unit away (see manhattan distance)

Global​

We want a convenient way to represent a coordinate to be able to compute whether one element is within the bounding box of another.

case class Coord(x: Int, y: Int):
  def within(start: Coord, end: Coord) =
    if y < start.y || y > end.y then false
    else if x < start.x || x > end.x then false
    else true

We also want to easily distinguish a Symbol from a Number, and to know whether a Symbol is adjacent to a Number:

case class PartNumber(value: Int, start: Coord, end: Coord)
case class Symbol(sym: String, pos: Coord):
  def neighborOf(number: PartNumber) = pos.within(
    Coord(number.start.x - 1, number.start.y - 1),
    Coord(number.end.x + 1, number.end.y + 1)
  )

Then we need to parse the input to get every Symbol and Number:

import scala.util.matching.Regex.Match

object IsInt:
  def unapply(in: Match): Option[Int] = in.matched.toIntOption

def findPartsAndSymbols(source: String) =
  val extractor = """(\d+)|[^.\d]""".r
  source.split("\n").zipWithIndex.flatMap: (line, i) =>
    extractor
      .findAllMatchIn(line)
      .map:
        case m @ IsInt(nb) =>
          PartNumber(nb, Coord(m.start, i), Coord(m.end - 1, i))
        case s => Symbol(s.matched, Coord(s.start, i))

The object IsInt with the .unapply method is called an extractor. It allows to define patterns to match on. Here it will give me a number if it can parse it from a string.

The findPartsAndSymbols does the parsing and returns a collection of PartNumber and Symbol. What we want to match on is either a number or a symbol (which is anything except the . and a digit). The regex match gives us some information (such as starting / ending position of the matched string) which we use to create the PartNumber and Symbol instances.

The m @ IsInt(nb) is a pattern match that will match on the IsInt extractor and binds the parsed integer to nb and the value being matched to m. A similar way to achieve this is:

.map: m =>
  m match
    case IsInt(nb) => PartNumber(nb, Coord(m.start, i), Coord(m.end - 1, i))
    case s => Symbol(s.matched, Coord(s.start, i))

Part 1​

Compute part1 as described above:

  1. Find all numbers and symbols in the grid
  2. Filter out the symbols in a separate collection
  3. For each number element of the grid and if it has a least one symbol neighbor, return its value
  4. Sum the resulting values
def part1(input: String) =
  val all = findPartsAndSymbols(input)
  val symbols = all.collect { case s: Symbol => s }
  all
    .collect:
      case n: PartNumber if symbols.exists(_.neighborOf(n)) =>
        n.value
    .sum

Part 2​

We might want to represent a Gear to facilitate the computation of the gear ratios:

case class Gear(part: PartNumber, symbol: Symbol)

(Note: a case class is not necessary here, a tuple would do the job)

Compute part2 as described above:

  1. Find all numbers and symbols in the grid
  2. Filter out the symbols in a separate collection
  3. For each number element of the grid and if it has one * neighbor, return a Gear with the number and the * symbol. For any other cases, return None
    • The .flatMap method will filter out the None values when flattening, so we get a collection of Gear only
  4. Group them by symbol and map the values to the number values
    • So we obtain a Map[Symbol, List[Int]] instead of a Map[Symbol, List[Gear]]
  5. Filter out the symbols with less/more than 2 adjacent numbers
  6. For each entry remaining, take the product of its two number values and sum the resulting products
def part2(input: String) =
  val all = findPartsAndSymbols(input)
  val symbols = all.collect { case s: Symbol => s }
  all
    .flatMap:
      case n: PartNumber =>
        symbols
          .find(_.neighborOf(n))
          .filter(_.sym == "*")
          .map(Gear(n, _))
      case _ => None
    .groupMap(_.symbol)(_.part.value)
    .filter(_._2.length == 2)
    .foldLeft(0) { _ + _._2.product }

Final code​

case class Coord(x: Int, y: Int):
  def within(start: Coord, end: Coord) =
    if y < start.y || y > end.y then false
    else if x < start.x || x > end.x then false
    else true
case class PartNumber(value: Int, start: Coord, end: Coord)
case class Symbol(sym: String, pos: Coord):
  def neighborOf(number: PartNumber) = pos.within(
    Coord(number.start.x - 1, number.start.y - 1),
    Coord(number.end.x + 1, number.end.y + 1)
  )

object IsInt:
  def unapply(in: Match): Option[Int] = in.matched.toIntOption

def findPartsAndSymbols(source: String) =
  val extractor = """(\d+)|[^.\d]""".r
  source.split("\n").zipWithIndex.flatMap: (line, i) =>
    extractor
      .findAllMatchIn(line)
      .map:
        case m @ IsInt(nb) =>
          PartNumber(nb, Coord(m.start, i), Coord(m.end - 1, i))
        case s => Symbol(s.matched, Coord(s.start, i))

def part1(input: String) =
  val all = findPartsAndSymbols(input)
  val symbols = all.collect { case s: Symbol => s }
  all
    .collect:
      case n: PartNumber if symbols.exists(_.neighborOf(n)) =>
        n.value
    .sum

case class Gear(part: PartNumber, symbol: Symbol)

def part2(input: String) =
  val all = findPartsAndSymbols(input)
  val symbols = all.collect { case s: Symbol => s }
  all
    .flatMap:
      case n: PartNumber =>
        symbols
          .find(_.neighborOf(n))
          .filter(_.sym == "*")
          .map(Gear(n, _))
      case _ => None
    .groupMap(_.symbol)(_.part.value)
    .filter(_._2.length == 2)
    .foldLeft(0) { _ + _._2.product }

Run it in the browser​

Part 1​

Part 2​

Solutions from the community​

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