var input = []int64{15, 12, 0, 14, 3, 1}

func main() {
	sw := aoc.NewStopwatch()
	fmt.Println("Step 1:")
	fmt.Println(memoryGame(input, 2020))
	fmt.Println(sw.Elapsed())

	sw.Reset()
	fmt.Println("Step 2:")
	fmt.Println(memoryGame(input, 30000000))
	fmt.Println(sw.Elapsed())
}

// memoryGame simulates the memory game and returns the number stated on
// the specified turn
func memoryGame(input []int64, finalTurn int64) int64 {
	seen := make(map[int64]int64)
	for i, n := range input {
		seen[n] = int64(i + 1) // The first turn is turn 1, not turn 0
	}
	last := seen[int64(len(seen)-1)]
	wasNew := true
	delta := int64(0)
	for i := len(seen) + 1; int64(i) <= finalTurn; i++ {
		last = delta
		if wasNew {
			last = 0
		}

		oldValue, found := seen[last]
		wasNew = !found
		if found {
			delta = int64(i) - oldValue
		}
		seen[last] = int64(i)
	}
	return last
}