Skip to content

Commit c557501

Browse files
encseencse
committed
wip
1 parent bf1435f commit c557501

File tree

1 file changed

+51
-72
lines changed

1 file changed

+51
-72
lines changed

‎2023/Day24/Solution.cs

Lines changed: 51 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
namespace AdventOfCode.Y2023.Day24;
22

33
using System;
4-
using System.Collections.Generic;
54
using System.Linq;
65
using System.Text.RegularExpressions;
76
using System.Numerics;
@@ -14,7 +13,7 @@ record Mat2(decimal a, decimal b, decimal c, decimal d);
1413
record Particle(Vec2 pos, Vec2 vel);
1514

1615
// part 2
17-
record Vec3(BigInteger x, BigInteger y, BigInteger z);
16+
record Vec3(decimal x, decimal y, decimal z);
1817
record Particle3(Vec3 pos, Vec3 vel);
1918

2019
[ProblemName("Never Tell Me The Odds")]
@@ -28,7 +27,7 @@ public object PartOne(string input) {
2827
return (
2928
from i in Enumerable.Range(0, particles.Length)
3029
from j in Enumerable.Range(0, particles.Length)
31-
where i< j
30+
where i < j
3231
let intersection = Meet(particles[i], particles[j])
3332
where (
3433
intersection.pos != null &&
@@ -37,20 +36,63 @@ where i< j
3736
intersection.t1 >= 0 && intersection.t2 >= 0
3837
)
3938
select 1
40-
).Sum();
39+
).Sum();
4140
}
4241

4342
public object PartTwo(string input) {
4443
var particles = ParseParticles3(input);
45-
return Solve(v => v.x, particles) + Solve(v => v.y, particles) + Solve(v => v.z, particles);
44+
var xy = Solve2D(particles, p => p.x, p => p.y);
45+
var xz = Solve2D(particles, p => p.x, p => p.z);
46+
return Math.Round(xy.p.x + xy.p.y + xz.p.y);
47+
}
48+
49+
(Vec2 p, Vec2 v) Solve2D(
50+
Particle3[] particles,
51+
Func<Vec3, decimal> dim1,
52+
Func<Vec3, decimal> dim2
53+
) {
54+
var s = 500;
55+
for (var v1 = -s; v1 < s; v1++) {
56+
for (var v2 = -s; v2 < s; v2++) {
57+
var p1 = new Particle(
58+
new Vec2(dim1(particles[0].pos), dim2(particles[0].pos)),
59+
new Vec2(dim1(particles[0].vel) - v1, dim2(particles[0].vel) - v2)
60+
);
61+
var p2 = new Particle(
62+
new Vec2(dim1(particles[1].pos), dim2(particles[1].pos)),
63+
new Vec2(dim1(particles[1].vel) - v1, dim2(particles[1].vel) - v2)
64+
);
65+
var (mp, _, __) = Meet(p1, p2);
66+
if (mp == null) {
67+
continue;
68+
}
69+
var ok = true;
70+
for (var i = 0; i < particles.Length && ok; i++) {
71+
var p = new Vec2(dim1(particles[i].pos), dim2(particles[i].pos));
72+
var v = new Vec2(dim1(particles[i].vel) - v1, dim2(particles[i].vel) - v2);
73+
74+
if (v.x != 0 && v.y != 0) {
75+
var tx = (mp.x - p.x) / v.x;
76+
var ty = (mp.y - p.y) / v.y;
77+
if (Math.Abs(tx - ty) > (decimal)0.00001) {
78+
ok = false;
79+
}
80+
}
81+
}
82+
if (ok) {
83+
return (mp, new Vec2(v1, v2));
84+
}
85+
}
86+
}
87+
throw new Exception();
4688
}
4789

