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
|
package main
import (
"bufio"
"fmt"
"os"
"strings"
)
func main() {
patterns, targets := readData("example.txt")
fmt.Println(part1(patterns, targets), 6)
fmt.Println(part2(patterns, targets), 16)
patterns, targets = readData("data.txt")
fmt.Println(part1(patterns, targets), 280)
fmt.Println(part2(patterns, targets))
}
func part1(patterns []string, targets []string) (okCount int) {
notFound := make(map[string]bool)
for _, target := range targets {
if doable(patterns, target, notFound) {
okCount++
}
}
return
}
func part2(patterns []string, targets []string) (okCount int) {
combis := make(map[string]int)
for _, target := range targets {
okCount += combinations(patterns, target, combis)
}
return
}
func combinations(patterns []string, target string, combis map[string]int) (combiCount int) {
if combiCountCache, ok := combis[target]; ok {
return combiCountCache
}
for _, p := range patterns {
if len(p) > len(target) {
continue
}
if target[:len(p)] != p {
continue
}
if len(p) == len(target) {
if p == target {
combiCount++
}
} else {
combiCount += combinations(patterns, target[len(p):], combis)
}
}
combis[target] = combiCount
return
}
func doable(patterns []string, target string, notFound map[string]bool) bool {
if len(target) == 0 {
return true
}
if _, n := notFound[target]; n {
return false
}
for _, p := range patterns {
if len(p) > len(target) {
continue
}
if target[:len(p)] != p {
continue
}
if doable(patterns, target[len(p):], notFound) {
return true
}
}
notFound[target] = true
return false
}
func readData(fileName string) (patterns []string, targets []string) {
fp, _ := os.Open(fileName)
scanner := bufio.NewScanner(fp)
scanner.Scan()
patterns = strings.Split(scanner.Text(), ",")
for i, p := range patterns {
patterns[i] = strings.TrimSpace(p)
}
scanner.Scan()
for scanner.Scan() {
targets = append(targets, strings.TrimSpace(scanner.Text()))
}
return
}
|
