/
main.go
115 lines (91 loc) 路 1.91 KB
/
main.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package main
import (
"bufio"
"log"
"math/big"
"os"
"strconv"
"strings"
)
func timestamp(s string) (int64, error) {
return strconv.ParseInt(s, 10, 64)
}
type Bus struct {
x int64
n int64
}
func buses(s string) ([]Bus, error) {
var i []Bus
for offset, bus := range strings.Split(s, ",") {
if bus == "x" {
continue
}
b, err := strconv.Atoi(bus)
if err != nil {
return nil, err
}
i = append(i, Bus{n: int64(b), x: int64(offset)})
}
return i, nil
}
func PartOne(timestamp int64, buses []Bus) int64 {
var waiting int64
var onbus int64
for _, bus := range buses {
val := (bus.n - (timestamp % bus.n))
if waiting == 0 || val < waiting {
waiting = val
onbus = bus.n
}
}
return waiting * onbus
}
func product(buses []Bus, f func(Bus) int64) int64 {
p := int64(1)
for _, b := range buses {
p *= f(b)
}
return p
}
func inverseModulo(g, n int64) int64 {
bigN := big.NewInt(n)
bigG := big.NewInt(g)
return (&big.Int{}).ModInverse(bigG, bigN).Int64()
}
func PartTwo(buses []Bus) int64 {
productOfModulos := product(buses, func(b Bus) int64 { return int64(b.n) })
var t int64
for _, bus := range buses {
nullifyingCoeff := (productOfModulos / bus.n)
offsetCoeff := inverseModulo(nullifyingCoeff, bus.n) * (bus.n - bus.x)
t += nullifyingCoeff * offsetCoeff
}
return t % productOfModulos
}
func main() {
f, err := os.Open("input.txt")
if err != nil {
log.Printf("opening file: %v", err)
return
}
defer f.Close()
s := bufio.NewScanner(bufio.NewReader(f))
var lines []string
for s.Scan() {
lines = append(lines, s.Text())
}
if s.Err() != nil {
log.Printf("error scanning: %v", s.Err())
return
}
timestamp, err := timestamp(lines[0])
if err != nil {
log.Printf("error timestamp: %v", err)
}
b, err := buses(lines[1])
if err != nil {
log.Printf("error buses: %v", err)
}
log.Printf("pt(1): %v", PartOne(timestamp, b))
log.Printf("pt(2): %v", PartTwo(b))
}