Day 10: Knot Hash

If you were hoping for some slightly more hardcore challenges from the AoC, then Day 10 should be right up your street. There’s hexadecimal, bitwise XOR, ASCII and all sorts of other fun things going on. As always, let’s take a look at the challenge text and see where to begin!

Solving Part 1

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.

This doesn’t actually sound too bad. We can leverage some tricks we learnt on Day 6 to handle a circular list. Before we try to tackle the list of 256 numbers, we can work through the example for today. Let’s fire up a Q session and get started.

We need a few variables to keep track of the position and skip size, we can call these p and s respectively and initialise them both to zero

q)p:s:0 / assign both p and s to zero as a one-liner

And let’s call our list 0 1 2 3 4, l

q)til 5 / til gives us the range from 0 up to the input
0 1 2 3 4
q)l:til 5 / saves writing a few characters

Variable initialisation done, next stop: the tricky bit.

We need to index into our list l at position p, and extract the next 3 (first item in our input list i) items (wrapping around if need be), reverse them and put them back in place.

From Day 6 we saw we could use til and mod in order to generate a range of indexes (indices) that wrapped around a circular list:

(offset + til range) mod (count list)

Replacing the placeholders with our variables, and the first length, 3, gives us

q)(p + til 3) mod count l
0 1 2

And sure enough, these are the indices we want, using them to index back into l gives us 0 1 2 as expected

q)l (p + til 3) mod count l
0 1 2

We need to reverse these values, and then put them back into our list l. For that we can use the amend operator that we also used on Day 6.

For today’s challenge we will be using it with 4 parameters:

@[variable;indices;function;arguments]

The variable is our list, l, the indices are given by (p + til 3) mod count l, the function is assignment, :, and the arguments are the reverse of l (p + til 3) mod count l.

q)@[l;(p + til 3) mod count l;:;reverse l (p + til 3) mod count l]
2 1 0 3 4

