Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit bd6ec98

Browse filesBrowse files
lucianoqlucianoq
committed
Solution for 2023, day 24 + vendor
1 parent bac48cc commit bd6ec98
Copy full SHA for bd6ec98

File tree

Expand file treeCollapse file tree

336 files changed

+75949
-1
lines changed
Filter options

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Dismiss banner
Expand file treeCollapse file tree

336 files changed

+75949
-1
lines changed

‎2023/24/Makefile

Copy file name to clipboard
+17Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
main1:
2+
go build -o main1 main1.go common.go
3+
4+
main2:
5+
go build -o main2 main2.go common.go
6+
7+
.PHONY: run1 run2 clean
8+
9+
run1: main1
10+
./main1 <input
11+
12+
run2: main2
13+
./main2 <input
14+
15+
clean:
16+
rm -f main1 main2
17+

‎2023/24/common.go

Copy file name to clipboard
+31Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package main
2+
3+
import (
4+
"bufio"
5+
"fmt"
6+
"os"
7+
)
8+
9+
type P struct{ x, y, z float64 }
10+
11+
type HailStone struct{ Pos, Vel P }
12+
13+
func parse() []HailStone {
14+
hail := []HailStone{}
15+
scanner := bufio.NewScanner(os.Stdin)
16+
for scanner.Scan() {
17+
ice := HailStone{}
18+
_, _ = fmt.Sscanf(
19+
scanner.Text(),
20+
"%f, %f, %f @ %f, %f, %f",
21+
&ice.Pos.x,
22+
&ice.Pos.y,
23+
&ice.Pos.z,
24+
&ice.Vel.x,
25+
&ice.Vel.y,
26+
&ice.Vel.z,
27+
)
28+
hail = append(hail, ice)
29+
}
30+
return hail
31+
}

‎2023/24/main1.go

Copy file name to clipboard
+74Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package main
2+
3+
import "fmt"
4+
5+
const (
6+
Min = 200000000000000
7+
Max = 400000000000000
8+
)
9+
10+
func main() {
11+
hail := parse()
12+
13+
count := 0
14+
for i := 0; i < len(hail)-1; i++ {
15+
for j := i + 1; j < len(hail); j++ {
16+
p, intersect := findIntersection(hail[i], hail[j])
17+
18+
if intersect {
19+
if p.x >= Min && p.x <= Max && p.y >= Min && p.y <= Max {
20+
count++
21+
}
22+
}
23+
}
24+
}
25+
26+
fmt.Println(count)
27+
}
28+
29+
func findIntersection(h1, h2 HailStone) (P, bool) {
30+
// (1) xf = x0 + vx*t ==> t = (xf-x0)/vx
31+
// (2) yf = y0 + vy*t
32+
//
33+
// Combining (1) and (2)
34+
// yf = y0 + vy * (xf-x0)/vx
35+
// yf = y0 + (vy/vx)(xf-x0)
36+
// yf = (vy/vx) * xf + [ y0 - (vy/vx)*x0 ]
37+
// y = m * x + q
38+
//
39+
// m = vy/vx
40+
// q = y0 - m*x0
41+
42+
m1 := h1.Vel.y / h1.Vel.x
43+
m2 := h2.Vel.y / h2.Vel.x
44+
45+
if m1 == m2 {
46+
// parallel lines
47+
return P{}, false
48+
}
49+
50+
q1 := h1.Pos.y - m1*h1.Pos.x
51+
q2 := h2.Pos.y - m2*h2.Pos.x
52+
53+
xf := (q2 - q1) / (m1 - m2)
54+
yf := m1*xf + q1
55+
56+
// they meet in (xf,yf)
57+
// need to check if this was in the past
58+
59+
// From (1)
60+
t1 := (xf - h1.Pos.x) / h1.Vel.x
61+
if t1 < 0 {
62+
// past
63+
return P{}, false
64+
}
65+
66+
// From (1)
67+
t2 := (yf - h2.Pos.y) / h2.Vel.y
68+
if t2 < 0 {
69+
// past
70+
return P{}, false
71+
}
72+
73+
return P{xf, yf, 0}, true
74+
}

‎2023/24/main2.go

