FazeCT Day 8: Playground
Part 1
Equipped with a new understanding of teleporter maintenance, you confidently step onto the repaired teleporter pad.
You rematerialize on an unfamiliar teleporter pad and find yourself in a vast underground space which contains a giant playground!
Across the playground, a group of Elves are working on setting up an ambitious Christmas decoration project. Through careful rigging, they have suspended a large number of small electrical junction boxes.
Their plan is to connect the junction boxes with long strings of lights. Most of the junction boxes don't provide electricity; however, when two junction boxes are connected by a string of lights, electricity can pass between those two junction boxes.
The Elves are trying to figure out which junction boxes to connect so that electricity can reach every junction box. They even have a list of all of the junction boxes' positions in 3D space (your puzzle input).
For example:
162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
This list describes the position of 20 junction boxes, one per line. Each position is given as X,Y,Z coordinates. So, the first junction box in the list is at X=162, Y=817, Z=812.
To save on string lights, the Elves would like to focus on connecting pairs of junction boxes that are as close together as possible according to straight-line distance. In this example, the two junction boxes which are closest together are 162,817,812 and 425,690,689.
By connecting these two junction boxes together, because electricity can flow between them, they become part of the same circuit. After connecting them, there is a single circuit which contains two junction boxes, and the remaining 18 junction boxes remain in their own individual circuits.
Now, the two junction boxes which are closest together but aren't already directly connected are 162,817,812 and 431,825,988. After connecting them, since 162,817,812 is already connected to another junction box, there is now a single circuit which contains three junction boxes and an additional 17 circuits which contain one junction box each.
The next two junction boxes to connect are 906,360,560 and 805,96,715. After connecting them, there is a circuit containing 3 junction boxes, a circuit containing 2 junction boxes, and 15 circuits which contain one junction box each.
The next two junction boxes are 431,825,988 and 425,690,689. Because these two junction boxes were already in the same circuit, nothing happens!
This process continues for a while, and the Elves are concerned that they don't have enough extension cables for all these circuits. They would like to know how big the circuits will be.
After making the ten shortest connections, there are 11 circuits: one circuit which contains 5 junction boxes, one circuit which contains 4 junction boxes, two circuits which contain 2 junction boxes each, and seven circuits which each contain a single junction box. Multiplying together the sizes of the three largest circuits (5, 4, and one of the circuits of size 2) produces 40.
Your list contains many junction boxes; connect together the 1000 pairs of junction boxes which are closest together. Afterward, what do you get if you multiply together the sizes of the three largest circuits?2003,26067,72758
75355,33832,416
30456,58025,11108
50345,48499,75382
3725,49456,41389
26766,31067,6012
2577,88080,67312
42607,1258,50954
21976,21736,7222
25164,65502,33712
12595,35660,82974
43469,70108,73370
65571,20640,94235
27571,44492,17285
17505,23661,48581
75251,73385,64610
20729,32875,98422
67144,62810,2279
39058,48758,30953
24372,87714,52165
66505,764,3061
46736,253,98684
31389,68188,93075
26813,303,8432
93049,63204,8385
46412,72383,59661
61525,81350,15992
54513,79619,44514
32860,54353,8397
90865,50759,27655
57328,13464,90952
23863,53473,50677
41870,51538,55556
28056,6722,31040
35652,65647,69754
70235,76117,99626
47461,86503,85514
90036,85160,32183
43402,79341,54752
42452,94354,8197
67383,59744,26147
3541,54676,44343
55712,11899,95855
30094,74600,28785
85713,52460,58857
58702,92323,65076
57458,53584,44367
73647,39973,9194
99117,82430,4567
26233,64688,49812
38633,57392,7973
43744,48548,93721
54566,34283,64748
88259,43383,45477
11375,55413,9054
49695,54237,19017
34664,38594,358
46961,8968,61817
80498,6830,81701
29606,62094,94920
91616,22557,93133
34438,30771,11256
92643,50533,49758
32377,75372,17447
28885,94587,17502
32384,74734,47440
47344,12212,17793
65829,35942,81949
10237,10025,93555
41690,62046,71279
70839,63452,24259
12104,59862,98061
79497,41323,77312
20081,38532,11442
47742,25617,57111
705,41356,32242
77111,7192,31793
35126,90188,76378
43086,10390,8753
47650,40186,51791
78866,6532,68306
94889,61345,86717
67171,52881,52191
74763,26804,28451
80905,27569,31768
8311,67143,41978
76128,12841,92493
92124,57407,97611
47615,25180,55554
60927,95895,33157
23562,40209,86695
77147,6500,7528
95055,62200,32317
42338,34499,53891
92918,48108,16944
908,40318,33627
33362,17817,37964
33069,22935,76096
29694,39086,42383
13678,61719,57177
53754,69459,30351
8146,14086,71696
38854,48631,77659
1727,60358,1379
47420,37641,94775
80330,30754,78099
21255,17670,43369
3163,24182,97095
48223,46807,70659
29857,32075,11385
46871,76905,85730
25913,95921,85250
23750,42502,12240
21677,21359,34811
29371,18911,59509
42064,26144,3644
10202,26348,78302
22249,2860,40655
1572,77120,36082
53086,90934,7208
17720,27837,28087
2232,67846,16963
43372,7210,24665
85504,14054,17128
81336,45425,12001
60023,13519,56230
80369,38279,52315
9127,90740,24860
17449,20692,74766
64652,60561,46330
23240,96247,21417
84930,31692,10839
70760,87421,46383
90606,86123,33011
24374,96702,72007
79252,83338,97972
17510,83516,42862
76647,64403,93534
81919,10925,1451
99370,84698,294
78646,66074,67178
65535,53422,39656
63296,58202,2479
54390,65908,55042
3741,9343,23210
81183,66473,20081
65121,5932,50408
58278,1173,29823
10871,39289,86614
38289,63615,4333
87126,32047,15062
19712,95354,67459
18676,7225,20403
841,21778,55825
10686,42521,67414
99360,2820,91716
29176,85337,56272
58510,32012,87924
22650,40050,55737
19352,67205,23999
19811,78489,61249
52132,5278,6343
70817,13387,12795
34577,97599,10572
72324,55738,71575
84110,81236,79898
35106,94646,31760
90766,99756,93032
7459,70376,49662
9258,50865,22212
28673,3339,82664
11639,98386,62322
46724,34778,25838
33581,57509,74290
34334,29789,87496
56037,79737,63852
85360,64068,44093
99858,2137,34245
35772,80589,96139
36910,62410,93597
19880,85792,82443
11125,78154,9982
20753,17796,8201
85668,52012,71880
25557,8874,55252
17758,15920,65020
38619,29952,29821
8473,33485,62633
56748,48740,91264
56849,55069,70405
59313,13992,87804
13011,9043,35282
39154,53515,80291
99500,47503,67790
51693,65148,5031
75453,53130,37918
17692,72489,79790
3229,50301,33298
19293,39025,66036
74405,55776,62637
6711,48973,4975
32699,6388,18968
69587,92671,25936
91327,87601,65036
87234,18455,750
57479,53175,40848
64377,36211,81318
81526,92592,32829
95864,5301,17547
44747,3119,99821
93617,44283,81249
64977,95721,45896
25146,59793,16106
77191,23617,24782
20939,28053,98836
98074,72653,99181
89642,77037,87113
60418,11350,46891
77619,49211,58627
33684,37089,67584
25660,22374,42369
63728,23321,69445
92726,42276,58094
93110,50683,30139
66565,28583,65287
16165,44812,28857
73892,80518,79193
87018,91832,70512
36724,70073,74031
64391,55396,28867
27433,83305,40954
77774,47710,68404
13199,91873,72708
77655,96196,20165
83431,82845,39762
59746,31523,57377
29159,27649,40722
50218,53863,31053
74639,90032,89807
981,10692,69455
11246,74139,31714
25107,4204,88716
84577,70872,52423
85419,46206,15609
15504,59575,39299
21567,7107,4446
5641,45032,6001
82913,47228,68746
24567,3310,3068
48468,6143,96260
31132,79338,95061
60217,94710,56560
7,82682,14654
88232,63894,47487
93438,84107,31006
2734,63695,24646
16687,12764,78070
31267,96424,25855
74732,46349,32166
8890,4470,64657
94899,84279,42348
74868,57029,32676
75946,98082,57043
28881,30176,91295
56412,65700,67730
98183,46183,846
76952,21942,32992
71321,3068,98993
63521,45675,92519
15856,87990,91248
46993,21210,30027
86722,37422,92076
18079,2284,17869
56920,45968,44331
34084,13523,3670
39268,16531,98599
48259,33611,27609
26521,46084,63807
38180,62385,95625
98983,99892,90253
53805,60007,63128
79935,12106,46849
41976,8772,61281
68221,19105,10645
10503,19083,6484
69728,87703,25740
70000,56543,99160
9541,94528,88612
7723,69391,13793
45887,47766,63333
79559,55020,11237
69152,65839,88293
50915,14381,34444
78380,75197,4194
62800,94173,81737
10583,7454,34551
56794,63157,47175
94330,72175,47920
87842,21838,44442
49034,82756,91737
91311,84908,12342
45234,70650,95628
7268,26858,18689
37038,90186,61058
99184,57432,50030
40295,25627,57178
66165,30689,47820
17584,29719,72130
84317,92410,98716
51695,97580,69679
91,46004,21822
70347,3218,57431
69483,68321,30022
47794,24082,8705
99421,2054,20650
10588,88292,23715
73695,60759,6342
76900,23062,6037
53241,90700,74397
6294,47955,36317
40262,16349,82757
73142,75107,72709
68693,46252,10022
97428,61033,54358
56843,24245,8989
7355,74264,56514
85077,58621,86945
88547,58035,45771
71469,44806,66203
60139,76785,99349
83425,9487,21334
42116,99530,49060
1485,21577,35494
55829,86645,54227
98005,71403,53181
90956,37943,66587
93118,35940,96516
99759,2968,44019
5747,81245,24368
73163,6395,84657
40891,36384,76316
95933,86255,5975
40923,82707,48238
47306,594,35963
52514,51226,38425
56912,31841,46664
16970,73184,61844
88036,81105,97025
16250,56972,22856
25926,35629,2459
44996,13361,46337
77393,66217,48874
24943,48605,19210
16172,285,49408
2566,93042,75711
72710,1166,4532
50886,34453,1636
91821,21682,63870
8514,53574,41699
42735,42393,8135
76289,40615,48210
7048,63837,99364
5034,59837,96558
56016,48517,53300
29042,59082,54266
25751,34838,5679
90659,87136,35173
84044,9463,23120
77500,52750,73461
37443,11356,80512
14136,38747,93625
42006,6482,71030
11783,49727,49726
90742,81267,61093
54995,66826,99500
45881,86842,95520
4069,21167,53652
91399,24540,49814
30837,15606,56778
71461,64684,96694
54321,60876,98029
67782,84675,32730
81283,3960,58524
81432,53879,78254
8934,33027,67068
34021,85494,18520
55068,81765,77646
55969,78535,93383
92694,55442,63731
74950,70523,66399
38970,28068,9877
52390,43938,50762
34221,61270,19496
12677,20365,19686
8093,60390,14777
4634,35761,50853
43183,69825,54014
71870,83842,44741
87253,25141,86798
95218,22275,20459
26162,78577,50277
49151,23821,37384
7728,74844,67219
24549,85346,43073
5248,10312,79212
75404,71981,87573
35105,74673,92725
15825,97037,35953
38366,52499,69796
82339,37770,41974
69137,38838,42369
21544,83925,24071
77993,66862,53673
94708,65689,19371
59942,76968,52154
99762,98379,82932
51253,25451,92623
45402,58172,78980
5105,36388,87222
57514,11260,22896
91272,11660,21744
85225,15859,22177
45875,92690,3015
84553,93189,28214
49,69255,58377
45007,16201,96763
47911,57405,57341
34809,99894,35242
15541,65555,57444
22097,89032,34583
61494,6626,9419
34570,82323,81480
90121,74373,57073
53329,24221,70104
9904,61825,24905
76666,14406,5564
49440,65608,97007
3719,92499,84012
53186,76907,99117
87130,53519,57601
86797,88703,97324
25912,93173,83196
41778,61744,76123
55632,2886,48996
90810,51410,21040
15799,89301,50620
82717,39670,27369
1082,36291,45185
96906,60029,74181
20360,15940,76252
36341,36849,19122
89134,27352,77390
75458,6731,7386
15268,74947,56522
87604,7141,38181
36088,25145,19136
11417,59698,8763
11956,71130,35037
61172,33736,16046
73090,60770,68070
18498,46231,27096
31796,20888,53845
89330,24642,34961
22208,4328,76500
52397,73045,44031
82914,33484,12090
86133,44307,67712
60438,16183,47602
15428,24602,54037
32395,45025,49249
17927,38785,85634
45069,21116,25765
63382,34360,90125
1912,80647,12281
1048,12446,15551
11889,48142,55954
54369,67457,3665
51733,46538,51128
61796,75319,72140
72032,15276,20023
99860,60829,18660
9823,61641,53539
95160,81558,83876
50989,38250,8838
56980,79648,8435
57288,41265,58564
88830,30676,50945
79217,19852,94038
16192,975,8179
86326,39635,26205
93125,68315,65709
44762,45045,87870
3572,77397,76041
94343,54662,28452
18972,46193,19834
8118,2840,44275
6636,58447,42726
90087,40927,21414
12286,30066,57424
4681,63810,59362
7792,15748,62351
41080,72053,58814
59334,58306,86742
83740,20570,79304
41539,81891,62010
42652,33116,80302
22913,84874,71411
60696,4094,53117
88007,42286,23407
98661,10410,12401
40810,1697,8724
63817,1750,65768
44841,25708,55142
63036,18451,31500
56826,44055,1750
3279,51805,22560
36096,1972,90274
45191,62357,75069
19808,85452,13409
60587,76184,2222
86155,85088,80240
56170,63205,34510
20486,27278,85580
15133,38712,56842
9886,46080,36769
95819,71379,98206
30358,64732,31430
83033,4015,69653
9578,91629,79408
13904,90658,31037
26140,50005,92376
25242,94997,24243
72799,60920,83250
34025,27382,13643
90256,92247,56244
88134,50163,33382
92198,23076,42666
2259,43890,25157
59018,1964,84783
13339,10233,94275
73552,28922,99691
11215,23818,33029
80271,55056,7695
4830,84251,6270
17958,32449,55384
82902,75059,66488
49840,73792,27962
72673,74719,13324
99805,66043,38117
53310,91520,51546
27627,82754,7331
3835,68824,27839
67027,37813,41590
50521,40235,98049
20035,36721,79576
3102,16594,95479
52716,45189,38286
63851,20163,68136
34084,53053,77192
30327,28072,67856
57349,34365,90232
60821,73050,52550
12095,37268,69588
55065,90443,36406
74162,15396,11127
73397,95963,11062
94855,20087,49182
94713,65553,26349
33239,95312,23063
76362,76598,37125
9389,35481,77969
77939,10355,63662
15167,61050,11962
54663,23801,18665
57477,49459,19561
29303,22509,74761
76163,17165,31266
69197,10940,37305
88512,91072,39229
43505,54435,1827
62644,14226,69945
1793,63313,70603
69408,62116,2315
65677,38441,65102
14815,38593,73273
90527,63495,96085
32923,87108,45346
16976,98782,55092
42117,36451,41415
60587,91886,94614
59769,66571,26273
68913,92471,25410
35579,19930,88440
48118,71293,83438
69091,75488,83222
34021,66703,93707
86365,23839,2998
94234,12578,88028
94032,95822,83823
80508,67801,60769
40246,12668,40316
22171,17698,65443
65831,32506,29219
12670,3728,73670
4254,61451,95330
30863,61498,73955
71969,92210,89358
65531,74966,59209
99684,51692,10466
63722,26116,31637
83733,10486,21565
55,59143,70154
18614,42891,37583
97461,93329,89089
95517,65079,62625
68488,222,6582
15982,75186,32386
62564,84035,78210
81622,41841,82301
69815,54160,56241
83894,46993,73760
37171,85782,47708
93347,21157,33503
60200,13033,67851
11726,66182,9370
8495,33514,16012
55577,42309,3748
51026,29330,86646
37810,37675,33723
68608,31676,51995
28942,21568,15901
76049,98540,21291
26223,48216,25453
39453,53944,19430
45468,2044,61167
18805,90416,96404
78743,75485,10195
38373,32893,81537
99119,4465,33985
41899,52272,79844
55671,5283,6108
24336,44954,93887
8248,99174,63452
46386,91351,17853
48562,74746,86910
8988,58276,73339
37227,89563,84567
40901,42323,7643
73535,10124,96888
97028,13545,74112
28224,97636,59493
47079,76381,97484
67876,62265,63226
90960,65753,52208
67803,77076,60898
54581,65279,27170
90754,65561,38908
78139,76286,17075
45956,81984,91945
74663,5687,99865
34894,49776,90421
36934,1914,49896
88836,98174,89444
78447,87267,13830
75551,65356,82419
51713,28851,473
13958,51802,1247
42880,43615,92674
83408,47074,28202
19172,45118,34794
46142,23452,9674
22190,63376,7611
61474,4378,26745
53168,99622,92087
76961,51842,94967
72136,94088,91710
2458,29205,54974
54560,20322,70647
62462,33144,69469
58713,32519,73299
14034,91135,18899
45251,32423,16952
50801,43652,29137
10818,31604,57413
4156,7150,34366
71554,48878,61705
60075,5184,46451
29746,38800,26246
28069,38717,32807
46630,84701,72134
88768,5122,91920
47806,17211,12881
61470,65808,99035
21802,51335,63257
18174,93315,11805
57651,46944,89587
10873,97382,6625
84435,11979,96512
43910,33908,91089
85579,97547,50700
332,6221,35532
69353,60410,55014
68063,55476,93956
1840,45243,19651
73403,76160,30538
20722,28219,7244
64759,42154,42098
93026,53088,65173
42415,24880,90080
50441,52496,74530
33836,64691,28913
3571,81728,51803
53265,85005,65969
376,63195,33411
3669,89180,87604
6455,22615,24947
39562,68932,58475
87548,87664,50484
31601,80709,97434
13512,99996,35893
38284,46126,9843
68432,50285,15342
61035,74798,16902
13834,56369,1431
79066,11448,4132
70720,73439,24461
78702,87107,35906
56084,91153,63240
12471,84011,10087
83188,4248,27610
882,11864,9947
73537,15641,77199
99773,91294,44825
98848,81015,28755
81338,97227,89842
33971,77600,52716
82706,87105,97751
59997,19498,22826
46721,60165,61334
38552,39598,5183
43427,24619,85740
14177,18339,14937
37120,68987,7679
51296,57196,93968
6894,30513,30760
519,84483,74334
64786,4992,25412
30075,41667,55858
30487,91649,28129
15068,86263,81714
22353,14190,21179
75549,27994,58834
15904,84907,74143
85103,46795,86013
51456,31089,44653
94074,19912,31356
7562,84361,56741
13582,22009,28983
46779,68796,12297
8816,51826,49190
99699,17851,86843
88679,78898,8231
73129,43067,91558
88376,12343,40651
30112,99934,85696
55793,59878,85526
64469,382,84559
30065,30602,70828
82919,92583,60329
96296,24779,98270
24603,53324,88548
89817,87339,89261
51030,77248,94471
97253,48154,30594
29557,97512,65339
16391,19602,28215
55867,80539,465
47454,25519,769
30365,22486,38211
93157,46685,79037
56626,80959,40442
58636,10986,68708
14900,32188,72946
10539,60385,3388
17864,95370,22420
5530,62794,71342
41112,13127,27893
2441,67875,7924
51512,47963,12910
23977,93096,13252
80644,53905,39780
72392,18086,97955
31885,71517,35528
37771,86701,97340
83488,90499,9143
28971,52580,57919
70134,72480,42948
5539,29713,24450
61139,52953,10338
91707,99047,8275
48373,54999,31766
54159,87244,51475
8660,72960,26472
38082,70161,55125
16550,10390,87343
53246,33087,90673
23067,48613,75263
68427,53941,76004
96816,5759,67754
83217,83507,90525
78632,76089,63303
89720,43904,47930
56091,83745,55211
9076,3090,35074
39514,1406,34719
44612,42229,60920
24534,99719,75603
541,26413,77926
71200,1123,89894
38759,42808,79772
12622,86181,99602
70279,9712,19277
35367,85066,44972
13926,86838,67600
45111,71214,97878
42586,27235,73985
95995,54800,33838
37102,51789,92334
34379,27961,4784
37872,20979,87710
7341,24358,14075
49338,44765,76134
57857,33165,18757
51004,44341,92704
44127,15354,67903
81824,67779,56815
1676,47811,13440
85182,65177,12187
26330,81386,44899
52951,6121,10254
51105,26721,92983
19924,73940,78606
5722,58961,8106
50747,19866,71258
79929,69320,40708
94304,54945,24340
46702,23698,63211
49473,4051,97120
27978,10755,36976
45406,59265,56900
59739,3615,4891
10957,67490,37842
79044,67237,51229
36309,93111,30569
57088,18358,39842
11434,87886,10352
63746,92958,32928
74631,65600,23729
30120,23374,44750
71253,40605,67285
8959,83800,11650
35458,27831,65362
64271,81524,51174
97994,91360,21818
6785,6107,43016
56896,87604,21533
60913,67118,92063
32600,92546,78984
3462,58293,358
27184,3241,573
2430,92623,80574
46512,6577,35432
18809,83598,27358
96961,44960,61908
62372,50644,29464
55511,89849,99195
22302,1129,81284
57728,31766,97415
80921,17986,61903
45226,26241,48850
69822,48746,92812
53724,6142,56062
24528,90034,42030
48022,95617,79403
1975,54649,16815
25355,96027,574
37414,26438,88111
40059,73562,50122
99877,11007,62064
1270,60027,24028
37542,1002,98168
71876,24751,54109
93455,74766,37790
65098,76547,27576
2230,45538,3101
97598,43721,49937
3201,42521,68249
88176,25960,34051
78525,88423,4505
74650,55235,37686
68810,62151,97012
9733,8363,32574
11558,14463,91148
23632,67561,42387
32742,16959,70826
89965,74941,32396
39334,67383,66404
25821,70353,50820
89482,66261,85197
54428,36543,20309
34947,84494,7843
68363,59665,41729
98008,66774,97335
44290,15018,59363
21281,11712,53773
20618,57408,31090
94857,39108,46228
22803,72723,88573
83475,17072,47625
52814,63136,65718
90905,41524,46430
94495,79802,72874
44964,51161,20422
51678,51005,74745
40459,85548,16345
42878,71112,22056
40855,77902,50449
44663,10668,17576
2415,4377,77957
12481,53600,85579
56567,72597,54650
80175,96069,95117
37196,91346,79333
64775,24413,26536
34143,80824,768
99092,56638,34725
609,37420,60934
94804,60102,42935
82161,61512,58325
57482,20138,35351
43470,6075,57962
92626,42841,1374
77925,28265,11074
6903,19401,94415
1804,1592,36921
15327,2321,9249
67610,77995,48697
13518,65861,1993
17123,77906,8847
56157,43980,7629
82615,72806,67248
97109,77471,77883
61573,95693,19696
6943,91649,31862
49892,68828,67882
15723,39853,40492
78505,78138,85418
16715,30051,48619
35144,7364,97869
70532,68675,22593
8316,55014,63894
85643,64639,32503
37000,17029,28096
8151,77104,9277
17902,85493,80346
75686,78252,98451
84581,90409,71241
68967,47039,59119
77658,16753,17633
36752,7317,38054
59005,30546,57346
26573,34945,34858
73202,70431,72712
98360,36569,49040
24860,8137,74822
51176,99285,67172
6638,89262,13388
19037,20720,91462
24156,29496,66467
75620,6610,33200
17453,93162,40513
53583,40811,30471
13516,84979,72126
56225,28307,12534
99067,50229,83836
32676,5158,69185
32653,70593,27474
11598,15777,65439
79989,71810,39665
80280,71335,47721
63957,69660,40490
80195,25136,4922
6015,61105,77581
22059,81606,86110
88807,39782,57858
27046,5479,25500
85769,67988,39886
78022,61215,1893
57901,34817,9810
38502,66834,39398This problem is straightforward: Connect the nodes (junction boxes) by always picking the shortest possible wire to connect the unconnected parts.
The challenge is pretty much identical to applying Kruskal’s Algorithm for finding a minimum spanning tree (MST).
First, we parse the input and store the 3D coordinates using the parser component. We use the following structure to store the points:
[ptr + 0]: X coordinate (8 bytes).[ptr + 8]: Y coordinate (8 bytes).[ptr + 16]: Z coordinate (8 bytes).
section .bss
points resq 6000
points_cnt resq 1
; ----------------------------------------------------------------------
; Component: Parser
; Args: rdi
; Ret: Add the current point (x, y, z) to points list
parser:
push r12
push r13
mov rax, qword [points_cnt]
imul r12, rax, 24
lea r13, [points + r12]
call atoi
mov [r13], rax
inc rdi
call atoi
mov [r13 + 8], rax
inc rdi
call atoi
mov [r13 + 16], rax
inc qword [points_cnt]
pop r13
pop r12
retAfter that, for each pair of points, we calculate the distance between them. Normally, to get the distance between points, we have to calculate the Euclidean distance, using the following formula:
However, there is no need to calculate the actual Euclidean distance which requires floating-point math. Since we only need to compare the distances (for example, ), we can just compare the squared distances instead (that is, ).
Next, we have to sort the edges in ascending order by their length (or distance between the origin vertices). This time I will use quick sort instead of bubble sort like in Day 5: Cafeteria.
; ----------------------------------------------------------------------
; Component: Sort edges
; Args: rdi, rsi, rdx
; Ret: Quicksort to sort edges
sort_edges:
cmp rsi, rdx
jge .done_sort_edges
push rbx
push r8
push r9
push r10
push r11
push r12
push r13
push r14
push r15
mov r12, rsi
mov r13, rdx
imul rbx, rdx, 16
add rbx, rdi
mov r14, [rbx]
mov rax, rsi
dec rax
mov rcx, rsi
.partition_loop:
cmp rcx, r13
jge .partition_end
imul r15, rcx, 16
add r15, rdi
mov r8, [r15]
cmp r8, r14
jge .next_j
inc rax
imul r9, rax, 16
add r9, rdi
mov r10, [r9]
mov r11, [r9 + 8]
mov r8, [r15]
push rbx
mov rbx, [r15 + 8]
mov [r9], r8
mov [r9 + 8], rbx
mov [r15], r10
mov [r15 + 8], r11
pop rbx
.next_j:
inc rcx
jmp .partition_loop
.partition_end:
inc rax
imul r9, rax, 16
add r9, rdi
mov r10, [r9]
mov r11, [r9 + 8]
mov r8, [rbx]
mov r15, [rbx + 8]
mov [r9], r8
mov [r9 + 8], r15
mov [rbx], r10
mov [rbx + 8], r11
push rax
push r13
mov rdx, rax
dec rdx
call sort_edges
pop r13
pop rax
mov rsi, rax
inc rsi
mov rdx, r13
call sort_edges
pop r15
pop r14
pop r13
pop r12
pop r11
pop r10
pop r9
pop r8
pop rbx
.done_sort_edges:
retNow, the challenge wants us to connect the 1000 closest pairs of points. To deal with this, we implement a Disjoint Set Union (DSU) data structure to solve the problem.
For each of the first 1000 edges, given that the edge spans from A to B, we have to:
- Find the root of
A’s group, call itroot_A. - Find the root of
B’s group, call itroot_B. - If
root_A != root_B, union them by turningroot_Binto one of the childrens ofroot_A, while adding the size ofB’s group to the size ofA’s group.
The last thing to do is to find the three largest circuits by finding the largest size values.
Below is the solver component that does all the mentioned steps.
; ----------------------------------------------------------------------
; Component: Solver
; Args: None
; Ret: DSU + Kruskal for forming circuits, update result
solver:
push rbx
push r8
push r9
push r10
push r11
push r12
push r13
push r14
mov r12, qword [points_cnt]
xor rbx, rbx
mov qword [edges_cnt], 0
mov r14, edges
.outer_loop:
cmp rbx, r12
jge .edges_done
mov r13, rbx
inc r13
.inner_loop:
cmp r13, r12
jge .inner_done
imul rax, rbx, 24
imul rcx, r13, 24
mov rdx, [points + rax]
sub rdx, [points + rcx]
imul rdx, rdx
mov r11, rdx
mov rdx, [points + rax + 8]
sub rdx, [points + rcx + 8]
imul rdx, rdx
add r11, rdx
mov rdx, [points + rax + 16]
sub rdx, [points + rcx + 16]
imul rdx, rdx
add r11, rdx
mov qword [r14], r11
mov dword [r14 + 8], ebx
mov dword [r14 + 12], r13d
add r14, 16
inc qword [edges_cnt]
inc r13
jmp .inner_loop
.inner_done:
inc rbx
jmp .outer_loop
.edges_done:
mov rdi, edges
mov rsi, qword [edges_cnt]
test rsi, rsi
jz .done_solver
dec rsi
xor rdx, rdx
mov rdx, rsi
xor rsi, rsi
call sort_edges
mov rcx, qword [points_cnt]
xor rbx, rbx
.init_dsu:
cmp rbx, rcx
jge .dsu_ready
mov dword [parent + rbx * 4], ebx
mov dword [sizes + rbx * 4], 1
inc rbx
jmp .init_dsu
.dsu_ready:
mov r14, edges
mov r12, 1000
cmp qword [edges_cnt], r12
cmovl r12, qword [edges_cnt]
xor r13, r13
.kruskal_loop:
cmp r13, r12
jge .calculate_result
movsxd rax, dword [r14 + 8]
movsxd rbx, dword [r14 + 12]
mov rdi, rax
call find_set
mov r8, rax
mov rdi, rbx
call find_set
mov r9, rax
cmp r8, r9
je .next_edge
mov dword [parent + r9 * 4], r8d
mov eax, dword [sizes + r8 * 4]
add eax, dword [sizes + r9 * 4]
mov dword [sizes + r8 * 4], eax
mov dword [sizes + r9 * 4], 0
.next_edge:
add r14, 16
inc r13
jmp .kruskal_loop
.calculate_result:
xor r8, r8
xor r9, r9
xor r10, r10
mov rcx, qword [points_cnt]
xor rbx, rbx
.scan_sizes:
cmp rbx, rcx
jge .multiply_result
mov eax, [parent + rbx * 4]
cmp rax, rbx
jne .skip_size
mov eax, [sizes + rbx * 4]
cmp rax, r8
jle .check_2nd
mov r10, r9
mov r9, r8
mov r8, rax
jmp .skip_size
.check_2nd:
cmp rax, r9
jle .check_3rd
mov r10, r9
mov r9, rax
jmp .skip_size
.check_3rd:
cmp rax, r10
jle .skip_size
mov r10, rax
.skip_size:
inc rbx
jmp .scan_sizes
.multiply_result:
mov rax, r8
imul rax, r9
imul rax, r10
mov [result], rax
.done_solver:
pop r14
pop r13
pop r12
pop r11
pop r10
pop r9
pop r8
pop rbx
retThe final solution after adding helpers is shown below.
section .data
filename db "../problem/input.txt", 0
section .bss
input resb 100000
output resb 20
result resq 1
points resq 6000
edges resb 32000000
parent resd 2000
sizes resd 2000
points_cnt resq 1
edges_cnt resq 1
section .text
global _start
_start:
; Open input file
mov rax, 2
mov rdi, filename
xor rsi, rsi
xor rdx, rdx
syscall
mov rbx, rax
; Read input file
xor rax, rax
mov rdi, rbx
mov rsi, input
mov rdx, 100000
syscall
; Close the file
mov rax, 3
mov rdi, rbx
syscall
; Split the lines and process them one by one
mov r8, input
mov r9, input
mov qword [result], 0
mov qword [points_cnt], 0
reader:
movzx rax, byte [r9]
test rax, rax
je process_last_line
cmp rax, 10
je process_line
inc r9
jmp reader
process_line:
mov rdi, r8
call parser
inc r9
mov r8, r9
jmp reader
process_last_line:
cmp r8, r9
je solve_part
mov rdi, r8
call parser
solve_part:
call solver
; Print result to stdout
mov rdi, qword [result]
call print_int
; Exit the program
mov rax, 60
xor rdi, rdi
syscall
; ----------------------------------------------------------------------
; Component: Atoi (String to Int) conversion
; Args: rdi
; Ret: rax = atoi(rdi)
; Terminate if any byte is not in range [0-9]
atoi:
xor rax, rax
.convert:
movzx rsi, byte [rdi]
test rsi, rsi
je .atoi_done
cmp rsi, 10
je .atoi_done
cmp rsi, '0'
jl .atoi_done
cmp rsi, '9'
jg .atoi_done
sub rsi, '0'
imul rax, 10
add rax, rsi
inc rdi
jmp .convert
.atoi_done:
ret
; ----------------------------------------------------------------------
; Component: Print Integer
; Args: rdi
print_int:
mov rax, rdi
mov rcx, output
add rcx, 19
mov byte [rcx], 10
mov rbx, 10
.loop:
dec rcx
xor rdx, rdx
div rbx
add dl, '0'
mov [rcx], dl
test rax, rax
jnz .loop
; Calculate length
mov rdx, output
add rdx, 20
sub rdx, rcx
; Print
mov rax, 1
mov rdi, 1
mov rsi, rcx
syscall
ret
; ----------------------------------------------------------------------
; Component: Parser
; Args: rdi
; Ret: Add the current point (x, y, z) to points list
parser:
push r12
push r13
mov rax, qword [points_cnt]
imul r12, rax, 24
lea r13, [points + r12]
call atoi
mov [r13], rax
inc rdi
call atoi
mov [r13 + 8], rax
inc rdi
call atoi
mov [r13 + 16], rax
inc qword [points_cnt]
pop r13
pop r12
ret
; ----------------------------------------------------------------------
; Component: Solver
; Args: None
; Ret: DSU + Kruskal for forming circuits, update result
solver:
push rbx
push r8
push r9
push r10
push r11
push r12
push r13
push r14
mov r12, qword [points_cnt]
xor rbx, rbx
mov qword [edges_cnt], 0
mov r14, edges
.outer_loop:
cmp rbx, r12
jge .edges_done
mov r13, rbx
inc r13
.inner_loop:
cmp r13, r12
jge .inner_done
imul rax, rbx, 24
imul rcx, r13, 24
mov rdx, [points + rax]
sub rdx, [points + rcx]
imul rdx, rdx
mov r11, rdx
mov rdx, [points + rax + 8]
sub rdx, [points + rcx + 8]
imul rdx, rdx
add r11, rdx
mov rdx, [points + rax + 16]
sub rdx, [points + rcx + 16]
imul rdx, rdx
add r11, rdx
mov qword [r14], r11
mov dword [r14 + 8], ebx
mov dword [r14 + 12], r13d
add r14, 16
inc qword [edges_cnt]
inc r13
jmp .inner_loop
.inner_done:
inc rbx
jmp .outer_loop
.edges_done:
mov rdi, edges
mov rsi, qword [edges_cnt]
test rsi, rsi
jz .done_solver
dec rsi
xor rdx, rdx
mov rdx, rsi
xor rsi, rsi
call sort_edges
mov rcx, qword [points_cnt]
xor rbx, rbx
.init_dsu:
cmp rbx, rcx
jge .dsu_ready
mov dword [parent + rbx * 4], ebx
mov dword [sizes + rbx * 4], 1
inc rbx
jmp .init_dsu
.dsu_ready:
mov r14, edges
mov r12, 1000
cmp qword [edges_cnt], r12
cmovl r12, qword [edges_cnt]
xor r13, r13
.kruskal_loop:
cmp r13, r12
jge .calculate_result
movsxd rax, dword [r14 + 8]
movsxd rbx, dword [r14 + 12]
mov rdi, rax
call find_set
mov r8, rax
mov rdi, rbx
call find_set
mov r9, rax
cmp r8, r9
je .next_edge
mov dword [parent + r9 * 4], r8d
mov eax, dword [sizes + r8 * 4]
add eax, dword [sizes + r9 * 4]
mov dword [sizes + r8 * 4], eax
mov dword [sizes + r9 * 4], 0
.next_edge:
add r14, 16
inc r13
jmp .kruskal_loop
.calculate_result:
xor r8, r8
xor r9, r9
xor r10, r10
mov rcx, qword [points_cnt]
xor rbx, rbx
.scan_sizes:
cmp rbx, rcx
jge .multiply_result
mov eax, [parent + rbx * 4]
cmp rax, rbx
jne .skip_size
mov eax, [sizes + rbx * 4]
cmp rax, r8
jle .check_2nd
mov r10, r9
mov r9, r8
mov r8, rax
jmp .skip_size
.check_2nd:
cmp rax, r9
jle .check_3rd
mov r10, r9
mov r9, rax
jmp .skip_size
.check_3rd:
cmp rax, r10
jle .skip_size
mov r10, rax
.skip_size:
inc rbx
jmp .scan_sizes
.multiply_result:
mov rax, r8
imul rax, r9
imul rax, r10
mov [result], rax
.done_solver:
pop r14
pop r13
pop r12
pop r11
pop r10
pop r9
pop r8
pop rbx
ret
; ----------------------------------------------------------------------
; Component: Find set
; Args: rdi
; Ret: rax = index of root
find_set:
movsxd rax, dword [parent + rdi * 4]
cmp rax, rdi
je .found
push rdi
mov rdi, rax
call find_set
pop rdi
mov dword [parent + rdi * 4], eax
.found:
ret
; ----------------------------------------------------------------------
; Component: Sort edges
; Args: rdi, rsi, rdx
; Ret: Quicksort to sort edges
sort_edges:
cmp rsi, rdx
jge .done_sort_edges
push rbx
push r8
push r9
push r10
push r11
push r12
push r13
push r14
push r15
mov r12, rsi
mov r13, rdx
imul rbx, rdx, 16
add rbx, rdi
mov r14, [rbx]
mov rax, rsi
dec rax
mov rcx, rsi
.partition_loop:
cmp rcx, r13
jge .partition_end
imul r15, rcx, 16
add r15, rdi
mov r8, [r15]
cmp r8, r14
jge .next_j
inc rax
imul r9, rax, 16
add r9, rdi
mov r10, [r9]
mov r11, [r9 + 8]
mov r8, [r15]
push rbx
mov rbx, [r15 + 8]
mov [r9], r8
mov [r9 + 8], rbx
mov [r15], r10
mov [r15 + 8], r11
pop rbx
.next_j:
inc rcx
jmp .partition_loop
.partition_end:
inc rax
imul r9, rax, 16
add r9, rdi
mov r10, [r9]
mov r11, [r9 + 8]
mov r8, [rbx]
mov r15, [rbx + 8]
mov [r9], r8
mov [r9 + 8], r15
mov [rbx], r10
mov [rbx + 8], r11
push rax
push r13
mov rdx, rax
dec rdx
call sort_edges
pop r13
pop rax
mov rsi, rax
inc rsi
mov rdx, r13
call sort_edges
pop r15
pop r14
pop r13
pop r12
pop r11
pop r10
pop r9
pop r8
pop rbx
.done_sort_edges:
retThe sizes of the three largest circuits, given that 1000 pairs of junction boxes which are closest together are connected, produce a product of 98696.
Part 2
The Elves were right; they definitely don't have enough extension cables. You'll need to keep connecting junction boxes together until they're all in one large circuit.
Continuing the above example, the first connection which causes all of the junction boxes to form a single circuit is between the junction boxes at 216,146,977 and 117,168,530. The Elves need to know how far those junction boxes are from the wall so they can pick the right extension cable; multiplying the X coordinates of those two junction boxes (216 and 117) produces 25272.
Continue connecting the closest unconnected pairs of junction boxes together until they're all in the same circuit. What do you get if you multiply together the X coordinates of the last two junction boxes you need to connect?In this second part, we now have to keep connecting junction boxes until everythin is in one big circuit, and get the product of the X coordinates from the last two junction boxes that need to be connected to form the final circuit.
Now, instead of restricting the maximum amount of pairs to 1000, we start by defining a counter that is equal to the number of junction boxes. This counter implies that we currently have that many disconnected circuits.
Recall the merging logic, given that the edge spans from A to B, we have to:
- Find the root of
A’s group, call itroot_A. - Find the root of
B’s group, call itroot_B. - If
root_A != root_B, union them by turningroot_Binto one of the childrens ofroot_A, while adding the size ofB’s group to the size ofA’s group. - Decrement the counter (because we just merged two circuits together - the total amount of disconnected circuits is reduced by one).
Upon reaching counter == 1, we successfully connected all circuits together to form one single circuit. If the last two points are C and D, our result is simply the product of X coordinates of C and D.
We update the solver component to adapt to the changes in the problem.
; ----------------------------------------------------------------------
; Component: Solver
; Args: None
; Ret: DSU + Kruskal for forming circuits, update result
solver:
push rbx
push r8
push r9
push r10
push r11
push r12
push r13
push r14
mov r12, qword [points_cnt]
xor rbx, rbx
mov qword [edges_cnt], 0
mov r14, edges
.outer_loop:
cmp rbx, r12
jge .edges_done
mov r13, rbx
inc r13
.inner_loop:
cmp r13, r12
jge .inner_done
imul rax, rbx, 24
imul rcx, r13, 24
mov rdx, [points + rax]
sub rdx, [points + rcx]
imul rdx, rdx
mov r11, rdx
mov rdx, [points + rax + 8]
sub rdx, [points + rcx + 8]
imul rdx, rdx
add r11, rdx
mov rdx, [points + rax + 16]
sub rdx, [points + rcx + 16]
imul rdx, rdx
add r11, rdx
mov qword [r14], r11
mov dword [r14 + 8], ebx
mov dword [r14 + 12], r13d
add r14, 16
inc qword [edges_cnt]
inc r13
jmp .inner_loop
.inner_done:
inc rbx
jmp .outer_loop
.edges_done:
mov rdi, edges
mov rsi, qword [edges_cnt]
test rsi, rsi
jz .done_solver
dec rsi
xor rdx, rdx
mov rdx, rsi
xor rsi, rsi
call sort_edges
mov rcx, qword [points_cnt]
xor rbx, rbx
.init_dsu:
cmp rbx, rcx
jge .dsu_ready
mov dword [parent + rbx * 4], ebx
mov dword [sizes + rbx * 4], 1
inc rbx
jmp .init_dsu
.dsu_ready:
mov r14, edges
mov r12, 1000
cmp qword [edges_cnt], r12
cmovl r12, qword [edges_cnt]
mov r12, qword [edges_cnt]
mov r15, qword [points_cnt]
xor r13, r13
.kruskal_loop:
cmp r13, r12
jge .calculate_result
jge .done_solver
movsxd rax, dword [r14 + 8]
movsxd rbx, dword [r14 + 12]
mov rdi, rax
call find_set
mov r8, rax
mov rdi, rbx
call find_set
mov r9, rax
cmp r8, r9
je .next_edge
mov dword [parent + r9 * 4], r8d
mov eax, dword [sizes + r8 * 4]
add eax, dword [sizes + r9 * 4]
mov dword [sizes + r8 * 4], eax
mov dword [sizes + r9 * 4], 0
dec r15
cmp r15, 1
je .calculate_result
.next_edge:
add r14, 16
inc r13
jmp .kruskal_loop
.calculate_result:
xor r8, r8
xor r9, r9
xor r10, r10
mov rcx, qword [points_cnt]
xor rbx, rbx
.scan_sizes:
cmp rbx, rcx
jge .multiply_result
mov eax, [parent + rbx * 4]
cmp rax, rbx
jne .skip_size
mov eax, [sizes + rbx * 4]
cmp rax, r8
jle .check_2nd
mov r10, r9
mov r9, r8
mov r8, rax
jmp .skip_size
.check_2nd:
cmp rax, r9
jle .check_3rd
mov r10, r9
mov r9, rax
jmp .skip_size
.check_3rd:
cmp rax, r10
jle .skip_size
mov r10, rax
.skip_size:
inc rbx
jmp .scan_sizes
.multiply_result:
movsxd rax, dword [r14 + 8]
movsxd rbx, dword [r14 + 12]
imul rsi, rax, 24
mov r8, [points + rsi]
imul rsi, rbx, 24
mov r9, [points + rsi]
mov rax, r8
imul rax, r9
imul rax, r10
mov [result], rax
.done_solver:
pop r14
pop r13
pop r12
pop r11
pop r10
pop r9
pop r8
pop rbx
retAnd finally, the full solver for the second part:
section .data
filename db "../problem/input.txt", 0
section .bss
input resb 100000
output resb 20
result resq 1
points resq 6000
edges resb 32000000
parent resd 2000
sizes resd 2000
points_cnt resq 1
edges_cnt resq 1
section .text
global _start
_start:
; Open input file
mov rax, 2
mov rdi, filename
xor rsi, rsi
xor rdx, rdx
syscall
mov rbx, rax
; Read input file
xor rax, rax
mov rdi, rbx
mov rsi, input
mov rdx, 100000
syscall
; Close the file
mov rax, 3
mov rdi, rbx
syscall
; Split the lines and process them one by one
mov r8, input
mov r9, input
mov qword [result], 0
mov qword [points_cnt], 0
reader:
movzx rax, byte [r9]
test rax, rax
je process_last_line
cmp rax, 10
je process_line
inc r9
jmp reader
process_line:
mov rdi, r8
call parser
inc r9
mov r8, r9
jmp reader
process_last_line:
cmp r8, r9
je solve_part
mov rdi, r8
call parser
solve_part:
call solver
; Print result to stdout
mov rdi, qword [result]
call print_int
; Exit the program
mov rax, 60
xor rdi, rdi
syscall
; ----------------------------------------------------------------------
; Component: Atoi (String to Int) conversion
; Args: rdi
; Ret: rax = atoi(rdi)
; Terminate if any byte is not in range [0-9]
atoi:
xor rax, rax
.convert:
movzx rsi, byte [rdi]
test rsi, rsi
je .atoi_done
cmp rsi, 10
je .atoi_done
cmp rsi, '0'
jl .atoi_done
cmp rsi, '9'
jg .atoi_done
sub rsi, '0'
imul rax, 10
add rax, rsi
inc rdi
jmp .convert
.atoi_done:
ret
; ----------------------------------------------------------------------
; Component: Print Integer
; Args: rdi
print_int:
mov rax, rdi
mov rcx, output
add rcx, 19
mov byte [rcx], 10
mov rbx, 10
.loop:
dec rcx
xor rdx, rdx
div rbx
add dl, '0'
mov [rcx], dl
test rax, rax
jnz .loop
; Calculate length
mov rdx, output
add rdx, 20
sub rdx, rcx
; Print
mov rax, 1
mov rdi, 1
mov rsi, rcx
syscall
ret
; ----------------------------------------------------------------------
; Component: Parser
; Args: rdi
; Ret: Add the current point (x, y, z) to points list
parser:
push r12
push r13
mov rax, qword [points_cnt]
imul r12, rax, 24
lea r13, [points + r12]
call atoi
mov [r13], rax
inc rdi
call atoi
mov [r13 + 8], rax
inc rdi
call atoi
mov [r13 + 16], rax
inc qword [points_cnt]
pop r13
pop r12
ret
; ----------------------------------------------------------------------
; Component: Solver
; Args: None
; Ret: DSU + Kruskal for forming circuits, update result
solver:
push rbx
push r8
push r9
push r10
push r11
push r12
push r13
push r14
mov r12, qword [points_cnt]
xor rbx, rbx
mov qword [edges_cnt], 0
mov r14, edges
.outer_loop:
cmp rbx, r12
jge .edges_done
mov r13, rbx
inc r13
.inner_loop:
cmp r13, r12
jge .inner_done
imul rax, rbx, 24
imul rcx, r13, 24
mov rdx, [points + rax]
sub rdx, [points + rcx]
imul rdx, rdx
mov r11, rdx
mov rdx, [points + rax + 8]
sub rdx, [points + rcx + 8]
imul rdx, rdx
add r11, rdx
mov rdx, [points + rax + 16]
sub rdx, [points + rcx + 16]
imul rdx, rdx
add r11, rdx
mov qword [r14], r11
mov dword [r14 + 8], ebx
mov dword [r14 + 12], r13d
add r14, 16
inc qword [edges_cnt]
inc r13
jmp .inner_loop
.inner_done:
inc rbx
jmp .outer_loop
.edges_done:
mov rdi, edges
mov rsi, qword [edges_cnt]
test rsi, rsi
jz .done_solver
dec rsi
xor rdx, rdx
mov rdx, rsi
xor rsi, rsi
call sort_edges
mov rcx, qword [points_cnt]
xor rbx, rbx
.init_dsu:
cmp rbx, rcx
jge .dsu_ready
mov dword [parent + rbx * 4], ebx
mov dword [sizes + rbx * 4], 1
inc rbx
jmp .init_dsu
.dsu_ready:
mov r14, edges
mov r12, qword [edges_cnt]
mov r15, qword [points_cnt]
xor r13, r13
.kruskal_loop:
cmp r13, r12
jge .done_solver
movsxd rax, dword [r14 + 8]
movsxd rbx, dword [r14 + 12]
mov rdi, rax
call find_set
mov r8, rax
mov rdi, rbx
call find_set
mov r9, rax
cmp r8, r9
je .next_edge
mov dword [parent + r9 * 4], r8d
dec r15
cmp r15, 1
je .calculate_result
.next_edge:
add r14, 16
inc r13
jmp .kruskal_loop
.calculate_result:
movsxd rax, dword [r14 + 8]
movsxd rbx, dword [r14 + 12]
imul rsi, rax, 24
mov r8, [points + rsi]
imul rsi, rbx, 24
mov r9, [points + rsi]
mov rax, r8
imul rax, r9
mov [result], rax
.done_solver:
pop r14
pop r13
pop r12
pop r11
pop r10
pop r9
pop r8
pop rbx
ret
; ----------------------------------------------------------------------
; Component: Find set
; Args: rdi
; Ret: rax = index of root
find_set:
movsxd rax, dword [parent + rdi * 4]
cmp rax, rdi
je .found
push rdi
mov rdi, rax
call find_set
pop rdi
mov dword [parent + rdi * 4], eax
.found:
ret
; ----------------------------------------------------------------------
; Component: Sort edges
; Args: rdi, rsi, rdx
; Ret: Quicksort to sort edges
sort_edges:
cmp rsi, rdx
jge .done_sort_edges
push rbx
push r8
push r9
push r10
push r11
push r12
push r13
push r14
push r15
mov r12, rsi
mov r13, rdx
imul rbx, rdx, 16
add rbx, rdi
mov r14, [rbx]
mov rax, rsi
dec rax
mov rcx, rsi
.partition_loop:
cmp rcx, r13
jge .partition_end
imul r15, rcx, 16
add r15, rdi
mov r8, [r15]
cmp r8, r14
jge .next_j
inc rax
imul r9, rax, 16
add r9, rdi
mov r10, [r9]
mov r11, [r9 + 8]
mov r8, [r15]
push rbx
mov rbx, [r15 + 8]
mov [r9], r8
mov [r9 + 8], rbx
mov [r15], r10
mov [r15 + 8], r11
pop rbx
.next_j:
inc rcx
jmp .partition_loop
.partition_end:
inc rax
imul r9, rax, 16
add r9, rdi
mov r10, [r9]
mov r11, [r9 + 8]
mov r8, [rbx]
mov r15, [rbx + 8]
mov [r9], r8
mov [r9 + 8], r15
mov [rbx], r10
mov [rbx + 8], r11
push rax
push r13
mov rdx, rax
dec rdx
call sort_edges
pop r13
pop rax
mov rsi, rax
inc rsi
mov rdx, r13
call sort_edges
pop r15
pop r14
pop r13
pop r12
pop r11
pop r10
pop r9
pop r8
pop rbx
.done_sort_edges:
retWhat do we get if we multiply together the X coordinates of the last two junction boxes we need to connect? We get 2245203960.