Advent of Code - Refactoring a cleaner solution

This year I have been participating in the Advent of Code, a yearly (for obvious reasons) event where a new puzzle is released each day of Advent which requires some coding skills to solve. It has been fun so far and I’m sure it’s only going to get harder. It’s an excellent opportunity to practice some algorithm skills and also to learn some new things.

The Day 4 challenge titled Giant Squid involved playing some games of bingo against a giant squid. I found this puzzle a bit easier than Day 3 but I think that’s mostly because I was a bit more awake and my kids weren’t asking for their breakfast while I was trying to understand the problem!

📢 Before I go any further I want to state for the record that the final refactored solution shown in the post was directly inspired by some code my co-worker Lex put onto GitLab. All credit goes to Lex and I’m grateful he’s put his code out in the public so I can learn from it

For each puzzle you’re given some sample input and the expected result for that input, and then given a much larger dataset against which you need to run your solution to get the answer.

For this particular puzzle the sample input looked like this

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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

The first line of comma separated numbers represented the ordered list of numbers called during a game of Bingo, and the next section of three 5x5 grids each represent a Bingo card.

For my solution I defined a couple of classes one to represent an overall Bingo game and another to represent each Card.

1
2
3
4
5
6
7

public class BingoCard
{
    public int[,] CompletedCard { get; set; }
    public Dictionary<int, string> NumberMap { get; set; }
    public List<int> AllNumbers { get; set; }
    public bool HasCompletedRowOrColumn { get; set; }
}

To solve the puzzle you needed to find the first Card that would win based on the order of numbers called (that first comma separated list of numbers). Once the matching Bingo Card had been found, the answer to the puzzle was calculated by the sum of all unmarked numbers multiplied by the number that had just been called.

A Bingo Card is the winner - according to the Squid 🦑 - if it has either a column or row where all numbers have been marked (or called out).

This blog post is particularly about working out if a bingo card has a row or column fully marked (and thus a winning card), it doesn’t show the full solution to the puzzle. To see my fully worked solution take a look over on GitHub.

Introducing the BingoCard class

When the BingoCard is constructed in my stripped down version (it’s a bit more complicated in the full version), I initialise a few properties:

• NumberMap is a Dictionary<int,string> this maps a grid value (the int key) to a coordinate (string which takes the form x,y)
• AllNumbers is a List<int> of all the numbers that are present on the Card - this isn’t used in this example, but I used it in my final solution to check if a Card contained the justCallednumber before going searching for it.
• CompletedCard is an int[5,5] multi-dimensional array, it’s initialised with a default value of -1 in each location

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

private static BingoCard GetBingoCard(List<List<string>> cardRows)
{
    var bingoCard = new BingoCard
    {
        NumberMap = new Dictionary<int, string>(),
        AllNumbers = new List<int>(),
        CompletedCard = new[,] { { -1, -1, -1, -1, -1 }, { -1, -1, -1, -1, -1 }, { -1, -1, -1, -1, -1 }, { -1, -1, -1, -1, -1 }, { -1, -1, -1, -1, -1 } }
    };

    for (int column = 0; column < 5; column++)
    {
        for (int row = 0; row < 5; row++)
        {
            bingoCard.NumberMap.Add(b, $"{column},{row}");
            bingoCard.AllNumbers.Add(b);
        }
    }

    return bingoCard;
}

The List<List<string>> that’s passed in represents the 5x5 grid, which looks like this

1
2
3
4
5
6
7

private static List<List<string>> _cardRows = new List<List<string>> {
    new List<string> {"22","13","17","11","0"},
    new List<string> {"8","2","23","4","24"},
    new List<string> {"21","9","14","16","7"},
    new List<string> {"6","10","3","18","5"},
    new List<string> {"1","12","20","15","19"}
};

This is something I’ve put together for demonstration purposes, the way I parse the input in my actual solution is different to the above.

Working out if a BingoCard has a full row or column

With the details of the BingoCard out of the way, here’s a stripped down version of how I calculated if a specific Card had a full row or column

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

private bool HasFullRowOrColumn(BingoCard bingoCard, List<int> input)
{
    var winnerFound = false;
    for (int i = 0; i < input.Count; i++)
    {
	      var justCalledNumber = input[i];

        var coordinates = bingoCard.NumberMap[justCalledNumber].Split(",");
        var column = int.Parse(coordinates[0]);
        var row = int.Parse(coordinates[1]);
        bingoCard.AllNumbers.Remove(justCalledNumber);

        bingoCard.CompletedCard[column, row] = justCalledNumber;
        if (CheckGrid(bingoCard, column, row))
        {
            return true;
        }
    }

    return false;
}