Copy file name to clipboard
+130Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
package main
2+
3+
import (
4+
"fmt"
5+
6+
"gonum.org/v1/gonum/mat"
7+
)
8+
9+
// Given:
10+
// (1) p¹ = p₀¹ + v¹⋅t
11+
// (2) p² = p₀² + v²⋅t
12+
// (3) p³ = p₀³ + v³⋅t
13+
// ...
14+
//
15+
// Find:
16+
// p = p₀ + v⋅t
17+
//
18+
// such as:
19+
// p¹=p when t¹=t
20+
// p²=p when t²=t
21+
// p³=p when t³=t
22+
// ...
23+
//
24+
// where
25+
// pⁿ = [pₓⁿ, pᵧⁿ, pₛⁿ]
26+
// p₀ⁿ = [pₓ₀ⁿ, pᵧⁿ, pₛ₀ⁿ]
27+
// vⁿ = [vₓⁿ, vᵧⁿ, vₛⁿ]
28+
29+
// p¹ + v¹⋅t = p + v⋅t
30+
// p² + v²⋅t = p + v⋅t
31+
// p³ + v³⋅t = p + v⋅t
32+
// pⁿ + vⁿ⋅t = p + v⋅t
33+
//
34+
// (p - p¹) = (v¹ - v)t¹
35+
// (p - p²) = (v² - v)t²
36+
// (p - p³) = (v³ - v)t³
37+
// (p - pⁿ) = (vⁿ - v)tⁿ
38+
// and so:
39+
// (p - pⁿ) ⋅ (v-vⁿ) = 0
40+
func main() {
41+
hail := parse()
42+
43+
// Ax = b
44+
//
45+
// A = [ 0, -v⁰ₛ +v¹ₛ, v⁰ᵧ - v¹ᵧ, 0, -p¹ₛ +p⁰ₛ, p¹ᵧ -p⁰ᵧ
46+
// v⁰ₛ -v¹ₛ, 0, -v⁰ₓ + v¹ₓ, p¹ₛ -p⁰ₛ, 0, -p¹ₓ +p⁰ₓ
47+
// -v⁰ᵧ +v¹ᵧ, v⁰ₓ -v¹ₓ, 0, -p¹ᵧ +p⁰ᵧ, p¹ₓ -p⁰ₓ, 0
48+
// 0, -v⁰ₛ +v²ₛ, v⁰ᵧ - v²ᵧ, 0, -p²ₛ +p⁰ₛ, p²ᵧ -p⁰ᵧ
49+
// v⁰ₛ -v²ₛ, 0, -v⁰ₓ + v²ₓ, p²ₛ -p⁰ₛ, 0, -p²ₓ +p⁰ₓ
50+
// -v⁰ᵧ +v²ᵧ, v⁰ₓ -v²ₓ, 0, -p²ᵧ +p⁰ᵧ, p²ₓ -p⁰ₓ, 0 ]
51+
//
52+
// x = [ pₓ
53+
// pᵧ
54+
// pₛ
55+
// vₓ
56+
// vᵧ
57+
// vₛ ]
58+
//
59+
// b = [ p¹ᵧ⋅v¹ₛ -p¹ₛ⋅v¹ᵧ -p⁰ᵧ⋅v⁰ₛ +p⁰ₛ⋅v⁰ᵧ,
60+
// p¹ₛ⋅v¹ₓ -p¹ₓ⋅v¹ₛ -p⁰ₛ⋅v⁰ₓ +p⁰ₓ⋅v⁰ₛ,
61+
// p¹ₓ⋅v¹ᵧ -p¹ᵧ⋅v¹ₓ -p⁰ₓ⋅v⁰ᵧ +p⁰ᵧ⋅v⁰ₓ,
62+
// p²ᵧ⋅v²ₛ -p²ₛ⋅v²ᵧ -p⁰ᵧ⋅v⁰ₛ +p⁰ₛ⋅v⁰ᵧ,
63+
// p²ₛ⋅v²ₓ -p²ₓ⋅v²ₛ -p⁰ₛ⋅v⁰ₓ +p⁰ₓ⋅v⁰ₛ,
64+
// p²ₓ⋅v²ᵧ -p²ᵧ⋅v²ₓ -p⁰ₓ⋅v⁰ᵧ +p⁰ᵧ⋅v⁰ₓ ]
65+
//
66+
67+
// hail[0] with hail[1]
68+
// (p0 - p[1]) x (v0 - v[1]) == 0
69+
A00 := diff(crossMatrix(hail[0].Vel), crossMatrix(hail[1].Vel))
70+
A03 := diff(crossMatrix(hail[1].Pos), crossMatrix(hail[0].Pos))
71+
72+
// hail[0] with hail[2]
73+
// (p0 - p[2]) x (v0 - v[2]) == 0
74+
A30 := diff(crossMatrix(hail[0].Vel), crossMatrix(hail[2].Vel))
75+
A33 := diff(crossMatrix(hail[2].Pos), crossMatrix(hail[0].Pos))
76+
77+
A := mat.NewDense(6, 6, []float64{
78+
A00[0], A00[1], A00[2], A03[0], A03[1], A03[2],
79+
A00[3], A00[4], A00[5], A03[3], A03[4], A03[5],
80+
A00[6], A00[7], A00[8], A03[6], A03[7], A03[8],
81+
A30[0], A30[1], A30[2], A33[0], A33[1], A33[2],
82+
A30[3], A30[4], A30[5], A33[3], A33[4], A33[5],
83+
A30[6], A30[7], A30[8], A33[6], A33[7], A33[8],
84+
})
85+
86+
b0 := diff(hail[1].Pos.cross(hail[1].Vel).toF(), hail[0].Pos.cross(hail[0].Vel).toF())
87+
b3 := diff(hail[2].Pos.cross(hail[2].Vel).toF(), hail[0].Pos.cross(hail[0].Vel).toF())
88+
89+
b := mat.NewVecDense(6, []float64{b0[0], b0[1], b0[2], b3[0], b3[1], b3[2]})
90+
91+
var x mat.VecDense
92+
_ = x.SolveVec(A, b)
93+
94+
rock := HailStone{
95+
Pos: P{x.At(0, 0), x.At(1, 0), x.At(2, 0)},
96+
Vel: P{x.At(3, 0), x.At(4, 0), x.At(5, 0)},
97+
}
98+
99+
fmt.Printf("%.0f\n", rock.Pos.x+rock.Pos.y+rock.Pos.z)
100+
}
101+
102+
func crossMatrix(p P) []float64 {
103+
return []float64{
104+
0, -p.z, p.y,
105+
p.z, 0, -p.x,
106+
-p.y, p.x, 0,
107+
}
108+
}
109+
110+
func diff(a, b []float64) []float64 {
111+
res := make([]float64, len(a))
112+
for i := 0; i < len(a); i++ {
113+
res[i] = a[i] - b[i]
114+
}
115+
return res
116+
}
117+
118+
// https://wikimedia.org/api/rest_v1/media/math/render/svg/3242bd71d63c393d02302c7dbe517cd0ec352d31
119+
// https://en.wikipedia.org/wiki/Cross_product#Coordinate_notation
120+
func (p P) cross(p2 P) P {
121+
return P{
122+
p.y*p2.z - p.z*p2.y,
123+
p.z*p2.x - p.x*p2.z,
124+
p.x*p2.y - p.y*p2.x,
125+
}
126+
}
127+
128+
func (p P) toF() []float64 {
129+
return []float64{p.x, p.y, p.z}
130+
}

