# Advent of Code 2017, Day 10: Knot Hash

#ruby #advent of code 2017

On Day 10 we are implementing knot hashing. This algorithm starts with a list of numbers from 0 to 255, a current position which begins at 0 and skip size which also begins at 0. Additionally we have a list of lengths, which is given as our input.

The knot hashing algorithm works like this:

• Reverse the order of that length of elements in the list, starting with the element at the current position.
• Move the current position forward by that length plus the skip size.
• Increase the skip size by one.

The list is circular, so if your reverse operation goes beyond the list it should also consider elements at the front of the list.

In Ruby we can utilize Array’s `rotate` method to move all necessary elements from the from to the end of the list, do our operations and then rotate back.

Below solution is doing exactly that:

``````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 parse_input(filename)
end

list = (0..255).to_a
lengths = parse_input("10.txt")
start = 0
offset = 0

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

puts list[0..1].reduce(:*)
``````

## Part B

The second part builds on the foundation from first part. There are couple of additions. First we need to add additional values to our initial lengths list. Then we need to repeat knot hashing 64 times. And finally we need to XOR all values in each 16 character block. This will leave us with 16 values only which we should convert to hexadecimal final number that will be our hash.

Here is the solution:

``````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 parse_input(filename)
File.read(filename).strip.split("").map(&:ord) + [17, 31, 73, 47, 23]
end

list = (0..255).to_a
lengths = parse_input("10.txt")
list = mix(list, lengths, 64)
puts densify(list)
``````

`reverse` method is the same as in the first part. `mix` method is applying `reverse` multiple times and `densify` is reducing the larger list by XOR-ing 16 values blocks and outputing final hash.