This repository has been archived by the owner on Apr 15, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
145 lines (132 loc) · 3.17 KB
/
main.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
143
144
145
package main
import (
"bytes"
"fmt"
"sort"
"strings"
"github.com/derat/advent-of-code/lib"
)
func main() {
rules := make(map[string]string) // 2->3 and 3->4
for _, ln := range lib.InputLines("2017/21") {
var src, dst string
lib.Extract(ln, `^([.#/]+) => ([.#/]+)$`, &src, &dst)
for _, s := range transforms(src) {
rules[s] = dst
}
}
// In each dimension:
//
// - 3 maps to one 4.
// - 4 maps to one 6.
// - 6 maps to three 3s.
//
// 3 -> 4 (3->4)
// 4 -> 6 (4->6)
// 6 -> 9 (6->3)
// 9 -> 12 (3->4)
// 12 -> 18 (4->6)
// 18 -> 27 (6->3)
// 27 -> 36 (3->4)
// 36 -> 54 (4->6)
// 54 -> 81 (6->3)
// 81 -> 108 (3->4)
// 108 -> 162 (4->6)
exps := make(map[string][]string) // expansions from one pattern to the others that it creates
var add func(string)
add = func(src string) {
var dsts []string
switch len(src) {
case 11: // 3x3 -> one 4x4
dsts = []string{rules[src]}
case 19: // 4x4 -> one 6x6
var subs [][]string
for _, sub := range split2(src) { // split into four 2x2s
subs = append(subs, strings.Split(rules[sub], "/")) // convert each to 3x3
}
dst := []string{ // join to 6x6
subs[0][0] + subs[1][0],
subs[0][1] + subs[1][1],
subs[0][2] + subs[1][2],
subs[2][0] + subs[3][0],
subs[2][1] + subs[3][1],
subs[2][2] + subs[3][2],
}
dsts = []string{strings.Join(dst, "/")}
case 41: // 6x6 -> nine 3x3
for _, sub := range split2(src) { // split into nine 2x2s
dsts = append(dsts, rules[sub]) // convert each to 3x3
}
default:
}
exps[src] = dsts
for _, dst := range dsts {
if _, ok := exps[dst]; !ok {
add(dst)
}
}
}
const init = ".#./..#/###" // initial pattern given in puzzle
add(init) // generate all possible 3x3, 4x4, and 6x6 expansions
var count func(string, int) int
count = func(s string, n int) int {
if n == 0 {
return strings.Count(s, "#")
}
var sum int
for _, d := range exps[s] {
sum += count(d, n-1)
}
return sum
}
fmt.Println(count(init, 5))
fmt.Println(count(init, 18))
}
// split2 splits the supplied string into 2x2 blocks.
func split2(s string) []string {
var res []string
rows := strings.Split(s, "/")
for r := 0; 2*r < len(rows); r++ {
for c := 0; 2*c < len(rows[r]); c++ {
sub := make([]string, 2)
for i := 0; i < 2; i++ {
sub[i] = rows[2*r+i][2*c : 2*(c+1)]
}
res = append(res, strings.Join(sub, "/"))
}
}
return res
}
// transforms returns all transformations that can be produced
// by flipping and rotating the supplied string (e.g. "#./.#").
// This is similar to 2020/20.
func transforms(s string) []string {
rows := lib.ByteGrid(bytes.Split([]byte(s), []byte("/")))
lib.AssertEq(len(rows), len(rows[0])) // square
ts := make([]string, 8)
for tr := 0; tr < 8; tr++ {
trows := rows.Copy()
if tr&1 != 0 {
trows = trows.FlipVert()
}
if tr&2 != 0 {
trows = trows.FlipHoriz()
}
if tr&4 != 0 {
trows = trows.RotateCW()
}
ts[tr] = string(bytes.Join(trows, []byte("/")))
}
// Remove duplicates.
sort.Strings(ts)
i := 0
for j := 1; j < len(ts); j++ {
if ts[i] == ts[j] {
continue
}
i++
ts[i] = ts[j]
}
ts = ts[:i+1]
return ts
}