adventofcode/2020/day10/main.go

package main

import (
	"fmt"
	"sort"

	h "git.bullercodeworks.com/brian/adventofcode/helpers"
)

func main() {
	fmt.Println("# Day 10")
	inp := h.StdinToIntSlice()
	sort.Ints(inp)
	jumps := part1(inp)
	fmt.Println("## Part 1")
	fmt.Println(jumps[1] * jumps[3])

	fmt.Println("## Part 2")
	fmt.Println(part2(inp))
}

func part1(inp []int) map[int]int {
	jumps := make(map[int]int)
	var curr int
	var used []int
	wrk := make([]int, len(inp))
	copy(wrk, inp)
	for len(used) < len(inp) {
		var next int
		for i := range wrk {
			if i == 0 {
				next = wrk[i]
			} else {
				diff := wrk[i] - curr
				if diff > 0 && diff < next-curr {
					next = wrk[i]
				}
			}
		}
		jumps[next-curr]++
		curr = next
		used = append(used, curr)
		var nextList []int
		for i := range wrk {
			if wrk[i] != curr {
				nextList = append(nextList, wrk[i])
			}
		}
		wrk = make([]int, len(nextList))
		copy(wrk, nextList)
	}
	jumps[3]++
	return jumps
}

var prevs map[int][]int
var psbs map[int]int

func part2(inp []int) int {
	psbs = make(map[int]int)
	psbs[0] = 1
	prevs = make(map[int][]int)
	var phone int
	for i := range inp {
		if inp[i] > phone {
			phone = inp[i]
		}
	}
	// Add the outlet
	inp = append(inp, 0)
	// Add the phone
	phone = phone + 3
	inp = append(inp, phone)
	for i := range inp {
		prevs[inp[i]] = findPrevPoss(inp[i], inp)
	}

	return findConfigs(phone)
}

func findConfigs(curr int) int {
	if p, ok := psbs[curr]; ok {
		return p
	} else {
		var ret int
		for _, v := range prevs[curr] {
			ret = ret + findConfigs(v)
		}
		psbs[curr] = ret
		return ret
	}
}

// Find the options immediately preceeding curr
func findPrevPoss(curr int, inp []int) []int {
	if curr == 0 {
		return []int{}
	}
	var next []int
	for i := range inp {
		if inp[i] >= curr {
			continue
		}
		if curr-inp[i] <= 3 {
			next = append(next, inp[i])
		}
	}
	return next
}