Robert Mion

Posted on Jul 30, 2022

Knot Hash

#adventofcode #algorithms #computerscience #programming

Advent of Code 2017 Day 10

Why not Day 14?

Day 14 is a hashing puzzle
It references today's puzzle at the end of an important sentence: the state of the grid is tracked by the bits in a sequence of knot hashes
After re-reading the instructions for Day 14 several times, I felt lost as to what to do next
I thought it would be best to attempt and hopefully solve Day 10 first

Part 1

Going in circles again
Stumped at first, then an animation to clarify
Writing the full algorithm

Going in circles again

A list of numbers
Where the first and last numbers are linked (e.g. wrapping)
A number of iterations
Where the numbers must change according to some rules
A reversal of a subset of numbers
Where the indices of those numbers is likely to overlap the last and first several numbers in the list

Stumped at first, then an animation to clarify

Seeing this illustration within the instructions confused and intimidated me:

2 1) 0 ([3] 4
...
4 3) 0 ([1] 2

The subset of numbers that must be reversed overlaps the bookends of the list

I thought to myself:

How would I do this with slice() or concat() as part of an array mutation?

A bit of head-scratching later, and I had what I hope is an epiphany for a fairly naive approach:

Reversing the order of the correct values in the list

2 1) 0 ([3] 4

Indices
0 1  2   3  4

Indices that must be reversed, in order
3 % 5,  4 % 5,  5 % 5,  6 % 5
    3       4       0       1

    3  4  0  1

Values at those indices
    3  4  2  1

New values, in reversed order
    1  2  4  3

Updating each index with its new value
3  4  0  1
|  |  |  |
1  2  4  3

list[3] = 1
list[4] = 2
list[0] = 4
list[1] = 3

Resulting in
4 3) 0 ([1] 2

Updating the current position

Per the instructions:

The current position moves forward by the length plus the skip size

For the example input:

input_length: 5

Initially:
length = 3, position = 0, skip = 0

New position:
(position + (length + skip)) % input_length
(0 + (3 + 0)) % 5
(0 + 3) % 5
3 % 5
3

Next:
length = 4, position = 3, skip = 1

New position:
(position + (length + skip)) % input_length
(3 + (4 + 1)) % 5
(3 + 5) % 5
8 % 5
3

Next:
length = 1, position = 3, skip = 2

New position:
(position + (length + skip)) % input_length
(3 + (1 + 2)) % 5
(3 + 3) % 5
6 % 5
1

Next:
length = 5, position = 1, skip = 3

New position:
(position + (length + skip)) % input_length
(1 + (5 + 3)) % 5
(1 + 8) % 5
9 % 5
4

I think I have a winning formula!

I made this animation to ensure I fully understood how I expect this algorithm to work:

Writing the full algorithm

Create the list of lengths:
  Split the input at each comma to create a list of strings
  Coerce each string to a number

Create the list of 256 numbers: 0-255
  Create an array with 256 elements, where each element's value is the index of that element

Set position and skip to 0

For each number in lengths
  Create a list of indices:
    Create an array with a length equal to the current length
      And set each item's value to the remainder of:
        - The current position
        - Plus the index of the item
        - Divided by 256
  Create a list of values:
    For each number in the list of indices
      Return the number at that index in the list of 256 numbers
  Reverse the list of numbers
  For each number in the list of indices
    Update the number in the list of 256 numbers at the location identified by the current item so that it becomes the number in the list values at the location of the index of the current item in the list of indices
  Update the current position to the remainder of:
    - The current position
    - Plus the sum of the current length and skip
    - Divided by 256
  Increment skip by 1

That seems like a lot.

Surprisingly, my algorithm is just over 10 lines of code.

As for the results:

It works on the example input and string length!
It works on my puzzle input and string length!

Part 2

This is what I need to attempt Day 14!
Three parts?!
Testing my algorithm on the examples and my puzzle input

Here's what I need to attempt Day 14!

I'm glad I didn't spend too much time scratching my head confused by Day 14's puzzle
Time to read all these new instructions and hope that I write an algorithm that generates a correct answer...so I can return to Day 14 and at least attempt it!

Three parts?!

Create the actual list of lengths
64 rounds; spare hash; dense hash;
Hexadecimal conversion

Create the actual list of lengths

The puzzle input is no longer numbers
It is a string
From which, numbers must be derived
Using ASCII codes

Thankfully, JavaScript makes it easy to get any character's ASCII code:

String.CharCodeAt(0)

Thus, my algorithm for getting the lengths from my puzzle input is:

Split the input at each character into an array of characters
For each character
  Replace the character with it's character code

Then, the cherry on top:

add the following lengths to the end of the sequence: 17, 31, 73, 47, 23

No problem, with help from concat():

parsed_list_of_numbers.concat([17, 31, 73, 47, 23])

64 rounds; spare hash; dense hash;

64 rounds:

Do 64 times:
  Part 1's algorithm

That may have been the easiest part...assuming I understood it correctly:

Don't reset current position or skips
Go through the entire list of lengths 64 times
Continually update the same array of 256 numbers: 0-255

Spare hash:

The numbers 0-255 in some order: got it!

Reduce these to a list of only 16 numbers called the dense hash

How?

Use numeric bitwise XOR to combine each consecutive block of 16 numbers in the sparse hash

Yikes, bitwise operators. I recall using them in one of the Intcode computer puzzles.

Thankfully, the Mozilla Developer Network (MDN) offers an understandable definition:

The bitwise XOR operator (^) returns a 1 in each bit position for which the corresponding bits of either but not both operands are 1s.

Along with an example:

const a = 5;        // 00000000000000000000000000000101
const b = 3;        // 00000000000000000000000000000011

console.log(a ^ b); // 00000000000000000000000000000110
// expected output: 6

That makes sense, and seems like the bitwise XOR operator works just like other operators: + - * % / || &&

Back to the task:

Create a dense hash list that starts empty
For each subsequent group of 16 numbers in the sparse hash
  Accumulate a decimal number resulting from the continual combination of each number using the bitwise XOR operator
  Add the resulting integer to the dense hash list

My JavaScript algorithm:

let dense = []
for (let i = 0; i < 256; i += 16) {
  dense.push(
    sparse_hash
      .slice(i, i + 16)
      .reduce(
        (accumulator, current) => accumulator ^ current
      )
  )
}

Hexadecimal conversion

First, a google search:

[programming language] convert decimal to hex

In my case, the programming language is JavaScript.

And the Stack Overflow answer I found is:

hex_string = some_number.toString(16);

Wonderful!

I still need to ensure that any hex strings I generate are two characters in length.

Thankfully, I am very familiar with the method that helps me do that: padStart()

two_digit_hex_string = someNumber.toString(16).padStart(2,'0')

2 is the maximum length of the string
0 is the character used to make the string the maximum length, if necessary

Thus, my algorithm is:

For each number in the dense hash
  Convert it to a hexadecimal string
    Prepend the string with a 0 if it is a single character

Lastly, I need to concatenate the resulting hex string elements into a single string.

For each 2-character hex string
  Accumulate a string that stitches the current value onto the accumulated string thus far

Testing my algorithm on the examples and my puzzle input

empty string: success!
AoC 2017: success!
1,2,3: success!
1,2,4: success!
My puzzle input: SUCCESS!

I did it!!

I solved both parts!
I made a GIF to help me strategize how I might write a working algorithm for Part 1
I understood the tasks well enough to write an algorithm for Part 2 without help, or to search for a working algorithmic tactic!
I am fully prepared to return to Day 14 and attempt to solve Part 1!

And now, back to Day 14!

DEV Community