We're getting closer to christmas, and for me the challenges are getting harder each day. On Day 16 , we dealing with hexadecimal and binary data. The description is quite lengthy and it can be alot to take in.
I'll give you a simple summary, but if you want the details I suggest you use the link above to check it out yourself.
Our input is a string containing a hexadecimal representation of a message sent from our elf friends. This need to be converted to binary and then processed to get the information we're after. The input can look like this:
D2FE28
Convert this to binary, and you should get this:
110100101111111000101000
The first 3 bits represents the Packet Version. The next 3 bits represents the Packet Type Id. In this example, the version is 6 and the type is 4. Type 4 is a bit of a special case, as it means that this packet contains a literal value, a single binary number. All other types are operators, that can contain sub-packet that in turn might contain sub-packet , and so on. Let's take a look at another example:
38006F45291200
This hexadecimal string will give us this binary:
00111000000000000110111101000101001010010001001000000000
We get the Packet Version (1) and Packet Type Id (6) the same way we did before. Since this isn't a type 4, we also have the 7th bit that tells us the Length Type Id. Since this is a single bit, it's either 0 or 1.
- If it's 0, the next 15 bits represents a number that tells us the total length of bits that the sub-packets in this packet is made of.
- If it's 1, the next 11 bits tells us the number of sub-packets this packet contains. (Just the number of immediate sub-packets, not including sub-sub-packets etc.)
For Part 1, we're parsing our input and trying to sum all of the Packet Versions we can find, including any and all sub-packets.
For Part 2, we are using our operator packets to calculate our answer based on differenct functions. Which function to use depends on the Packet Type Id. We need to find the value of the outermost packet from our input.
Both parts will be solved in one go, as I built upon my first solution when solving Part 2. Let's look at some code:
var binaryString = input.Aggregate(string.Empty,
(current, c) => current + Convert.ToString(Convert.ToInt32(c.ToString(), 16), 2).PadLeft(4, '0'));
This is how I turn my hexadecimal string into a binary representation of the same. For each char in the original string, we convert that char to int using base 16, then back to string using base 2 and finally pad with zeroes on the left so that we always get a length of 4.
private static (long, int, long) ReadPacket(string packet, long versionSum)
{
var version = Convert.ToInt64(packet[..3], 2);
var typeId = Convert.ToInt64(packet.Substring(3, 3), 2);
versionSum += version;
if (typeId == 4)
{
return ProcessLiteralValues(packet, versionSum);
}
var values = new List<long>();
var lengthTypeId = Convert.ToInt32(packet[6].ToString(), 2);
var bitSize = lengthTypeId == 0 ? 15 : 11;
var processedBitsCount = 0;
const int packageContentStartIndex = 7;
if (lengthTypeId == 0)
{
var bitsToProcess = Convert.ToInt32(packet.Substring(packageContentStartIndex, bitSize), 2);
while (bitsToProcess != processedBitsCount)
{
var (subVersionSum, bitsUsed, value) = ReadPacket(
packet.Substring(packageContentStartIndex + bitSize + processedBitsCount, bitsToProcess - processedBitsCount),
versionSum);
processedBitsCount += bitsUsed;
values.Add(value);
versionSum = subVersionSum;
}
}
else
{
var numberOfSubpackets = Convert.ToInt32(packet.Substring(packageContentStartIndex, bitSize), 2);
for (var i = 0; i < numberOfSubpackets; i++)
{
var (subVersionSum, bitsUsed, value) = ReadPacket(packet[(packageContentStartIndex + bitSize + processedBitsCount)..], versionSum);
processedBitsCount += bitsUsed;
values.Add(value);
versionSum = subVersionSum;
}
}
var totalBitsUsed = processedBitsCount + bitSize + packageContentStartIndex;
Func<List<long>, long> resultFunc = typeId switch
{
0 => val => val.Sum(),
1 => val => val.Aggregate((x, y) => x * y),
2 => val => val.Min(),
3 => val => val.Max(),
5 => val => val[0] > val[1] ? 1 : 0,
6 => val => val[0] < val[1] ? 1 : 0,
7 => val => val[0] == val[1] ? 1 : 0,
_ => throw new Exception()
};
return (versionSum, totalBitsUsed, resultFunc(values));
}
Here's the magic stuff. First, we get our Packet Version and Packet Type Id. We're also keeping track of the version sum as we go along. If it's a Type 4, we process it like this:
private static (long, int, long) ProcessLiteralValues(string packet, long versionSum)
{
var packetContent = packet[6..];
var index = 0;
var keepProcessing = true;
var actualValue = new StringBuilder();
while (keepProcessing)
{
keepProcessing = packetContent [index] == '1';
actualValue.Append(packetContent [(index + 1)..(index + 5)]);
index += 5;
}
return (versionSum, index + 6, Convert.ToInt64(actualValue.ToString(), 2));
}
The packet content starts after our first 6 bits. So we just process the packet one chunk at a time, appending the the content to our string builder and keep checking if we're supposed to keep going. Once done, we can return our "actual value". We also keep track of bits that have been processed, so we don't accidentaly go over the same part of the packet twice, later.
That was literal values. Lets look at operator packets where LengthTypeId == 0:
if (lengthTypeId == 0)
{
var bitsToProcess = Convert.ToInt32(packet.Substring(packageContentStartIndex, bitSize), 2);
while (bitsToProcess != processedBitsCount)
{
var (subVersionSum, bitsUsed, value) = ReadPacket(
packet.Substring(packageContentStartIndex + bitSize + processedBitsCount, bitsToProcess - processedBitsCount),
versionSum);
processedBitsCount += bitsUsed;
values.Add(value);
versionSum = subVersionSum;
}
}
We need to find the int value of how many bits to process from our original packet bits. Then we keep processing packets until we've reached that amount of bits, always keeping track of our values and updating our version sum.
else
{
var numberOfSubpackets = Convert.ToInt32(packet.Substring(packageContentStartIndex, bitSize), 2);
for (var i = 0; i < numberOfSubpackets; i++)
{
var (subVersionSum, bitsUsed, value) = ReadPacket(packet[(packageContentStartIndex + bitSize + processedBitsCount)..], versionSum);
processedBitsCount += bitsUsed;
values.Add(value);
versionSum = subVersionSum;
}
}
If Length Type Id == 1, we find out how many sub-packets there are supposed to be, and the process until we've reached that number. And finally, we can use our operators to calculate the correct values, and in the end give us our final value:
var totalBitsUsed = processedBitsCount + bitSize + packageContentStartIndex;
Func<List<long>, long> resultFunc = typeId switch
{
0 => val => val.Sum(),
1 => val => val.Aggregate((x, y) => x * y),
2 => val => val.Min(),
3 => val => val.Max(),
5 => val => val[0] > val[1] ? 1 : 0,
6 => val => val[0] < val[1] ? 1 : 0,
7 => val => val[0] == val[1] ? 1 : 0,
_ => throw new Exception()
};
return (versionSum, totalBitsUsed, resultFunc(values));
Since this method is called recursively, totalBitsUsed is needed to keep track of what has been processed already. I decided to use a switch expression to define our different functions depending on the Packet Type Id, and then just call resultFunc on the last line.
So to get both our answers, we call the method like this:
var (part1, _, part2) = ReadPacket(binaryString, 0);
We discard the middle value, since it's only needed in the internal, recursive calls of ReadPacket