Advent of code 2021: Day 4
This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.
In this article I'll be solving: Advent of code 2021: Day #4.
Part 1: Bingo card reader
I’m explained the game of bingo because I’m being attacked by a giant squid which wants to play bingo. There’s an input file, which at the top contains bingo numbers, and it follows by a set of bingo cards. To properly set up this puzzle, I split this file up in: numbers and bingo_cards.
The first step is to make a little bingo card struct and implement various functions on this bingo card, like testing if the bingo card has a bingo and to mark of numbers etc. However, while building this I found out that the bingo cards are all “properly spaced” which makes the parsing rather difficult. Sometimes a number is split with a single space, and sometimes there are two spaces. To make it simpler for Rust, I decided to make every bingo card number split by a “single space”. To do this in vim:
Swap out all double spaces with single spaces:
%s/ / /g
Drop all the leading spaces:
%s/^ //g
This way I can build a BingoCard instance like such:
#[derive(Debug)]
struct Square(u8, bool);
struct BingoCard {
points: Vec<Vec<Square>>
}
impl BingoCard {
fn from_str(card: &str) -> BingoCard {
let points: Vec<Vec<Square>> = card
.split("\n")
.map(|row| {
row.split(" ").map(|n| {
Square(n.parse::<u8>().unwrap(), false)
}).collect()
})
.collect();
BingoCard { points: points }
}
}
The first method to implement on BingoCard is the ability to be able to cross off squares. That method is fairly simple:
# on struct BingoCard:
pub fn cross(&mut self, digit: u8) {
for row in &mut self.points {
for square in row {
if square.0 == digit {
square.mark();
break;
}
}
}
}
# on sturct Square:
pub fn mark(&mut self) {
self.1 = true
}
The next method to write is to check which card has a bingo! The puzzle specifies that only horizontal and vertical rows count as a bingo, and I can ignore diagonal (for now). I build a very simple is_bingo method, nothing crazy optimized or anything, considering there are only 25 squares:
pub fn is_bingo(&self) -> bool {
let mut is_bingo = false;
let mut len = self.points.len();
// Horizontal bingo
for row in &self.points {
if row.iter().all(|n| n.1) {
is_bingo = true;
break;
}
}
// Vertical bingo
while len > 0 {
if self.points.iter().all(|row| row[len - 1].1) {
is_bingo = true;
break;
}
len -= 1
}
is_bingo
}
The first step in this process is to find the board which has the first bingo, which we can reasonably solve. The second step is to find the sum of all unmarked numbers, which is also not too complicated to make a method for considering our setup:
# in BingoCard struct:
pub fn sum_unmarked(&self) -> u16 {
let mut total_sum = 0;
for row in &self.points {
for square in row {
if !square.1 {
total_sum += square.0 as u16
}
}
}
total_sum
}
Time to stitch all moving parts together:
'outer: for i in 0..(bingo_numbers.len() / 5) {
let round = &bingo_numbers[i * 5..(i + 1) * 5];
for bingo_number in round {
for bingo_card in &mut bingo_cards {
bingo_card.cross(*bingo_number)
}
}
for bingo_card in &bingo_cards {
if bingo_card.is_bingo() {
println!("{:?}", bingo_card);
break 'outer;
}
}
}
Each round a set of 5 numbers are picked and crossed off the bingo card, after each round we check which card has the first bingo. The card I get is the card which looks like:
6 26 69 27 75
61 33 88 38 20
9 56 70 98 82
80 76 55 66 29
97 84 42 77 73
This card has a horizontal bingo on the bottom row. We need to know the number that caused the bingo, meaning we can just as well loop over each number individually - instead of in sets of 5. We can reduce the above code down to:
'outer: for bingo_number in &bingo_numbers {
for bingo_card in &mut bingo_cards {
bingo_card.cross(*bingo_number);
if bingo_card.is_bingo() {
println!(
"{:?}",
bingo_card.sum_unmarked() * *bingo_number as u16
);
break 'outer;
}
}
}
I’m not spoiling the answer, but I got the right answer. That’s another star! ⭐️.
Part 2: Let the squid win
The second part of the puzzle is to let the squid win and test which bingo card gets the slowest bingo. Isn’t this technically running the full numbers, but without the break at the end? Not entirely, you have to ‘ditch’ bingo cards which were winners before by marking them as winning cards. I’ve done this by adding a boolean field to BingoCard called has_won. The loop goes something like this:
let mut points = 0;
for bingo_number in bingo_numbers {
for bingo_card in &mut bingo_cards {
bingo_card.cross(*bingo_number);
if bingo_card.is_bingo() && !bingo_card.has_won {
points = bingo_card.sum_unmarked() * *bingo_number as u32;
bingo_card.win();
}
}
}
points
Firstly, you’ll notice that I changed the sum_unmarked() to a u32 because I experienced some overflow troubles. The idea is to test if the bingo card is a previous winner and set it as a winning bingo card by using the win() method. Nothing too exceptional.
Again, no spoilers, but it got me to the correct answer and to my next star! ⭐️
The full solution is available on GitHub.
