Advent of Code Day 14 was a strange, strange thing. At first, it made no sense. Something about disk fragmentation and encoding addresses as knot hashes and whatnot.
What the hell is a knot hash? O.o
Turns out it's from Advent of Code Day 10. Conveniently called "knot hash". On Day 10, you build a general hashing function following this schema 👇
Don't worry, that image didn't tell me anything either.
AoC's description of the process makes more sense
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.
Okay. So that's difficult to follow, and it's kind of annoying to build, but Day 10 boils down to what we do best in our day-to-day programming: Follow instructions to implement a random piece of business logic.
Day 10, star 1
The puzzle is the instructions. We just gotta write the correct code. In Python, mine looks like this:
def knot_1round(pos, skip, lengths, input):
for length in lengths:
if pos+length > len(input):
wrap = (pos+length)%len(input)
else:
wrap = 0
nums = input[pos:pos+length] + input[:wrap]
nums = list(reversed(nums))
if wrap > 0:
input = nums[-wrap:] + input[wrap:pos] + nums[:-wrap] + input[pos+length:]
else:
input = input[:pos] + nums + input[pos+length:]
pos = (pos+length+skip)%len(input)
skip += 1
return pos, skip, input
Boring, predictable, nothing special. Go through the list of numbers, use input lengths, do the knot hashing. The neat part of this code is Python's spectacular support for list slicing and dicing.
You can use the : operator to get different parts of a list. Left side means "up to" and right side means "after". You can use negative numbers.
Dealing with the circular wraparound part was mindbendy and a bit tedious. You can't just cut the list and put it together. You have to use a bunch of different bits and sections.
Day 10, star 2
For the second part, we assembled 64 single rounds of knot hashing into a full knot hash. Again, just following instructions and most of the hard work coming down to understanding those instructions.
No fun insights needed 😴
def knot(input):
lengths = [ord(str(c)) for c in input] + [17, 31, 73, 47, 23]
pos = 0
skip = 0
numbers = range(0, 256)
for i in xrange(64):
pos, skip, numbers = knot_1round(pos, skip, lengths, numbers)
blocks = [reduce(lambda b, n: b^n, numbers[i:i+16]) for i in xrange(0, len(numbers), 16)]
print numbers[0:16]
return "".join(["%0.2X" % c for c in blocks])
You take the input, turn each character into its ASCII number, add a static salt thing [17, 31, 73, 47, 23], then run the knot round 64 times. Make sure each round feeds the current position and skip size into the next one.
In the end, you take that result and parse it back into a hexadecimal string.
So an empty string input produces a2582a3a0e66e6e86e3812dcb672a272, for example.
shrug emoji
Day 14, star 1
With our general knot hashing function in hand, we could take on Day 14. Only took me 70 minutes to get here 😂
But Day 14, the first part at least, was trivial now that the hashing made sense.
The goal is to figure out how many blocks of a disk space are occupied. You are given an input string, and you compute it into 128 knot hashes, then you transform those knot hashes into binary, and count how many 1's there are.
Again, in Python, it looks like this 👇
inputs = [input+"-"+str(i) for i in xrange(128)]
def star1(inputs):
used = 0
for input in inputs:
hash = knot(input)
used += sum(bin(int(c, 16))[2:].count('1') for c in hash)
return used
Make a list of 128 inputs, walk through it, calculate hashes, transform them into binary, count the 1's and sum it up. Done.
That was easy.
Then Star 2 came along, and it asked to count regions. That is adjacent 1's that are touching.
So I said, “Screw this, I'm tired,” and went to bed. 😴
Continue reading about Advent of Code Day 14 – Disk Fragmentation
Semantically similar articles hand-picked by GPT-4
- Advent of Code Days 17 & 18 – Spinlocks and Interpreters
- Advent of Code Day 19 – A Series of Tubes
- Advent of Code Day 13, Packet Scanners
- Advent of Code Day 20 – Particle Swarm
- Advent of Code Day 15 – Dueling JavaScript Generators
Learned something new?
Read more Software Engineering Lessons from Production
I write articles with real insight into the career and skills of a modern software engineer. "Raw and honest from the heart!" as one reader described them. Fueled by lessons learned over 20 years of building production code for side-projects, small businesses, and hyper growth startups. Both successful and not.
Subscribe below 👇
Software Engineering Lessons from Production
Join Swizec's Newsletter and get insightful emails 💌 on mindsets, tactics, and technical skills for your career. Real lessons from building production software. No bullshit.
"Man, love your simple writing! Yours is the only newsletter I open and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"
Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.
Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.
Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.
Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev
Want to Stop copy pasting D3 examples and create data visualizations of your own? Learn how to build scalable dataviz React components your whole team can understand with React for Data Visualization
Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections
Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog
Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com
By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️