AdventOfCode2020/19/main.go

176 lines
4.0 KiB
Go
Raw Permalink Normal View History

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()
}
}