# Day 4: Giant Squid

by @Sporarum, student at EPFL.

## Puzzle description

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

## Parsing

## Example Input

`14,30,18,8,3,10,77,4,48,67,28,38,63,43,62,12,68,88,54,32,17,21,83,64,97,53,24,2,60,96,86,23,20,93,65,34,45,46,42,49,71,9,61,16,31,1,29,40,59,87,95,41,39,27,6,25,19,58,80,81,50,79,73,15,70,37,92,94,7,55,85,98,5,84,99,26,66,57,82,75,22,89,74,36,11,76,56,33,13,72,35,78,47,91,51,44,69,0,90,52`

13 62 38 10 41

93 59 60 74 75

79 18 57 90 28

56 76 34 96 84

78 42 69 14 19

96 38 62 8 7

78 50 53 29 81

88 45 34 58 52

33 76 13 54 68

59 95 10 80 63

36 26 74 29 55

43 87 46 70 21

9 17 38 58 63

56 79 85 51 2

50 57 67 86 8

29 78 3 24 79

15 81 20 6 38

97 41 28 42 82

45 68 89 85 92

48 33 40 62 4

<elided>

The input has two parts. First, a list of all numbers from 1 to 99 drawn in a random order (without repetition). Then, after two newlines, a list of bingo boards, separated again by double newlines. We notice they also contain only numbers from 1 to 99.

Since the numbers and the list of boards are all separated by double newlines, we can split our input into sections as follows:

`val inputSections: List[String] = input.split("\n\n").toList`

Once that's done, we can separate the parts by just using `head`

and `tail`

, thus giving us the numbers, and the list of boards, but those are still only text!

### Parsing Numbers

For the numbers, since they are separated by `,`

and nothing else, we can parse them with:

`val numbers: List[Int] = inputSections.head.split(',').map(_.toInt)`

### Parsing Boards

A board is a table of integers, and a table is a list of lines, where each line is also list.
And so we have our type for the boards: `List[List[Int]]`

!

But not so fast, we would like to add some extra operations on boards, so we wrap it in a case class: (don't worry if you don't understand the methods, we'll explain them later)

`case class Board(lines: List[List[Int]]):`

def mapNumbers(f: Int => Int): Board = Board(lines.map(_.map(f)))

def columns: List[List[Int]] = lines.transpose

Now that we have our representation, we still have to actually parse the string that represents a board, for that we'll create a companion object with a method `parse`

that takes a `String`

as input, and returns a `Board`

:

`object Board:`

def parse(inputBoard: String): Board = ???

Let's start from the ground up. Assuming we have a line, how do we find all the numbers? We can use a regular expression(Regexes):

- "digit" ->
`\d`

- "one or more" ->
`+`

- "one or more digits" ->
`\d+`

`val numberParser = raw"\d+".r`

`raw`

allows us to write things like `\d`

without it being translated as a line return.
`.r`

converts our `String`

to a `Regex`

.

For each line, `numberParser`

finds every number in it, and we parse them to `Int`

:

`def parseLine(inputLine: String): List[Int] =`

numberParser.findAllIn(inputLine).toList.map(_.toInt)

And the lines are separated by newlines:

`val lines = inputBoard.split('\n').toList`

Board(lines.map(parseLine))

Where `lines.map(parseLine)`

means:

- create a new list
- for each
`line`

in`lines`

put`parseLine(line)`

in the list

This gives us a `List[List[Int]]`

, which we use to construct a `Board`

.

Since we have multiple `Board`

s:

`val originalBoards: List[Board] = inputSections.tail.map(Board.parse)`

## Reasoning about the problem

It's kind of difficult to think about all those numbers being picked at random turn. We can simplify the problem by replacing each number by the "turn" at which it was drawn.

`zipWithIndex`

transforms our list of numbers into a list of number-index pair, where the index is, in this case, the turn at which the number is picked.
We can then convert it to a `Map`

, to be able to use it like a function.
To be able also to go back, we invert our `Map`

by swapping its keys and values.

`val numberToTurn = numbers.zipWithIndex.toMap`

val turnToNumber = numberToTurn.map(_.swap)

Our simplified boards are therefore:

`val boards = originalBoards.map(board => board.mapNumbers(numberToTurn))`

The `mapNumbers`

method defined in `Board`

takes a function and apply it to each number in the `Board`

to construct a new `Board`

.

It is now time to find when a board wins:

`def winningTurn(board: Board): Int =`

A line is completed at the turn that is its maximum element. Only a single line needs to be full for a board to win, so we only keep the smallest:

` val lineMin = board.lines.map(line => line.max).min`

The columns work the same way:

` val colMin = board.columns.map(col => col.max).min`

`Board.columns`

is computed using `transpose`

, which transforms the lines into columns and the columns into lines.

A board wins if a line wins or if a column wins, so we return the min:

` lineMin min colMin`

Applying `winningTurn`

to each board gives us:

`val winningTurns: List[(Board, Int)] =`

boards.map(board => (board, winningTurn(board)))

We still need to do one more thing before we can solve the problem: computing the score of a board. The score is the sum of all numbers that have not been drawn yet, times the turn at which the board wins.

`def score(board: Board, turn: Int) = ???`

For each line, the numbers that have not been drawn are the ones bigger than the winning turn of that board.
We filter them with `lines.filter(_ > turn)`

.

However, only taking the sum would be wrong, as we are using the turns, and not the original numbers! We thus need to map them to their original values:

`val sumNumsNotDrawn = board.lines.map{ line =>`

line.filter(_ > turn).map(turnToNumber(_)).sum

}.sum

The score is then:

`turnToNumber(turn) * sumUnmarkedNums`

## Solution of Part 1

In part one, we have to compute the score of the first board to win. This is the board whith the smallest winning turn.

`val (winnerBoard, winnerTurn) = winningTurns.minBy((_, turn) => turn)`

And so the score is:

`val winnerScore = score(winnerBoard, winnerTurn)`

## Solution of Part 2

In part two, we have to find the score of the last board to win, so we swap the `minBy`

by a `maxBy`

to get our result:

`val (loserBoard, loserTurn) = winningTurns.maxBy((_, turn) => turn)`

val loserScore = score(loserBoard, loserTurn)

## Run it in the browser

#### Part 1

#### Part 2

## Run it locally

You can get this solution locally by cloning the scalacenter/scala-advent-of-code repository.

`$ git clone https://github.com/scalacenter/scala-advent-of-code`

$ cd scala-advent-of-code

You can run it with scala-cli.

`$ scala-cli 2021 -M day4.run`

The answer of part 1 is 14093.

The answer of part 2 is 17388.

You can replace the content of the `input/day4`

file with your own input from adventofcode.com to get your own solution.

## Solutions from the community

- Solution of @tOverney.
- Solution of @FlorianCassayre.
- Solution of Jan Boerman.

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