Skip to content

Commit a3d9b80

Browse files
encseencse
committed
2023/24
1 parent 7efabdc commit a3d9b80

File tree

1 file changed

+109
-92
lines changed

1 file changed

+109
-92
lines changed

‎2023/Day24/Solution.cs

Lines changed: 109 additions & 92 deletions
Original file line numberDiff line numberDiff line change
@@ -5,140 +5,157 @@ namespace AdventOfCode.Y2023.Day24;
55
using System.Text.RegularExpressions;
66
using System.Data;
77

8-
// WIP, dont look at this :D
9-
// part 1
10-
record Vec2(decimal x, decimal y);
11-
record Mat2(decimal a, decimal b, decimal c, decimal d);
12-
record Particle(Vec2 pos, Vec2 vel);
13-
14-
// part 2
15-
record Vec3(decimal x, decimal y, decimal z);
16-
record Particle3(Vec3 pos, Vec3 vel);
8+
record Vec2(decimal x0, decimal x1);
9+
record Vec3(decimal x0, decimal x1, decimal x2);
10+
record Particle<T>(T pos, T vel);
1711

1812
[ProblemName("Never Tell Me The Odds")]
1913
class Solution : Solver {
2014

2115
public object PartOne(string input) {
22-
var particles = Proj(ParseParticles(input), v => v.x, v => v.y);
16+
var particles = Proj(ParseParticles(input), v => (v.x0, v.x1));
2317

2418
var begin = 200000000000000;
2519
var end = 400000000000000;
2620

27-
return (
28-
from i in Enumerable.Range(0, particles.Length)
29-
from j in Enumerable.Range(0, particles.Length)
30-
where i < j
31-
let intersection = Meet(particles[i], particles[j])
32-
where (
33-
intersection.pos != null &&
34-
begin <= intersection.pos.x && intersection.pos.x <= end &&
35-
begin <= intersection.pos.y && intersection.pos.y <= end &&
36-
intersection.t1 >= 0 && intersection.t2 >= 0
37-
)
38-
select 1
39-
).Sum();
40-
}
21+
bool reachesInFuture(Particle<Vec2> p, Vec2 pos) {
22+
if (p.vel.x0 == 0) {
23+
return pos.x0 == p.pos.x0;
24+
}
25+
return (pos.x0 - p.pos.x0) / p.vel.x0 >= 0;
26+
}
4127

42-
Particle[] Proj(
43-
Particle3[] ps,
44-
Func<Vec3, decimal> dim1,
45-
Func<Vec3, decimal> dim2
46-
) {
47-
return ps.Select(p =>
48-
new Particle(
49-
new Vec2(dim1(p.pos), dim2(p.pos)),
50-
new Vec2(dim1(p.vel), dim2(p.vel))
51-
)
52-
).ToArray();
28+
var res = 0;
29+
for (var i = 0; i < particles.Length; i++) {
30+
for (var j = i + 1; j < particles.Length; j++) {
31+
var pos = Meet(particles[i], particles[j]);
32+
if (pos != null &&
33+
begin <= pos.x0 && pos.x0 <= end &&
34+
begin <= pos.x1 && pos.x1 <= end &&
35+
reachesInFuture(particles[i], pos) &&
36+
reachesInFuture(particles[j], pos)
37+
) {
38+
res++;
39+
}
40+
}
41+
}
42+
return res;
5343
}
5444

5545
public object PartTwo(string input) {
5646
var particles = ParseParticles(input);
57-
var xy = Solve2D(Proj(particles, p => p.x, p => p.y));
58-
var xz = Solve2D(Proj(particles, p => p.x, p => p.z));
59-
return Math.Round(xy.p.x + xy.p.y + xz.p.y);
47+
var stoneXY = Solve2D(Proj(particles, vec => (vec.x0, vec.x1)));
48+
var stoneXZ = Solve2D(Proj(particles, vec => (vec.x0, vec.x2)));
49+
return Math.Round(stoneXY.x0 + stoneXY.x1 + stoneXZ.x1);
6050
}
6151

62-
(Vec2 p, Vec2 v) Solve2D(
63-
Particle[] particles
64-
) {
65-
var s = 500;
52+
Particle<Vec2> TranslateV(Particle<Vec2> p, Vec2 vel) =>
53+
new Particle<Vec2>(p.pos, new Vec2(p.vel.x0 - vel.x0, p.vel.x1 - vel.x1));
54+
55+
Vec2 Solve2D(Particle<Vec2>[] particles) {
56+
// We will bruteforce the velocity of the stone in the two dimensions
57+
// we are working right now.
58+
//
59+
// We can transform the particles to the reference frame that moves
60+
// together with the stone, just subtract the stone's velocity
61+
// from the particle's velocity.
62+
//
63+
// If we knew the position of the stone as well, we could use a
64+
// reference frame where the stone rested at (0,0) but we dont know it yet.
65+
// But in that was the case each particle had to go through (0,0) to get
66+
// hit by the stone.
67+
//
68+
// Now the twist is: our stone still has some fixed coordinates in this
69+
// reference frame we selected, and it's still true that all particles
70+
// has to go through that point.
71+
//
72+
// So if we have the right velocity, we can find a point that is crossed
73+
// by every particles. And this has to be the position of the stone.
74+
75+
var s = 500; //arbitrary limits for the brute force that worked for me.
6676
for (var v1 = -s; v1 < s; v1++) {
6777
for (var v2 = -s; v2 < s; v2++) {
68-
var p1 = new Particle(particles[0].pos,
69-
new Vec2(particles[0].vel.x - v1, particles[0].vel.y - v2)
78+
var vel = new Vec2(v1, v2);
79+
var pos = Meet(
80+
TranslateV(particles[0], vel),
81+
TranslateV(particles[1], vel)
7082
);
71-
var p2 = new Particle(particles[1].pos,
72-
new Vec2(particles[1].vel.x - v1, particles[1].vel.y - v2)
73-
);
74-
75-
var (mp, _, __) = Meet(p1, p2);
76-
if (mp == null) {
83+
84+
if (pos == null) {
7785
continue;
7886
}
79-
var ok = true;
80-
for (var i = 0; i < particles.Length && ok; i++) {
81-
var pi = particles[i].pos;
82-
var vi = new Vec2(particles[i].vel.x - v1, particles[i].vel.y - v2);
83-
84-
if (vi.x != 0 && vi.y != 0) {
85-
var tx = (mp.x - pi.x) / vi.x;
86-
var ty = (mp.y - pi.y) / vi.y;
87+
88+
var hitsAllStones = true;
89+
for (var i = 0; i < particles.Length && hitsAllStones; i++) {
90+
var pi = TranslateV(particles[i], vel);
91+
// ignore the case when the velocity is 0,
92+
// we should check these as well, but it's not necessary
93+
// to solve solve my input.
94+
if (pi.vel.x0 != 0 && pi.vel.x1 != 0) {
95+
var tx = (pos.x0 - pi.pos.x0) / pi.vel.x0;
96+
var ty = (pos.x1 - pi.pos.x1) / pi.vel.x1;
8797
if (Math.Abs(tx - ty) > (decimal)0.00001) {
88-
ok = false;
98+
hitsAllStones = false;
8999
}
90100
}
91101
}
92-
if (ok) {
93-
return (mp, new Vec2(v1, v2));
102+
103+
if (hitsAllStones) {
104+
return pos;
94105
}
95106
}
96107
}
97108
throw new Exception();
98109
}
99110

100-
// the position where the path of the particles cross and the time(s) when
101-
// they are at the meeting point.
102-
(Vec2 pos, decimal t1, decimal t2) Meet(Particle part1, Particle part2) {
103-
// Solving m * x = b provides the meeting point
104-
Mat2 m = new Mat2(
105-
part1.vel.y, -part1.vel.x,
106-
part2.vel.y, -part2.vel.x
111+
// returns the position where the path of the particles cross
112+
// I don't have a matrix library at my disposal, but we just need
113+
// to compute the determinant, the inverse of m, and one matrix
114+
// multiplication, so I'll inline it here. I can't make it better.
115+
Vec2 Meet(Particle<Vec2> p1, Particle<Vec2> p2) {
116+
117+
var (a11, a12, a21, a22)= (
118+
p1.vel.x1, -p1.vel.x0,
119+
p2.vel.x1, -p2.vel.x0
107120
);
121+
108122
Vec2 b = new Vec2(
109-
part1.vel.y * part1.pos.x - part1.vel.x * part1.pos.y,
110-
part2.vel.y * part2.pos.x - part2.vel.x * part2.pos.y
123+
p1.vel.x1 * p1.pos.x0 - p1.vel.x0 * p1.pos.x1,
124+
p2.vel.x1 * p2.pos.x0 - p2.vel.x0 * p2.pos.x1
111125
);
112126

113-
// I don't have a matrix library at my disposal, but we just need
114-
// to compute the determinant, the inverse of m, and one matrix
115-
// multiplication, so I'll inline it here. I can't make it better.
116-
var determinant = m.a * m.d - m.b * m.c;
117-
if (determinant == 0 || part1.vel.x == 0 || part2.vel.x == 0) {
118-
return (null, -1, -1); //particles don't meet
127+
var determinant = a11 * a22 - a12 * a21;
128+
if (determinant == 0 || p1.vel.x0 == 0 || p2.vel.x0 == 0) {
129+
return null; //particles don't meet
119130
}
120131

121-
var inverse = new Mat2(
122-
m.d / determinant, -m.b / determinant,
123-
-m.c / determinant, m.a / determinant
124-
);
125-
126-
var pos = new Vec2(
127-
inverse.a * b.x + inverse.b * b.y,
128-
inverse.c * b.x + inverse.d * b.y
132+
var (i11, i12, i21, i22) = (
133+
a22 / determinant, -a12 / determinant,
134+
-a21 / determinant, a11 / determinant
129135
);
130136

131-
// times come from solving pi.pos + pi.vel * t = pos for x (or y):
132-
var t1 = (pos.x - part1.pos.x) / part1.vel.x;
133-
var t2 = (pos.x - part2.pos.x) / part2.vel.x;
134-
return (pos, t1, t2);
137+
return new Vec2(
138+
i11 * b.x0 + i12 * b.x1,
139+
i21 * b.x0 + i22 * b.x1
140+
);
135141
}
136142

137-
138-
Particle3[] ParseParticles(string input) => (
143+
Particle<Vec3>[] ParseParticles(string input) => (
139144
from line in input.Split('\n')
140145
let v = Regex.Matches(line, @"-?\d+").Select(m => decimal.Parse(m.Value)).ToArray()
141-
select new Particle3(new Vec3(v[0], v[1], v[2]), new Vec3(v[3], v[4], v[5]))
146+
select new Particle<Vec3>(new Vec3(v[0], v[1], v[2]), new Vec3(v[3], v[4], v[5]))
142147
).ToArray();
143-
}
144148

149+
Particle<Vec2>[] Proj(
150+
Particle<Vec3>[] ps,
151+
Func<Vec3, (decimal, decimal)> proj
152+
) => (
153+
from p in ps
154+
let pos = proj(p.pos)
155+
let vel = proj(p.vel)
156+
select new Particle<Vec2>(
157+
new Vec2(pos.Item1, pos.Item2),
158+
new Vec2(vel.Item1, vel.Item2)
159+
)
160+
).ToArray();
161+
}

0 commit comments

Comments
 (0)