main.go (7066B)
1 package main
2
3 import (
4 "bufio"
5 "fmt"
6 "os"
7 "regexp"
8 "strconv"
9 )
10
11 const (
12 LIT = 1
13 DARK = 0
14 TOP = 0
15 LEFT = 1
16 BOTTOM = 2
17 RIGHT = 3
18 )
19
20 type Tile struct {
21 id int
22 size int
23 v []int
24 }
25
26 func (this Tile) get(x, y int) int {
27 return this.v[x*this.size+y]
28 }
29
30 func (this Tile) set(x, y, val int) {
31 this.v[x*this.size+y] = val
32 }
33
34 func (this Tile) computeBorder() [4]int {
35 top, left, bottom, right := 0, 0, 0, 0
36 for i := 0; i < this.size; i++ {
37 top <<= 1
38 top += this.get(0, i)
39 left <<= 1
40 left += this.get(i, 0)
41 bottom <<= 1
42 bottom += this.get(this.size-1, i)
43 right <<= 1
44 right += this.get(i, this.size-1)
45 }
46 res := [4]int{top, left, bottom, right}
47 for i, _ := range res {
48 // Disambiguate by picking the larger between flipped versions.
49 res[i] = max(res[i], reverseBit(res[i], this.size))
50 }
51 return res
52 }
53
54 func (this Tile) rotate(rot int) (new Tile) {
55 // Rotate clockwise rot*90 degrees.
56 new = Tile{this.id, this.size, make([]int, this.size*this.size)}
57 for x := 0; x < this.size; x++ {
58 for y := 0; y < this.size; y++ {
59 xNew, yNew := x, y
60 for i := 0; i < rot%4; i++ {
61 xNew, yNew = yNew, this.size-1-xNew
62 }
63 new.set(xNew, yNew, this.get(x, y))
64 }
65 }
66 return new
67 }
68
69 func (this Tile) flip(flp int) (new Tile) {
70 // Flip left to right flp times.
71 new = Tile{this.id, this.size, make([]int, this.size*this.size)}
72 for x := 0; x < this.size; x++ {
73 for y := 0; y < this.size; y++ {
74 xNew, yNew := x, y
75 for i := 0; i < flp%2; i++ {
76 xNew, yNew = xNew, this.size-1-yNew
77 }
78 new.set(xNew, yNew, this.get(x, y))
79 }
80 }
81 return new
82 }
83
84 func (this Tile) toString() (res []string) {
85 for x := 0; x < this.size; x++ {
86 row := ""
87 for y := 0; y < this.size; y++ {
88 switch this.get(x, y) {
89 case LIT:
90 row += "#"
91 case DARK:
92 row += "."
93 }
94 }
95 res = append(res, row)
96 }
97 return
98 }
99
100 func reverseBit(x int, size int) (res int) {
101 for i := 0; i < size; i++ {
102 res <<= 1
103 res += x & 1
104 x >>= 1
105 }
106 return
107 }
108
109 func max(x int, y int) int {
110 if x > y {
111 return x
112 } else {
113 return y
114 }
115 }
116
117 func readInput(filename string) (res []Tile) {
118 file, _ := os.Open(filename)
119 defer file.Close()
120
121 matcher := regexp.MustCompile(`Tile ([0-9]{4}):`)
122 scanner := bufio.NewScanner(file)
123 for scanner.Scan() {
124 line := scanner.Text()
125 if line == "" {
126 continue
127 }
128 matched := matcher.FindStringSubmatch(line)
129 id, _ := strconv.Atoi(matched[1])
130 v := []int{}
131 size := len(line)
132 for i := 0; i < size; i++ {
133 scanner.Scan()
134 line := scanner.Text()
135 for _, ch := range line {
136 switch ch {
137 case '#':
138 v = append(v, LIT)
139 case '.':
140 v = append(v, DARK)
141 }
142 }
143 }
144 res = append(res, Tile{id, size, v})
145 }
146 return
147 }
148
149 func main() {
150 input := readInput("./input.txt")
151 // 7901522557967
152 fmt.Println(part1(input))
153 // 2476
154 fmt.Println(part2(input))
155 }
156
157 func countBorders(tiles []Tile) (res map[int]int) {
158 res = map[int]int{}
159 for _, t := range tiles {
160 for _, v := range t.computeBorder() {
161 res[v] += 1
162 }
163 }
164 return
165 }
166
167 func part1(input []Tile) (res int64) {
168 // Shared borders are unique, i.e. no more than 1 pair.
169 borderCount := countBorders(input)
170 // Angle tiles only have 2 shared borders.
171 angleTiles := []int{}
172 for _, t := range input {
173 sharedCount := 0
174 for _, v := range t.computeBorder() {
175 sharedCount += borderCount[v] / 2
176 }
177 if sharedCount == 2 {
178 angleTiles = append(angleTiles, t.id)
179 }
180 }
181 res = 1
182 for i := 0; i < 4; i++ {
183 res *= int64(angleTiles[i])
184 }
185 return
186 }
187
188 func assembleImage(tiles []Tile) (res Tile) {
189 borderCount := countBorders(tiles)
190 idMap := map[int]Tile{}
191 for _, v := range tiles {
192 idMap[v.id] = v
193 }
194 // Find correct arrangment of tile ids.
195 used := map[int]bool{}
196 image := [][]int{}
197 row := []int{}
198 leftReq, topReq := 0, 0
199 for {
200 // Find next tile according to left and top borders.
201 found := false
202 for id, t := range idMap {
203 if used[id] {
204 continue
205 }
206 leftSide, topSide := -1, -1
207 for side, v := range t.computeBorder() {
208 // 0 means unique borders not shared with others.
209 if borderCount[v] == 1 {
210 v = 0
211 }
212 if leftSide == -1 && v == leftReq {
213 leftSide = side
214 } else if topSide == -1 && v == topReq {
215 topSide = side
216 }
217 }
218 if leftSide != -1 && topSide != -1 {
219 // Add to image after correctly orienting it.
220 found = true
221 // Use top to compute rotation.
222 t = t.rotate(topSide)
223 // Use left to compute flip.
224 if left := t.computeBorder()[LEFT]; (leftReq != 0 && left != leftReq) ||
225 (leftReq == 0 && borderCount[left] != 1) {
226 t = t.flip(1)
227 }
228 idMap[id] = t
229 row = append(row, id)
230 used[id] = true
231 break
232 }
233 }
234 if !found {
235 panic("No matching tile found!")
236 }
237 // Update requirements.
238 lastBorder := idMap[row[len(row)-1]].computeBorder()
239 if borderCount[lastBorder[BOTTOM]] == 1 &&
240 borderCount[lastBorder[RIGHT]] == 1 {
241 // Image finished.
242 image = append(image, row)
243 break
244 } else if borderCount[lastBorder[RIGHT]] == 1 {
245 // Start new row.
246 image = append(image, row)
247 row = []int{}
248 leftReq = 0
249 topReq = idMap[image[len(image)-1][0]].computeBorder()[BOTTOM]
250 } else {
251 // Start next in row.
252 leftReq = lastBorder[RIGHT]
253 if len(image) == 0 {
254 topReq = 0
255 } else {
256 topReq = idMap[image[len(image)-1][len(row)]].computeBorder()[BOTTOM]
257 }
258 }
259 }
260 // Piece together full image. Resulting image is always square.
261 tileSize := idMap[image[0][0]].size
262 pixels := []int{}
263 for i := 0; i < len(image); i++ {
264 for x := 1; x < tileSize-1; x++ {
265 for j := 0; j < len(image[0]); j++ {
266 for y := 1; y < tileSize-1; y++ {
267 pixels = append(pixels, idMap[image[i][j]].get(x, y))
268 }
269 }
270 }
271 }
272 return Tile{0, (tileSize - 2) * len(image), pixels}
273 }
274
275 func findMonster(image []string, monsterRegex []*regexp.Regexp, monsterLen int) (res int) {
276 for x := 0; x <= len(image)-len(monsterRegex); x++ {
277 for yMax := monsterLen; yMax < len(image[0]); {
278 // Match per sliding window of same size so we have at most 1 match.
279 matchCount := 0
280 for i := 0; i < len(monsterRegex); i++ {
281 matchCount += len(monsterRegex[i].FindAllStringIndex(image[x+i][(yMax-monsterLen):yMax], -1))
282 }
283 if matchCount == len(monsterRegex) {
284 res += 1
285 // Sea monters don't overlap, so we can do this; makes counting easier too.
286 yMax += monsterLen
287 }
288 yMax += 1
289 }
290 }
291 return
292 }
293
294 func part2(input []Tile) (res int) {
295 monsterRegex := []*regexp.Regexp{
296 regexp.MustCompile(`..................#.`),
297 regexp.MustCompile(`#....##....##....###`),
298 regexp.MustCompile(`.#..#..#..#..#..#...`),
299 }
300 monsterLen := 20
301 monsterLitCount := 15 // Each sea monster has 15 '#'s.
302 image := assembleImage(input)
303 litSum := 0
304 for _, p := range image.v {
305 litSum += p
306 }
307 // Try all orientations of the image.
308 for rot := 0; rot <= 3; rot++ {
309 for flp := 0; flp <= 1; flp++ {
310 image := image.rotate(rot).flip(flp).toString()
311 monsterCount := findMonster(image, monsterRegex, monsterLen)
312 if monsterCount > 0 {
313 return litSum - monsterCount*monsterLitCount
314 }
315 }
316 }
317 return
318 }