Daily bit(e) of C++ | Advent of Code: Day 24
Daily bit(e) of C++ #357, Advent of Code using Modern C++: Day 24.
Welcome to day 24 of Advent of Code using Modern C++. Before you start reading, I highly encourage you to try to solve the two problems yourself: https://adventofcode.com/2023/day/24.
If you missed it, I have prepared a template repository for C++, with a development environment (through a devcontainer) with a bleeding edge version of the C++ toolchain: https://github.com/HappyCerberus/aoc-2023-cpp.
Today, figuring out collisions in 3D space.
Part one
For part one, we have to determine intersections in the X-Y plane.
We can do this using a fairly straightforward mathematical formula; however, there is a small hitch that makes it annoying to solve in C++. While our coordinates are all in the integer domain, they have been chosen such that they will overflow even for int64_t.
Because of this, I have switched to a long double, which fortunately did not cause imprecision issues.
Our goal is to return the total number of intersections within the bounding box. We also have to consider that while the lines representing the Hailstones might intersect, they might intersect in the past, and we only care about intersections in the future.
Finally, we can improve our computations' precision by re-normalising the Hailstones' positions to the bounding box (this is required even for long double).
Part two
And for part two, I gave up on C++ completely. I did try to implement a Plane/Line intersection approach, but it got so tedious that I just went to mathematical software.
This is perhaps compounded by my distaste for programming problems that are, in fact, mathematical problems. I see zero point in programming something that can be trivially solved using mathematical software.
I can at least explain how you can solve part two using mathematics.
Consider that if two Hailstones are to collide, they have to have the same position after a specific time. This means:
a.x + a.vx*t = b.x + b.vx*t
a.y + a.vy*t = b.y + b.vy*t
a.z + a.vz*t = b.z + b.vz*t
We know the positions and speeds of Hailstones in our input. We do not know the starting position, speed of our throw, and time of collision.
Sadly, this means that we have three equations with 7 variables. However, if we take three different Hailstones from the input, we will have 9 variables (3 positions, 3 speeds, 3 times) and nine equations. I.e. something we can trivially solve. I went to SageMath for the solution:
x = var('x')
y = var('y')
z = var('z')
vx = var('vx')
vy = var('vy')
vz = var('vz')
t1 = var('t1')
t2 = var('t2')
t3 = var('t3')
eq1 = 197869613734967 == x + (vx-150)*t1
eq2 = 292946034245705 == y + (vy-5)*t1
eq3 = 309220804687650 == z + (vz+8)*t1
eq4 = 344503265587754 == x + (vx+69)*t2
eq5 = 394181872935272 == y + (vy-11)*t2
eq6 = 376338710786779 == z + (vz+46)*t2
eq7 = 293577250654200 == x + (vx+17)*t3
eq8 = 176398758803665 == y + (vy-101)*t3
eq9 = 272206447651388 == z + (vz-26)*t3
solutions = solve([eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9],x,y,z,vx,vy,vz,t1,t2,t3)
solutions[0][0]+solutions[0][1]+solutions[0][2]Conclusion
How did you do with today’s problems? Did you also surrender to mathematical software?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.