122 lines
2.0 KiB
Go
122 lines
2.0 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"log"
|
|
"os"
|
|
|
|
"git.annabunch.es/annabunches/adventofcode/2020/lib/util"
|
|
)
|
|
|
|
type SumTracker map[int][]Tuple
|
|
|
|
type Tuple struct {
|
|
First, Second int
|
|
}
|
|
|
|
func checkValue(sumMap SumTracker, value int) bool {
|
|
_, ok := sumMap[value]
|
|
return ok
|
|
}
|
|
|
|
func addSums(sumMap SumTracker, values []int, index int) {
|
|
for i := index - 25; i < index; i++ {
|
|
sum := values[i] + values[index]
|
|
sumMap[sum] = append(sumMap[sum], Tuple{First: i, Second: index})
|
|
}
|
|
}
|
|
|
|
func removeSums(sumMap SumTracker, index int) {
|
|
for sum, tupleList := range sumMap {
|
|
newList := make([]Tuple, 0)
|
|
|
|
for _, tuple := range tupleList {
|
|
if !(tuple.First == index || tuple.Second == index) {
|
|
newList = append(newList, tuple)
|
|
}
|
|
}
|
|
sumMap[sum] = newList
|
|
if len(sumMap[sum]) == 0 {
|
|
delete(sumMap, sum)
|
|
}
|
|
}
|
|
}
|
|
|
|
// find and return the slice of values that sums to sum
|
|
func findListSum(values []int, sum int) []int {
|
|
i := 0
|
|
j := 0
|
|
total := 0
|
|
for total != sum {
|
|
for total < sum {
|
|
if j >= len(values) {
|
|
log.Panicf("Couldn't find a match.")
|
|
}
|
|
|
|
total += values[j]
|
|
j++
|
|
}
|
|
|
|
for total > sum {
|
|
total -= values[i]
|
|
i++
|
|
}
|
|
}
|
|
|
|
return values[i:j]
|
|
}
|
|
|
|
func sumMinMax(values []int) int {
|
|
min := values[0]
|
|
max := values[0]
|
|
|
|
for _, x := range values {
|
|
if x < min {
|
|
min = x
|
|
}
|
|
|
|
if x > max {
|
|
max = x
|
|
}
|
|
}
|
|
|
|
return min + max
|
|
}
|
|
|
|
func main() {
|
|
step := os.Args[1]
|
|
values := util.InputParserInts(os.Args[2])
|
|
|
|
var badValue int
|
|
sumMap := make(SumTracker)
|
|
|
|
// build up the preamble
|
|
for i := 0; i < 25; i++ {
|
|
for j := i + 1; j < 25; j++ {
|
|
sum := values[i] + values[j]
|
|
if _, ok := sumMap[sum]; !ok {
|
|
sumMap[sum] = make([]Tuple, 0)
|
|
}
|
|
|
|
sumMap[sum] = append(sumMap[sum], Tuple{First: i, Second: j})
|
|
}
|
|
}
|
|
|
|
for i := 25; i < len(values); i++ {
|
|
if !checkValue(sumMap, values[i]) {
|
|
badValue = values[i]
|
|
break
|
|
}
|
|
addSums(sumMap, values, i)
|
|
removeSums(sumMap, i-25)
|
|
}
|
|
|
|
switch step {
|
|
case "1":
|
|
fmt.Println(badValue)
|
|
case "2":
|
|
sumValues := findListSum(values, badValue)
|
|
fmt.Println(sumMinMax(sumValues))
|
|
}
|
|
}
|