AoC 2017 Day 10: Knot Cool

Source: Knot Hash

Part 1: Starting with a list of the numbers from 1 to n and a list of lengths (as input):

  1. Initialize current_position and skip_size to 0
  2. For each length element in the lengths list:
  3. Reverse the first length elements of the list (starting at current_position)
  4. Move forward by length plus skip_size
  5. Increment skip_size by 1

After applying the above algorithm, what is the product of the first two elements in the list (from the original first position, not the current_position)?

Okay. That’s kind of a bizarre algorithm. Let’s turn it into code:

def twist(rope, lengths):
    '''Twist the rope based on lengths; repeating a given number of times.'''

    origin = 0
    skip = -1

    for length in lengths:
        skip += 1
        skip %= len(rope)

        # Reverse the first n elements; move the current position forward over that length
        rope = rope[length:] + list(reversed(rope[:length]))

        # Move the current position forward by the skip size
        rope = rope[skip:] + rope[:skip]

        # Keep track of how much we rotatedso we can rotate it back
        origin -= length + skip

    # Rotate it back so the original 'first' position is first again
    origin %= len(rope)
    rope = rope[origin:] + rope[:origin]

    return rope

Which lets us directly calculate the first part:

lib.add_argument('--marks', type = int, required = True, help = 'The number of marks on the string')

lengths = [int(el) for line in lib.input() for el in line.split(',')]

rope = list(range(lib.param('marks')))
rope = twist(rope, lengths)

print(rope[0] * rope[1])

Part 2: Add the ability to repeat the above process a given number of rounds.

Next, treat the input as if it were ASCII, rather than numbers (so that 1,2,3 is actually the sequence: [49, 44, 50, 44, 51]) and add the ability to add an arbitrary sequence of bytes to the end of the sequence.

Once you have the final ordering of numbers, convert them to a hex value as so:

  1. Split the output into groups of 16 bytes each, apply xor to the entire group of 16 to get a single byte.
  2. Convert each byte into a hex value.

Calculate the hash of your input using 16 rounds and the extra bytes [17, 31, 73, 47, 23].

This is by far the craziest jump of functionality between part 1 and part 2 I’ve seen in any of the Advent of Code puzzles thus far… Let’s try it.

First, we want to extend the twist function to run multiple rounds:

def twist(rope, lengths, rounds = 1):
    '''Twist the rope based on lengths; repeating a given number of times.'''

    origin = 0
    skip = -1

    for round in range(rounds):
        for length in lengths:
            skip += 1
            skip %= len(rope)

            # Reverse the first n elements; move the current position forward over that length
            rope = rope[length:] + list(reversed(rope[:length]))

            # Move the current position forward by the skip size
            rope = rope[skip:] + rope[:skip]

            # Keep track of how much we rotatedso we can rotate it back
            origin -= length + skip

    # Rotate it back so the original 'first' position is first again
    origin %= len(rope)
    rope = rope[origin:] + rope[:origin]

    return rope

That was easy enough. Next, we want to upgrade how we’re doing input to support ASCII and additional bytes:

lib.add_argument('--ascii-key', nargs = '?', const = True, help = 'Interpret lengths as ASCII instead of the default')
lib.add_argument('--additional-key-bytes', type = int, nargs = '+', help = 'Additional args to add to the end of the length list')

if lib.param('ascii_key'):
    if isinstance(lib.param('ascii_key'), str):
        lengths = [ord(c) for c in lib.param('ascii_key')]
    else:
        lengths = [ord(c) for line in lib.input() for c in line]
else:
    lengths = [int(el) for line in lib.input() for el in line.split(',')]

if lib.param('additional_key_bytes'):
    lengths += lib.param('additional_key_bytes')

(This is one reason I wrote the library functions) this time around…)

Next, we want to generate the hex hash from the list of bytes:

root_length = int(math.sqrt(lib.param('marks')))

sparse_hash = rope
dense_hash = [
    functools.reduce(operator.xor, sparse_hash[i : i+root_length])
    for i in range(0, lib.param('marks'), root_length)
]
hex_hash = ''.join(f'{i:02x}' for i in dense_hash)

print(hex_hash)

operator.xor is the ^ (xor function) as a function, so we can pass it to other functions. functools.reduce will take a list of values and apply the given function (this is why I needed a function) to pairs of values until there is only one value left. This has the effect of xoring all of the values in the list, which is what we need.

To turn them into hex values, we’ll use a format string : {i:02x}. This means: take an integer (i) and print it as a hex value :x that is two characters wide (:2x) and left padded with 0 (:02x). You eventually get used to those. 😄

For our test cases, I’m printing both the product of the first two and the final hash, but the values for those are different. You can use sed to pull out specific lines though:

$ python3 run-all.py day-10

day-10  python3 knot-cool.py input.txt --marks 256 | sed -n '1p'        0.06845784187316895     1935
day-10  python3 knot-cool.py input.txt --ascii-key --additional-key-bytes 17 31 73 47 23 --marks 256 --rounds 64 | sed -n '2p'  0.09150004386901855     dc7e7dee710d4c7201ce42713e6b8359

That’s a fascinating problem. I bet that we’ll see this hashing function again1, so we’ll wrap the whole thing up in a function, clean it up, and put it in lib.py2:

def knothash(value, rounds = 64):
    lengths = [ord(c) for c in value] + [17, 31, 73, 47, 23]
    rope = list(range(256))

    origin = 0
    skip = -1

    for round in range(rounds):
        for length in lengths:
            skip += 1
            skip %= len(rope)

            rope = rope[length:] + list(reversed(rope[:length]))
            rope = rope[skip:] + rope[:skip]
            origin -= length + skip

    origin %= len(rope)
    rope = rope[origin:] + rope[:origin]

    dense_hash = [
        functools.reduce(operator.xor, rope[i : i+16])
        for i in range(0, 256, 16)
    ]
    hex_hash = ''.join(f'{i:02x}' for i in dense_hash)

    return hex_hash

  1. And unlike last time, I’m actually correct↩︎

  2. Hard coding the constant bytes; I wonder if those mean anything… ↩︎