4890
// the position where the path of the particles cross and the time(s) when
4991
// they are at the meeting point.
5092
(Vec2 pos, decimal t1, decimal t2) Meet(Particle p1, Particle p2) {
5193
// Solving m * x = b provides the meeting point
5294
Mat2 m = new Mat2(
53-
p1.vel.y, -p1.vel.x,
95+
p1.vel.y, -p1.vel.x,
5496
p2.vel.y, -p2.vel.x
5597
);
5698
Vec2 b = new Vec2(
@@ -62,12 +104,12 @@ public object PartTwo(string input) {
62104
// to compute the determinant, the inverse of m, and one matrix
63105
// multiplication, so I'll inline it here. I can't make it better.
64106
var determinant = m.a * m.d - m.b * m.c;
65-
if (determinant == 0) {
107+
if (determinant == 0 || p1.vel.x == 0 || p2.vel.x == 0) {
66108
return (null, -1, -1); //particles don't meet
67109
}
68110

69111
var inverse = new Mat2(
70-
m.d / determinant, -m.b / determinant,
112+
m.d / determinant, -m.b / determinant,
71113
-m.c / determinant, m.a / determinant
72114
);
73115

@@ -82,79 +124,16 @@ public object PartTwo(string input) {
82124
return (pos, t1, t2);
83125
}
84126

85-
BigInteger Solve(Func<Vec3, BigInteger> dim, Particle3[] particles) {
86-
for (var v0 = -10000; v0 < 10000; v0++) {
87-
var items = new List<(BigInteger dv, BigInteger x)>();
88-
foreach (var p in particles) {
89-
var dv = v0 - dim(p.vel);
90-
if (IsPrime(dv) && items.All(i => i.dv != dv)) {
91-
items.Add((dv: dv, x: dim(p.pos)));
92-
}
93-
}
94-
if (items.Count > 1) {
95-
var p0 = ChineseRemainderTheorem(items.ToArray());
96-
var ok = true;
97-
foreach (var p in particles) {
98-
var dv = v0 - dim(p.vel);
99-
var dx = dim(p.pos) > p0 ? dim(p.pos) - p0 : p0 - dim(p.pos);
100-
if (dv == 0) {
101-
if (dx != 0) {
102-
ok = false;
103-
}
104-
} else {
105-
if (dx % dv != 0) {
106-
ok = false;
107-
}
108-
}
109-
}
110-
if (ok) {
111-
return p0;
112-
}
113-
}
114-
}
115-
throw new Exception();
116-
117-
}
118-
119-
public static bool IsPrime(BigInteger number) {
120-
if (number <= 2) return false;
121-
if (number % 2 == 0) return false;
122-
123-
for (int i = 3; i * i <= number; i += 2)
124-
if (number % i == 0)
125-
return false;
126-
127-
return true;
128-
}
129-
130127
Particle[] ParseParticles(string input) => (
131128
from line in input.Split('\n')
132129
let v = Regex.Matches(line, @"-?\d+").Select(m => decimal.Parse(m.Value)).ToArray()
133130
select new Particle(new Vec2(v[0], v[1]), new Vec2(v[3], v[4]))
134131
).ToArray();
135132

136-
137133
Particle3[] ParseParticles3(string input) => (
138134
from line in input.Split('\n')
139-
let v = Regex.Matches(line, @"-?\d+").Select(m => BigInteger.Parse(m.Value)).ToArray()
135+
let v = Regex.Matches(line, @"-?\d+").Select(m => decimal.Parse(m.Value)).ToArray()
140136
select new Particle3(new Vec3(v[0], v[1], v[2]), new Vec3(v[3], v[4], v[5]))
141137
).ToArray();
142-
143-
// https://rosettacode.org/wiki/Chinese_remainder_theorem#C.23
144-
BigInteger ChineseRemainderTheorem((BigInteger mod, BigInteger a)[] items) {
145-
var prod = items.Aggregate(BigInteger.One, (acc, item) => acc * item.mod);
146-
var sum = items.Select((item, i) => {
147-
var p = prod / item.mod;
148-
return item.a * ModInv(p, item.mod) * p;
149-
});
150-
151-
var s = BigInteger.Zero;
152-
foreach (var item in sum) {
153-
s += item;
154-
}
155-
156-
return s % prod;
157-
}
158-
BigInteger ModInv(BigInteger a, BigInteger m) => BigInteger.ModPow(a, m - 2, m);
159138
}
160139

0 commit comments

Comments
 (0)