Source: Knot Hash
Part 1: Starting with a list of the numbers from
1tonand a list oflengths(as input):
- Initialize
current_positionandskip_sizeto0- For each
lengthelement in thelengthslist:- Reverse the first
lengthelements of the list (starting atcurrent_position)- Move forward by
lengthplusskip_size- Increment
skip_sizeby 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,3is 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:
- Split the output into groups of 16 bytes each, apply xor to the entire group of 16 to get a single byte.
- 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