Day 10 Knot Hash

10.1 Part I

On Day 10, you discover elves trying to develop a kind of knot-hash system.

This hash function simulates tying a knot in a circle of string with 256 marks on it. Based on the input to be hashed, the function repeatedly selects a span of string, brings the ends together, and gives the span a half-twist to reverse the order of the marks within it. After doing this many times, the order of the marks is used to build the resulting hash.

  4--5   pinch   4  5           4   1
 /    \  5,0,1  / \/ \  twist  / \ / \
3      0  -->  3      0  -->  3   X   0
 \    /         \ /\ /         \ / \ /
  2--1           2  1           2   5
  
To achieve this, begin with a list of numbers from 0 to 255, a current position which begins at 0 (the first element in the list), a skip size (which starts at 0), and a sequence of lengths (your puzzle input). Then, for each length:

- 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; if the current position and the length try to reverse elements beyond the end of the list, the operation reverses using as many extra elements as it needs from the front of the list. If the current position moves past the end of the list, it wraps around to the front. Lengths larger than the size of the list are invalid.

We start with a smaller list for testing and check against the example in full puzzle description.

elements <- c(0, 1, 2, 3, 4)
lengths <- c(3, 4, 1, 5)

We can now write out our steps in code, like below:

skip_size <- 0
curr_pos <- 1 #current position

for(i in lengths){ #for each of the lengths provided
    i = i - 1 #make it easier to work with:
    #ex: length 3 means (curr_pos, curr_pos + 1, curr_pos + 2)
    #2 = 3 - 1
    
    if(i != 0){
        curr_pos <- curr_pos %% length(elements) #give a value within range
        
        #twist segment
        if(curr_pos + i <= length(elements)){ #if looping not needed
            
            #extract sublist of loop to twist
            sublist <- elements[curr_pos:(curr_pos + i)]
            
            #now twist and put it back!
            elements[curr_pos:(curr_pos + i)] <- sublist[length(sublist):1]
            
        } else { #if the segment loops...
            end_pos <- (curr_pos + i) %% length(elements)
            
            #extract segments from end and beg and combine
            seg1 <- elements[curr_pos:length(elements)]
            seg2 <- elements[1:end_pos]
            sublist <- c(seg1, seg2)
            
            #twist it!
            elem_twist <- sublist[length(sublist):1]
            
            #put back into loop
            elements[curr_pos:length(elements)] <- elem_twist[1:length(seg1)]
            elements[1:end_pos] <- elem_twist[(length(seg1) + 1):length(elem_twist)]                
        }
    }
    curr_pos <- curr_pos + i + 1 + skip_size
    skip_size <- skip_size + 1
}

What we’re really curious about though, is the result of multiplying the first two numbers in the list. We get:

elements[1] * elements[2]

## [1] 12

Variables make it easy to just replace the test with the puzzle input and run through the script again!

10.2 Part II

Part II is a bit more involved, and requires additional steps/conversions:

1. Turn every character in input (lengths) into ASCII code
2. Add these to end: 17, 31, 73, 47, 23
3. Run 64 rounds, keep lengths/curr_pos/skip_size for each round
4. Reduce ordered numbers (“sparse hash”) to dense hash
5. XOR blocks of 16 –> get 16 numbers

I learned a lot about computer science/encryption, which is both confusing and fascinating at the same time. It’s like these people were professional puzzle makers!

Unfortunately, I never finished this one, so I’ll end my puzzle-spree here and save it for another rainy day (which in southern California, may be a long ways away…).

_fin :umbrella: :whale2: