Advent of Code 2023 - Day 24

README.md

Advent of Code - 2023

Day 24 - Never Tell Me the Odds

Part 1 - Collision Detection

We're meant to analyze the trajectories of hailstones to determine where they might collide and create snow.

This puzzle is all about computational geometry and collision detection.

We're told to ignore the Z axis entirely -- that doesn't bode well for part 2.

Input Format:

Each line of input data corresponds to a single hailstone, formatted as px, py, pz @ vx, vy, vz. Here, px, py, pz represent the initial position, and vx, vy, vz represent the velocity in the respective axes.

Objective:

• Consider only the X and Y axes for the hailstones' movement.
• Determine how many pairs of hailstones will have intersecting paths within a specified test area, defined by minimum and maximum X and Y coordinates.
• Ignore intersections that occur in the past or outside the defined test area.

Test Data:

19, 13, 30 @ -2, 1, -2
18, 19, 22 @ -1, -1, -2
20, 25, 34 @ -2, -2, -4
12, 31, 28 @ -1, -2, -1
20, 19, 15 @ 1, -5, -3

With a x and y of 7-27

For the full input we're meant look for intersections that happen with an X and Y position each at least 200000000000000 and at most 400000000000000

Plan:

1. Parse the Input Data

• Read the input data, which provides the initial position (px, py, pz) and velocity (vx, vy, vz) for each hailstone.
• Store this data in a structured format, like a list of dictionaries or objects, for easy access and manipulation.

2. Model the Hailstones' Movement

• Recognize that the hailstones move linearly based on their velocity.
• For each hailstone, the position at any given time t can be calculated using the formula:
  • new_position = initial_position + velocity × t
• This movement is independent for each axis (X, Y, Z).

3. Simplify the Problem

• As per the problem statement, ignore the Z-axis and focus only on the X and Y axes.
• The task is to find intersections of paths, which reduces to finding points where two hailstones have the same X and Y coordinates at the same time.

4. Find Intersection Points

• Compare every pair of hailstones to check if their paths intersect.
• For each pair, set up a system of linear equations based on their positions and velocities in the X and Y axes.
• Solve these equations to find the time t at which they intersect, if they do.
• Ensure that the time t is positive, indicating a future intersection.

5. Check Intersection within Test Area

• For each intersection, verify whether the intersection point lies within the specified test area (defined by minimum and maximum X and Y coordinates).
• Count only those intersections that fall within this area.

6. Handle Special Cases

• Parallel paths: If two hailstones have the same velocity, their paths are parallel and will not intersect.
• Past intersections: Disregard intersections that occur at negative time values, as they indicate past intersections.

7. Count Valid Intersections

• Keep a count of all pairs of hailstones whose paths intersect within the test area.

Reality

I ended up reading through a bunch of other folks' solutions and looking around for various ways to find valid intersections and eventually I managed to cobble together something that worked... I'm still an imposter, of course

Part 2 - Collision Intention

Description:

In this part of the challenge, the objective shifts from analyzing natural collisions to actively causing them. You are given the ability to throw a rock with any chosen position and velocity in a 3D space (including the Z axis) to hit every hailstone.

Puzzle Overview:

• Goal: Determine the initial position and velocity to throw a rock so that it collides with each hailstone exactly once.
• Hailstones: Each hailstone has a known initial position and velocity.
• Rock: You can choose its initial position and velocity.
• Collision: The rock should collide with each hailstone at some point in time, without changing its velocity upon collision.

Example:

Given hailstones with their positions and velocities, you must find a position and velocity for the rock so that it intersects with each hailstone's path at some point in time.

Solution Strategy:

1. Modeling Hailstones and Rock Trajectories:
   • Represent the motion of each hailstone and the rock in 3D space over time.
2. Finding Potential Collision Points:
   • For each hailstone, calculate where and when the rock would need to be to collide with it.
   • This involves solving a set of equations for each hailstone, considering its trajectory and the rock's potential trajectory.
3. Identifying Common Collision Points:
   • The solution requires a common position and time where the rock can collide with all hailstones.
   • Analyze the set of potential collision points from each hailstone to find a common point in time and space.
