# Advent of Code 2017, Day 14: Disk Defragmentation

## Part A

On Day 14 we are trying to help disk defragmentation. This task requires to complete Day 10 and have knot hashing algorithm implemented.

Here is the solution:

``````key = "flqrgnkx"

class KnotHashing
class << self
def reverse(list, from, length)
to = from + length - 1
wrap = list.size - to

if wrap <= 0
wrap -= 1
from = from + wrap
list.rotate!(-wrap)
list[from..] = list[from..].reverse
list.rotate!(wrap)
else
list[from..to] = list[from..to].reverse
end

list
end

def mix(list, lengths, rounds)
start = 0
offset = 0

rounds.times do
lengths.each do |length|
list = reverse(list, start, length)
start = (start + length + offset) % list.size
offset += 1
end
end

list
end

def densify(list)
index = 0
result = []

while index < list.size
result.push(list[index, 16].reduce(:^))
index += 16
end

result.map do |value|
value.to_s(16).rjust(2, "0")
end.join
end

def hash(input)
lengths = input.strip.split("").map(&:ord) + [17, 31, 73, 47, 23]
list = (0..255).to_a
list = mix(list, lengths, 64)
densify(list)
end
end
end

used = 0
128.times do |row|
hash = KnotHashing.hash("#{key}-#{row}")
hash.each_char do |char|
bits = char.to_i(16).to_s(2)
used += bits.split("").select { |bit| bit == "1" }.size
end
end

puts used
``````

When we have hashing algorithm, the solution is pretty trivial. We just generate hash for 128 rows using given key and then we convert each hash into bits and count number of ones.

## Part B

Second part is more complicated. If we convert each row into bits and plot it like 2d map we can have something like this:

``````##.#.#..-->
.#.#.#.#
....#.#.
#.#.##.#
.##.#...
##..#..#
.#...#..
##.#.##.-->
|      |
V      V
``````

Hash characters represent 1s and dots represent 0s. Some filled cells are connected and together they create a region. We can and put a number on each region and have something like this:

``````11.2.3..-->
.1.2.3.4
....5.6.
7.8.55.9
.88.5...
88..5..8
.8...8..
88.8.88.-->
|      |
V      V
``````

Our goal is to output how many distinct regions are there.

Here is the solution:

``````key = "flqrgnkx"

class KnotHasing
class << self
def reverse(list, from, length)
to = from + length - 1
wrap = list.size - to

if wrap <= 0
wrap -= 1
from = from + wrap
list.rotate!(-wrap)
list[from..] = list[from..].reverse
list.rotate!(wrap)
else
list[from..to] = list[from..to].reverse
end

list
end

def mix(list, lengths, rounds)
start = 0
offset = 0

rounds.times do
lengths.each do |length|
list = reverse(list, start, length)
start = (start + length + offset) % list.size
offset += 1
end
end

list
end

def densify(list)
index = 0
result = []

while index < list.size
result.push(list[index, 16].reduce(:^))
index += 16
end

result.map do |value|
value.to_s(16).rjust(2, "0")
end.join
end

def hash(input)
lengths = input.strip.split("").map(&:ord) + [17, 31, 73, 47, 23]
list = (0..255).to_a
list = mix(list, lengths, 64)
densify(list)
end
end
end

map = (0..127).map do |row|
hash = KnotHasing.hash("#{key}-#{row}")
bits = hash.chars.map do |char|
char.to_i(16).to_s(2).rjust(4, "0")
end

bits.join.split("").map(&:to_i)
end

@p = []
@rank = []

def make_set(x)
@p[x] = x
@rank[x] = 0
end

def union(x, y)
end

if @rank[x] > @rank[y]
@p[y] = x
else
@p[x] = y
if @rank[x] == @rank[y]
@rank[y] += 1
end
end
end

def find(x)
if x != @p[x]
@p[x] = find(@p[x])
end

@p[x]
end

(128 * 128).times do |number|
next if map[number / 128][number % 128] == 0

make_set(number)

neighbors = []
neighbors.push(number - 128) if number > 128
neighbors.push(number - 1) if number % 128 > 0
neighbors.select { |neighbor| @p[neighbor] }.each do |neighbor|
union(number, neighbor)
end
end

counts = {}

(128 * 128).times do |number|
if @p[number]
counts[find(number)] ||= 0
counts[find(number)] += 1
end
end

puts counts.keys.size
``````

I’ve already described data structure for disjoint sets already in solution for Day 12. We can use the same approach here. Each point on the map initially represents the set with just this point. We can then iterate over all the points, check their neighbors and if they are also filled we can union both sets.

In the end we just need to count the number of remaining distinct sets.