AdventOfCode2020/18/main.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"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)
}

// an expression is a list of expressions and a list of operators that intersperse those expressions, OR a number.
// as a sanity check, the length of the body list should always be one more than operators, unless both are 0,
// in which case number must be set. Luckily, we don't have to worry about 0 (the "empty" state for numbers).
type expression struct {
	body      []expression
	operators []op
	number    int
}

// op can be one of two things.
type op struct {
	plus     bool
	multiply bool
}

// 1 + 2 should parse to
// expression{
// 		body:[
// 			expression{number: 1},
// 			expression{number: 2},
// 		],
// 		operators:[
// 			op{plus: true},
// 		],
// }

// (2 * 2) + 2 should parse to:
// expression{
// 		body:[
// 			expression{
// 				body: [
// 					expression{number: 2},
// 					expression{number: 2},
// 				],
// 				operators: [
// 					op{multiply: true},
// 				],
// 			},
// 			expression{number: 2},
// 		],
// 		operators:[
// 			op{plus:true}
// 		]
// }

func parseExpression(e expression, s string) (expression, string) {
	for i := 0; i < len(s); {
		switch s[i] {
		case '(':
			sub, remainder := parseExpression(expression{}, s[i+1:])
			e.body = append(e.body, sub)
			i = len(s) - len(remainder) + 1 // skip everything we just parsed in the subexpression
		case ')':
			return e, s[i:]
		case '*':
			e.operators = append(e.operators, op{multiply: true})
			i = i + 1
		case '+':
			e.operators = append(e.operators, op{plus: true})
			i = i + 1
		case ' ':
			i = i + 1
		case '1', '2', '3', '4', '5', '6', '7', '8', '9':
			// luckily, it's all single-digit numbers and I don't need to track parser state
			// an ASCII byte number minus the rune value of 0 equals the integer itself: '1' - '0' == 49 - 48;
			// rune math returns a platform-specific int, so cast to generic int.
			e.body = append(e.body, expression{number: int(s[i] - '0')})
			i = i + 1
		}
	}
	return e, ""
}

func printExpression(e expression) string {
	result := ""
	for i := 0; i < len(e.body); i = i + 1 {
		if e.body[i].number != 0 {
			result = result + fmt.Sprintf("%d ", e.body[i].number)
		} else {
			result = result + "(" + printExpression(e.body[i]) + ") "
		}
		if i < len(e.operators) {
			if e.operators[i].multiply {
				result = result + "* "
			} else if e.operators[i].plus {
				result = result + "+ "
			}
		}
	}
	return strings.TrimSpace(result)
}

// evaluation starts at the root then descends into the sub-expressions.
func evalLeftToRight(e expression) int {
	var result int
	if e.number != 0 {
		result = e.number
	} else {
		result = evalLeftToRight(e.body[0])
	}
	for i := 0; i < len(e.operators); i = i + 1 {
		if e.operators[i].multiply {
			result = result * evalLeftToRight(e.body[i+1])
		}
		if e.operators[i].plus {
			result = result + evalLeftToRight(e.body[i+1])
		}
	}
	return result
}

// previous approach might not work...
func evalPlusThenMultiplication(e expression) int {
	var result int
	if e.number != 0 {
		result = e.number
	} else {
		result = evalPlusThenMultiplication(e.body[0])
	}
	for i := 0; i < len(e.operators); i = i + 1 {
		if e.operators[i].multiply {
			result = result * evalPlusThenMultiplication(e.body[i+1])
		}
		if e.operators[i].plus {
			result = result + evalPlusThenMultiplication(e.body[i+1])
		}
	}
	return result
}

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

	total := 0

	for scanner.Scan() {
		line := scanner.Text()
		e, _ := parseExpression(expression{}, line)
		total = total + evalLeftToRight(e)
	}

	fmt.Println(total)
}

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

	total := 0

	for scanner.Scan() {
		line := scanner.Text()
		e, _ := parseExpression(expression{}, line)
		fmt.Println(printExpression(e), "=", evalPlusThenMultiplication(e))
	}

	fmt.Println(total)
}