4. Determining Rock's Initial Position and Velocity:
   • Once a common collision point (time and position) is found, work backward to determine the rock's required initial position and velocity.
5. Summing the Coordinates:
   • After finding the rock's initial position, sum up its X, Y, and Z coordinates as per the puzzle's final question.

hailstones.txt

291493672529314, 259618209733833, 379287136024123 @ -9, 119, -272
308409248682955, 156803514643857, 424989308414284 @ -78, 236, -255
195379943194796, 213851381371727, 355270583377422 @ 25, 14, -15
297329579961934, 122004770593749, 344090716183747 @ -87, 185, -36
295385164557865, 339802914312939, 293784344149228 @ 64, 10, -211
155809034672704, 276962605708219, 308527141561896 @ 65, -70, 49
379374976062190, 523822522311015, 436295585524315 @ -208, -433, -263
247918644285258, 312143526467359, 112155607012071 @ 189, 75, 390
342617287456519, 397354826185853, 200879077842813 @ 20, -132, -32
378033289852195, 344304802155174, 277151328831253 @ -244, 249, -576
329376422447230, 354844965599343, 218863978047367 @ -8, 17, -10
244732151114366, 241023555875268, 299614412087890 @ 91, 151, -79
229675166786762, 272496792240003, 403388647505619 @ -27, -68, -59
342641695024690, 405074098532187, 192422793097927 @ -23, -198, 69
307790269475010, 287974903224075, 133983400495495 @ 157, 448, 404
338204078494098, 220756564653275, 207895864790871 @ -119, 198, 127
256854809852143, 151282473118095, 430813946794295 @ -82, 22, -38
310795589424306, 300273918793951, 561603474537271 @ -105, -69, -358
216689910377710, 176014643762749, 302037819898693 @ 17, 89, 35
174016187301220, 213432519760749, 356227705342783 @ 20, -17, 14
242219599681270, 198095041632474, 234812336636788 @ 123, 291, 53
363124893146512, 442652496410205, 252364287745435 @ -131, -484, -450
351213223671270, 362935312834443, 228742908818179 @ -128, -74, 17
344214173972434, 388335215576475, 186571894620823 @ 103, 14, 8
349598760694057, 366914630609265, 194339201768647 @ 50, 264, -86
341614994957750, 190062425474889, 303119964664158 @ -149, 100, 15
222157711994666, 237412175293295, 408224324533627 @ -39, -51, -31
271757703912044, 464616309219749, 332689336082035 @ -74, -295, 20
250628766803800, 168532696620157, 208267299142314 @ 17, 192, 147
317020112206914, 277809818286032, 407863381711725 @ 15, 281, -708
139674271448922, 306849236561795, 263391082181071 @ 46, -123, 119
258096215553470, 289814915480794, 288168350695608 @ 27, 5, -17
363641445693300, 230988678372095, 207280361486617 @ -183, 14, 164
395475230137604, 286569114155087, 286374068821828 @ -227, -58, 53
290926236744178, 297457255748751, 294347374053647 @ -25, 7, -48
316790682490495, 379717245881004, 409858098674218 @ -110, -183, -153
334822390551460, 382851207647739, 198921551768833 @ 122, 10, -55
225775609455410, 89113641823329, 422613356792828 @ -33, 124, -63
70307326837874, 123895406185359, 143541754272355 @ 295, 235, 257
162794878008996, 173652810519316, 495533087752947 @ 33, 27, -138
258705632635810, 80655227230039, 157840377597263 @ 107, 651, 244
300344409299646, 183646111251361, 110595965169963 @ -69, 168, 318
213975778288718, 193764624265807, 340491818490139 @ -35, -12, 44
254365196823130, 485963685578899, 125027966220903 @ -34, -333, 276
185119816803022, 159164853646062, 332181755689210 @ 43, 89, 9
312682991980546, 296682404141739, 277578830074327 @ -52, 45, -48
334063201619320, 349082279167895, 224872082527799 @ -28, 44, -38
146865332069684, 118672354368894, 388923136846080 @ 49, 85, -21
241545018449890, 175575930639279, 238105656690763 @ 119, 336, 48
242998473052770, 260842386471899, 353094911438503 @ -15, -22, -40
298049374841860, 302953880934789, 280519903072663 @ -100, -93, 74
241726047709066, 396700833512351, 470178566023441 @ -61, -216, -91
143251881420009, 227630340282400, 400202239949349 @ 40, -43, -20
181693698716464, 371335237710474, 279589747245676 @ 25, -185, 89
199776083341870, 424271723369277, 330637576913863 @ 17, -247, 18
243099685892272, 278790917182863, 307263401526238 @ 13, -18, -7
311573992428958, 339563241504477, 421253358816085 @ -115, -137, -115
195139968654514, 399321212524987, 273718733311575 @ 29, -216, 84
168652905324066, 42922523093201, 136328134641529 @ 79, 264, 260
332492502844023, 232541271110323, 268437348702505 @ -122, 98, 32
229871163504332, 315811780311601, 273027152212607 @ -11, -108, 82
364596076994326, 405392531793979, 169077695698471 @ -142, -190, 206
368014471738282, 411404609914515, 359308233522031 @ -187, -232, -168
336734676406219, 363019597051899, 200746200694471 @ 154, 250, -118
240100311481720, 182734033187437, 419841535721491 @ -28, 57, -100
101659208850650, 143063258042099, 354417480491543 @ 78, 39, 30
316608300364190, 327231766296979, 349926929027083 @ -108, -100, -67
175882437786106, 207986866149867, 48272619812743 @ 314, 296, 528
288200702096579, 134237752092030, 431007956556798 @ -50, 247, -237
187799273615390, 251576716767794, 225064328926248 @ -5, -67, 159
345031129381395, 398704983119649, 192035012621928 @ -20, -152, 55
240614617391002, 436092108670983, 319023865196143 @ 5, -269, -12
127420991862727, 123135422678220, 57674678556796 @ 186, 217, 389
290291345885074, 335338153703259, 336486368450743 @ -64, -110, -52
345222677707330, 353264220909579, 228080629830103 @ -55, 76, -106
120731315974643, 121922962460939, 352925773636740 @ 154, 170, -39
246457027018171, 290587724108904, 299967181084042 @ 124, 75, -119
339299631313000, 347877395943849, 291783005889913 @ -156, -157, 73
186318069122314, 321229647672967, 378293022619411 @ 41, -117, -49
275970025052456, 254003877380129, 60447875537872 @ 129, 300, 581
343777030173730, 387603653627809, 190127595920333 @ 23, -49, 39
326625954078592, 221492115488361, 224589119605135 @ 28, 711, -66
330727351246045, 382460793638208, 258529227193591 @ 62, -53, -358
207849930952126, 217444078290659, 375450280446241 @ -7, -10, -19
330413601325446, 354867024118919, 215181365719423 @ -14, 15, 8
273539593790110, 527357437168179, 200706886651201 @ -93, -350, 184
371305621051250, 406992413205499, 294687273096023 @ -194, -219, -191
238331445291794, 405888543233043, 282145027415895 @ -17, -224, 66
164563908487373, 245446713465540, 386623255996042 @ 36, -47, -25
352203648341690, 391410023508659, 182689032755383 @ -14, -49, 74
196332283252558, 239566376209863, 435769782659827 @ -10, -51, -63
332262603162525, 477986526034049, 423864050467268 @ -146, -312, -93
336025171108531, 228814354002627, 246100455575479 @ -136, 66, 90
202554996256310, 144622073487839, 323843280557063 @ 70, 185, -26
231583793158585, 274098148570719, 431523663253009 @ 32, -10, -208
194039870771935, 220086273278949, 348459395283913 @ 32, 12, -12
350978977183535, 297706532696529, 401295634941628 @ -128, 136, -541
239988722464295, 366388864576004, 306003658418008 @ 54, -147, -43
225592715561806, 116755915783527, 495439611678523 @ -40, 79, -127
295163518502294, 256302372227871, 354092662486808 @ -69, 22, -87
238762928861436, 104277648663616, 429257920986946 @ 45, 321, -253
335646527589942, 267411223903873, 319409116881496 @ -149, -52, 29
308988592776658, 321707797031691, 264887445984871 @ -49, -24, -8
325655810895730, 314119726351931, 285885347173367 @ -88, -7, -56
228513865324464, 407705823788478, 98135183804964 @ -35, -227, 295
221021819586370, 258975000763563, 6625466634103 @ 12, -23, 438
320402078029900, 178059278800419, 383059738044013 @ -139, 18, -12
336426609877986, 385743547933251, 217242942544247 @ 13, -83, -78
59321749403267, 132811665802238, 377024432495280 @ 118, 47, 9
269221169152992, 144282527780641, 105622925246739 @ -32, 191, 316
322565467760320, 359196040673604, 209572790080603 @ 33, 9, 22
343911256200550, 402887944644989, 174632354525853 @ 41, -165, 157
353126168973970, 405273919582935, 172039271954023 @ -33, -184, 178
326846182468312, 226025647156965, 371867791604191 @ -142, -17, -18
372763417186486, 399946994118006, 284888654682571 @ -205, -159, -578
238591627755922, 274330093596843, 314686772435383 @ 95, 66, -102
350425162332062, 389369983875975, 179065186259203 @ 156, 127, 23
195114071161846, 225361264742211, 333450165595939 @ 18, -8, 19
200946455709850, 426471282348513, 438704787028177 @ -13, -247, -69
182130635710210, 211838995770339, 366144270406063 @ 21, -5, -7
337674626273200, 379119144804627, 124545588880084 @ 37, -14, 515
309119233707144, 345457984349776, 176480897161028 @ 189, 171, 163
341093069492194, 215426787755718, 543835877405731 @ -145, 83, -386
406947563701153, 361064263636829, 506655770864396 @ -244, -160, -263
138744154165460, 337520178393783, 264760081146471 @ 132, -128, 82
142884697542590, 14953861507879, 301051396847183 @ 36, 167, 84
62428000394402, 121573669531131, 285948127754263 @ 198, 136, 68
301235858359754, 290689686950351, 264197704796073 @ -45, 24, 13
69052754947310, 235657014607714, 418845817526938 @ 99, -61, -25
276020997007381, 154938920738092, 289050261086728 @ -64, 117, 53
340992490662874, 283734631397387, 247161636223296 @ -121, 74, 27
125358983559838, 388966759539897, 442450312355365 @ 59, -208, -64
247111468608036, 298684579131926, 247459506399721 @ 21, -37, 80
269799925928330, 346080114851941, 192870832715433 @ -53, -141, 183
21485022052306, 61917371383851, 14153560016647 @ 151, 113, 369
168759694289722, 235235657051967, 394018487592739 @ 91, 16, -100
346771701017358, 379090812136831, 195343843369543 @ -36, -27, 38
364922844998242, 405449109473563, 193296414410007 @ -100, -154, -176
286294122958642, 382870439083131, 153541929882391 @ -30, -177, 245
144541456321322, 259959262174823, 159041330065209 @ 99, -36, 229
169067477683714, 204758213310363, 221220702084535 @ 78, 46, 146
201146928516970, 172345662796719, 265025819376463 @ 51, 112, 78
122849126629390, 139266589388763, 133073803140829 @ 217, 218, 275
376610203535095, 524590501174134, 540682746641333 @ -202, -413, -380
155396067983527, 135079411201904, 346771075414519 @ 38, 65, 26
367025720824960, 399429967429654, 200118770338033 @ -163, -147, -28
188860323625695, 280509742808449, 228889209496588 @ 208, 56, 83
370994826025810, 516943861319289, 277158295638088 @ -193, -544, -105
360132758113355, 400823411389429, 179526450589128 @ -14, -72, 21
317723494997245, 403424754416019, 123033781749148 @ -10, -206, 371
231857064371422, 328033566747723, 258488840035627 @ 84, -66, 37
430250735327386, 317628879447345, 463851654198943 @ -269, -111, -162
197095573209612, 386367210346765, 255360476476089 @ 118, -187, 61
237963736351605, 265388533967262, 253761264381393 @ 162, 157, -12
363368985840202, 288715458856678, 222859449036721 @ -169, 153, 44
336715322008593, 367196238729037, 205425778003914 @ 18, 36, -15
172536009897664, 162754568611140, 345184409520034 @ 45, 67, 5
343839846989266, 277316030970699, 191154063170167 @ -41, 515, 86
364839061293440, 370333200866079, 202280142884213 @ -146, 76, -47
205180494328024, 181302108773882, 352998887224071 @ -7, 27, 10
253114332607887, 252973452511066, 373269612984083 @ -44, -31, -42
260563693507432, 370218908840841, 227275158133861 @ 90, -127, 65
211632379587750, 229189261429669, 267702494391083 @ 33, 27, 76
246925439769358, 403237078327653, 341438050336159 @ 101, -213, -194
314011896591392, 359513784621587, 220682410853239 @ 13, -46, 26
192947734147345, 343204650565017, 232772451195853 @ 162, -96, 88
400010012688090, 317666186832694, 389849162657458 @ -249, -51, -211
344654321611729, 249175343587025, 521971621625971 @ -160, -28, -226
334131140547988, 223459610704956, 530065014889646 @ -151, -17, -195
271802467841374, 312721714818849, 474166669352047 @ -61, -100, -190
346585589783366, 394172810646086, 185879034872896 @ 43, -73, 41
348026275676730, 387630874942399, 214450542419923 @ -71, -109, -31
338259203280741, 352302596311566, 118072221394886 @ 96, 283, 655
293750362255726, 291573521915979, 78443880264043 @ 41, 130, 488
327898963343795, 191014039376899, 482563685839609 @ -138, 50, -184
337166009346768, 391869416398867, 241936328612339 @ 150, -42, -536
318801805101604, 313350452906991, 260512311617500 @ -79, -18, 15
363665586589577, 276485965150536, 560019564776630 @ -182, -29, -371
283693315753962, 303343268529299, 260638812037467 @ 19, 30, -8
152531270776150, 182584879439265, 364189307415757 @ 17, -11, 29
331886310340210, 367196248652751, 203943027278671 @ 7, -9, 32
293670081918730, 338393014464039, 238074080259283 @ 11, -40, 32
340517885909575, 292220098034574, 263908972058479 @ 12, 565, -430
215180009575150, 159662811481959, 432250918416853 @ 109, 256, -295
111353526905854, 158069012352691, 414700573118491 @ 56, 12, -19
342149249853468, 379057271341489, 449130014242836 @ -147, -180, -231
164800679784870, 110492400316699, 384075961244050 @ 27, 90, -13
194218348327784, 317435294782571, 377991167649959 @ 96, -78, -126
265459439896876, 393130510464227, 448999804034887 @ -22, -202, -238
342485301424762, 306126318497295, 448916100464563 @ -155, -91, -157
285930806205610, 329883886388883, 254526439062823 @ 32, -17, -12
222718267472544, 137706718628633, 419538567330529 @ -50, 33, -25
355490264524645, 367186320360879, 230373412357398 @ -94, 46, -183
349202081810142, 291246578412431, 223213156752343 @ -99, 284, -22
318303996716125, 368813135346114, 214100266906048 @ -22, -95, 67
359828018775610, 334476869183979, 315718417210383 @ -178, -128, 19
310093135954874, 392333711576675, 96139866022847 @ 154, -127, 625
332723387475285, 384153175982064, 182503117349788 @ 30, -77, 131
360194406570013, 349779100748340, 127043801020300 @ -92, 337, 597
288773776244596, 318828306006264, 110180186804176 @ 9, -5, 359
123467355045370, 135168256391259, 212490220185583 @ 66, 58, 171
301530401246642, 315308990894907, 147997344598679 @ 208, 319, 331
229677118804378, 304422878069265, 134766211371802 @ -25, -104, 257
335208657102058, 429374769368011, 181336018815583 @ -76, -292, 173
153126745187446, 361996029410147, 361232623991831 @ 176, -148, -110
307543544558028, 310836622716592, 261806684128363 @ 9, 87, -82
305446483268280, 95007956275577, 26450381518969 @ -23, 588, 584
308195050787890, 376020805378859, 151124547509703 @ 101, -69, 295
181744775932850, 416582355770979, 374307216760003 @ -9, -236, 17
323567364535098, 398843484951019, 184056042477469 @ -29, -190, 161
239625227411666, 460421176139587, 263860052129839 @ -17, -297, 89
290391850460116, 123822800918427, 390474163576439 @ -112, 58, -6
274274367393128, 222419281142943, 357607375004572 @ -51, 46, -61
355957759423346, 403839841977963, 174439429446519 @ 61, -119, 102
92872979090114, 178033036374593, 184039848628045 @ 111, 24, 200
97741768910238, 219237917005243, 481345580120351 @ 70, -46, -84
219237852779083, 293460830478687, 286842878713720 @ 134, 22, -39
165873248906086, 48723353419159, 391521269184095 @ 14, 135, -8
120293816868514, 163820001937179, 368954885538727 @ 51, 10, 22
337142332745596, 160547517607569, 190677777707717 @ -130, 235, 175
359903966491060, 336058036164375, 214952259623515 @ -68, 608, -316
278704085129049, 332251057343106, 274876653327010 @ 16, -53, -25
341902521147010, 290550862384683, 187354875008647 @ -118, 79, 167
266132989640850, 85667158930666, 151187445755913 @ 127, 761, 268
226481708603128, 264873125336255, 125550562908581 @ -52, -88, 259
358194067651922, 464014334175995, 240376420942551 @ -161, -364, 36
255918918476926, 464443215434815, 151073769691223 @ 86, -361, 258
326934575138296, 227642710359355, 187154441418847 @ -139, -6, 194
355023487027664, 380684157575495, 166279629390635 @ -20, 92, 232
342708878447974, 365712377127771, 208254982911037 @ -31, 26, -15
275992353396058, 254199039060579, 312307418341759 @ -44, 15, -9
275807125436405, 450328581313154, 241879925570534 @ -38, -295, 97
355105298525698, 461358532374587, 174255797829999 @ -67, -634, 165
127304870812111, 107206164704598, 387938601844705 @ 110, 147, -56
191211556791145, 383063844291897, 383818462516984 @ 162, -176, -209
270008506829071, 306985556216215, 270509853345710 @ 14, -18, 7
254859649784435, 279691564762489, 252917958138213 @ 22, 12, 60
301554869022495, 278690002932659, 270658229427943 @ -96, -46, 74
292995486711810, 278124279008795, 299858987167607 @ -68, -18, 6
170086256676901, 192032278758264, 399539006601156 @ 14, -5, -21
363343862472525, 462708884039439, 206020620737318 @ -114, -770, -179
199767932051315, 231641229533994, 324467235209543 @ 34, 7, 10
185698250335984, 338189264810958, 295966585334407 @ 61, -131, 42
355845863753410, 453333218257139, 189979947718988 @ -145, -366, 147
263693411545060, 382941996378267, 552998788505917 @ -68, -198, -231
357882206779336, 415793203698444, 221686125924646 @ -59, -285, -335
58482797244400, 283357087767651, 380695065023959 @ 112, -106, 10
329961895718995, 370045430297334, 264316414918513 @ -70, -109, -72
248082141022960, 238905086388339, 221882363855113 @ 22, 70, 123
209808257975519, 379817673897890, 358895541155856 @ 160, -163, -201
275001200474245, 405709429886895, 479845248771052 @ 52, -218, -579
215447048650693, 286084440368310, 308066874352459 @ 86, -7, -34
243779481735825, 367408788584499, 186923174146441 @ 162, -110, 164
22569070313760, 307206567552909, 336933487682743 @ 202, -113, 26
209855802119430, 266771395093679, 336731626000023 @ 28, -33, -14
152285478372850, 300465378313851, 147474491960791 @ 177, -44, 252
317340728176012, 355422381584551, 214819746096109 @ 8, -24, 41
218567618087469, 163809178763437, 274368240641493 @ -36, 24, 108
263714419323370, 253066561988427, 236112367528733 @ -13, 34, 103
318025834942906, 209033552746731, 422873100748303 @ -82, 192, -317
287128402777502, 364357342250719, 245621206783419 @ 153, -40, -104
248072289852880, 330038730987654, 167572107691063 @ 41, -77, 218
189081821987410, 458283001653339, 444430934012663 @ 35, -290, -129
232689117806470, 338009512571859, 347647996245103 @ -44, -152, 24
286524941660398, 398498738895345, 392464150253677 @ 41, -197, -405
289581406826830, 404120121547236, 281550894569635 @ 27, -213, -90
238710152421370, 355292544483489, 351300821030563 @ 23, -140, -82
356304901805038, 320639399358399, 251359082876207 @ -166, -65, 64
299258143464579, 329939012733995, 241161767292621 @ 78, 74, -60
391208392886390, 342636257835159, 562331178144743 @ -227, -116, -446
347915406224905, 378141743469594, 140106553810348 @ 28, 79, 481
407508472819681, 342065101666042, 327670405171882 @ -232, -157, 47
68256701718408, 52950691008669, 156980686432495 @ 150, 175, 230
241577764898038, 246780391542179, 295501616392079 @ -19, -10, 46
335640266041963, 366897853889835, 320775200954400 @ -154, -182, 49
305567299016286, 304550890065435, 234102345829961 @ -15, 58, 37
255844102411545, 236416893288454, 223372017812513 @ 34, 113, 108
359486749992297, 388233343083006, 180756857053962 @ -42, 61, 45
256997657349820, 240682040678865, 191215964897935 @ -58, -29, 190
337489509798277, 387749886514020, 191762667954925 @ 48, -67, 44
308731611545420, 173487498189829, 444926426740073 @ -39, 356, -468
405934168591492, 433302451890441, 495881447316868 @ -251, -268, -327
342562531851970, 329852991659459, 146721758630247 @ -133, -60, 262
201459697721034, 226176452581883, 409625152149327 @ -20, -42, -29
342190286602489, 382361323151712, 199647031503058 @ 36, -7, -37
295823889919724, 237024181773491, 238902193047203 @ -56, 86, 88
313871022274978, 350907196244889, 236256681248611 @ -25, -55, 16
359840463350408, 352014789184705, 312578822471289 @ -159, -52, -224
63266051000177, 144958221562269, 401563955793621 @ 120, 40, -20
289363911332530, 4297357886271, 201584988813263 @ 47, 964, 118
139623875169600, 365121525551783, 489522324414385 @ 42, -184, -109
285387003808144, 234159759801909, 194429463680919 @ -91, -20, 186
312338296007416, 230717344302005, 321196352977333 @ -67, 156, -112
109900900224955, 79824552813534, 271811127497488 @ 70, 103, 113
299767049618653, 243317066662260, 262990449670462 @ -34, 143, 5
336430697131966, 368621759709731, 209166228902299 @ -16, -16, 5
391878841792417, 405438773779004, 446025651245823 @ -214, -225, -62
382391688500786, 283246166659291, 375114971709047 @ -212, -18, -128
307671490544586, 326499940532387, 232143193625119 @ 10, 39, 11
369326492413668, 408128175647671, 194002024388681 @ -174, -204, -83

