✨ Advent of Code — Day 04 <2021 />
Day 4: Giant Squid
* Cf. aoc. d. iv
Today we are going to play bingo * with a giant squid. 🦑
Imagine being almost 1.5km below the surface of the ocean, unable to see any sunlight, and suddenly encountering a
giant squid attached to your submarine. While you try to figure out why the squid is there, you decide to pass the time
by playing bingo with him on the submarine’s bingo subsystem.
If you want to go straight to the code, you can check it out on our codelicia’s repository.
MOUNTING THE BINGO BOARD
The first challenge of the day is to mount the bingo board. The board is a 5x5 matrix, where each cell is a number.
We need to split the input into a list of boards. Each board is a list of lists of drawn numbers.
The first line of our input is a list of numbers separated by commas. This list represents the numbers drawn. Let’s parse it into a list of integers.
class Day04(input: String) {
private val newline = "\n"
private val section = "\n\n"
private val sections = input.split(section)
private val draws = sections[0].trim().split(",").map(String::toInt)
init { println("Draws: $draws") }
}
val input = "7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1\n\n 22 13 17 11 0\n8 2 23 4 24\n21 9 14 16 7\n6 10 3 18 5\n1 12 20 15 19\n\n 3 15 0 2 22\n 9 18 13 17 5\n 19 8 7 25 23\n 20 11 10 24 4\n 14 21 16 12 6\n\n 14 21 17 24 4\n 10 16 15 9 19\n 18 8 23 26 20\n 22 11 13 6 5\n 2 0 12 3 7"
fun main(): Unit { Day04(input) }
The rest of the input is a list of boards. Each board consists of a list of lists of numbers List<List<Int>>.
But I also want to know if the number has already been drawn. So I will use a Pair<Int, Boolean> to represent each
number. The first element of the pair is the number, and the second element is a boolean indicating whether the number
has already been drawn.
Let’s parse it!
class Day04(input: String) {
private val newline = "\n"
private val section = "\n\n"
private val sections = input.split(section)
private val draws = sections[0].trim().split(",").map(String::toInt)
private val cards : List<BingoBoard> = buildList {
for (i in 1 until sections.size) {
val numbers = sections[i].split(newline).map { it.split(" ").filter(String::isNotBlank).map(String::toInt) }
add(BingoBoard(numbers.map { row -> row.map { it to false } }))
}
}
class BingoBoard(public var numbers: List<List<Pair<Int, Boolean>>>) {}
init {
val xs = cards.map { it.numbers }
println("Boards: $xs") }
}
val input = "7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1\n\n 22 13 17 11 0\n8 2 23 4 24\n21 9 14 16 7\n6 10 3 18 5\n1 12 20 15 19\n\n 3 15 0 2 22\n 9 18 13 17 5\n 19 8 7 25 23\n 20 11 10 24 4\n 14 21 16 12 6\n\n 14 21 17 24 4\n 10 16 15 9 19\n 18 8 23 26 20\n 22 11 13 6 5\n 2 0 12 3 7"
fun main(): Unit { Day04(input) }
I’ve also used a BingoBoard class to represent the board. This class is not doing much right now, but it will be useful
later on.
PARS I
For the first part of the challenge, we need to find the winner board. As we have a BingoBoard class, I will use it
to implement the logic to check if a board is a winner, and to mark a number as drawn.
class Day04(input: String) {
private val newline = "\n"
private val section = "\n\n"
private val sections = input.split(section)
private val draws = sections[0].trim().split(",").map(String::toInt)
private val cards : List<BingoBoard> = buildList {
for (i in 1 until sections.size) {
val numbers = sections[i].split(newline).map { it.split(" ").filter(String::isNotBlank).map(String::toInt) }
add(BingoBoard(numbers.map { row -> row.map { it to false } }))
}
}
class BingoBoard(private var numbers: List<List<Pair<Int, Boolean>>>) {
fun mark(number: Int) {
numbers = numbers.map {
it.map { pair ->
if (pair.first == number) pair.first to true else pair
}
}
}
fun unmarkedSum(): Int = numbers.flatten().filter { !it.second }.sumOf { it.first }
fun hasBingo(): Boolean {
val diagonal = List(numbers[0].size) { column -> List(numbers[0].size) { numbers[it][column] } }
val merge = numbers + diagonal
merge.forEach { row ->
row.forEach { _ ->
if (row.count { it.second } == row.size) return true
}
}
return false
}
}
}
val input = "7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1\n\n 22 13 17 11 0\n8 2 23 4 24\n21 9 14 16 7\n6 10 3 18 5\n1 12 20 15 19\n\n 3 15 0 2 22\n 9 18 13 17 5\n 19 8 7 25 23\n 20 11 10 24 4\n 14 21 16 12 6\n\n 14 21 17 24 4\n 10 16 15 9 19\n 18 8 23 26 20\n 22 11 13 6 5\n 2 0 12 3 7"
fun main(): Unit { println("Definition of the BingoBoard") }
hasBingo()checks if a bingo occured on the board. It does so by checking if all the numbers in a row or a column have been drawn. The trick here is to add the diagonal to the board, so that we can check the diagonals as well.unmarkedSum()returns the sum of the numbers that have not been drawn yet.mark(n: Int)marks a number as drawn.
Last but not least, we need to find the winner board. To do so, we will iterate over the draws and mark the numbers on the boards. If a board has a bingo, we return the sum of the unmarked numbers. But if you think a little bit more about it, we can actually get all the winner boards at once, just by appending the boards to a list when they have a bingo.
class Day04(input: String) {
private val newline = "\n"
private val section = "\n\n"
private val sections = input.split(section)
private val draws = sections[0].trim().split(",").map(String::toInt)
private val cards : List<BingoBoard> = buildList {
for (i in 1 until sections.size) {
val numbers = sections[i].split(newline).map { it.split(" ").filter(String::isNotBlank).map(String::toInt) }
add(BingoBoard(numbers.map { row -> row.map { it to false } }))
}
}
class BingoBoard(private var numbers: List<List<Pair<Int, Boolean>>>) {
fun mark(number: Int) {
numbers = numbers.map {
it.map { pair ->
if (pair.first == number) pair.first to true else pair
}
}
}
fun unmarkedSum(): Int = numbers.flatten().filter { !it.second }.sumOf { it.first }
fun hasBingo(): Boolean {
val diagonal = List(numbers[0].size) { column -> List(numbers[0].size) { numbers[it][column] } }
val merge = numbers + diagonal
merge.forEach { row ->
row.forEach { _ ->
if (row.count { it.second } == row.size) return true
}
}
return false
}
}
private fun cardsScore(): MutableSet<Pair<Int, Int>> {
val cardsInBingoOrder = mutableSetOf<Pair<Int, Int>>()
draws.forEach { numberCalled ->
cards.forEach { it.mark(numberCalled) }
val isBingo = cards.filter { it.hasBingo() }
isBingo.forEach { card ->
if (false == cardsInBingoOrder.map { it.first }.contains(card.hashCode())) {
cardsInBingoOrder.add(card.hashCode() to numberCalled * card.unmarkedSum())
}
}
}
return cardsInBingoOrder
}
fun part1(): Int = cardsScore().first().second
fun part2(): Int = cardsScore().last().second
}
val input = "7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1\n\n 22 13 17 11 0\n8 2 23 4 24\n21 9 14 16 7\n6 10 3 18 5\n1 12 20 15 19\n\n 3 15 0 2 22\n 9 18 13 17 5\n 19 8 7 25 23\n 20 11 10 24 4\n 14 21 16 12 6\n\n 14 21 17 24 4\n 10 16 15 9 19\n 18 8 23 26 20\n 22 11 13 6 5\n 2 0 12 3 7"
fun main(): Unit { Day04(input) }
To get the solution for part 1, we just need to get the first element of the list.
class Day04(input: String) {
private val newline = "\n"
private val section = "\n\n"
private val sections = input.split(section)
private val draws = sections[0].trim().split(",").map(String::toInt)
private val cards : List<BingoBoard> = buildList {
for (i in 1 until sections.size) {
val numbers = sections[i].split(newline).map { it.split(" ").filter(String::isNotBlank).map(String::toInt) }
add(BingoBoard(numbers.map { row -> row.map { it to false } }))
}
}
class BingoBoard(private var numbers: List<List<Pair<Int, Boolean>>>) {
fun mark(number: Int) {
numbers = numbers.map {
it.map { pair ->
if (pair.first == number) pair.first to true else pair
}
}
}
fun unmarkedSum(): Int = numbers.flatten().filter { !it.second }.sumOf { it.first }
fun hasBingo(): Boolean {
val diagonal = List(numbers[0].size) { column -> List(numbers[0].size) { numbers[it][column] } }
val merge = numbers + diagonal
merge.forEach { row ->
row.forEach { _ ->
if (row.count { it.second } == row.size) return true
}
}
return false
}
}
private fun cardsScore(): MutableSet<Pair<Int, Int>> {
val cardsInBingoOrder = mutableSetOf<Pair<Int, Int>>()
draws.forEach { numberCalled ->
cards.forEach { it.mark(numberCalled) }
val isBingo = cards.filter { it.hasBingo() }
isBingo.forEach { card ->
if (false == cardsInBingoOrder.map { it.first }.contains(card.hashCode())) {
cardsInBingoOrder.add(card.hashCode() to numberCalled * card.unmarkedSum())
}
}
}
return cardsInBingoOrder
}
fun part1(): Int = cardsScore().first().second
fun part2(): Int = cardsScore().last().second
}
val input = "7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1\n\n 22 13 17 11 0\n8 2 23 4 24\n21 9 14 16 7\n6 10 3 18 5\n1 12 20 15 19\n\n 3 15 0 2 22\n 9 18 13 17 5\n 19 8 7 25 23\n 20 11 10 24 4\n 14 21 16 12 6\n\n 14 21 17 24 4\n 10 16 15 9 19\n 18 8 23 26 20\n 22 11 13 6 5\n 2 0 12 3 7"
fun main(): Unit { println(Day04(input).part1()) }
Star of the day granted 💫
PARS II
Predictably, part 2 is actually asking for us to provide the last board that has a bingo. Luckily, we already have a function that returns the boards in the order they get a bingo, so we just need to get the last one.
class Day04(input: String) {
private val newline = "\n"
private val section = "\n\n"
private val sections = input.split(section)
private val draws = sections[0].trim().split(",").map(String::toInt)
private val cards : List<BingoBoard> = buildList {
for (i in 1 until sections.size) {
val numbers = sections[i].split(newline).map { it.split(" ").filter(String::isNotBlank).map(String::toInt) }
add(BingoBoard(numbers.map { row -> row.map { it to false } }))
}
}
class BingoBoard(private var numbers: List<List<Pair<Int, Boolean>>>) {
fun mark(number: Int) {
numbers = numbers.map {
it.map { pair ->
if (pair.first == number) pair.first to true else pair
}
}
}
fun unmarkedSum(): Int = numbers.flatten().filter { !it.second }.sumOf { it.first }
fun hasBingo(): Boolean {
val diagonal = List(numbers[0].size) { column -> List(numbers[0].size) { numbers[it][column] } }
val merge = numbers + diagonal
merge.forEach { row ->
row.forEach { _ ->
if (row.count { it.second } == row.size) return true
}
}
return false
}
}
private fun cardsScore(): MutableSet<Pair<Int, Int>> {
val cardsInBingoOrder = mutableSetOf<Pair<Int, Int>>()
draws.forEach { numberCalled ->
cards.forEach { it.mark(numberCalled) }
val isBingo = cards.filter { it.hasBingo() }
isBingo.forEach { card ->
if (false == cardsInBingoOrder.map { it.first }.contains(card.hashCode())) {
cardsInBingoOrder.add(card.hashCode() to numberCalled * card.unmarkedSum())
}
}
}
return cardsInBingoOrder
}
fun part1(): Int = cardsScore().first().second
fun part2(): Int = cardsScore().last().second
}
val input = "7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1\n\n 22 13 17 11 0\n8 2 23 4 24\n21 9 14 16 7\n6 10 3 18 5\n1 12 20 15 19\n\n 3 15 0 2 22\n 9 18 13 17 5\n 19 8 7 25 23\n 20 11 10 24 4\n 14 21 16 12 6\n\n 14 21 17 24 4\n 10 16 15 9 19\n 18 8 23 26 20\n 22 11 13 6 5\n 2 0 12 3 7"
fun main(): Unit { println(Day04(input).part2()) }
That is it for today! See you tomorrow!