advent-of-code

commit 027a3b7ed112e16cf7705b5c12258f39147ebd8c
parent 328fcd1c0ebf48d91ea2323e9a35017cb15d28e8
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date:   Sun, 13 Dec 2020 09:19:37 -0600

Add 2020 day 13

Diffstat:
A
2020/day13/input.txt
 | 
2
++
A
2020/day13/main.go
 | 
94
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 96 insertions(+), 0 deletions(-)
diff --git a/2020/day13/input.txt b/2020/day13/input.txt
@@ -0,0 +1,2 @@
+1002578
+19,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,751,x,29,x,x,x,x,x,x,x,x,x,x,13,x,x,x,x,x,x,x,x,x,23,x,x,x,x,x,x,x,431,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,17
diff --git a/2020/day13/main.go b/2020/day13/main.go
@@ -0,0 +1,94 @@
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strconv"
+	"strings"
+)
+
+const (
+	X = 0
+)
+
+func readInput(filename string) (res []int) {
+	file, _ := os.Open(filename)
+	defer file.Close()
+
+	scanner := bufio.NewScanner(file)
+	for scanner.Scan() {
+		row := scanner.Text()
+		for _, elem := range strings.Split(row, ",") {
+			num, err := strconv.Atoi(elem)
+			if err == nil {
+				res = append(res, num)
+			} else {
+				res = append(res, X)
+			}
+		}
+	}
+	return
+}
+
+func main() {
+	input := readInput("./input.txt")
+	// 5257
+	fmt.Println(part1(input))
+	// 538703333547789
+	fmt.Println(part2(input))
+}
+
+func part1(input []int) (res int) {
+	minWait := input[0]
+	for _, bus := range input[1:] {
+		if bus != X {
+			wait := (bus - (input[0] % bus)) % bus
+			if wait < minWait {
+				minWait = wait
+				res = bus * wait
+			}
+		}
+	}
+	return
+}
+
+func modInv(a, n int64) (inv int64) {
+	// Extended Euclidean algorithm
+	// Finds modulo inverse: inv * a == 1 (mod n)
+	var (
+		t    int64 = 0
+		tNew int64 = 1
+		r    int64 = n
+		rNew int64 = a
+	)
+	for rNew != 0 {
+		q := r / rNew
+		t, tNew = tNew, t-q*tNew
+		r, rNew = rNew, r-q*rNew
+	}
+	return (t + n) % n
+}
+
+func part2(input []int) (res int64) {
+	// Chinese remainder theorem, note bus IDs are coprime
+	var (
+		lcm int64 = 1
+		fct       = []int64{}
+		rem       = []int64{}
+	)
+	for i, bus := range input[1:] {
+		if bus != X {
+			lcm *= int64(bus)
+			fct = append(fct, int64(bus))
+			rem = append(rem, int64((bus-i%bus)%bus))
+		}
+	}
+	for i, _ := range fct {
+		pp := lcm / fct[i]
+		inv := modInv(pp, fct[i])
+		// Change res (mod id[i]) without affecting others
+		res = (res + pp*inv*rem[i]) % lcm
+	}
+	return
+}