main.go (2949B)
1 package main
2
3 import (
4 "bufio"
5 "fmt"
6 "os"
7 "regexp"
8 "strconv"
9 "strings"
10 )
11
12 type req struct {
13 min1 int
14 max1 int
15 min2 int
16 max2 int
17 }
18
19 func (this req) isValid(x int) bool {
20 return (x >= this.min1 && x <= this.max1) || (x >= this.min2 && x <= this.max2)
21 }
22
23 func readInput(filename string) (reqs map[string]req, tickets [][]int) {
24 file, _ := os.Open(filename)
25 defer file.Close()
26
27 reqs = map[string]req{}
28 tickets = [][]int{}
29 scanner := bufio.NewScanner(file)
30 reqMatcher := regexp.MustCompile(`([a-z ]+): ([0-9]+)-([0-9]+) or ([0-9]+)-([0-9]+)`)
31 ticketMatcher := regexp.MustCompile(`([0-9]+),?`)
32 for scanner.Scan() {
33 if line := scanner.Text(); line == "" {
34 break
35 } else {
36 matches := reqMatcher.FindAllStringSubmatch(line, -1)
37 min1, _ := strconv.Atoi(matches[0][2])
38 max1, _ := strconv.Atoi(matches[0][3])
39 min2, _ := strconv.Atoi(matches[0][4])
40 max2, _ := strconv.Atoi(matches[0][5])
41 reqs[matches[0][1]] = req{min1, max1, min2, max2}
42 }
43 }
44 for scanner.Scan() {
45 matches := ticketMatcher.FindAllStringSubmatch(scanner.Text(), -1)
46 if len(matches) > 0 {
47 newTicket := []int{}
48 for _, v := range matches {
49 num, _ := strconv.Atoi(v[1])
50 newTicket = append(newTicket, num)
51 }
52 tickets = append(tickets, newTicket)
53 }
54 }
55 return
56 }
57
58 func main() {
59 reqs, tickets := readInput("./input.txt")
60 // 24980
61 fmt.Println(part1(reqs, tickets))
62 // 809376774329
63 fmt.Println(part2(reqs, tickets))
64 }
65
66 func part1(reqs map[string]req, tickets [][]int) (errRate int) {
67 for _, ticket := range tickets[1:] { // Skip my ticket
68 for _, num := range ticket {
69 anyValid := false
70 for _, req := range reqs {
71 if req.isValid(num) {
72 anyValid = true
73 break
74 }
75 }
76 if !anyValid {
77 errRate += num
78 }
79 }
80 }
81 return
82 }
83
84 func countZeros(x []int) (count int, lastZeroIdx int) {
85 for i, v := range x {
86 if v == 0 {
87 count += 1
88 lastZeroIdx = i
89 }
90 }
91 return
92 }
93
94 func part2(reqs map[string]req, tickets [][]int) (res int) {
95 invalidCount := map[string][]int{}
96 for field, _ := range reqs {
97 invalidCount[field] = make([]int, len(tickets[0]))
98 }
99 TicketCheck:
100 for _, ticket := range tickets[1:] { // Skip my ticket
101 for _, num := range ticket {
102 anyValid := false
103 for _, req := range reqs {
104 if req.isValid(num) {
105 anyValid = true
106 break
107 }
108 }
109 if !anyValid {
110 continue TicketCheck
111 }
112 }
113 for i, num := range ticket {
114 for field, req := range reqs {
115 if !req.isValid(num) {
116 invalidCount[field][i] += 1
117 }
118 }
119 }
120 }
121 fieldIdx := map[string]int{}
122 for len(invalidCount) > 0 {
123 for field, counts := range invalidCount {
124 if count, idx := countZeros(counts); count == 1 {
125 fieldIdx[field] = idx
126 delete(invalidCount, field)
127 for _, counts := range invalidCount {
128 counts[idx] = 1
129 }
130 break
131 }
132 }
133 }
134 res = 1
135 for field, idx := range fieldIdx {
136 if strings.HasPrefix(field, "departure") {
137 res *= tickets[0][idx]
138 }
139 }
140 return
141 }