-
Notifications
You must be signed in to change notification settings - Fork 1
/
aoc6.go
127 lines (105 loc) · 2.38 KB
/
aoc6.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
116
117
118
119
120
121
122
123
124
125
126
127
// aoc6.go --
// advent of code 2023 day 6
//
// https://adventofcode.com/2023/day/6
// https://github.com/erik-adelbert/aoc
//
// (ɔ) Erik Adelbert - erik_AT_adelbert_DOT_fr
// -------------------------------------------
// 2023-12-6: initial commit
package main
import (
"bufio"
"fmt"
"os"
"strings"
)
func main() {
input := bufio.NewScanner(os.Stdin)
// parse multiple (part1) and single (part2) race data
times, T := parse(input) // first line
dists, D := parse(input) // second line
// solve V.x = d with V = (t - x) <=> (x - t) * x - d = 0
// this quadratic formula leads to
// Δ = √(t² + 4d) / 2
// x₀₁ = t ± √(t² + 4d) / 2
// solution r = | ⌈x₀⌉ - ⌊x₁⌋ | + 1
solve := func(t, d int) int {
Δ := isqrt(t*t - 4*d)
x0 := (t - Δ) / 2 // divide by two now
x1 := t - x0
if x0*(t-x0) <= d {
x0++ // ceil
}
if x1*(t-x1) <= d {
x1-- // floor
}
return x1 - x0 + 1
}
Π := 1
for i := range times {
Π *= solve(times[i], dists[i])
}
fmt.Println(Π, solve(T, D))
}
func parse(input *bufio.Scanner) ([]int, int) {
input.Scan() // advance input reading
// ditch header, split fields
line := input.Text()
fields := fields(line[index(line, ":")+1:])
a := make([]int, 0, len(fields)) // part1
var A strings.Builder // part2
for _, s := range fields {
a = append(a, atoi(s)) // convert/collect for part1
A.WriteString(s) // concatenate for part2
}
return a, atoi(A.String())
}
// Go package strings wrapper/sugar
var index, fields = strings.Index, strings.Fields
// strconv.Atoi simplified core loop
// s is ^\d+$
func atoi(s string) (n int) {
for i := range s {
n = 10*n + int(s[i]-'0')
}
return
}
// isqrt
var tab64 = [64]uint64{
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5,
}
func log2(n uint64) uint64 {
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
n |= n >> 32
return tab64[((n-(n>>1))*0x07EDD5E59A4E28C2)>>58]
}
func isqrt(x int) int {
x64 := uint64(x)
var b, r uint64
for p := uint64(1 << ((uint(log2(x64)) >> 1) << 1)); p != 0; p >>= 2 {
b = r | p
r >>= 1
if x64 >= b {
x64 -= b
r |= p
}
}
return int(r)
}
func debug(a ...any) {
if false {
fmt.Println(a...)
}
}