From fac8626030e19a50bf652b1f665d5836a3b79616 Mon Sep 17 00:00:00 2001
From: Steven Le Rouzic <steven.lerouzic@gmail.com>
Date: Thu, 19 Dec 2024 23:34:57 +0100
Subject: Day 19
---
day19/main.go | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 105 insertions(+)
create mode 100644 day19/main.go
(limited to 'day19/main.go')
diff --git a/day19/main.go b/day19/main.go
new file mode 100644
index 0000000..96dac55
--- /dev/null
+++ b/day19/main.go
@@ -0,0 +1,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
+}
--
cgit