Advent Of Code 2021

Time for Day 4 of Advent of Code. Time to play bingo with a giant squid. The question for Part 1 is quite clear, given a list of numbers and a set of bingo boards, find the first winning board and the last number called to make that board win. Then sum all the unmarked numbers on the board and multiply with the last number.

Our input looks something like this:

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

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

I decided to create a bunch of classes to help me keep this simple.

public class Board
{
    public List<Row> Rows = new List<Row>();
    public void MarkNumber(int number)
    {
        foreach (var row in Rows)
        {
            row.Numbers.Where(x => x.Value == number).ToList().ForEach(x => x.Marked = true);
        }
    }
    public bool HasBingo()
    {
        if (Rows.Any(r => r.Numbers.All(n => n.Marked)))
        {
            return true;
        }

        for (int i = 0; i < 5; i++)
        {
            var numbers = Rows.Select(r => r.Numbers[i]);
            if (numbers.All(n => n.Marked))
            {
                return true;
            }
        }


        return false;
    }
}
public class Row
{
    public int RowNr { get; set; }
    public List<Number> Numbers = new List<Number>();
}

public class Number
{
    public int Value { get; set; }
    public bool Marked = false;
}

So, we have Boards, Rows and Numbers, and a couple of methods on the board to mark numbers and check for bingo.

Lets parse the input and make use of the classes:

var input = File.ReadAllLines("input.txt").Where(x => !string.IsNullOrWhiteSpace(x)).ToArray();
var numbers = input[0].Split(',').Select(int.Parse);

var boards = GetBoards(input.Skip(1).ToArray());

GetBoards() looks like this:

public static IEnumerable<Board> GetBoards(string[] input)
{
    var boards = new List<Board>();
    var board = new Board();

    var rowNr = 0;

    for (int i = 0; i < input.Length; i++)
    {
        if (board.Rows.Count() > 4)
        {
            boards.Add(board);
            board = new Board();
            rowNr = 0;
        }

        var rowNumbers = input[i].Trim().Replace("  ", " ").Split(' ').Select(x => int.Parse(x.Trim()));
        var row = new Row
        {
            RowNr = rowNr,
            Numbers = rowNumbers.Select(x => new Number { Value = x }).ToList()
        };
        board.Rows.Add(row);
    }

    return boards;
}

We basically go through the input lines, creating a new board each 5 rows. Nothing to special here. To solve Part 1, we just have to call each number and mark numbers on the boards until one of them has bingo, and then do our final calculation to get the answer:

public static void Part1(IEnumerable<Board> boards, IEnumerable<int> numbers)
{
    Board winningBoard = null;
    int lastNumberCalled = 0;

    foreach (var number in numbers)
    {
        foreach (var board in boards)
        {
            board.MarkNumber(number);
        }

        if (boards.Any(b => b.HasBingo()))
        {
            lastNumberCalled = number;
            winningBoard = boards.Single(b => b.HasBingo());
            break;
        }
    }

    var sumUnMarked = winningBoard.Rows.SelectMany(r => r.Numbers.Where(x => !x.Marked).Select(x => x.Value)).Sum();
    Console.WriteLine($"Part1: {sumUnMarked * lastNumberCalled}");
}

I don't really like nested foreach loops, but it works and isn't too slow in this case. Sometimes I just don't have time to do it better :)

For Part 2, we are looking for the last board to win. The answer is calculated in the same way as Part 1, but using the last winning board instead.

public static void Part2(IEnumerable<Board> boards, IEnumerable<int> numbers)
{
    Board winningBoard = null;
    int lastNumberCalled = 0;

    var boardList = boards.ToList();

    foreach (var number in numbers)
    {
        foreach (var board in boardList)
        {
            board.MarkNumber(number);
        }

        if (winningBoard == null)
        {
            if (boardList.Any(b => b.HasBingo()))
            {
                boardList.RemoveAll(b => b.HasBingo());
                if (boardList.Count == 1)
                {
                    winningBoard = boardList.First();
                }
            }
        }
        else
        {
            if (winningBoard.HasBingo())
            {
                lastNumberCalled = number;
                break;
            }
        }
    }
    var sumUnMarked = winningBoard.Rows.SelectMany(r => r.Numbers.Where(x => !x.Marked).Select(x => x.Value)).Sum();
    Console.WriteLine($"Part2: {sumUnMarked * lastNumberCalled}");
}

Again, we call number by number, marking the numbers on the board and checking for bingo. If a board gets bingo, we remove it from the list of boards. This goes on until there is only one board left, and that board gets bingo. Then we can get our answer.

Not to pleased with my solutions here, I'm sure there is a more clever algorithm to use. But my own time constraints and a little bit of lazyness led me to these solutions, and they do get the correct answers atleast :)

Advent Of Code 2021 - Day 4