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()orconcat()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')
-
2is the maximum length of the string -
0is 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!
Top comments (0)