-
Notifications
You must be signed in to change notification settings - Fork 0
/
sol13.go
142 lines (125 loc) · 3.53 KB
/
sol13.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
package year2022
import (
"fmt"
"sort"
"strings"
"github.com/dhruvmanila/advent-of-code/go/pkg/iterator"
"github.com/dhruvmanila/advent-of-code/go/pkg/stack"
"github.com/dhruvmanila/advent-of-code/go/util"
)
const (
dividerPacketTwo = "[[2]]"
dividerPacketSix = "[[6]]"
)
// packetTokenizer is used to generate the tokens for the packet.
// Valid tokens are: "[", "]", "," and any digits from 0-9.
type packetTokenizer struct {
packet *iterator.Iterator[string]
stack *stack.Stack[string]
}
func newPacketTokenizer(packet string) *packetTokenizer {
return &packetTokenizer{
packet: iterator.New(strings.Split(packet, "")),
stack: stack.New[string](),
}
}
// next returns the next token for the packet. It panics when an invalid
// token is found.
func (t *packetTokenizer) next() string {
if val, ok := t.stack.Pop(); ok {
return val
}
for t.packet.Next() {
switch token := t.packet.Value(); token {
case ",":
continue
case "]", "[":
return token
case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9":
NextLoop:
// Collect the next digits to form the entire number.
for t.packet.Next() {
switch nextToken := t.packet.Value(); nextToken {
case ",":
break NextLoop
case "]":
// Now that the number is complete and we've found a
// token, push it on to the stack for it to be returned
// on the next call.
t.stack.Push(nextToken)
break NextLoop
case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9":
token += nextToken
}
}
return token
default:
panic(fmt.Sprintf("%q: illegal token", token))
}
}
return ""
}
// pushback pushes the given number on to the stack. This basically converts
// the number packet to a list packet.
func (t *packetTokenizer) pushback(number string) {
// To convert it to a list packet, we need the closing bracket to occur
// after the number. We've already consumed the open bracket.
t.stack.Push("]")
t.stack.Push(number)
}
// Less returns true if the lhs packet is less than the rhs packet as per
// the rules stated in the problem statement.
func Less(lhs string, rhs string) bool {
p1, p2 := newPacketTokenizer(lhs), newPacketTokenizer(rhs)
for t1, t2 := p1.next(), p2.next(); t1 != "" && t2 != ""; t1, t2 = p1.next(), p2.next() {
switch {
case (t1 == "[" && t2 == "[") || (t1 == "]" && t2 == "]"):
continue
case t1 == "]" || t1 == "":
return true
case t2 == "]" || t2 == "":
return false
case t1 == "[":
p2.pushback(t2)
case t2 == "[":
p1.pushback(t1)
default:
n1, n2 := util.MustAtoi(t1), util.MustAtoi(t2)
if n1 == n2 {
continue
}
return n1 < n2
}
}
return false
}
func Sol13(input string) (string, error) {
pairs, err := util.ReadSections(input)
if err != nil {
return "", err
}
// Collect all the packets to sort it later. The capacity includes the
// divider packets to be added for the second part.
packets := make([]string, 0, len(pairs)*2+2)
orderedIndexSum := 0
for idx, pair := range pairs {
lhs, rhs := pair[0], pair[1]
packets = append(packets, lhs, rhs)
if Less(lhs, rhs) {
orderedIndexSum += idx + 1 // Packet pairs are 1-indexed
}
}
// Add the divider packets.
packets = append(packets, dividerPacketTwo, dividerPacketSix)
sort.Slice(packets, func(i, j int) bool {
return Less(packets[i], packets[j])
})
decoderKey := 1
for idx, packet := range packets {
switch packet {
case dividerPacketTwo, dividerPacketSix:
decoderKey *= (idx + 1) // Packets are 1-indexed
}
}
return fmt.Sprintf("13.1: %d\n13.2: %d\n", orderedIndexSum, decoderKey), nil
}