Advent of Code 2017, Day 10: Knot Hash

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)
  File.read(filename).strip.split(",").map(&:to_i)
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.