AdventOfCode2020/09/main.go

package main

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

func checkNotSum(t int, s []int) bool {
	for offset, i := range s {
		for _, j := range s[offset+1:] {
			if i+j == t {
				return true
			}
		}
	}
	return false
}

// this triple-nested for-loop (including sumOfSlice) cannot be the fastest way to do this...
func findMinMax(t int, s []int) (int, int) {
	for o := range s {
		for q := range s[o+1:] {
			if t == sumOfSlice(s[o:o+1+q]) {
				winner := s[o : o+1+q]
				sort.Slice(winner, func(i, j int) bool {
					return winner[i] < winner[j]
				})
				return winner[0], winner[len(winner)-1]
			}
		}
	}
	return 0, 0
}

func sumOfSlice(s []int) int {
	sum := 0
	for _, a := range s {
		sum = sum + a
	}
	return sum
}

// XMAS starts by transmitting a preamble of 25 numbers.
// After that, each number you receive should be the sum of any two of the 25 immediately previous numbers.
// The two numbers will have different values, and there might be more than one such pair.

// For example, suppose your preamble consists of the numbers 1 through 25 in a random order.
// To be valid, the next number must be the sum of two of those numbers:
// 26 would be a valid next number, as it could be 1 plus 25 (or many other pairs, like 2 and 24).
// 49 would be a valid next number, as it is the sum of 24 and 25.
// 100 would not be valid; no two of the previous 25 numbers sum to 100.
// 50 would also not be valid; although 25 appears in the previous 25 numbers, the two numbers in the pair must be different.

// The first step of attacking the weakness in the XMAS data is to find the first number in the list (after the preamble) which is not the sum of two of the 25 numbers before it.
// What is the first number that does not have this property?

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

	numbers := []int{}

	for scanner.Scan() {
		line := scanner.Text()
		i, _ := strconv.Atoi(line)
		numbers = append(numbers, i)
		if len(numbers) > 25 {
			if !checkNotSum(i, numbers[len(numbers)-26:len(numbers)-1]) {
				fmt.Println(i)
				return
			}
		}
	}
}

// The final step in breaking the XMAS encryption relies on the invalid number you just found:
// you must find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1.

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

	numbers := []int{}

	for scanner.Scan() {
		line := scanner.Text()
		i, _ := strconv.Atoi(line)
		numbers = append(numbers, i)
		if len(numbers) > 25 {
			if !checkNotSum(i, numbers[len(numbers)-26:len(numbers)-1]) {
				min, max := findMinMax(i, numbers)
				fmt.Println(min + max)
				return
			}
		}
	}
}