70 lines
1.4 KiB
Go
70 lines
1.4 KiB
Go
|
package main
|
||
|
|
|
||
|
|
import (
|
||
|
|
"fmt"
|
||
|
|
"strings"
|
||
|
|
"os"
|
||
|
|
)
|
||
|
|
|
||
|
|
func count(pattern string, towels []string) int {
|
||
|
|
counter := 0
|
||
|
|
|
||
|
|
// Iterate over the map in sorted key order
|
||
|
|
for _, t := range towels {
|
||
|
|
if pattern == t { counter++ }
|
||
|
|
|
||
|
|
if strings.HasPrefix(pattern, t) {
|
||
|
|
counter += count(pattern[len(t):], towels)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return counter
|
||
|
|
}
|
||
|
|
|
||
|
|
func count_with_map(pattern string, pmap map[string]int) int {
|
||
|
|
counter := 0
|
||
|
|
|
||
|
|
for key, val := range pmap {
|
||
|
|
if pattern == key { return val }
|
||
|
|
|
||
|
|
if strings.HasPrefix(pattern, key) {
|
||
|
|
counter += count_with_map(pattern[len(key):], pmap)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return counter
|
||
|
|
}
|
||
|
|
|
||
|
|
func construct_pmap(towels []string) map[string]int {
|
||
|
|
pmap := make(map[string]int)
|
||
|
|
|
||
|
|
for _, t := range towels {
|
||
|
|
pmap[t] = count(t, towels)
|
||
|
|
}
|
||
|
|
|
||
|
|
return pmap
|
||
|
|
}
|
||
|
|
|
||
|
|
func check(err error) {
|
||
|
|
if err != nil { panic(err) }
|
||
|
|
}
|
||
|
|
|
||
|
|
func main() {
|
||
|
|
dat, err := os.ReadFile("data.txt")
|
||
|
|
check(err)
|
||
|
|
input := strings.TrimSpace(string(dat))
|
||
|
|
|
||
|
|
towels := strings.Split(strings.Split(input, "\n\n")[0], ", ")
|
||
|
|
patterns := strings.Split(input, "\n\n")[1]
|
||
|
|
|
||
|
|
// maps pattern to number of combinations
|
||
|
|
pmap := construct_pmap(towels)
|
||
|
|
|
||
|
|
counter := 0
|
||
|
|
for i, pattern := range strings.Split(patterns, "\n") {
|
||
|
|
counter += count_with_map(pattern, pmap)
|
||
|
|
}
|
||
|
|
|
||
|
|
fmt.Println(counter)
|
||
|
|
}
|