sigh. fucked around with my recursive function without adding a memory map for like 30mins. solved it instantly when I just added the map.
--------Part 1-------- --------Part 2--------
Day Time Rank Score Time Rank Score
19 00:47:38 4625 0 00:49:43 3421 0
type towels struct {
next map[byte]*towels
end bool
}
func main() {
var err error
var dat []byte
dat, err = os.ReadFile("./" + os.Args[1])
check(err)
input := make([][]byte, 0)
vss := strings.Split(string(dat), "\n\n")
for _, vs := range strings.Split(vss[0], ",") {
vs = strings.TrimSpace(vs)
if len(vs) <= 0 {
continue
}
input = append(input, []byte(vs))
}
patterns := make([][]byte, 0)
for _, vs := range strings.Split(vss[1], "\n") {
vs = strings.TrimSpace(vs)
if len(vs) <= 0 {
continue
}
patterns = append(patterns, []byte(vs))
}
dmap := &towels{next: make(map[byte]*towels), end: false}
for _, in := range input {
curr := dmap
for i, b := range in {
nm, ok := curr.next[b]
if !ok {
nm = &towels{next: make(map[byte]*towels), end: false}
curr.next[b] = nm
}
if i == len(in)-1 {
nm.end = true
curr.next[b] = nm
}
curr = nm
}
}
sum := 0
gcount := 0
for _, pat := range patterns {
fmt.Println("pat", string(pat))
ccount := findp(dmap, make(map[string]int), pat)
if ccount > 0 {
fmt.Println("make")
sum++
} else {
fmt.Println("cant")
}
gcount += ccount
}
fmt.Println("sum", sum)
fmt.Println("sum1", gcount)
}
func findp(pats *towels, mem map[string]int, word []byte) int {
if ss, ok := mem[string(word)]; ok {
return ss
}
if len(word) == 0 {
return 1
}
npats := pats
ok := false
ccount := 0
for i, cha := range word {
npats, ok = npats.next[cha]
if !ok {
break
}
if ok && npats.end {
// fmt.Println("match", string(word[:i+1]))
cc := findp(pats, mem, word[i+1:])
ccount += cc
}
}
mem[string(word)] = ccount
return ccount
}
