# 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:

let:

• `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 in me.

2 Likes

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.
I‘ll have to look closer into this one, I think. Mathy sounds good.

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.