Added solutions for 16th day: Packet Decoder

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)
+}