AdventOfCode2020/19/main.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
	"time"
)

func main() {
	start := time.Now()
	partOne()
	duration := time.Since(start)
	partTwo()
	duration2 := time.Since(start)
	fmt.Printf("p1: %s, p2: %s\n", duration, duration2-duration)
}

// options: 20 => [][20]; 20 10 => [][20, 10]; 20 | 10 => [][20][10]; 20 10 | 39 12 => [][20, 10][39, 12];
// token is only set for the two "bottom" rules of "a" and "b"
// options and token will never both be set
// ints all point to rule numbers in overall rule list
type rule struct {
	name    int
	options [][]int
	token   rune
}

func parseRule(s string) rule {
	r := rule{
		options: make([][]int, 0),
	}
	sp := strings.Split(s, ": ")
	r.name, _ = strconv.Atoi(sp[0])

	// either it's a token rule...
	if sp[1] == `"a"` || sp[1] == `"b"` {
		r.token = []rune(strings.Trim(sp[1], `"`))[0]
		return r
	}

	// ...or an options rule.
	opts := strings.Split(sp[1], " | ")
	for _, o := range opts {
		opt := []int{}
		for _, i := range strings.Split(o, " ") {
			ii, _ := strconv.Atoi(i)
			opt = append(opt, ii)
		}
		r.options = append(r.options, opt)
	}
	return r
}

func validateString(rules []rule, currentRule int, s string) (bool, string) {
	activeRule := rules[currentRule]
	// if we're run out of string, the rule obviously cannot match
	if len(s) == 0 {
		return false, ""
	}
	// we've reached a leaf; check if the current head of the string matches our expected rune
	if len(activeRule.options) == 0 {
		return []rune(s)[0] == activeRule.token, s[1:]
	}
	// if there's only one option, attempt to apply the rules
	if len(activeRule.options) == 1 {
		option := activeRule.options[0]
		if len(option) == 1 {
			return validateString(rules, option[0], s)
		}
		if len(option) == 2 {
			ok, remainder := validateString(rules, option[0], s)
			if ok {
				return validateString(rules, option[1], remainder)
			}
		}
		if len(option) == 3 {
			ok, remainder := validateString(rules, option[0], s)
			if ok {
				ok, remainder = validateString(rules, option[1], remainder)
			}
			if ok {
				return validateString(rules, option[2], remainder)
			}
		}
	}
	// otherwise, we need to branch into our options and try and apply their rules
	if len(activeRule.options) == 2 {
		ok := false
		remainder := ""
		optionOne := activeRule.options[0]
		if len(optionOne) == 1 {
			ok, remainder = validateString(rules, optionOne[0], s)
		}
		if len(optionOne) == 2 {
			ok, remainder = validateString(rules, optionOne[0], s)
			if ok {
				ok, remainder = validateString(rules, optionOne[1], remainder)
			}
		}
		if len(optionOne) == 3 {
			ok, remainder = validateString(rules, optionOne[0], s)
			if ok {
				ok, remainder = validateString(rules, optionOne[1], remainder)
			}
			if ok {
				ok, remainder = validateString(rules, optionOne[2], remainder)
			}
		}
		if ok {
			return ok, remainder
		}
		optionTwo := activeRule.options[1]
		if len(optionTwo) == 1 {
			ok, _ = validateString(rules, optionTwo[0], s)
		}
		if len(optionTwo) == 2 {
			ok, remainder = validateString(rules, optionTwo[0], s)
			if ok {
				return validateString(rules, optionTwo[1], remainder)
			}
		}
		if len(optionTwo) == 3 {
			ok, remainder = validateString(rules, optionTwo[0], s)
			if ok {
				ok, remainder = validateString(rules, optionTwo[1], remainder)
			}
			if ok {
				return validateString(rules, optionTwo[2], remainder)
			}
		}
	}
	return false, s
}

func partOne() {
	f, _ := os.Open("input")
	reader := bufio.NewReader(f)
	scanner := bufio.NewScanner(reader)

	rules := make([]rule, 134)
	for scanner.Scan() {
		line := scanner.Text()
		if line == "" {
			break
		}
		rule := parseRule(line)
		rules[rule.name] = rule
	}

	total := 0
	for scanner.Scan() {
		line := scanner.Text()
		if ok, _ := validateString(rules, 0, line); ok {
			fmt.Println("VALID:", line)
			total = total + 1
		} else {
			fmt.Println("INVALID:", line)
		}
	}

	fmt.Println(total)
}

func partTwo() {
	f, _ := os.Open("input")
	reader := bufio.NewReader(f)
	scanner := bufio.NewScanner(reader)

	for scanner.Scan() {
		// line := scanner.Text()
	}
}