When you are in a submarine, and a squid blocks it with its tentacles, it obviously means that he wants to play bingo with you. That is the hilariously absurd aspect of Advent of Code :).

In this problem, the longest part was input parsing. I got the first star in 2 hours, and I spent 30 minutes for the second star. I finished in the top 10000 solvers, contrary to last two days.

Data structures

The first task is to define simple data structures to modelize the problem. The main structure, called BingoGame, contains a vcetor of integers (the drawn numbers) and a vector of grids. Grids are represented as matrices of BingoSquare structs, that contain an integer (the number on the bingo grid) and a boolean flag, set to true if the number has been marked.

#[derive(Copy, Clone)]
pub struct BingoSquare {
    number: u64,
    marked: bool
}

type BingoGrid = Vec<Vec<BingoSquare>>;

pub struct BingoGame {
    numbers: Vec<u64>,
    grids: Vec<BingoGrid>
}

Input

I have had an issue here. In the input files, grids are with the following format :

 8 28 76 19  5
86 34 50 98 29
80 91 46 90 40
33 58 21 22 49
64 41 87 92 72

The problem is that numbers can be separated by several spaces. The naive idea

let grid_tokens = input[i].split(' ').collect::<Vec<&str>>();

does not work properly, as this would return ["8", "28, "76", "19", "", "5"] for the first line. It is necessary to remove “parasite” empty Strings from the vector with a filter.

let grid_tokens = input[i].split(' ').filter(|x| *x != "").collect::<Vec<&str>>();

A simpler possibility I didn’t know is to use the method split_whitespace()

Part 1

We have to figure out which grid is the first to win (i.e to have 5 aligned marked numbers, horizontally or vertically). First, we write a function to determine whether a given row or column has 5 marked numbers :

pub fn is_line_bingo(line: &Vec<BingoSquare>) -> bool {
    for i in 0..5 {
        if !line[i].marked {
            return false;
        }
    }
    
    true
}

This function is called for each row and each column by the function is_bingo(), that checks whether a grid is winning or not.

pub fn is_bingo(grid: &BingoGrid) -> bool {
    for i in 0..5 {
        let column = vec![grid[0][i], grid[1][i], grid[2][i], grid[3][i],
            grid[4][i]];
        if is_line_bingo(&grid[i]) || is_line_bingo(&column) {
            return true;
        }
    }
    false
}

After having determined which grid wins first, we need to calculate its score. The score is the sum of unmarked squares multiplied by the last number drawn. I chose to write a function to calculate the sum of unmarked squares, and to finish the score calculation in the main function.

This function shows how a good usage of iterator methods, like map() and filter(), can simplify a code in Rust.

pub fn unmarked_sum(grid: &BingoGrid) -> u64 {
    let mut grid_sum = 0;

    for i in 0..5 {
        grid_sum += grid[i].iter().filter(|x| !x.marked)
            .map(|x| x.number).sum::<u64>();
    }
    grid_sum
}

The part 1 main function is very simple. We just update all grids, turn after turn, with drawn numbers until a grid wins.

pub fn solve_part1(input: &Vec<String>) -> u64 {
    let mut bingo_game = BingoGame::new(input);
    
    for turn in 0..bingo_game.numbers.len() {
        bingo_game.play(turn);

        for n in 0..bingo_game.grids.len() {
            let grid = &bingo_game.grids[n];
            if is_bingo(&grid) {
                return unmarked_sum(&grid) * bingo_game.numbers[turn];
            }
        }
    }
    
    0
}

Part 2

Now, we want to know which grid is the last to win. To do so, we save in a vector the indexes of finished grids. When this vector size is equal to the number of grids, this means that all grids are finished. The last element of the vector is the index of the last winning grid.

pub fn solve_part2(input: &Vec<String>) -> u64 {
    let mut bingo_game = BingoGame::new(input);
    let mut bingos = Vec::new();
    
    for turn in 0..bingo_game.numbers.len() {
        bingo_game.play(turn);

        for n in 0..bingo_game.grids.len() {
            if bingos.contains(&n) {
                continue;
            }
            if is_bingo(&bingo_game.grids[n]) {
                bingos.push(n);
            }
        }

        if bingos.len() == bingo_game.grids.len() {
            return unmarked_sum(&bingo_game.grids[*bingos.last().unwrap()]) * bingo_game.numbers[turn];
        }
    }

    0
}