Advent Of Code 2021 Using C#: Day03 - Binary Diagnostic

Day03 is a bit more demanding than the last two days. We need to analyze a bit sequence and extract information based on bit position and frequency.

The code came to be a little verbose and complex, but it's not too terrible or overly complicated.

Part1

The puzzle provides us with a list of bit sequences. From this dataset, we need to calculate two values, delta and epsilon, corresponding to the power consumption of the submarine. It will be easier to follow the calculations if we consider our dataset to be a two-dimensional array of bits.

The delta value is a sequence generated by locating the most common value on each column of our two-dimensional array. The epsilon value is a sequence of the least common values of each column.

After determining the delta and epsilon values, we have to convert the binary numbers to decimals. Finally, we need the product of those two numbers.

Let's design the algorithm for that solution.

POWER_CONSUMPTION(Values)
Input: A list of binary numbers
Output: The product of delta times epsilon values

FOR i=0 TO Length(Values[0])
    common += GetMostCommon(Values, i)
    uncommon += GetLeastCommon(Values, i)
ENDFOR

common = ConvertToDecimal(common)
uncommon = ConvertToDecimal(uncommon)

return common * uncommon

With the algorithm figured out, let's start the C# implementation.

Getting specific bits from the sequence

To retrieve the bits of each sequence column-wise, I have created the GetBitsAt method:

private static string[] GetBitsAt(string[] sequence, int index)
{
    if (index > sequence[0].Length)
        throw new ArgumentOutOfRangeException(nameof(index));

    string[] bits = new string[sequence.Length];

    for (int i = 0; i < sequence.Length; i++)
    {
        bits[i] = sequence[i][index].ToString();
    }

    return bits;
}

The method accepts a string array and an index as arguments.

A string in C# provides a Chars[] property. This property allows accessing individual Char objects by their index position in the string. Thus we can access specific characters from each string of the sequence array. In essence, we can treat the sequences array as a two-dimensional matrix of characters.

Thus, the method can iterate the bit sequence in a column-wise fashion. The column to iterate depends on the provided index argument.

Calculating the most common element in the sequence

To find the most common bits in the sequence columns, I have created the MostCommon method:

public static string MostCommon(string[] sequence)
    => sequence.GroupBy(v => v)
               .OrderByDescending(g => g.Count())
               .First()
               .Key;

The method accepts a string array and uses a LINQ query to extract the most common element in the sequence.

Let's break this query into its constituents.

GroupBy(v => v): The sequence elements will be grouped to 0 and 1.
OrderByDescending(g => g.Count()): The two groups will be ordered in descending order based on their respective element counts.
First(): This will return the first element of the first group.
Key: The value of the extracted element.

With these two methods out of the way, the rest of the solution is trivial.

var gammaRate = "";
var epsilonRate = "";


for (int i = 0; i < data[0].Length; i++)
{
    string mostCommon = MostCommon(GetBitsAt(data, i));
    gammaRate += mostCommon;

    if (mostCommon.Equals("1"))
        epsilonRate += "0";
    else
        epsilonRate += "1";
}


var result = Convert.ToInt32(gammaRate, 2) * Convert.ToInt32(epsilonRate, 2);

Part2

In Part 2, we again need to keep track of the most common and least common bits. But this time, instead of generating our values, we are eliminating them based on a set of criteria.

Again we are traversing our sequences column-wise. The process of finding the oxygen generator rating is almost identical to generating the delta value from the previous puzzle. Keep only the sequences that have the most common bit on each position. The only difference is that if there are an equal number of 0 bits and 1 bits, keep the sequences with 1 in that position.

The same goes for the CO2 scrubber rating. Keep only the sequences that have the least common bit on each position. This time, in the case of equality, keep the sequences with 0 in that position.

I'm again using the MostCommon and GetBitAt methods from the previous puzzle. I am not proud of this solution because it has some code replication, and some refactoring is definitely of order, but this is the solution I came up with when I first solved it. I guess this is the downside of competitive programming.

There are three new methods here.

The HasMostCommon method checks if the given sequence has the most common bit on that position.

private static bool HasMostCommon(string sequence, string bit, int position)
    => sequence[position].ToString().Equals(bit);

GetOxygenRating and GetCO2Rating calculate the oxygen and CO2 ratings respectively, in a recursive manner.

private static string GetOxygenRating(string[] sequences, int index)
{
    if (sequences.Length == 1)
        return sequences[0];

    string mostCommon = Utils.MostCommon(GetBitsAt(sequences, index));

    List<string> common = new();
    List<string> uncommon = new();

    foreach (var sequence in sequences)
    {
        if (HasMostCommon(sequence, mostCommon, index))
            common.Add(sequence);
        else
            uncommon.Add(sequence);
    }

    if (common.Count == uncommon.Count)
        if (uncommon[0][index].ToString().Equals("1"))
            return GetOxygenRating(uncommon.ToArray(), index + 1);

    return GetOxygenRating(common.ToArray(), index + 1);
}

private static string GetCO2Rating(string[] sequences, int index)
{
    if (sequences.Length == 1)
        return sequences[0];

    string mostCommon = Utils.MostCommon(GetBitsAt(sequences, index));

    List<string> common = new List<string>();
    List<string> uncommon = new List<string>();

    foreach (var sequence in sequences)
    {
        if (HasMostCommon(sequence, mostCommon, index))
            common.Add(sequence);
        else
            uncommon.Add(sequence);
    }

    if (common.Count == uncommon.Count)
        if (common[0][index].ToString().Equals("0"))
            return GetCO2Rating(common.ToArray(), index + 1);

    return GetCO2Rating(uncommon.ToArray(), index + 1);
}

The HasMostCommon method checks if the given sequence has the most common bit on that position.

The rest of the solution is once again really trivial.

string oxygen = GetOxygenRating(data, 0);
string co2 = GetCO2Rating(data, 0);

var result = (Convert.ToInt32(oxygen, 2) * Convert.ToInt32(co2, 2))

That's All Folks!

That’s it for day 3. I’m not exactly happy with this code. It could definitely use some refactoring and some clean-up but in competitive programming, some times you have to sacrifice form for speed of implementation.

I hope I could provide y'all with a more in-depth explanation of how my solutions work.

You can find this solution and others in my Github Repo.

Hope you had fun and see you around for the next episode of Advent of Code 2021!