It's bingo time (AoC 2021 Day 4)

Our underwater journey continues. It can get dark underwater, and today is no exception. The only thing we can see apparently is a giant squid that has attached itself to the outside of our submarine.

It's only logical that we decide to play Bingo with the squid. Hey, maybe we should check the oxygen generator and co2 levels again; we seem to be making strange decisions.

Part 1

The rules of Bingo are simple: A unique number is drawn from a pool. If your board contains this number, you mark it off. The first player with five numbers marked in a horizontal or vertical direction wins the game.

Since the squid is excellent at multi-tasking, it will play many boards simultaneously.

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

22 13 17 11  0
 8  2 23  4 24
21  9 14 16  7
 6 10  3 18  5
 1 12 20 15 19
 
 3 15  0  2 22
 9 18 13 17  5
19  8  7 25 23
20 11 10 24  4
14 21 16 12  6

I'll spare you the boring part of parsing the input numbers and bingo boards; that's quickly done with a few strings.Fields.

For the first part, we only need to find the board that wins first. We compute its score by taking the sum of all unmarked numbers and multiplying that with the number that was last drawn.

I chose to represent the board as a struct, containing the list of numbers, a list of booleans of the same length, and a boolean flag to indicate whether the board has won already.

type Board struct {
	numbers  []int
	matched  []bool
	hasBingo bool
}

After constructing all the bingo boards, we can loop over the list of drawn numbers:

Loop:
for i := range numbers {
    for b := range boards {
        if boards[b].hasBingo {
            continue
        }
        boards[b].markDigit(numbers[i])

        if boards[b].isBingo() {
            score = boards[b].sumUnmarked() * numbers[i]
            break Loop
        }
    }
}

For each new number, we call markDigit (implementation omitted for brevity) on each board. The method checks whether the number is on the board and marks it as matched. Once a board has a bingo, we compute its score and break out of the loop.

func (b *Board) isBingo() bool {
	// Check rows
	isBingo := true
	for i := 0; i < len(b.matched); i += 5 {
		isBingo = true
		for j := 0; j < 5; j++ {
			isBingo = isBingo && b.matched[i+j]
		}
		if isBingo {
			return true
		}
	}

	// Check columns
	for i := 0; i < 5; i++ {
		isBingo = true
		for j := 0; j < 5; j++ {
			isBingo = isBingo && b.matched[i+j*5]
		}
		if isBingo {
			return true
		}
	}
	return false
}

sumUnmarked iterates over the list of all numbers to find those that are unmarked.  

func (b *Board) sumUnmarked() (sum int) {
	for i := range b.numbers {
		if !b.matched[i] {
			sum += b.numbers[i]
		}
	}
	return
}

Let the games begin!

Part 2

In part two, we worry that it might be wiser to let the squid win, who knows what it'll do to our precious submarine if it lost. We can easily modify our loop from part one and keep track of the board that wins last.

for i := range numbers {
    for b := range boards {
        if boards[b].hasBingo {
            continue
        }
        boards[b].markDigit(numbers[i])

        if boards[b].isBingo() {
            if firstScore == 0 {
                firstScore = boards[b].sumUnmarked() * numbers[i]
            }
            lastScore = boards[b].sumUnmarked() * numbers[i]
            boards[b].hasBingo = true
        }
    }
}

I don't think I've ever solved the second part of any Advent of Code puzzle quite this quickly.

Wrap up

There's little to say about today's puzzle. It was an easy puzzle and serves as a good exercise to practice some basic programming.  

A possible optimization for isBingo would be using a binary representation  marked since we could then leverage bitmasks. Given that we're dealing with a low number of boards and performance wasn't an issue, I'll leave that as an exercise for later.