Skip to main content

Day 4: Scratchcards

by @shardulc

Puzzle description​

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

Solution summary​

First, we note that both parts rely on counting how many winning numbers there are on a card, so we write the helper function countWinning. Then, part 1 converts each card's winning numbers count to a number of points and adds them up. Part 2 cannot be expressed as a map over the winning counts because the value for a card possibly depends on the cards before it. Thus, we write it as a fold, where the accumulator tracks: (1) the number of cards won up to the current card; and (2) the number of copies of cards to be processed, i.e. their multiplicities, for as many of the following cards as needed.

Count number of winning numbers​

def countWinning(card: String): Int =

Most of this function is string manipulation:

  val numbers = card
    .substring(card.indexOf(":") + 1)   // discard "Card X:"
    .split(" ")
    .filterNot(_.isEmpty())
  val (winningNumberStrs, givenNumberStrs) = numbers.span(_ != "|")
  val winningNumbers = winningNumberStrs.map(_.toInt).toSet
  // drop the initial "|"
  val givenNumbers = givenNumberStrs.drop(1).map(_.toInt).toSet

Although this is not specified in the puzzle description, it seems like a number can appear at most once in the list of winning numbers as well as in the given numbers, so it is valid to perform toSet and the final counting step, which is what we return:

  winningNumbers.intersect(givenNumbers).size
end countWinning

Lastly, the standard library conveniently gives us an iterator over lines.

def winningCounts(input: String): Iterator[Int] =
  input.linesIterator.map(countWinning)
end winningCounts

Part 1​

def part1(input: String): String =
  winningCounts(input)
    .map(winning => if winning > 0 then Math.pow(2, winning - 1).toInt else 0)
    .sum.toString()
end part1

Part 2​

def part2(input: String): String =
  winningCounts(input)

The key insight here is that when we process one card, the cards we win (if any) are always at the immediately following indices. So instead of keeping track of absolute indices (e.g. "3 copies of card 5"), we only keep track of how many cards we've won relative to the current index (e.g. "3 copies of the next-to-next card"). This is the Vector in the accumulator of our fold.

    .foldLeft((0, Vector(1))){ case ((numCards, multiplicities), winning) =>

In each iteration, we remove its first element, i.e. the multiplicity of the current card...

      val thisMult = multiplicities(0)

... and carry forward the rest:

      val restMult = multiplicities
        .drop(1)

If we just won no new cards, then we extend the vector by a single 1 for the 1 original copy of the next card to be processed in the next iteration. Else, we extend the vector by as many elements as required to keep track of the cards we just won.

        .padTo(Math.max(1, winning), 1)

Remember that we win a copy of a later card for every copy we'd already won of the current card.

        .zipWithIndex
        .map((mult, idx) => if idx < winning then mult + thisMult else mult)
      (numCards + thisMult, restMult)
    }
    ._1.toString()
end part2

Throughout the iteration, the vector satisfies the following invariants:

  • It has at least one element.
  • All its elements are positive.
  • When processing a card, the first element is the final multiplicity of that card. (It is summed up in numCards in the accumulator.)

Why track by relative index instead of absolute?

  • We don't have to parse or store the card numbers.
  • We can discard information as soon as it is no longer needed, and keep only limited information about the future, in this case bounded by the maximum possible number of winning numbers.
  • (Personal opinion) It makes for a nicer, purely functional solution!

Final code​

def countWinning(card: String): Int =
  val numbers = card
    .substring(card.indexOf(":") + 1)   // discard "Card X:"
    .split(" ")
    .filterNot(_.isEmpty())
  val (winningNumberStrs, givenNumberStrs) = numbers.span(_ != "|")
  val winningNumbers = winningNumberStrs.map(_.toInt).toSet
  // drop the initial "|"
  val givenNumbers = givenNumberStrs.drop(1).map(_.toInt).toSet
  winningNumbers.intersect(givenNumbers).size
end countWinning

def winningCounts(input: String): Iterator[Int] =
  input.linesIterator.map(countWinning)
end winningCounts

def part1(input: String): String =
  winningCounts(input)
    .map(winning => if winning > 0 then Math.pow(2, winning - 1).toInt else 0)
    .sum.toString()
end part1

def part2(input: String): String =
  winningCounts(input)
    // we only track the multiplicities of the next few cards as needed, not all of them;
    // and the first element always exists, and corresponds to the current card;
    // and the elements are always positive (because there is at least 1 original copy of each card)
    .foldLeft((0, Vector(1))){ case ((numCards, multiplicities), winning) =>
      val thisMult = multiplicities(0)
      val restMult = multiplicities
        .drop(1)
        // these are the original copies of the next few cards
        .padTo(Math.max(1, winning), 1)
        .zipWithIndex
        // these are the extra copies we just won
        .map((mult, idx) => if idx < winning then mult + thisMult else mult)
      (numCards + thisMult, restMult)
    }
    ._1.toString()
end part2

Run it in the browser​

Part 1​

Part 2​

Solutions from the community​

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