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
Part 1
Provided the following diagram with the beam moving down from the S, how many times will the beam be split?
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,689I got as far as generating an array of distances and indexes for use with generating the circuits but everything I tried from there did not work. Eventually I allowed myself to take hints form other peoples solutions.
One solution I found used a union find algorithm. This seemed useful to understand better so I spent some time learning about how this works and how to use it.
After creating an array distances that has (distance, i, i+j+1) where i and j are both indexes for lines in input the following for is used to create the circuits.
def find(x):
# print(x)
while x != parent[x]:
x = parent[x]
return x
def union(a,b):
a, b = find(a), find(b)
if a == b:
return 0
parent[b] = a
size[a] += size[b]
return size[a]
for _, a, b in distances[:1000]:
union(a,b)Part 2
For this part the answer is the result of multiplying together the X coordinates of the last two junction boxes you need to connect. This removes the 1000 connection limit from the first part so we just need to do about the same thing making sure to break out of the while loop having capture the last two points so we can multiply the X coordinates of each for the answer.
while True:
_, a, b = distances[k]
if union(a, b) == line_count:
break
k += 1
x1 = int(Lines[a].split(',')[0])
x2 = int(Lines[b].split(',')[0])Once I got past the knowledge gap of the first part the second was fairly easy.
Comments
This blog uses a Mastodon and webmentions for comments. You can comment by replying on Mastodon/ActivityPub/Fediverse account or webmention.