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.
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)
link(find(x), find(y))
end
def link(x, y)
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.