private bool CheckGrid(BingoCard bingoCard, int column, int row)
{
    //check column
    var countOfFilled = 0;
    for (int i = 0; i < 5; i++)
    {
        if (bingoCard.CompletedCard[column, i] >= 0)
        {
            countOfFilled += 1;
        }

        if (countOfFilled == 5)
        {
            return true;
        }
    }

    //check row
    countOfFilled = 0;
    for (int i = 0; i < 5; i++)
    {
        if (bingoCard.CompletedCard[i, row] >= 0)
        {
            countOfFilled += 1;
        }

        if (countOfFilled == 5)
        {
            return true;
        }
    }

    return false;
}

There are two methods included in this block of code, the first method HasFullRowOrColumn takes a BingoCard which is the card to check and the List<int> represents the numbers that are called during the game.

The HasFullRowOrColumn method loops through the input and lookups the coordinates of the justCalledNumber and then turns that into an int column and int row and uses those coordinates to add the justCalledNumber to the CompletedCard grid (the int[5,5] array), the BingoCard and the column and row coordinates are passed into the CheckGrid method.

The CheckGrid method checks to see if there is a row or column that is fully marked. It does this by looping through the CompletedCard grid twice, once for the 5 values of the row in which a value was just added and then a second time for the column in which a value was just added. While searching through the column/row if it contains a value that is equal to or greater than 0 then it adds 1 to the countofFilled variable. (The reason for >=0 condition is that 0 is a valid game number). If countOfFilled equals 5 then it means that the column or row has 5 values and therefore the card is a winner.

This minor task is completed in 57 lines of code, and to be honest it’s not code I’m particularly proud of, can it be done better?

Refactoring BingoCard to a c# record and simplifying the grid check

📢 I want to reiterate, the code that follows is more or less a direct copy of some code my co-worker wrote to solve the puzzle. It should also be pretty obvious from the code above that I didn’t see his solution until after I had already solved the puzzle myself!

To refactor BingoCard into a c# record we’re going to need another helper record first, introducing Position record type, which represents a position on the Bingo card.

1

public record Position(int x, int y);

Then the BingoCard can be refactored to a simple record type (which I’ve called BingoBoardso names don’t clash) this takes in a Dictionary<Position, int>

1

public record BingoBoard(Dictionary<Position, int> grid);

To generate a BingoBoard I wrote the following test helper method

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

private static BingoBoard GetBingoCard(List<List<string>> cardRows)
{
    Dictionary<Position, int> grid = new Dictionary<Position, int>();
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            grid.Add(new Position(i, j), int.Parse(cardRows[i][j]));
        }
    }

    return new(grid);
}

This helper method takes in the same List<List<string>> input as shown above in the previous example and returns the new record type. Right, so with setup out of the way how do we check if this new record type has a row or column fully marked? Turns out to be incredibly easy an simple!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

private bool HasFullRowOrColumn(BingoBoard bingoBoard, List<int> input)
{
    for (int i = 0; i < 5; i++)
    {
        int xCount = bingoBoard.grid.Count(kvp => kvp.Key.x == i && input.Contains(kvp.Value));
        int yCount = bingoBoard.grid.Count(kvp => kvp.Key.y == i && input.Contains(kvp.Value));

        if (xCount is not 5 && yCount is not 5)
            continue;

        return true;
    }
    return false;
}

The HasFullRowOrColumn method now is vastly simplified compared to my attempt above and took me a few times reading over it to fully get it (it might be more obvious to you dear reader much quicker than it was to me!). What it does it loop through all rows and columns (the x and y) and count the number of values in that column that are included in the input . If the count is not 5 for either the row or column searched then continue on to search the next row/column otherwise return true (meaning that either a row or column is fully marked).

📢 Once again I can’t take any credit, this was all written by my co-worker Lex.

This alternative solution is accomplished in just 14 lines of code. Not that lines of code is necessarily a good indicator but I must say I’m impressed by the simplicity of Lex’s solution.

You can see the full code snippets in the blog post in my AdventOfCode GitHub repository, and you can find Lex’s full solution in his GitLab repository.

What I learnt

1. Having the right data structure makes a big difference, as you can see in the way an operation can be run against a Dictionary<Position, int> vs List<BingoCard>
2. I need to brush up on my Linq skills, as my solution/approach could be improved upon
3. c# records are neat and I need to use them more

Merry Christmas 🎄