Note: This does not save the updated the value in l unless we use `l or assign the result back into l as follows:

q)l:@[l;(p + til 3) mod count l;:;reverse l (p + til 3) mod count l]
q)l
2 1 0 3 4
q)@[`l;(p + til 3) mod count l;:;reverse l (p + til 3) mod count l]  / backticks only works on globals
`l
q)l / we performed reverse twice on the same indices, thus we are back to the start!
0 1 2 3 4
q)l:@[l;(p + til 3) mod count l;:;reverse l (p + til 3) mod count l] / get back to 2 1 0 3 4
q)l
2 1 0 3 4

We should now increment the position, p by that length (3) plus the skip size (s), wrapping around with mod

q)p+:(3 + s) mod count l
q)p / check the value of p
3

And now increase the skip size by one

q)s+:1

Let’s perform the apply again with the next input length, 4

q)l:@[l;(p + til 4) mod count l;:;reverse l (p + til 4) mod count l]
q)l
4 3 0 1 2

…and then update p and s

q)p+:(4 + s) mod count l
q)s+:1

Next input is 1 which has no impact on our list, but we still need to update p and s

q)l:@[l;(p + til 1) mod count l;:;reverse l (p + til 1) mod count l]
q)l
4 3 0 1 2
q)p+:(1 + s) mod count l
q)s+:1

.. and now with the final input, 5 gives us the following list:

q)l:@[l;(p + til 5) mod count l;:;reverse l (p + til 5) mod count l]
q)l
3 4 2 1 0

In order to multiply the first two numbers together we can use take, # and prd which returns us the product of the inputs:

q)2#l     / take 2 from list l
3 4
q)prd 2#l / multiply together
12

Great. We have some code that works for the example, albeit with a lot of keyboard work. Let’s put the 3 steps (updating list l, updating p and updating s) together into a function.

This is the first function we’ve created that will have two arguments. We will be passing in (1) the list to be modified, and (2) a number to modify the list.

Q etiquette dictates we should use x and y as parameters, but for starters we can use list for the list parameter, and length for the input length parameter:

{[list;length]
  list:@[list;(p + til length) mod count list;:;reverse list (p + til length) mod count list];
  p+:(length + s) mod count list; / update position p
  s+:1;                           / add 1 to s
  list                            / return the list from the function (don't add a semicolon here!)
  }

We are performing (p + til length) mod count list twice. Instead we can perform it once, save the result to a variable and then use this the next time we need it. Let’s assign the first occurrence to variable i for indices, and then use that as the 2nd parameter of the apply function:

{[list;length]
  list:@[list;i;:;reverse list i:(p + til length) mod count list]; / 'left of right' evaluation :)
  p+:(length + s) mod count list;                                  / update position p
  s+:1;                                                            / add 1 to s
  list                                                             / return list
  }

If we want to adhere to etiquette then the function becomes, which we can call knot:

knot:{[x;y]                                       / we don't actually need the [x;y]
  x:@[x;i;:;reverse x i:(p + til y) mod count x]; / amend list
  p+:(y + s) mod count x;                         / update position p
  s+:1;                                           / add 1 to s
  x                                               / return list
  }

Let’s reset p and s, and run through the example again, using knot

q)p:s:0 / reset position and skip size
q)knot[til 5;3]
2 1 0 3 4
q)knot[2 1 0 3 4;4]
4 3 0 1 2
q)knot[4 3 0 1 2;1]
4 3 0 1 2
q)knot[4 3 0 1 2;5]
3 4 2 1 0

It would be great if we could feed the result of knot back into knot for each of the input lengths… and we can.

Q gives us the adverb over to perform a function over a list.

Generally over will feed 2 items from a list into a function, and then take the result and continue feeding it and each additional item from the list into that function. This can be demonstrated by combining over with add, +, on the numbers 1 to 10. Note that because + is a built-in that is normally used infix (e.g. 1 + 3), we need to wrap it in brackets:

q)1 + til 10 / numbers 1 through 10
1 2 3 4 5 6 7 8 9 10
q)(+) over 1 + til 10
55

The sister function to over is scan, which outputs each result along the way, and can be very useful in seeing what is going on:

q)(+) scan 1 + til 10
1 3 6 10 15 21 28 36 45 55

Unfortunately for today’s challenge, the syntax is not that easy to understand. We also want to avoid using global variables (p and s). Therefore there are 4 arguments to pass into our function:

The input list, e.g. 0 1 2 3 4
The initial value of pointer p: 0
The initial value of skip size, also 0
The list operations to perform, e.g. 3 4 1 5

We wish to iterate over the sequence of lengths whilst keeping track of our input list, p and s.

Until I figure out a better method, the easiest way to do this appear to be grouping together our input, p and s as a 3-item list:

q)(0 1 2 3 4;0;0)
0 1 2 3 4
0
0

The first (or 0th) item in this list is our input list, we can use 0 to index to fetch it:

q)(0 1 2 3 4;0;0) 0
0 1 2 3 4

We are keeping track of p as the second item (index 1), and s as third item (index 2):

q)(0 1 2 3 4;0;0) 1 / this is the 2nd item in the list, p
0
q)(0 1 2 3 4;0;0) 2 / this is the 3rd item in the list, s
0

If we were to rewrite our earlier knot function to account for the fact that we are passing in a 3-item list rather than leaning on global variables to track p and s, it might look like this:

knot:{[x;y]
  l:x 0;                                          / list is item 0
  p:x 1;                                          / p is item 1
  s:x 2;                                          / s is item 2
  l:@[l;i;:;reverse l i:(p + til y) mod count l]; / amend list
  p+:(y + s) mod count l;                         / update position p
  s+:1;                                           / add 1 to s
  (x;p;s)                                         / return a 3-item list with the updated values
  };

We can test this with the first length:

q)knot[(til 5;0;0);3]
2 1 0 3 4
3
1

If we feed in the next length using the returned values:

q)knot[(2 1 0 3 4;3;1);4]
4 3 0 1 2
3
2

Combining this new function with scan \ (spitting out each interim step) gives:

q)knot\[(til 5;0;0);3 4 1 5]
1 0 3 4 3 1
3 0 1 2 3 2
3 0 1 2 6 3
4 2 1 0 9 4

We only care about the final result, so we should use over /:

q)knot/[(til 5;0;0);3 4 1 5]
3 4 2 1 0
9
4

More accurately, we only care about the first item of the final result:

q)first knot/[(til 5;0;0);3 4 1 5]
3 4 2 1 0

So we can rewrite the knot function as returning the first item from the result of performing an over. We will pass p and s with starting values of 0:

knot:{[x;y]
  first {
    l:x 0;                                          / list is item 0
    p:x 1;                                          / p is item 1
    s:x 2;                                          / s is item 2
    l:@[l;i;:;reverse l i:(p + til y) mod count l]; / amend list
    p+:(y + s) mod count l;                         / update position p
    s+:1;                                           / add 1 to s
    (l;p;s)                                         / return a 3-item list with the updated values
    }/[(x;0;0);y]
  };

Our knot function can now be called with 2 arguments: the input list, and the list of lengths:

q)knot[til 5;3 4 1 5]
3 4 2 1 0
q)prd 2#knot[til 5;3 4 1 5]
12

OK! We can handle the example as a one-liner. Let’s take a look at the puzzle input for today.

q)read0 `:input/10.txt
"97,167,54,178,2,11,209,174,119,248,254,0,255,1,64,190"