hailstones_example.txt

19, 13, 30 @ -2,  1, -2
18, 19, 22 @ -1, -1, -2
20, 25, 34 @ -2, -2, -4
12, 31, 28 @ -1, -2, -1
20, 19, 15 @  1, -5, -3

main.py

#!/usr/bin/env python3

import sys
from itertools import combinations

# Matrix utility functions
def matrix_transpose(m):
    return list(map(list, zip(*m)))

def matrix_minor(m, i, j):
    return [row[:j] + row[j + 1:] for row in (m[:i] + m[i + 1:])]

def matrix_determinant(m):
    if len(m) == 2:
        return m[0][0] * m[1][1] - m[0][1] * m[1][0]

    return sum(((-1)**c) * m[0][c] * matrix_determinant(matrix_minor(m, 0, c)) for c in range(len(m)))


def matrix_inverse(m):
    det = matrix_determinant(m)
    if det == 0:
        return None

    cofactors = [
        [
            ((-1)**(r + c)) * matrix_determinant(matrix_minor(m, r, c))
            for c in range(len(m))
        ]
        for r in range(len(m))
    ]

    inverse = [
        [val / det for val in row]
        for row in matrix_transpose(cofactors)
    ]

    return inverse


def matrix_mul(m, vec):
    return [sum(r * v for r, v in zip(row, vec)) for row in m]