‎go.mod

Copy file name to clipboardExpand all lines: go.mod
+4-1Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,4 +2,7 @@ module github.com/lucianoq/adventofcode
22

33
go 1.23.4
44

5-
require github.com/lucianoq/container/set v0.0.0-20220318183130-8a364c4afb3e
5+
require (
6+
github.com/lucianoq/container/set v0.0.0-20220318183130-8a364c4afb3e
7+
gonum.org/v1/gonum v0.15.1
8+
)

‎go.sum

Copy file name to clipboard
+4Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,6 @@
11
github.com/lucianoq/container/set v0.0.0-20220318183130-8a364c4afb3e h1:22MyLR3FQpLZGoCTyvD05lbVOptCgY4U+uAGVdPf3OQ=
22
github.com/lucianoq/container/set v0.0.0-20220318183130-8a364c4afb3e/go.mod h1:MQlqJvLUYtP+m6YG0x7FteiDO0QQCN0i0d1KqFtxO/c=
3+
golang.org/x/exp v0.0.0-20231110203233-9a3e6036ecaa h1:FRnLl4eNAQl8hwxVVC17teOw8kdjVDVAiFMtgUdTSRQ=
4+
golang.org/x/exp v0.0.0-20231110203233-9a3e6036ecaa/go.mod h1:zk2irFbV9DP96SEBUUAy67IdHUaZuSnrz1n472HUCLE=
5+
gonum.org/v1/gonum v0.15.1 h1:FNy7N6OUZVUaWG9pTiD+jlhdQ3lMP+/LcTpJ6+a8sQ0=
6+
gonum.org/v1/gonum v0.15.1/go.mod h1:eZTZuRFrzu5pcyjN5wJhcIhnUdNijYxX1T2IcrOGY0o=

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.