main.go (1632B)
1 package main
2
3 import (
4 "bufio"
5 "fmt"
6 "os"
7 "strconv"
8 "strings"
9 )
10
11 const (
12 X = 0
13 )
14
15 func readInput(filename string) (res []int) {
16 file, _ := os.Open(filename)
17 defer file.Close()
18
19 scanner := bufio.NewScanner(file)
20 for scanner.Scan() {
21 row := scanner.Text()
22 for _, elem := range strings.Split(row, ",") {
23 num, err := strconv.Atoi(elem)
24 if err == nil {
25 res = append(res, num)
26 } else {
27 res = append(res, X)
28 }
29 }
30 }
31 return
32 }
33
34 func main() {
35 input := readInput("./input.txt")
36 // 5257
37 fmt.Println(part1(input))
38 // 538703333547789
39 fmt.Println(part2(input))
40 }
41
42 func part1(input []int) (res int) {
43 minWait := input[0]
44 for _, bus := range input[1:] {
45 if bus != X {
46 wait := (bus - (input[0] % bus)) % bus
47 if wait < minWait {
48 minWait = wait
49 res = bus * wait
50 }
51 }
52 }
53 return
54 }
55
56 func modInv(a, n int64) (inv int64) {
57 // Extended Euclidean algorithm
58 // Finds modulo inverse: inv * a == 1 (mod n)
59 var (
60 t int64 = 0
61 tNew int64 = 1
62 r int64 = n
63 rNew int64 = a
64 )
65 for rNew != 0 {
66 q := r / rNew
67 t, tNew = tNew, t-q*tNew
68 r, rNew = rNew, r-q*rNew
69 }
70 return (t + n) % n
71 }
72
73 func part2(input []int) (res int64) {
74 // Chinese remainder theorem, note bus IDs are coprime
75 var (
76 lcm int64 = 1
77 fct = []int64{}
78 rem = []int64{}
79 )
80 for i, bus := range input[1:] {
81 if bus != X {
82 lcm *= int64(bus)
83 fct = append(fct, int64(bus))
84 rem = append(rem, int64((bus-i%bus)%bus))
85 }
86 }
87 for i, _ := range fct {
88 pp := lcm / fct[i]
89 inv := modInv(pp, fct[i])
90 // Change res (mod id[i]) without affecting others
91 res = (res + pp*inv*rem[i]) % lcm
92 }
93 return
94 }