main.go (2820B)
1 package main
2
3 import (
4 "bufio"
5 "fmt"
6 "os"
7 "regexp"
8 "strconv"
9 )
10
11 const (
12 LETTER = -1 - iota
13 PIPE
14 PAREN_L
15 PAREN_R
16 PLUS
17 BRACE_L
18 BRACE_R
19 )
20
21 type Rules map[int][]int
22
23 func readInput(filename string) (rules Rules, messages []string) {
24 file, _ := os.Open(filename)
25 defer file.Close()
26
27 sep := regexp.MustCompile(`[: "]+`)
28 scanner := bufio.NewScanner(file)
29 rules = Rules{}
30 for scanner.Scan() {
31 line := scanner.Text()
32 if line == "" {
33 break
34 }
35 tokens := []int{}
36 for _, token := range sep.Split(line, -1) {
37 if token == "" {
38 continue
39 }
40 if num, err := strconv.Atoi(token); err == nil {
41 tokens = append(tokens, num)
42 } else {
43 switch token {
44 case "|":
45 tokens = append(tokens, PIPE)
46 default:
47 tokens = append(tokens, LETTER, int(token[0]))
48 }
49 }
50 }
51 rules[tokens[0]] = tokens[1:]
52 }
53 for scanner.Scan() {
54 messages = append(messages, scanner.Text())
55 }
56 return
57 }
58
59 func main() {
60 rules, messages := readInput("./input.txt")
61 // 272
62 fmt.Println(part1(rules, messages))
63 // 374
64 fmt.Println(part2(rules, messages))
65 }
66
67 func toRegexp(rules Rules, target int) string {
68 expr := ""
69 stack := []int{target}
70 for len(stack) > 0 {
71 switch stack[0] {
72 case LETTER:
73 expr += string(byte(stack[1]))
74 stack = stack[2:]
75 case PIPE:
76 expr, stack = expr+"|", stack[1:]
77 case PAREN_L:
78 expr, stack = expr+"(", stack[1:]
79 case PAREN_R:
80 expr, stack = expr+")", stack[1:]
81 case PLUS:
82 expr, stack = expr+"+", stack[1:]
83 case BRACE_L:
84 expr, stack = expr+"{", stack[1:]
85 for stack[0] != BRACE_R {
86 expr, stack = expr+string('0'+stack[0]), stack[1:]
87 }
88 expr, stack = expr+"}", stack[1:]
89 default:
90 sub := append(append([]int{PAREN_L}, rules[stack[0]]...), PAREN_R)
91 stack = append(sub, stack[1:]...)
92 }
93 }
94 return expr
95 }
96
97 func part1(rules Rules, messages []string) (matchCount int) {
98 matcher := regexp.MustCompile("^" + toRegexp(rules, 0) + "$")
99 for _, msg := range messages {
100 if matcher.MatchString(msg) {
101 matchCount += 1
102 }
103 }
104 return
105 }
106
107 func part2(rules Rules, messages []string) (matchCount int) {
108 rules[8] = append(rules[8], PLUS)
109 // Find max repetitations of 42 and 31
110 max42, matcher42 := 0, regexp.MustCompile(toRegexp(rules, 42))
111 max31, matcher31 := 0, regexp.MustCompile(toRegexp(rules, 31))
112 for _, msg := range messages {
113 if count := len(matcher42.FindAllStringSubmatch(msg, -1)); count > max42 {
114 max42 = count
115 }
116 if count := len(matcher31.FindAllStringSubmatch(msg, -1)); count > max31 {
117 max31 = count
118 }
119 }
120 for i := 2; i <= max42 && i <= max31; i++ {
121 rules[11] = append(rules[11], PIPE, 42, BRACE_L, i, BRACE_R, 31, BRACE_L, i, BRACE_R)
122 }
123 matcher := regexp.MustCompile("^" + toRegexp(rules, 0) + "$")
124 for _, msg := range messages {
125 if matcher.MatchString(msg) {
126 matchCount += 1
127 }
128 }
129 return
130 }