On Day 12 we are working with disjoint sets. Our input looks like this:
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
Numbers represent program ids. The input file defines which programs are connected via pipes. Our goal is to output how many programs are in the group 0.
Because each number can belong to just one set we have disjoint sets here. In the beginning each number has its own set with just one element. We can read our input and combine sets as specified in the input. There is a perfect structure for representing disjoint sets. I know this data structure by the name Find & Union.
We will use the simpler version with just one array @p that will hold the parent value. The value will be used for indexing, so for number 5 it’s parent will be stored at @p[5]. In the beginning each value of this array will be equal to its index. This means that each number is in its own set.
If we want to combine two sets need to pick one number as parent and then set it as. Let’s see an example given our input file.
In the beginning we have 7 numbers from 0 to 6, so our @p array will look like this [0, 1, 2, 3, 4, 5, 6]
First line of our input is 0 <-> 2, so we need to join set containing number 0 with set containing number 2. After this joining we will have @p looking like this [0, 1, 0, 3, 4, 5, 6].
Now if join 2 and 6 we will have [0, 1, 0, 3, 4, 5, 2]
If we want to find what is the parent of given number we can just look at @p and then follow references until we reach the value that is the same as index. If we check 6, it’s parent is 2. So we check 2 and it also has a parent 0. Finally parent of 0 is 0 so we stop here.
Here is the solution in Ruby:
data = File.readlines("12.txt", chomp: true)
size = data.size
@p = []
def make_set(x)
@p[x] = x
end
def union(x, y)
link(find(x), find(y))
end
def link(x, y)
@p[y] = x
end
def find(x)
if x != @p[x]
@p[x] = find(@p[x])
end
@p[x]
end
size.times do |number|
make_set(number)
end
data.each do |line|
parts = line.split(" <-> ")
number = parts[0].to_i
neighbors = parts[1].split(",").map { |item| item.strip.to_i }
neighbors.each do |neighbor|
union(number, neighbor)
end
end
root = find(0)
count = 0
size.times do |number|
if find(number) == root
count += 1
end
end
puts count
find method is used to find the top-level value that is the parent for all numbers in the given set. It has certain optimization implemented called path compression. It is used to remove long chains of parents and link child numbers with one top-level parent directly.
For example we can have all numbers belonging to the same set, but with long parent chains like this [0, 0, 1, 2, 3, 4, 5]. You can see that all numbers belong to one set, but 1 is connected to 0, 2 is connected to 1, 3 to 2, 4 to 3, 5 to 4 and 6 to 5. To find top-level parent of 6 find method will need to follow this long path and scan the whole table. Path compression after following such long path is updating all numbers to link to the top-level element. So after calling it for 6 we would have the following [0, 0, 0, 0, 0, 0, 0].
Our solution is using Find & Union data structure. First we create all sets, each containing just one number. Then we read our input and we union sets as specified. Finally we find the root for 0 and count how many sets have the same root value, meaning that belong to the same set.
In the second part we need to output how many sets there are after joining everything. Here is the solution:
require "debug"
require "set"
data = File.readlines("12.txt", chomp: true)
size = data.size
@p = []
def make_set(x)
@p[x] = x
end
def union(x, y)
link(find(x), find(y))
end
def link(x, y)
@p[y] = x
end
def find(x)
if x != @p[x]
@p[x] = find(@p[x])
end
@p[x]
end
size.times do |number|
make_set(number)
end
data.each do |line|
parts = line.split(" <-> ")
number = parts[0].to_i
neighbors = parts[1].split(",").map { |item| item.strip.to_i }
neighbors.each do |neighbor|
union(number, neighbor)
end
end
count = (0...size).map do |number|
find(number)
end.uniq.size
puts count