Advent Of Code 2021 Using C#: Day03 - Binary Diagnostic
Tags: adventofcode, csharp
Published: 2021-12-20 11:26:35

[Day03](https://adventofcode.com/2021/day/3) 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:

```csharp
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[]](https://docs.microsoft.com/en-us/dotnet/api/system.string.chars?view=net-5.0) property. This property allows accessing individual [Char](https://docs.microsoft.com/en-us/dotnet/api/system.char?view=net-5.0) 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:

```csharp
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.

```csharp
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.

```csharp
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. 

```csharp
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);
}
```

```csharp
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.

```csharp
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](https://github.com/Kalkwst/Advent-Of-Code-2021).

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