aoc-2020/d09/main.go

package main

import (
	"bufio"
	"container/list"
	"fmt"
	"log"
	"os"
	"strconv"
)

func processLines(path string, f func(string) (stop bool, err error)) error {
	file, err := os.Open(path)
	if err != nil {
		return err
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	for scanner.Scan() {
		stop, err := f(scanner.Text())
		if stop || err != nil {
			return err
		}
	}
	if err := scanner.Err(); err != nil {
		return err
	}
	return nil
}

// LimitedList acts as a list with a fixed size
type LimitedList struct {
	elements  *list.List
	maxLength int
}

// Len returns the current length of the fixed list
func (ll *LimitedList) Len() int {
	return ll.elements.Len()
}

// Full checks if the fixed list is full
func (ll *LimitedList) Full() bool {
	return ll.Len() == ll.maxLength
}

// Front moves the pointer to the front of the list
func (ll *LimitedList) Front() *list.Element {
	return ll.elements.Front()
}

// Push adds an item to the back of the fixed list
func (ll *LimitedList) Push(v interface{}) *list.Element {
	if ll.Full() {
		_ = ll.elements.Remove(ll.Front())
	}
	return ll.elements.PushBack(v)
}

// NewLimitedList initializes a new list limited to the given length
func NewLimitedList(size int) *LimitedList {
	return &LimitedList{
		list.New(),
		size,
	}
}

// Pair of numbers
type Pair struct {
	A, B int
}

func searchPairs(l LimitedList, target int) (Pair, error) {
	var x, y int
	for ex := l.Front(); ex != nil; ex = ex.Next() {
		x = ex.Value.(int)
		for ey := ex.Next(); ey != nil; ey = ey.Next() {
			y = ey.Value.(int)
			if x+y == target {
				return Pair{x, y}, nil
			}
		}
	}

	return Pair{}, fmt.Errorf("could not find pair matching %d in %v", target, l)
}

func searchPairsSlice(numbers []int, target int) (Pair, error) {
	for i, x := range numbers {
		for _, y := range numbers[i:] {
			if x+y == target {
				return Pair{x, y}, nil
			}
		}
	}

	return Pair{}, fmt.Errorf("could not find pair matching %d in %v", target, numbers)
}

func part1Old() int {
	bufferSize := 25
	buffer := []int{}
	result := -1
	err := processLines("input.txt", func(line string) (stop bool, err error) {
		v, err := strconv.Atoi(line)
		if err != nil {
			return
		}
		if len(buffer) < bufferSize {
			buffer = append(buffer, v)
		} else {
			// Check number
			_, err = searchPairsSlice(buffer[len(buffer)-bufferSize:], v)
			if err != nil {
				stop = true
				err = nil
				result = v
				return
			}
			buffer = append(buffer, v)
		}
		return
	})

	if err != nil {
		log.Fatal(err)
	}

	if result < 0 {
		fmt.Println("All valid")
	} else {
		fmt.Printf("First non matching is %d\n", result)
	}

	return result
}

func part1() int {
	ll := NewLimitedList(25)
	result := -1
	err := processLines("input.txt", func(line string) (stop bool, err error) {
		v, err := strconv.Atoi(line)
		if err != nil {
			return
		}
		if !ll.Full() {
			ll.Push(v)
		} else {
			// Check number
			_, err = searchPairs(*ll, v)
			if err != nil {
				stop = true
				err = nil
				result = v
				return
			}
			ll.Push(v)
		}
		return
	})

	if err != nil {
		log.Fatal(err)
	}

	if result < 0 {
		fmt.Println("All valid")
	} else {
		fmt.Printf("First non matching is %d\n", result)
	}

	return result
}

// SumQueue acts as a list with a fixed size
type SumQueue struct {
	elements *list.List
	sum      int
}

// Len returns the current length of the queue
func (sq *SumQueue) Len() int {
	return sq.elements.Len()
}

// Sum returns the sum of the items in the queue
func (sq *SumQueue) Sum() int {
	return sq.sum
}

// Front moves the pointer to the front of the list
func (sq *SumQueue) Front() *list.Element {
	return sq.elements.Front()
}

// Push adds an item to the back of the queue
func (sq *SumQueue) Push(v int) *list.Element {
	sq.sum = sq.sum + v
	return sq.elements.PushBack(v)
}

// Pop removes an item from the queue
func (sq *SumQueue) Pop() int {
	v := sq.elements.Remove(sq.Front()).(int)
	sq.sum = sq.sum - v
	return v
}

// NewSumQueue creates a new SumQueue
func NewSumQueue() *SumQueue {
	return &SumQueue{
		list.New(),
		0,
	}
}

func part2(target int) {
	sq := NewSumQueue()
	found := false
	err := processLines("input.txt", func(line string) (stop bool, err error) {
		v, err := strconv.Atoi(line)
		// fmt.Println(v, sq.Len())
		if err != nil {
			return
		}
		if v == target {
			return
		}
		sq.Push(v)
		if sq.Sum() == target {
			// Found it!
			stop = true
			found = true
			return
		}
		for sq.Sum() > target && sq.Sum() > 0 {
			// While too big, pop from the front
			_ = sq.Pop()
		}
		if sq.Sum() == target {
			// Found it!
			stop = true
			found = true
			return
		}
		return
	})

	if err != nil {
		log.Fatal(err)
	}

	if found {
		min := -1
		max := -1
		for e := sq.Front(); e != nil; e = e.Next() {
			if min < 0 || e.Value.(int) < min {
				min = e.Value.(int)
			}
			if e.Value.(int) > max {
				max = e.Value.(int)
			}
		}
		fmt.Printf("Found %d numbers matching min %d max %d sum %d", sq.Len(), min, max, min+max)
	} else {
		fmt.Println("Didn't find anything")
	}
}

func main() {
	result := part1()
	part2(result)
}