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!
Top comments (0)