# Vector utility functions
def vector_diff(a, b):
    return tuple(a_i - b_i for a_i, b_i in zip(a, b))

def get_equations(a, va, b, vb):
    dx, dy, dz = vector_diff(a, b)
    dvx, dvy, dvz = vector_diff(va, vb)

    coefficients = [
        [0, -dvz, dvy, 0, -dz, dy],
        [dvz, 0, -dvx, dz, 0, -dx],
        [-dvy, dvx, 0, -dy, dx, 0]
    ]
    constants = [
        b[1]*vb[2] - b[2]*vb[1] - (a[1]*va[2] - a[2]*va[1]),
        b[2]*vb[0] - b[0]*vb[2] - (a[2]*va[0] - a[0]*va[2]),
        b[0]*vb[1] - b[1]*vb[0] - (a[0]*va[1] - a[1]*va[0]),
    ]
    return coefficients, constants

# Main function to solve hailstone collision problem

def solve_hailstone_collision(hailstones):
    total = 0
    for a, b in combinations(hailstones, 2):
        intersection = intersection_2d_forward(*a, *b)
        if intersection:
            is_within_range = all(200000000000000 <= coord <= 400000000000000 for coord in intersection)
            if is_within_range:
                total += 1
    return total

# Intersection calculation for 2D forward movement
def intersection_2d_forward(position_a, velocity_a, position_b, velocity_b):
    position_a_next = tuple(position_a[i] + velocity_a[i] for i in range(2))
    position_b_next = tuple(position_b[i] + velocity_b[i] for i in range(2))
    displacement_a = [(position_a[i] - position_a_next[i], position_b[i] - position_b_next[i]) for i in range(2)]

    if (divisor := matrix_determinant(displacement_a)) == 0:
        return None

    determinants = (matrix_determinant([position_a, position_a_next]), matrix_determinant([position_b, position_b_next]))
    x, y = (matrix_determinant([determinants, displacement]) / divisor for displacement in displacement_a)

    # Check if the intersection point is ahead of both hailstones
    check_a = ((x > position_a[0]) == (velocity_a[0] > 0)) and ((y > position_a[1]) == (velocity_a[1] > 0))
    check_b = ((x > position_b[0]) == (velocity_b[0] > 0)) and ((y > position_b[1]) == (velocity_b[1] > 0))

    return (x, y) if check_a and check_b else None

