From f169c1bbd9863966a94a07b3972518259710a6b2 Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Thu, 16 Dec 2021 20:49:45 +0100 Subject: Added solutions for 16th day: Packet Decoder --- 2021/16/bits/scanner.go | 217 ++++++++++++++++++++++++++++++++++++++++++++++++ 2021/16/example | 1 + 2021/16/example2 | 1 + 2021/16/example3 | 1 + 2021/16/example4 | 1 + 2021/16/example5 | 1 + 2021/16/example6 | 1 + 2021/16/example7 | 1 + 2021/16/example8 | 1 + 2021/16/example9 | 1 + 2021/16/first.go | 33 ++++++++ 2021/16/go.mod | 3 + 2021/16/input | 1 + 2021/16/second.go | 16 ++++ 14 files changed, 279 insertions(+) create mode 100644 2021/16/bits/scanner.go create mode 100644 2021/16/example create mode 100644 2021/16/example2 create mode 100644 2021/16/example3 create mode 100644 2021/16/example4 create mode 100644 2021/16/example5 create mode 100644 2021/16/example6 create mode 100644 2021/16/example7 create mode 100644 2021/16/example8 create mode 100644 2021/16/example9 create mode 100644 2021/16/first.go create mode 100644 2021/16/go.mod create mode 100644 2021/16/input create mode 100644 2021/16/second.go diff --git a/2021/16/bits/scanner.go b/2021/16/bits/scanner.go new file mode 100644 index 0000000..296705d --- /dev/null +++ b/2021/16/bits/scanner.go @@ -0,0 +1,217 @@ +package bits + +import ( + "bufio" + "fmt" + "io" +) + +type Bits struct { + Version byte + TypeID byte + Value int + Operators []*Bits + Len int +} + +// Scanner represents a lexical scanner. +type Scanner struct { + r *bufio.Reader + buff byte + readBits byte + parsingDepth int +} + +// NewScanner returns a new instance of Scanner. +func NewScanner(r io.Reader) *Scanner { + return &Scanner{r: bufio.NewReader(r)} +} + +// read reads the next bits from the bufferred reader. +// Returns the rune(0) if an error occurs (or io.EOF is returned). +func (s *Scanner) readBit() (bool, error) { + var ret bool + s.readBits++ + switch s.readBits { + case 2: + ret = s.buff&0b0100 != 0 + case 3: + ret = s.buff&0b0010 != 0 + case 4: + ret = s.buff&0b0001 != 0 + default: + var err error + s.buff, err = s.r.ReadByte() + if err != nil || s.buff == '\n' { + return false, err + } + if s.buff <= '9' { + s.buff -= '0' + } else { + s.buff = s.buff - 'A' + 10 + } + if err != nil { + return false, err + } + s.readBits = 1 + ret = s.buff&0b1000 != 0 + } + if ret { + fmt.Print("1") + } else { + fmt.Print("0") + } + return ret, nil +} + +// Scan returns the next Bits packet +func (s *Scanner) Scan() *Bits { + var bits Bits + for i := 0; i < 3; i++ { + bits.Version <<= 1 + b, err := s.readBit() + if err != nil { + return nil + } + if b { + bits.Version++ + } + } + fmt.Println("Version:", bits.Version) + for i := 0; i < 3; i++ { + bits.TypeID <<= 1 + b, err := s.readBit() + if err != nil { + return nil + } + if b { + bits.TypeID++ + } + } + bits.Len += 6 + fmt.Println("TypeID:", bits.TypeID) + if bits.TypeID == 4 { + for { + keepGoing, err := s.readBit() + if err != nil { + return nil + } + var buff byte + for i := 0; i < 4; i++ { + buff <<= 1 + b, err := s.readBit() + if err != nil { + return nil + } + if b { + buff++ + } + } + bits.Len += 5 + bits.Value = bits.Value<<4 + int(buff) + if !keepGoing { + break + } + } + fmt.Println("Value:", bits.Value) + } else { // operator + b, err := s.readBit() + if err != nil { + return nil + } + bits.Len++ + if b { + var buff int + for i := 0; i < 11; i++ { + buff <<= 1 + b, err := s.readBit() + if err != nil { + return nil + } + if b { + buff++ + } + } + bits.Len += 11 + fmt.Println("SubPackets type 1, nb of subpackets:", buff) + s.parsingDepth++ + for i := 0; i < buff; i++ { + subBits := s.Scan() + if subBits == nil { + return nil + } + bits.Operators = append(bits.Operators, subBits) + bits.Len += subBits.Len + } + s.parsingDepth-- + } else { + var buff int + for i := 0; i < 15; i++ { + buff <<= 1 + b, err := s.readBit() + if err != nil { + return nil + } + if b { + buff++ + } + } + bits.Len += 15 + fmt.Println("SubPackets type 0 of len:", buff) + s.parsingDepth++ + for buff > 0 { + subBits := s.Scan() + if subBits == nil { + return nil + } + bits.Operators = append(bits.Operators, subBits) + bits.Len += subBits.Len + buff -= subBits.Len + fmt.Println("remaining bits:", buff) + } + s.parsingDepth-- + } + } + if s.parsingDepth == 0 { + bits.Len += 4 - int(s.readBits) + s.readBits = 0 + } + switch bits.TypeID { + case 0: + for _, sub := range bits.Operators { + bits.Value += sub.Value + } + case 1: + bits.Value = 1 + for _, sub := range bits.Operators { + bits.Value *= sub.Value + } + case 2: + bits.Value = bits.Operators[0].Value + for _, sub := range bits.Operators { + if bits.Value > sub.Value { + bits.Value = sub.Value + } + } + case 3: + bits.Value = bits.Operators[0].Value + for _, sub := range bits.Operators { + if bits.Value < sub.Value { + bits.Value = sub.Value + } + } + case 5: + if bits.Operators[0].Value > bits.Operators[1].Value { + bits.Value = 1 + } + case 6: + if bits.Operators[0].Value < bits.Operators[1].Value { + bits.Value = 1 + } + case 7: + if bits.Operators[0].Value == bits.Operators[1].Value { + bits.Value = 1 + } + } + return &bits +} diff --git a/2021/16/example b/2021/16/example new file mode 100644 index 0000000..3f0eda1 --- /dev/null +++ b/2021/16/example @@ -0,0 +1 @@ +D2FE28 diff --git a/2021/16/example2 b/2021/16/example2 new file mode 100644 index 0000000..a7f8f25 --- /dev/null +++ b/2021/16/example2 @@ -0,0 +1 @@ +38006F45291200 diff --git a/2021/16/example3 b/2021/16/example3 new file mode 100644 index 0000000..bcc798c --- /dev/null +++ b/2021/16/example3 @@ -0,0 +1 @@ +EE00D40C823060 diff --git a/2021/16/example4 b/2021/16/example4 new file mode 100644 index 0000000..0d2cbff --- /dev/null +++ b/2021/16/example4 @@ -0,0 +1 @@ +8A004A801A8002F478 diff --git a/2021/16/example5 b/2021/16/example5 new file mode 100644 index 0000000..ed3b78a --- /dev/null +++ b/2021/16/example5 @@ -0,0 +1 @@ +620080001611562C8802118E34 diff --git a/2021/16/example6 b/2021/16/example6 new file mode 100644 index 0000000..827e51b --- /dev/null +++ b/2021/16/example6 @@ -0,0 +1 @@ +C0015000016115A2E0802F182340 diff --git a/2021/16/example7 b/2021/16/example7 new file mode 100644 index 0000000..0a1278e --- /dev/null +++ b/2021/16/example7 @@ -0,0 +1 @@ +A0016C880162017C3686B18A3D4780 diff --git a/2021/16/example8 b/2021/16/example8 new file mode 100644 index 0000000..0ab8df5 --- /dev/null +++ b/2021/16/example8 @@ -0,0 +1 @@ +C200B40A82 diff --git a/2021/16/example9 b/2021/16/example9 new file mode 100644 index 0000000..08def75 --- /dev/null +++ b/2021/16/example9 @@ -0,0 +1 @@ +04005AC33890 diff --git a/2021/16/first.go b/2021/16/first.go new file mode 100644 index 0000000..df0d644 --- /dev/null +++ b/2021/16/first.go @@ -0,0 +1,33 @@ +package main + +import ( + "bufio" + "fmt" + "os" + + "git.adyxax.org/aoc/2021/16/bits" +) + +var ( + score = 0 +) + +func computeScore(b *bits.Bits) { + score += int(b.Version) + for _, sub := range b.Operators { + computeScore(sub) + } +} + +func main() { + scanner := bits.NewScanner(bufio.NewReader(os.Stdin)) + for { + b := scanner.Scan() + fmt.Println(b) + if b == nil { + break + } + computeScore(b) + } + fmt.Println(score) +} diff --git a/2021/16/go.mod b/2021/16/go.mod new file mode 100644 index 0000000..471a883 --- /dev/null +++ b/2021/16/go.mod @@ -0,0 +1,3 @@ +module git.adyxax.org/aoc/2021/16 + +go 1.17 diff --git a/2021/16/input b/2021/16/input new file mode 100644 index 0000000..d1fbe79 --- /dev/null +++ b/2021/16/input @@ -0,0 +1 @@ +20546C8802538E136091C1802689BCD7DA45948D319D1B100747A009C97696E8B4ABFCA6AB8F4F26C401964A6271C80F802D392C01CEDDCE6E5CB829802F600A00021B14E34C361006E0AC418BB2CA6800BE4599BB6A73507002A52BEEB14D201802F600849E64D3369D37C74100866785B3D0ADFD8E601E5EB9DE2366D93ECB8B040142CB8ACE07CCB5CF34CA89380410B6134CE6FEF104A2B200243396976A00401A45004313D68435DBDDDA61CE6428C01491AEBF0C7E580AE00CCC401B86514216880370EE3443D2013DF003750004361343D88800084C4C8B116A679018300740010C8571BA32080350DA0D42800043A3044189AE0174B314D76E1F3ACF3BDAE3EE7298FF134002EF9DBCD0644127E3CAE7FCBA9A80393544F9A927C973DF1A500965A5CEA94C4DDA5658B94C6C3002A798A629CF21280532BAB4F4C7271E45EE6E71D8143A9BC7948804AB94D1D6006AC200EC1E8A10C00010985316A35C3620061E641644D661A4C012993E99208FC60097802F28F528F738606008CA47205400814C89CC8890064D400AB4BE0A66F2BF253E73AE8401424A7BFB16C0037E06CE0641E0013B08010A8930CE2B980351161DC3730066274188B020054A5E16965940057895ADEB5BF56A635ADE2354191D70566273A6F5B078266008D8022200D46E8291C4401A8CF0CE33CEDE55E9F9802BA00B4BD44A5EA2D10CC00B40316800BAE1003580A6D6026F00090E50024007C9500258068850035C00A4012ED8040B400D71002AF500284009700226336CA4980471D655E25D4650888023AB00525CAE5CBA5E428600BE003993778CB4732996E9887AE3F311C291004BD37517C0041E780A7808802AF8C1C00D0CDBE4ACAD69B3B004E13BDF23CAE7368C9F62448F64546008E0034F3720192A67AD9254917454200DCE801C99ADF182575BBAACAC7F8580 diff --git a/2021/16/second.go b/2021/16/second.go new file mode 100644 index 0000000..2669af7 --- /dev/null +++ b/2021/16/second.go @@ -0,0 +1,16 @@ +package main + +import ( + "bufio" + "fmt" + "os" + + "git.adyxax.org/aoc/2021/16/bits" +) + +func main() { + scanner := bits.NewScanner(bufio.NewReader(os.Stdin)) + b := scanner.Scan() + fmt.Println(b) + fmt.Println(b.Value) +} -- cgit v1.2.3