86 lines
1.8 KiB
Go
86 lines
1.8 KiB
Go
package main
|
|
|
|
import (
|
|
"bufio"
|
|
"fmt"
|
|
"os"
|
|
"strconv"
|
|
"strings"
|
|
"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 partOne() {
|
|
f, _ := os.Open("input")
|
|
reader := bufio.NewReader(f)
|
|
scanner := bufio.NewScanner(reader)
|
|
|
|
// naive implementation
|
|
scanner.Scan()
|
|
numbers := strings.Split(scanner.Text(), ",")
|
|
for {
|
|
i := len(numbers) - 1
|
|
lastNumber := numbers[i]
|
|
// walk backward through the list, looking for a match
|
|
for j := range numbers {
|
|
if len(numbers) == 2020 {
|
|
fmt.Println(numbers[2019])
|
|
return
|
|
}
|
|
if i-j == 0 {
|
|
// made it to the head of the list, no matches; append 0
|
|
numbers = append(numbers, "0")
|
|
break
|
|
} else if numbers[i-j-1] == lastNumber {
|
|
// a number matched; insert the difference between the last number and when we last saw it
|
|
numbers = append(numbers, fmt.Sprintf("%d", len(numbers)-1-(i-j-1)))
|
|
break
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func partTwo() {
|
|
f, _ := os.Open("input")
|
|
reader := bufio.NewReader(f)
|
|
scanner := bufio.NewScanner(reader)
|
|
|
|
// caching implementation. It's still slow, but it at least finishes...!
|
|
scanner.Scan()
|
|
numbers := strings.Split(scanner.Text(), ",")
|
|
seen := make(map[int]int)
|
|
|
|
// load in numbers
|
|
for i, v := range numbers[:len(numbers)-1] {
|
|
j, _ := strconv.Atoi(v)
|
|
seen[j] = i
|
|
}
|
|
|
|
i := len(numbers) - 1
|
|
lastNumber, _ := strconv.Atoi(numbers[i])
|
|
for {
|
|
if seen[lastNumber] == 30000000-1 {
|
|
fmt.Println(lastNumber)
|
|
return
|
|
}
|
|
if v, ok := seen[lastNumber]; ok {
|
|
// a number matched; insert the difference between the last number and when we last saw it
|
|
seen[lastNumber] = i
|
|
lastNumber = i - v
|
|
} else {
|
|
// never seen that before
|
|
seen[lastNumber] = i
|
|
lastNumber = 0
|
|
}
|
|
i = i + 1
|
|
}
|
|
}
|