aoc-2020/d10/main.go

package main

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

func part1() {
	values := []int{}
	if err := processLines("input.txt", func(line string) (bool, error) {
		v, err := strconv.Atoi(line)
		values = append(values, v)
		return false, err
	}); err != nil {
		log.Fatal(err)
	}

	sort.Ints(values)

	lastVal := 0
	ones := 0
	threes := 0
	for _, v := range values {
		diff := v - lastVal
		switch diff {
		case 1:
			ones++
		case 2:
		case 3:
			threes++
		default:
			log.Fatalf("unsupported distance: %d-%d=%d", v, lastVal, diff)
			return
		}
		lastVal = v
	}
	// Final devices is a 3 jolt diff
	threes++

	fmt.Printf("Total ones %d total threes %d. Product %d\n", ones, threes, ones*threes)
}

var memoized = map[int][][]int{}

func searchSlice(s []int, start int) [][]int {
	// Check for memoized results
	if memResults, ok := memoized[start]; ok {
		fmt.Printf("Cached value for index %d", start)
		return memResults
	}
	// Check for a memoized result
	// If at the end, return an empty array
	lastVal := s[start]
	if start == len(s)-1 {
		// fmt.Println("At end! Yay!")
		return [][]int{[]int{lastVal}}
	}
	fmt.Printf("Checking index %d value %d\n", start, lastVal)
	results := [][]int{}
	for i := 1; i <= 3 && start+i < len(s); i++ {
		v := s[start+i]
		if v-lastVal > 3 {
			// Not valid, skip this
			continue
		}
		subResults := searchSlice(s, start+i)
		for _, subResult := range subResults {
			subResult = append([]int{lastVal}, subResult...)
			results = append(results, subResult)
		}
	}
	// memoize the results
	memoized[start] = results
	return results
}

var memoizedC = map[int]int{}

func searchSliceC(s *[]int, start int) int {
	// Check for memoized results
	if memResultsC, ok := memoizedC[start]; ok {
		// fmt.Printf("Cached value for index %d", start)
		return memResultsC
	}
	// Check for a memoized result
	// If at the end, return an empty array
	lastVal := (*s)[start]
	if start == len(*s)-1 {
		// fmt.Println("At end! Yay!")
		return 1
	}
	fmt.Printf("Checking index %d value %d\n", start, lastVal)
	results := 0
	for i := 1; i <= 3 && start+i < len(*s); i++ {
		v := (*s)[start+i]
		if v-lastVal > 3 {
			// Not valid, skip this
			continue
		}
		results += searchSliceC(s, start+i)

	}
	// memoize the results
	memoizedC[start] = results
	return results
}

func part2() {
	values := []int{}
	if err := processLines("input.txt", func(line string) (bool, error) {
		v, err := strconv.Atoi(line)
		values = append(values, v)
		return false, err
	}); err != nil {
		log.Fatal(err)
	}

	values = append([]int{0}, values...)
	sort.Ints(values)
	deviceJolts := values[len(values)-1] + 3
	values = append(values, deviceJolts)
	fmt.Println("Total values", len(values))

	/*
		 * paths := []int{}
		 * i := 0
		 * for i < len(values) {
		 * 	// look ahead
		 * 	for l := 3; l > 1; l-- {
		 * 		if i+l < len(values) && values[i+l]-values[i] <= 3 {
		 * 			// Look ahead is valid
		 * 			paths = append([]int{l}, paths...)
		 * 			// We only want max, so break out if we found it
		 * 			i = i + l
		 * 			break
		 * 		}
		 * 	}
		 * 	i++
		 * }
		 * fmt.Println("Paths", paths)
		 * powTotal := 1.0
		 * for _, num := range paths {
		 * 	if powTotal == 1.0 {
		 * 		powTotal = float64(num)
		 * 	} else {
		 * 		powTotal = math.Pow(float64(powTotal), float64(num))
		 * 	}
		 * }
		 * fmt.Println("Total pow paths", powTotal)
		 * productTotal := 1
		 * for _, num := range paths {
		 * 	productTotal = productTotal * num
		 * }
		 * fmt.Println("Total product paths", productTotal)
	     *
		 * totalOptions := 0
		 * i = 0
		 * options := []int{}
		 * for i < len(values) {
		 * 	// look ahead
		 * 	for l := 3; l >= 1; l-- {
		 * 		if i+l < len(values) && values[i+l]-values[i] <= 3 {
		 * 			// Look ahead is valid
		 * 			totalOptions++
		 * 			options = append(options, l)
		 * 			break
		 * 		}
		 * 	}
		 * 	i++
		 * }
		 * fmt.Println("Options", options)
		 * fmt.Println("Total sum options *2=", totalOptions*2)
		 * totalProdOptions := 1
		 * for _, num := range options {
		 * 	totalProdOptions = totalProdOptions * num
		 * }
		 * fmt.Println("Total prod options", totalProdOptions)
	*/

	fmt.Printf("Looking for device jolts %d\n", deviceJolts)
	countResults := searchSliceC(&values, 0)
	fmt.Printf("Search found %d results\n", countResults)

	/*
	 * results := searchSlice(values, 0)
	 * fmt.Printf("Search found %d results\n", len(results))
	 */
}

func main() {
	part1()
	part2()
}