# 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

- Solution by Spamegg
- Solution by Karthick Pachiappan
- Solution by Yann Moisan
- Solution by Niels Prins
- Solution by Philippus Baalman
- Solution by jnclt
- Solution by Guillaume Vandecasteele
- Solution by Michael Pilquist
- Solution by Chidi Nweke
- Solution by natsukagami
- Solution by Karl Bielefeldt
- Solution by g.berezin
- Solution by Alexandru Nedelcu
- Solution by Thanh Le
- Solution by CJ Smith
- Solution by Jamie Thompson
- Solution by Seth Tisue
- Solution by Marconi Lanna
- Solution of Jan Boerman.
- Solution by Will Billingsley
- Solution by Brian Xiang
- Solution by Joel Edwards
- Solution by Rui Alves
- Solution by Paweł Cembaluk

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