advent-of-code

Perserverance, or the lack thereof

git clone git://git.shimmy1996.com/advent-of-code.git

main.go (2820B)

    1 package main
    2 
    3 import (
    4 	"bufio"
    5 	"fmt"
    6 	"os"
    7 	"regexp"
    8 	"strconv"
    9 )
   10 
   11 const (
   12 	LETTER = -1 - iota
   13 	PIPE
   14 	PAREN_L
   15 	PAREN_R
   16 	PLUS
   17 	BRACE_L
   18 	BRACE_R
   19 )
   20 
   21 type Rules map[int][]int
   22 
   23 func readInput(filename string) (rules Rules, messages []string) {
   24 	file, _ := os.Open(filename)
   25 	defer file.Close()
   26 
   27 	sep := regexp.MustCompile(`[: "]+`)
   28 	scanner := bufio.NewScanner(file)
   29 	rules = Rules{}
   30 	for scanner.Scan() {
   31 		line := scanner.Text()
   32 		if line == "" {
   33 			break
   34 		}
   35 		tokens := []int{}
   36 		for _, token := range sep.Split(line, -1) {
   37 			if token == "" {
   38 				continue
   39 			}
   40 			if num, err := strconv.Atoi(token); err == nil {
   41 				tokens = append(tokens, num)
   42 			} else {
   43 				switch token {
   44 				case "|":
   45 					tokens = append(tokens, PIPE)
   46 				default:
   47 					tokens = append(tokens, LETTER, int(token[0]))
   48 				}
   49 			}
   50 		}
   51 		rules[tokens[0]] = tokens[1:]
   52 	}
   53 	for scanner.Scan() {
   54 		messages = append(messages, scanner.Text())
   55 	}
   56 	return
   57 }
   58 
   59 func main() {
   60 	rules, messages := readInput("./input.txt")
   61 	// 272
   62 	fmt.Println(part1(rules, messages))
   63 	// 374
   64 	fmt.Println(part2(rules, messages))
   65 }
   66 
   67 func toRegexp(rules Rules, target int) string {
   68 	expr := ""
   69 	stack := []int{target}
   70 	for len(stack) > 0 {
   71 		switch stack[0] {
   72 		case LETTER:
   73 			expr += string(byte(stack[1]))
   74 			stack = stack[2:]
   75 		case PIPE:
   76 			expr, stack = expr+"|", stack[1:]
   77 		case PAREN_L:
   78 			expr, stack = expr+"(", stack[1:]
   79 		case PAREN_R:
   80 			expr, stack = expr+")", stack[1:]
   81 		case PLUS:
   82 			expr, stack = expr+"+", stack[1:]
   83 		case BRACE_L:
   84 			expr, stack = expr+"{", stack[1:]
   85 			for stack[0] != BRACE_R {
   86 				expr, stack = expr+string('0'+stack[0]), stack[1:]
   87 			}
   88 			expr, stack = expr+"}", stack[1:]
   89 		default:
   90 			sub := append(append([]int{PAREN_L}, rules[stack[0]]...), PAREN_R)
   91 			stack = append(sub, stack[1:]...)
   92 		}
   93 	}
   94 	return expr
   95 }
   96 
   97 func part1(rules Rules, messages []string) (matchCount int) {
   98 	matcher := regexp.MustCompile("^" + toRegexp(rules, 0) + "$")
   99 	for _, msg := range messages {
  100 		if matcher.MatchString(msg) {
  101 			matchCount += 1
  102 		}
  103 	}
  104 	return
  105 }
  106 
  107 func part2(rules Rules, messages []string) (matchCount int) {
  108 	rules[8] = append(rules[8], PLUS)
  109 	// Find max repetitations of 42 and 31
  110 	max42, matcher42 := 0, regexp.MustCompile(toRegexp(rules, 42))
  111 	max31, matcher31 := 0, regexp.MustCompile(toRegexp(rules, 31))
  112 	for _, msg := range messages {
  113 		if count := len(matcher42.FindAllStringSubmatch(msg, -1)); count > max42 {
  114 			max42 = count
  115 		}
  116 		if count := len(matcher31.FindAllStringSubmatch(msg, -1)); count > max31 {
  117 			max31 = count
  118 		}
  119 	}
  120 	for i := 2; i <= max42 && i <= max31; i++ {
  121 		rules[11] = append(rules[11], PIPE, 42, BRACE_L, i, BRACE_R, 31, BRACE_L, i, BRACE_R)
  122 	}
  123 	matcher := regexp.MustCompile("^" + toRegexp(rules, 0) + "$")
  124 	for _, msg := range messages {
  125 		if matcher.MatchString(msg) {
  126 			matchCount += 1
  127 		}
  128 	}
  129 	return
  130 }