Day 8: Playground

Note: If you’re attempting to read this as a Fediverse post, you might find it rather confusing. I recommend using a web browser to read it properly, following this link.

The challenge

We have a list of points x₁, x₂, … , xₙ in 3-dimensional space and order them in pairs P₁, P₂, … by ascending distance in space. We take the first 1000 and start to successively build clusters, in the following way:

1. The first cluster is the first pair.

2. We now take the next pair. If both of its points are already elements of a single cluster, we continue with the next pair.

3. If one point is contained in one cluster and the other in another, we join the two clusters together, thus making a single cluster out of 2.

4. If only one point is already an element of a cluster, we add the other one to the cluster, thus incrementing its size by 1.

5. If none of the two points isn’t an element of any cluster, the pair becomes a new cluster.

6. We continue until there is no pair left.

We now multiply the sizes of the three biggest clusters, which is the solution.

The idea

The first thing we do, is to build the ordered list @d of distances and pairs.

We follow the instructions from above, first by annotating which points are connected with each other in the Perl hash (dictionary) %c. Keys of the hash are the indices i of points. The values are others hashes with their keys being the indices of points x_i is connected to. This means: The keys of the hash corresponding to i is the cluster x_i is part of.

Once, we’re finished, we make sure, we build a set @c of disjoint clusters and order them by descending size, and we’re done.

Now that I look at it, I realise: This is definitely not the most efficient way of doing the whole thing. It still worked, so here is the code:

The updated challenge:

Having the full ordered list (not only 1000 items) of pairs, we build clusters as above until all clusters are connected. We take the last necessary pair, add their respective x-coordinates to get our solution.

The updated idea:

This is actually easier than the first part. We just have to keep in memory the very last pair we connect to a cluster. This most has certainly room for optimization, as we can stop, once a cluster has the same size as whole set of points. Still, it worked, so here is the code: