adventofcode/2020/day19/main.go

package main

import (
	"fmt"
	"regexp"
	"strings"

	h "git.bullercodeworks.com/brian/adventofcode/helpers"
)

func main() {
	fmt.Println("# Day 19")
	fmt.Println()
	inp := h.StdinToStringSlice()
	part := h.OptArgNumber(1, "2")
	solve(inp, h.Atoi(part))
}

/*
 8: 42 | 42 8
11: 42 31 | 42 11 31

Figure out the values of 31 & 42, then see how they
affect things as they repeat

31: 95 7 | 104 130
42: 29 104 | 115 95
*/

func solve(inp []string, part int) {
	var section int
	var rules []string
	var messages []string
	for _, v := range inp {
		if v == "" {
			// End of the rules list
			section++
		}
		switch section {
		case 0:
			rules = append(rules, v)
		case 1:
			messages = append(messages, v)
		}
	}
	if part == 1 {
		solveOne(rules, messages)
	} else {
		solveTwo(rules, messages)
	}
}

func solveOne(rules, messages []string) {
	reg := regexp.MustCompile(rulesToRegex(rules))
	var answer int
	for _, msg := range messages {
		if reg.MatchString(msg) {
			answer++
		}
	}
	fmt.Printf("## Part 1\nAnswer: %d\n", answer)
}

func solveTwo(rules, messages []string) {
	// Figure out how many levels deep we have to go to stabilize
	var answer int
	var last []int
	for i := 0; i < 1000; i++ {
		answer = 0
		rules = unwrapLoops(rules, i)
		reg := regexp.MustCompile(rulesToRegex(rules))
		for _, msg := range messages {
			if reg.MatchString(msg) {
				answer++
			}
		}
		if isStable(last, 10) {
			break
		}
		last = append(last, answer)
	}
	fmt.Printf("## Part 2\nAnswer: %d\n", answer)
}

func isStable(history []int, confidence int) bool {
	if len(history) < confidence {
		return false
	}
	last := h.MAX_INT
	for k := len(history) - 1; k > len(history)-confidence; k-- {
		if last == h.MAX_INT {
			last = history[k]
			continue
		}
		if history[k] != last {
			return false
		}
	}
	return true
}

func unwrapLoops(rules []string, depth int) []string {
	for i := range rules {
		wrk := rules[i]
		if strings.HasPrefix(wrk, "8:") {
			wrk = "8: 42 +"
		} else if strings.HasPrefix(wrk, "11:") {
			rule := "42 31"
			for k := 2; k < depth; k++ {
				rule += " | "
				for j := 0; j < k; j++ {
					rule += " 42 "
				}
				for j := 0; j < k; j++ {
					rule += " 31 "
				}
			}
			wrk = "11: " + rule
		}
		rules[i] = wrk
	}
	return rules
}

func rulesToRegex(rules []string) string {
	cache := make(map[int]string)
	for {
		if _, ok := cache[0]; ok {
			// We've cached 0, so we're all done
			break
		}
	loop:
		for _, rule := range rules {
			tokens := strings.Fields(rule)
			var num int
			fmt.Sscanf(tokens[0], "%d:", &num)
			if _, ok := cache[num]; ok {
				continue
			}
			tokens = tokens[1:]
			// A 'leaf'
			if len(tokens) == 1 && tokens[0][0] == '"' {
				cache[num] = string(tokens[0][1])
				continue
			}
			// All other rules
			ruleReg := "(?:"
			for _, tkn := range tokens {
				c := tkn[0]
				switch {
				case '0' <= c && c <= '9':
					tknN := h.Atoi(tkn)
					subRuleReg, ok := cache[tknN]
					if !ok {
						continue loop
					}
					ruleReg += subRuleReg
				case c == '|':
					ruleReg += "|"
				case c == '+':
					ruleReg += "+"
				default:
					panic("Error building RegEx:" + tkn)
				}
			}
			ruleReg += ")"
			cache[num] = ruleReg
		}
	}
	// We should be done now, we just want an exact match on rule 0
	return "^" + cache[0] + "$"
}