On Day 18 I wrote:
I don’t suppose he’ll ever supply a puzzle that relies on my old research topics…
Careful what you wish for!
If you’re as stuck on Part 2 as most people were (took roughly an hour for the first 100 people to solve it), take consolation in the fact that quite a few people posting solutions expressed their unhappiness with the puzzle. The most common technique was to reformulate the problem in a way that they then plug it into the Z3 theorem prover.
A few others took a more mathematical approach, sometimes making assumptions on the input. I’m a bit sick, so had trouble either following the explanations, or even looking at their code and making sense of it. I did translate one Python solution to Ada, and thought I’d call it a day after it gave me the right answer.
Unfortunately – or, depending on one’s point of view, fortunately – the discussion had given me another idea, based on the research I conducted in a previous life. The fancy name is “Groebner basis”, but essentially you’re looking at slightly non-linear polynomials. The trick is to make them linear, seeing everything as a nail, I used Groebner bases, but at least one person at Reddit used a different approach.
The only assumption this approach needs is that you can find at least three hailstones that intersect in the x, y plane. Part 1 has you count how often that happens, so that’s a good sign. Call them
h_3. You’re looking for a position (
z) and velocities
dz along with times
t_3 such that for each
x + t_i dx = h_i.x + t_i h_i.dx
…and similarly for
z. Rewrite them with everything on one side and you have nine equations in nine variables. Unfortunately,
dx etc. are unknown, which makes the products
t_i dx etc. nonlinear (a couple of Reddit commenters’ claims notwithstanding).
So a matrix won’t work… yet. To fix that, take 6 pairs of equations and multiply strategically in order to cancel the non-linear terms; this is an active research field in the general case, but here’s an example of how it works in this case:
f_i = x + t_i dx - h_i.x - t_i h_i.dx
g_i = y + t_i dy - h_i.y - t_i h_i.dy
s_i = dy f_i - dx g_i - h_i.dy f_i + h_i.dx g_i
r_i = s_1 - s_2
r_i is now linear in the variables
dy. Similar work gives you linear equations for
dz and for
You need two of each of the three sets of variables: that gives you 6 linear equations in 6 variables, which is “easily” solved using a two-dimensional array in Ada. I write “easily” in scare quotes because I did have to swap rows at least once.
I’m reasonably sure that’s not what the puzzle master intended; I suspect it’s closer to the Python solution I translated. Oh, look: he actually left a comment giving one of his approaches to solving it.
PS: oh, this is also ironic. usually the 3-d puzzles inspire in me.