aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJulien Dessaux2021-12-16 20:49:45 +0100
committerJulien Dessaux2021-12-16 20:49:45 +0100
commitf169c1bbd9863966a94a07b3972518259710a6b2 (patch)
tree837f8b9052e199c84322865c8304ae54e9d17ad5
parentAdded solutions for 15th day: Chiton shortest path exercises (diff)
downloadadvent-of-code-f169c1bbd9863966a94a07b3972518259710a6b2.tar.gz
advent-of-code-f169c1bbd9863966a94a07b3972518259710a6b2.tar.bz2
advent-of-code-f169c1bbd9863966a94a07b3972518259710a6b2.zip
Added solutions for 16th day: Packet Decoder
-rw-r--r--2021/16/bits/scanner.go217
-rw-r--r--2021/16/example1
-rw-r--r--2021/16/example21
-rw-r--r--2021/16/example31
-rw-r--r--2021/16/example41
-rw-r--r--2021/16/example51
-rw-r--r--2021/16/example61
-rw-r--r--2021/16/example71
-rw-r--r--2021/16/example81
-rw-r--r--2021/16/example91
-rw-r--r--2021/16/first.go33
-rw-r--r--2021/16/go.mod3
-rw-r--r--2021/16/input1
-rw-r--r--2021/16/second.go16
14 files changed, 279 insertions, 0 deletions
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)
+}