# Parse hailstone data from file or stdin
def parse_hailstone_data(file_path=None):
    hailstones = []
    with open(file_path, 'r') if file_path else sys.stdin as fin:
        for line in fin:
            position_str, velocity_str = line.split('@')
            position = tuple(map(int, position_str.split(',')))
            velocity = tuple(map(int, velocity_str.split(',')))
            hailstone = (position, velocity)
            hailstones.append(hailstone)
    return hailstones

# Main execution
def main():
    """
    Main function for solving the Advent of Code 2023 Day 24 problem.
    
    Reads hailstone data from a file, calculates intersections, and solves for optimal rock position and velocity.
    Prints the results for Part 1 and Part 2.
    """
    file_path = sys.argv[1] if len(sys.argv) > 1 else None
    hailstones = parse_hailstone_data(file_path)

    # Part 1: Calculate intersections
    total_intersections = solve_hailstone_collision(hailstones)
    print('Part 1:', total_intersections)

    # Part 2: Solve for optimal rock position and velocity
    if len(hailstones) >= 3:
        a, b, c = hailstones[:3]
        A1, B1 = get_equations(a[0], a[1], b[0], b[1])
        A2, B2 = get_equations(a[0], a[1], c[0], c[1])
        A = A1 + A2
        B = B1 + B2

        if inverse_A := matrix_inverse(A):
            answer = sum(map(round, matrix_mul(inverse_A, B)[:3]))
            print('Part 2:', answer)
        else:
            print('Part 2: No solution found')
    else:
        print('Not enough hailstones for Part 2 calculation')

if __name__ == "__main__":
    main()