Ah, a list of numbers separated by commas. We’ve not had this one yet, but it’s almost the same as Day 6, just separated by "," instead of "\t".

q)first read0 `:input/10.txt / take the first line
"97,167,54,178,2,11,209,174,119,248,254,0,255,1,64,190"
q)"," vs first read0 `:input/10.txt / split on ","
"97"
"167"
"54"
"178"
,"2"
"11"
"209"
"174"
"119"
"248"
"254"
,"0"
"255"
,"1"
"64"
"190"
q)"J"$"," vs first read0 `:input/10.txt / and use big-J casting to cast to longs
97 167 54 178 2 11 209 174 119 248 254 0 255 1 64 190

The other difference between solving the example and solving Part 1 is that our list needs to contain 256 items (0..255) rather than just 5. This is easy to generate with til

q)til 256
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..

So, lets feed our input list of 0..255, and puzzle input into knot, take the first 2 elements and calculate the product:

q)prd 2#knot[til 256;"J"$"," vs first read0 `:input/10.txt]
8536

Bingo. That’s today’s first star!

Solving Part 2

The logic you’ve constructed forms a single round of the Knot Hash algorithm; running the full thing requires many of these rounds. Some input and output processing is also required… instead of merely running one round like you did above, run a total of 64 rounds, using the same length sequence in each round. The current **position and skip size should be preserved between rounds.

The first thing to note is that we need to convert our puzzle input ASCII characters and then append 17 31 73 47 23.

We then need to perform the knot function 64 times.

Once that’s done we need to xor together each of the 16, 16-item blocks, before finally converting to hexadecimal.

Thankfully we can re-use our knot function as-is, we just need to add bit more code around it to get our second star.

Let’s crack on…

We know from Day 1 that using the small-j casting on a string will return us the ASCII values:

q)"j"$first read0 `:input/10.txt
57 55 44 49 54 55 44 53 52 44 49 55 56 44 50 44 49 49 44 50 48 57 44 49 55 52 44 49 49 57 44 50 52 56 44 50 53 52 44 48 44 50 53 53 44 49 44 54 52 44 49 57 48

We need to append 17 31 73 47 23 to this (scroll right to see that it’s worked!)

q)("j"$first read0 `:input/10.txt),17 31 73 47 23 / note brackets
57 55 44 49 54 55 44 53 52 44 49 55 56 44 50 44 49 49 44 50 48 57 44 49 55 52 44 49 49 57 44 50 52 56 44 50 53 52 44 48 44 50 53 53 44 49 44 54 52 44 49 57 48 17 31 73 47 23

If we want to perform our knot function 64 times with this input list we can just take 64 copies of this list, and feed them into knot.

In order to take (#) the whole list 64 times we need to enlist it. Here’s a quick example showing the difference:

q)10#1 2 3 / take 10 from the list '1 2 3'
2 3 1 2 3 1 2 3 1
q)10#enlist 1 2 3 / take 10 of the list '1 2 3'
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3

We then need to flatten this down again, which we can do with raze:

q)raze 10#enlist 1 2 3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

Let’s do the same with our puzzle input:

q)raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23
57 55 44 49 54 55 44 53 52 44 49 55 56 44 50 44 49 49 44 50 48 57 44 49 55 52 44 49 49 57 44 50 52 56 44 50 53 52 44 48 44 50 53 53 44 49 44 54 52 44 49 57 48 17 31 73 47 23 57 55 44 49 54 55 44 53 52 44 49 55 56 44 50 44 49 49 44 50 48 ..

It’s a long list…

q)count raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23
3712

Let’s feed this list into knot along with til 256:

q)knot[til 256;raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23]
128 8 0 225 59 13 127 253 100 224 188 218 153 239 58 220 159 163 111 2 23 237 54 182 228 56 50 61 75 99 34 7 76 168 53 192 216 57 176 204 105 21 52 132 198 244 62 223 19 90 67 136 174 33 246 72 141 139 249 133 179 121 35 89 155 4 241 3 1..

