Skip to content

Instantly share code, notes, and snippets.

@Vertygo

Vertygo/AdventOfCode_Day_16_II.cs

Created December 17, 2021 07:25
Show Gist options
  • Save Vertygo/eac4897f8dbea6b167a8918d52df55ab to your computer and use it in GitHub Desktop.
Save Vertygo/eac4897f8dbea6b167a8918d52df55ab to your computer and use it in GitHub Desktop.
Download ZIP
Raw
AdventOfCode_Day_16_II.cs
/*
- first 3 bits version
- second 3 bits type
Type = 4 LITERAL VALUE
encode a single binary number. To do this, the binary number is padded with leading zeroes until its length is a multiple of four bits, and then it is broken into groups of four bits. Each group is prefixed by a 1 bit except the last group, which is prefixed by a 0 bit.
Type = ther than 4 are OPERATOR
If literal value
rest of the value chunk by five
if first digit of one chunk is 1 means read on
if first digit of one chunk is 0 means end of message
If operator ->
- 1 bit operator =>
0 - next 15 bits are number that represent total length of bits
1 - then the next 11 bits are a number that represents the number of sub-packets immediately contained by this packet.
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
A = 1010
B = 1011
C = 1100
D = 1101
E = 1110
F = 1111
Type Ver
4 2
100 010
1
00000000001
001010100000000001101010000000000000101111010001111000
*/
public Dictionary<string, string> Operators = new Dictionary<string, string>()
{
["0000"] = "0",
["0001"] = "1",
["0010"] = "2",
["0011"] = "3",
["0100"] = "4",
["0101"] = "5",
["0110"] = "6",
["0111"] = "7",
["1000"] = "8",
["1001"] = "9",
["1010"] = "A",
["1011"] = "B",
["1100"] = "C",
["1101"] = "D",
["1110"] = "E",
["1111"] = "F"
};
public string HexToBits(string hexString)
{
var str = hexString.Select(ch => Convert.ToString(Convert.ToInt32(ch.ToString(), 16), 2).PadLeft(4, '0'));
var bits = string.Join("", str);
return bits;
}
void CallTests()
{
ClearResults();
EvaluateExpression(HexToBits("C200B40A82"));
if (lastOperation.Value != 3)
{
throw new Exception();
}
ClearResults();
EvaluateExpression(HexToBits("04005AC33890"));
if (lastOperation.Value != 54)
{
throw new Exception();
}
ClearResults();
EvaluateExpression(HexToBits("880086C3E88112"));
if (lastOperation.Value != 7)
{
throw new Exception();
}
ClearResults();
EvaluateExpression(HexToBits("CE00C43D881120"));
if (lastOperation.Value != 9)
{
throw new Exception();
}
ClearResults();
EvaluateExpression(HexToBits("D8005AC2A8F0"));
if (lastOperation.Value != 1)
{
throw new Exception();
}
ClearResults();
EvaluateExpression(HexToBits("F600BC2D8F"));
if (lastOperation.Value != 0)
{
throw new Exception();
}
ClearResults();
EvaluateExpression(HexToBits("9C005AC2F8F0"));
if (lastOperation.Value != 0)
{
throw new Exception();
}
ClearResults();
EvaluateExpression(HexToBits("9C0141080250320F1802104A08"));
if (lastOperation.Value != 1)
{
throw new Exception();
}
ClearResults();
if (Operations.Count != 0)
{
throw new Exception();
}
}
void ClearResults()
{
lastOperation = null;
Operations.Clear();
Ops.Clear();
level = 0;
}
Operator lastOperation;
Stack<Operator> Operations = new Stack<Operator>();
List<Operator> Ops = new List<UserQuery.Operator>();
void Main()
{
CallTests();
Util.ClearResults();
var bits = HexToBits(input);
$"Start {bits}".Dump();
EvaluateExpression(bits);
$"Result is: {lastOperation.Value}".Dump();
//firstOperation.Dump();
//Ops.Dump();
}
static int level = 0;
public class Operator
{
public int Level; //debug level
public Operator(string name)
{
Name = name;
Level=level++;
}
public List<Operator> Suboperations = new List<UserQuery.Operator>();
public string Name;
public virtual long Value {get;set;}
}
public class SumOperation : Operator
{
public SumOperation() : base("Sum")
{
}
public override long Value => Suboperations.Sum(s => s.Value);
}
public class ProductOperation : Operator
{
public ProductOperation() : base("Product")
{
}
public override long Value
{
get { return Suboperations.Select(s => s.Value).Aggregate((long)1, (acc, curr) => acc*curr); }
}
}
public class MinOperation : Operator
{
public MinOperation() : base("Min")
{
}
public override long Value => Suboperations.Min(s => s.Value);
}
public class MaxOperation : Operator
{
public MaxOperation() : base("Max")
{
}
public override long Value => Suboperations.Max(s => s.Value);
}
public class GreaterThanOperation : Operator
{
public GreaterThanOperation() : base("GreaterThan")
{
}
public override long Value => Suboperations[0].Value > Suboperations[1].Value ? 1 : 0;
}
public class LessThanOperation : Operator
{
public LessThanOperation() : base("LessThan")
{
}
public override long Value => Suboperations[0].Value < Suboperations[1].Value ? 1 : 0;
}
public class EqualOperation : Operator
{
public EqualOperation() : base("Equal")
{
}
public override long Value => Suboperations[0].Value == Suboperations[1].Value ? 1 : 0;
}
public class LiteralValue : Operator
{
public LiteralValue(long value) : base("value")
{
Value = value;
}
public override long Value {get;set;}
}
string EvaluateExpression(string bits)
{
Console.WriteLine();
(var version, var type, var subBits) = GetPacketInfo(bits);
if (type != 4)
{
if (lastOperation == null)
{
lastOperation = new SumOperation();
}
switch(type)
{
case 0:
{
var op = new SumOperation();
Ops.Add(op);
lastOperation.Suboperations.Add(op);
Operations.Push(lastOperation);
lastOperation = op;
$"0 [{op.Level}] -> OP Sum".Dump();
}
break;
case 1:
{
var op = new ProductOperation();
Ops.Add(op);
lastOperation.Suboperations.Add(op);
Operations.Push(lastOperation);
lastOperation = op;
$"1 [{op.Level}] -> OP Product".Dump();
}
break;
case 2:
{
var op = new MinOperation();
Ops.Add(op);
lastOperation.Suboperations.Add(op);
Operations.Push(lastOperation);
lastOperation = op;
$"2 [{op.Level}] -> OP Min".Dump();
}
break;
case 3:
{
var op = new MaxOperation();
Ops.Add(op);
lastOperation.Suboperations.Add(op);
Operations.Push(lastOperation);
lastOperation = op;
$"3 [{op.Level}] -> OP Max".Dump();
}
break;
case 5:
{
var op = new GreaterThanOperation();
Ops.Add(op);
lastOperation.Suboperations.Add(op);
Operations.Push(lastOperation);
lastOperation = op;
$"5 [{op.Level}] -> OP Greater than".Dump();
}
break;
case 6:
{
var op = new LessThanOperation();
Ops.Add(op);
lastOperation.Suboperations.Add(op);
Operations.Push(lastOperation);
lastOperation = op;
$"6 [{op.Level}] -> OP Less than".Dump();
}
break;
case 7:
{
var op = new EqualOperation();
Ops.Add(op);
lastOperation.Suboperations.Add(op);
Operations.Push(lastOperation);
lastOperation = op;
$"7 [{op.Level}] -> OP equal to".Dump();
}
break;
}
string lenghtType = "";
(lenghtType, subBits) = Cut(subBits, 1);
if (lenghtType == "0")
{
// next 15 bits are number that represent total length of bits
var strLengthToRead = string.Empty;
(strLengthToRead, subBits)= Cut(subBits, 15);
var lengthToRead = Convert.ToInt32(strLengthToRead, 2);
var read = "";
(read,subBits) = Cut(subBits, lengthToRead);
while (!string.IsNullOrEmpty(read))
{
read = EvaluateExpression(read);
}
lastOperation = Operations.Pop();
return subBits;
}
else
{
// then the next 11 bits are a number that represents the number of sub-packets immediately contained by this packet.
var strNumberOfSubPackets = "";
(strNumberOfSubPackets, subBits) = Cut(subBits, 11);
var numberOfSubPackets = Convert.ToInt32(strNumberOfSubPackets, 2);
for (int i = 0; i < numberOfSubPackets; i++)
{
subBits = EvaluateExpression(subBits);
}
lastOperation = Operations.Pop();
return subBits;
}
}
else
{
string bitNumbers = "";
string controlChar = "";
while (controlChar != "0")
{
string bitNumber;
(controlChar, subBits) = Cut(subBits, 1);
(bitNumber, subBits) = Cut(subBits, 4);
bitNumbers += bitNumber;
}
$"Bit Number -> {bitNumbers} -> {Convert.ToInt64(bitNumbers, 2)}".Dump();
lastOperation.Suboperations.Add(new LiteralValue(Convert.ToInt64(bitNumbers, 2)));
return subBits;
}
}
(int version, int type, string bits) GetPacketInfo(string bits)
{
(var version, var type, var remaining) = Cut(bits, 3, 3);
return (int.Parse(Operators["0"+version]), int.Parse(Operators["0"+type]), remaining);
}
(string left, string right) Cut(string str, int len)
{
return (str.Substring(0, len), str.Substring(len));
}
(string left, string mid, string right) Cut(string str, int len1, int len2)
{
return (str.Substring(0, len1), str.Substring(len1, len2), str.Substring(len1+len2));
}
string inputTest = @"04005AC33890";
string input = @"2056FA18025A00A4F52AB13FAB6CDA779E1B2012DB003301006A35C7D882200C43289F07A5A192D200C1BC011969BA4A485E63D8FE4CC80480C00D500010F8991E23A8803104A3C425967260020E551DC01D98B5FEF33D5C044C0928053296CDAFCB8D4BDAA611F256DE7B945220080244BE59EE7D0A5D0E6545C0268A7126564732552F003194400B10031C00C002819C00B50034400A70039C009401A114009201500C00B00100D00354300254008200609000D39BB5868C01E9A649C5D9C4A8CC6016CC9B4229F3399629A0C3005E797A5040C016A00DD40010B8E508615000213112294749B8D67EC45F63A980233D8BCF1DC44FAC017914993D42C9000282CB9D4A776233B4BF361F2F9F6659CE5764EB9A3E9007ED3B7B6896C0159F9D1EE76B3FFEF4B8FCF3B88019316E51DA181802B400A8CFCC127E60935D7B10078C01F8B50B20E1803D1FA21C6F300661AC678946008C918E002A72A0F27D82DB802B239A63BAEEA9C6395D98A001A9234EA620026D1AE5CA60A900A4B335A4F815C01A800021B1AE2E4441006A0A47686AE01449CB5534929FF567B9587C6A214C6212ACBF53F9A8E7D3CFF0B136FD061401091719BC5330E5474000D887B24162013CC7EDDCDD8E5E77E53AF128B1276D0F980292DA0CD004A7798EEEC672A7A6008C953F8BD7F781ED00395317AF0726E3402100625F3D9CB18B546E2FC9C65D1C20020E4C36460392F7683004A77DB3DB00527B5A85E06F253442014A00010A8F9106108002190B61E4750004262BC7587E801674EB0CCF1025716A054AD47080467A00B864AD2D4B193E92B4B52C64F27BFB05200C165A38DDF8D5A009C9C2463030802879EB55AB8010396069C413005FC01098EDD0A63B742852402B74DF7FDFE8368037700043E2FC2C8CA00087C518990C0C015C00542726C13936392A4633D8F1802532E5801E84FDF34FCA1487D367EF9A7E50A43E90";
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment