107 lines
2.3 KiB
Go
107 lines
2.3 KiB
Go
|
package main
|
||
|
|
|
||
|
|
import (
|
||
|
|
"os"
|
||
|
|
"fmt"
|
||
|
|
"strings"
|
||
|
|
"strconv"
|
||
|
|
"math"
|
||
|
|
)
|
||
|
|
|
||
|
|
// data types
|
||
|
|
type Equation struct {
|
||
|
|
result int
|
||
|
|
params []int
|
||
|
|
}
|
||
|
|
|
||
|
|
// general util
|
||
|
|
func check(e error) {
|
||
|
|
if e != nil { panic(e) }
|
||
|
|
}
|
||
|
|
|
||
|
|
func newEquations(data string) []*Equation {
|
||
|
|
/* Reads the puzzle input, return a list of Equation structs.
|
||
|
|
*/
|
||
|
|
lines := strings.Split(data, "\n")
|
||
|
|
equations := make([]*Equation, 0, len(lines))
|
||
|
|
|
||
|
|
for _, line := range lines {
|
||
|
|
split_line := strings.Split(line, ":")
|
||
|
|
|
||
|
|
// get result/ number before the colon
|
||
|
|
result, err := strconv.Atoi(split_line[0])
|
||
|
|
check(err)
|
||
|
|
|
||
|
|
// parse paramter/ numbers after the colon
|
||
|
|
str_params := strings.Split(strings.TrimSpace(split_line[1]), " ")
|
||
|
|
params := make([]int, 0, len(str_params))
|
||
|
|
for _, num := range str_params {
|
||
|
|
param, err := strconv.Atoi(num)
|
||
|
|
check(err)
|
||
|
|
|
||
|
|
params = append(params, param)
|
||
|
|
}
|
||
|
|
|
||
|
|
equations = append(equations, &Equation{ result: result, params: params })
|
||
|
|
}
|
||
|
|
|
||
|
|
return equations
|
||
|
|
}
|
||
|
|
|
||
|
|
func incr(arr []bool) []bool {
|
||
|
|
/* least significant bit first increment, true = 1/ false = 0 */
|
||
|
|
over := true
|
||
|
|
for i := range arr {
|
||
|
|
if !over { break }
|
||
|
|
over = over && arr[i]
|
||
|
|
arr[i] = !arr[i]
|
||
|
|
}
|
||
|
|
return arr
|
||
|
|
}
|
||
|
|
|
||
|
|
func isValid(eq *Equation) bool {
|
||
|
|
/* Checks whether the equation could be right by combining the paramters in
|
||
|
|
* all possible ways and comparing to the result.
|
||
|
|
*/
|
||
|
|
|
||
|
|
operators := make([]bool, len(eq.params) - 1)
|
||
|
|
|
||
|
|
for range int(math.Pow(2.0, float64(len(operators)))) {
|
||
|
|
|
||
|
|
// calc possible result
|
||
|
|
acc := eq.params[0]
|
||
|
|
for i, op := range operators {
|
||
|
|
if op {
|
||
|
|
acc += eq.params[i + 1]
|
||
|
|
} else {
|
||
|
|
acc *= eq.params[i + 1]
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// compare to actual result
|
||
|
|
if acc == eq.result { return true }
|
||
|
|
|
||
|
|
operators = incr(operators)
|
||
|
|
}
|
||
|
|
return false
|
||
|
|
}
|
||
|
|
|
||
|
|
// main loop
|
||
|
|
func main() {
|
||
|
|
|
||
|
|
// read in file
|
||
|
|
dat, err := os.ReadFile("data.txt")
|
||
|
|
check(err)
|
||
|
|
dat_str := strings.TrimSpace(string(dat))
|
||
|
|
|
||
|
|
|
||
|
|
equations := newEquations(dat_str)
|
||
|
|
|
||
|
|
result := 0
|
||
|
|
for _, eq := range equations {
|
||
|
|
if isValid(eq) { result += eq.result }
|
||
|
|
}
|
||
|
|
|
||
|
|
fmt.Println(result)
|
||
|
|
}
|