Never Tell Me The Odds

Advent of Code 2023 Day 24

Part 1

Curse you, Linear Algebra!

I read through the puzzle description.

I saw that it involves:

• Lines existing in 3D - though for now, we care only about 2 of the D's
• Finding the possible intersection between any two lines
• Checking whether the X,Y coordinates of that intersection also intersect with an arbitrarily-sized bounding box

Then I saw the floating point numbers where two lines could meet.

And I saw the bounding box. And all the zeroes!

And I saw the X,Y,Z values of the lines in my puzzle input.

And it's a lot.

A lot of math that I don't understand.

But sometimes puzzles like this are a great excuse to do some research.

And find new formulas.

And new libraries.

Sure, some might consider that cheating.

But I consider it part of solving the puzzle.

I might use someone else's algorithm to compute a critical step in search of the correct answer.

As long as I don't use someone else's algorithm to specifically generate the correct answer.

Discovering new formulas and libraries

I'm given:

• The coordinates of a point
• The parameters by which that point moves

Using that second data point, I can calculate an infinite number of other points on the straight line.

I only need one other point...

...to calculate the line's slope:

slope = (y2 - y1)/(x2 - x1)

Cool, I can figure out each line's slope.

But then what?

I really want to know if two lines intersect, and where.

A google search for javascript two lines intersect generates some very useful results:

• A stack overflow post that references Paul Bourke's article filled with formulas about points, lines and planes
• JavaScript source code that finds exactly what I'm looking for
• A JavaScript library filled with mathematical functions, one of which does exactly what I want - in 2D and 3D!

I read the relevant section ini Paul's article.

I didn't understand it, sadly.

But I do see how the JavaScript code perfectly maps Paul's formula into JavaScript syntax.

So, I'll call that a win.

Now I want to call this function with some points from the example input to confirm it works the way I need it to.

Testing Leo's function of Paul's formula

The intersect function expects eight parameters representing four pair of X,Y coordinates from two lines.

I provide it points from the first two hailstones in the example input.

I get false.

That's not what I wanted.

Why did I get false?

Well, there are three conditions in the function that could generate a false return value:

• the lines are of length 0
• Lines are parallel
• the intersection is along the segments

I am triggering that last one.

What if I remove that condition? Especially since it seems like a fact I don't care to check for in this challenge.

I now get the X and Y values I was expecting.

Good!

Now I want to test two points that crossed in the past to confirm I understand what that means.

I assume it means their intersection occurs on the line away from where the velocity is heading.

Values updated.

Function ran.

And just as the description stated, the X,Y coordinates are for a point on Hailstone A's line that is in the opposite direction of where it's headed.

It looks like this function suits my needs for Part 1.

But I still want to test math.js's Function Intersect method.

I feel like I'll need it for Part 2 where I'm likely to use the Z portion of each coordinate.

Testing math.js's Function Intersect

I installed the npm package in my replit.com sandbox.

I replaced my eight values with four 2-element arrays for each pair.

I ran the code.

It took a few seconds to complete, surprisingly.

But it spit out the same value and Leo's function.

I wonder why it took a few seconds to run?

For now, I think I'll stick with Leo's function.

Parsing the input into two endpoints

For a line like this:

19, 13, 30 @ -2,  1, -2

I need to use four of the six numbers:

 A,  B,  C @  D,  E,  F
 *   *        *   *

And do two calculations:

A + D
B + E

To get four final numbers:

X1 = A
Y1 = B
X2 = A + D
Y2 = B + E

I'll use regex to get all six numbers:

/(\d+)/g

Here's the beginning of my reduce algorithm:

const part1 = input.split('\n').reduce(
  (total, stone, index) => {
    let [xp, yp, zp, xv, yv, zv] = [...stone.matchAll(/-?\d+/g)].map(el => +el[0])
    let [x1, y1, x2, y2] = [xp, yp, xp + xv, yp + yv]
    return total
  }, 0
)

I'm seeing the values I expect.

Now it's time to add the loop and do the same for each unique pair of hailstones.

Loop and repeat parsing for line #2

I have to compare each hailstone.

That will require a loop.

But one that only compares pairs once.

Like this:

for (let i = 0; i < input.length - 1; i++) {
  for (let j = i + 1; j < input.length; j++) {
    // Compare
  }
}

Of course, doing this means I need to re-think my reduce.

That's ok. It's a simple change.

Now I've got tons of 2-letter variables being thrown around though.

Oh well.

Here's my latest algorithm:

const stones = input.split('\n')
let total = 0
for (let i = 0; i < stones.length - 1; i++) {
  let [xp, yp, zp, xv, yv, zv] = [...stones[i].matchAll(/-?\d+/g)].map(el => +el[0])
  let [x1, y1, x2, y2] = [xp, yp, xp + xv, yp + yv]
  for (let j = i + 1; j < stones.length; j++) {
    let [xp, yp, zp, xv, yv, zv] = [...stones[j].matchAll(/-?\d+/g)].map(el => +el[0])
    let [x3, y3, x4, y4] = [xp, yp, xp + xv, yp + yv]
    let target = intersect(
      x1, y1, x2, y2, x3, y3, x4, y4
    )
  }
}

Thankfully, I'm seeing all the X,Y coordinates - or mentions of parallel lines - that I expected.

My algorithm and Leo's algorithm are behaving correctly!

Next, I need to check for whether the intersection is inside of the bounding box.

In or out of scope

Pick two numbers that are not equal:

let min = 7
let max = 27

Each of my intersection's coordinates must at least be within that range, inclusive of both min and max.

let [x, y] = Object.values(target)
if (x >= min && x <= max && y >= min && y <= max) {
  // Proceed to next test
}

Running my program shows the expected text for my if...else clauses.

Past or future

The last test is whether the intersection occurs on a spot on either line that trends along the velocity, or trends away from it.

I'm struggling to think of a way to do this without overly complicated conditions.

Here's my over-conditional approach:

Given:
xp = A // stone 1's X position
xv = B // stone 1's X velocity
tx = C // intersection's X

if (C < A && A + B < A)
  Stone 1 is headed toward the intersection point
if (C < A && A + B > A)
  Stone 1 is headed away from the intersection point

And the opposite comparisons
if (C > A && A + B > A)
  Stone 1 is headed toward the intersection point
if (C > A && A + B < A)
  Stone 1 is headed away from the intersection point

And all four checks for the other stone

I need the first case to be true for all of them

That's eight conditions, each with two checks.

Yeesh!

What about sorting those three values and checking for whether A is the first or last item?

Because if the intersection point is in the future, then A + B and C should trend the same direction: away from A.

Thus, A should either be less than or greater than both A + B and C.

If this proves true, I can cut my conditions to just two...I think!

Time to try!

It seems to work!

Here's the complex-seeming - but much smarter - algorithm:

let [A1, B1, C1] = [x1p, x1p + x1v, x]
let s1x = [A1, B1, C1].sort((a,b) => a - b).indexOf(x1p) !== 1
let [D1, E1, F1] = [x2p, x2p + x2v, x]
let s2x = [D1, E1, F1].sort((a,b) => a - b).indexOf(x2p) !== 1
let [A2, B2, C2] = [y1p, y1p + y1v, y]
let s1y = [A2, B2, C2].sort((a,b) => a - b).indexOf(y1p) !== 1
let [D2, E2, F2] = [y2p, y2p + y2v, y]
let s2y = [D2, E2, F2].sort((a,b) => a - b).indexOf(y2p) !== 1
if ([s1x, s2x, s1y, s2y].every(el => el == true)) {
  total += 1
}

I compare to 1 because if the X or Y position is in the middle of the sorted array, then the intersection has occurred in the past (trending away from the velocity of the stone).

After running my algorithm, I see the expected answer of 2.

Am I ready to swap inputs, update bounding box dimensions, and see if I even generate an answer using my puzzle input?

...

I ran it.

I got an answer close to 20k.

Is it the correct answer?

...

It is!!!

Woohoo!!!

Thank you Paul and Leo for making this gold star possible for me to obtain!

Let's see how much harder Part 2 is...and if I'll need to use math.js instead for finding intersections in 3D.

Part 2

Jaw drops. How in the what now?

Another challenge in the theme of 'dream up the perfect candidate'.

I need to identify a line that intersects with all of the lines in my input.

And then identify an ideal point on that line.

Maybe I can look for a formula or algorithm to solve for that first part.

...

Couldn't find anything immediately.

I wish I could draw these lines no a 3D graph.

Sadly, I couldn't find an existing online tool to that easily.

My input has 300 points.

And now that I'm using the Z coordinate, those points - and the lines they create when moving - likely go in all sorts of directions.

So, even if I could see it, I doubt I would come up with the single point and line that crosses them all at the right time.

All that to say...it's time to move on to Day 25.

I'm happy I earned one gold star on Day 24.

I wasn't expecting Part 2 of Day 24 to be something I could solve, either.

As the cover image reiterates, special thanks to Paul and Leo for providing the necessary formulas and algorithms to make it possible for me to solve Part 1.

Onward to the final puzzle of the year!