2023 Day 24: Don't Tell Me The Odds

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_1, h_2, h_3. You’re looking for a position (x,y,z) and velocities dx, dy, dz along with times t_1, t_2, t_3 such that for each i

x + t_i dx = h_i.x + t_i h_i.dx

…and similarly for y and z. Rewrite them with everything on one side and you have nine equations in nine variables. Unfortunately, t_i and 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

…and r_i is now linear in the variables x, y, dx, and dy. Similar work gives you linear equations for x, z, dx, dz and for y, z, dy, dz.

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 :fearful: in me.


I think you mean „Day 24“ in the title.

But what I actually wanted to say is that it’s always fun and intriguing to read your impressions of the puzzles. :slightly_smiling_face:
I‘ll have to look closer into this one, I think. Mathy sounds good. :sweat_smile:

1 Like

Cool that you digested all that! The problem seems even more brutal than feared…
I didn’t begin to dig into it seriously, although hailstones are haunting me since yesterday.

Some other random thoughts (from things read 10 hours ago):

  • Perhaps it is worth trying brute force on velocities since they are in a “small” range (at least in my data). People on Reddit did it so with some claimed success.
  • Perhaps a small number of the hailstones is sufficient to find a solution. The system (300 hailstones in my data) seems super-overdetermined. People on Reddit seem to confirm that.
  • At least one person on Reddit had luck and a pair of hailstones had a special common feature.
1 Like

Oops! Thanks @JeremyGrosser for fixing it!

Thanks. I was afraid I’d get a negative reaction from some of the longer-winded venting the last few days, so I do appreciate the input.

1 Like

The system is definitely super-over-determined, since you only need 3 hailstones to solve it. I also had 300 hailstones.

I love that word, BTW. “super-over-determined”. Wish I were still teaching, so I could use it.