In order to cut this into chunks of 16, we can use cut. This operator takes 2 parameters, a list (or matrix) to operate on, and the size of the chunks to cut the input into.

q)4 cut "Hello, World!"
"Hell"
"o, W"
"orld"
,"!"

Let’s use this on the result of our knot

q)16 cut knot[til 256;raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23]
8   0   225 59  13  127 253 100 224 188 218 153 239 58  220
163 111 2   23  237 54  182 228 56  50  61  75  99  34  7  
168 53  192 216 57  176 204 105 21  52  132 198 244 62  223
90  67  136 174 33  246 72  141 139 249 133 179 121 35  89
4   241 3   181 187 146 254 27  173 236 81  66  71  135 255
91  211 191 30  183 193 154 202 87  138 80  250 114 15  85
206 190 203 208 120 170 109 164 129 26  107 98  110 102 124
25  9   147 51  166 86  240 39  45  185 160 92  189 74  32
143 126 200 55  222 73  36  63  10  103 214 245 95  226 212
49  83  231 151 65  169 12  161 196 162 101 156 149 41  88
195 96  20  78  140 118 108 199 122 205 31  5   201 68  194
233 40  157 116 172 43  113 123 106 79  115 6   84  232 125
148 235 29  213 119 18  234 134 44  242 177 17  215 16  97
243 70  167 171 48  14  130 112 117 165 94  142 209 158 227
131 144 238 230 42  252 11  104 47  248 210 69  219 82  152
28  251 93  186 184 22  60  137 229 1   247 24  175 46  197

The next step is to xor each of these lines together to create a ‘dense hash’ from this ‘sparse hash’. There is no bitwise xor built-in to Q. Instead we have to convert our inputs to boolean lists, perform xor on them, and then convert the result back.

In order to convert a number to it’s bit representation we need to use vs as an encoder.

q)0b vs 123 / this is the syntax to convert to a list of bits
0000000000000000000000000000000000000000000000000000000001111011b

In order to convert a list of bits back to a number, we need to use sv as a decoder

q)0b sv 0000000000000000000000000000000000000000000000000000000001111011b / converting back
123

We an use the <> comparison as xor. The xor of 65 and 27 is shown below

q)(0b vs 65)<>0b vs 27 / <> is not-equal, ie xor
0000000000000000000000000000000000000000000000000000000001011010b
q)0b sv (0b vs 65)<>0b vs 27
90

If we convert this to a lambda we get:

{ 0b sv (0b vs x)<>(0b vs y) }

Which we can call to xor and try out:

q)xor:{ 0b sv (0b vs x)<>(0b vs y) }
q)xor[65;27]
90

In order to apply this over a list, we can use the over adverb we used in Part 1.

The example states that the xor of 65 27 9 1 4 3 40 50 91 7 6 0 2 5 68 22 is 64, let’s make sure we agree:

q)xor over 65 27 9 1 4 3 40 50 91 7 6 0 2 5 68 22
64

Nice. Let’s apply xor over to each of our 16 lists

q){ xor over x } each 16 cut knot[til 256;raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23]
175 245 147 121 121 137 214 101 52 158 254 17 187 79 217 155

We can remove the lambda by wrapping the xor over in brackets:

q)(xor over) each 16 cut knot[til 256;raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23]
175 245 147 121 121 137 214 101 52 158 254 17 187 79 217 155

Now we need to convert this to hexadecimal. We can do this by casting to bytes with "x"$:

q)"x"$(xor over) each 16 cut knot[til 256;raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23]
0xaff593797989d665349efe11bb4fd99b

For completeness we should convert this to a string:

q)string "x"$(xor over) each 16 cut knot[til 256;raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23]
"af"
"f5"
"93"
"79"
"79"
"89"
"d6"
"65"
"34"
"9e"
"fe"
"11"
"bb"
"4f"
"d9"
"9b"

… which we need to flatten with raze

q)raze string "x"$(xor over) each 16 cut knot[til 256;raze 64#enlist ("j"$first read0 `:input/10.txt),17 31 73 47 23]
"aff593797989d665349efe11bb4fd99b"

… and today’s second star is ours!

Complete Solution To Day 10

My full solution for Day 10 is below.

I have simplified the code inside the knot function to save some of the assignments, but ultimately it’s doing the same job as the code posted above.