swizec.com

#### Senior Mindset Book

Get promoted, earn a bigger salary, work for top companies

# Advent of Code Day 14 – Disk Fragmentation

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:

```.css-1yb0ye3{font-family:monospace;color:#728fcb;background-color:#faf8f5;font-size:0.9em;padding-left:0;padding-right:0;}.css-1yb0ye3 .comment,.css-1yb0ye3 .prolog,.css-1yb0ye3 .doctype,.css-1yb0ye3 .cdata,.css-1yb0ye3 .punctuation{color:#b6ad9a;}.css-1yb0ye3 .namespace{opacity:0.7;}.css-1yb0ye3 .tag,.css-1yb0ye3 .operator,.css-1yb0ye3 .number{color:#063289;}.css-1yb0ye3 .property,.css-1yb0ye3 .function{color:#b29762;}.css-1yb0ye3 .tag-id,.css-1yb0ye3 .selector,.css-1yb0ye3 .atrule-id{color:#2d2006;}.css-1yb0ye3 .attr-name{color:#896724;}.css-1yb0ye3 .boolean,.css-1yb0ye3 .string,.css-1yb0ye3 .entity,.css-1yb0ye3 .url,.css-1yb0ye3 .attr-value,.css-1yb0ye3 .keyword,.css-1yb0ye3 .control,.css-1yb0ye3 .directive,.css-1yb0ye3 .unit,.css-1yb0ye3 .statement,.css-1yb0ye3 .regex,.css-1yb0ye3 .at-rule{color:#728fcb;}.css-1yb0ye3 .placeholder,.css-1yb0ye3 .variable{color:#93abdc;}.css-1yb0ye3 .deleted{text-decoration-line:line-through;}.css-1yb0ye3 .inserted{text-decoration-line:underline;}.css-1yb0ye3 .italic{font-style:italic;}.css-1yb0ye3 .important,.css-1yb0ye3 .bold{font-weight:700;}.css-1yb0ye3 .important{color:#896724;}.css-1yb0ye3 .highlight{background:hsla(0, 0%, 70%, .5);}.css-o6ar0x{font-family:monospace;color:#728fcb;background-color:#faf8f5;font-size:0.9em;padding-left:0;padding-right:0;font-family:monospace;color:#728fcb;background-color:#faf8f5;font-size:0.9em;padding-left:0;padding-right:0;}.css-o6ar0x .comment,.css-o6ar0x .prolog,.css-o6ar0x .doctype,.css-o6ar0x .cdata,.css-o6ar0x .punctuation{color:#b6ad9a;}.css-o6ar0x .namespace{opacity:0.7;}.css-o6ar0x .tag,.css-o6ar0x .operator,.css-o6ar0x .number{color:#063289;}.css-o6ar0x .property,.css-o6ar0x .function{color:#b29762;}.css-o6ar0x .tag-id,.css-o6ar0x .selector,.css-o6ar0x .atrule-id{color:#2d2006;}.css-o6ar0x .attr-name{color:#896724;}.css-o6ar0x .boolean,.css-o6ar0x .string,.css-o6ar0x .entity,.css-o6ar0x .url,.css-o6ar0x .attr-value,.css-o6ar0x .keyword,.css-o6ar0x .control,.css-o6ar0x .directive,.css-o6ar0x .unit,.css-o6ar0x .statement,.css-o6ar0x .regex,.css-o6ar0x .at-rule{color:#728fcb;}.css-o6ar0x .placeholder,.css-o6ar0x .variable{color:#93abdc;}.css-o6ar0x .deleted{text-decoration-line:line-through;}.css-o6ar0x .inserted{text-decoration-line:underline;}.css-o6ar0x .italic{font-style:italic;}.css-o6ar0x .important,.css-o6ar0x .bold{font-weight:700;}.css-o6ar0x .important{color:#896724;}.css-o6ar0x .highlight{background:hsla(0, 0%, 70%, .5);}.css-o6ar0x .comment,.css-o6ar0x .prolog,.css-o6ar0x .doctype,.css-o6ar0x .cdata,.css-o6ar0x .punctuation{color:#b6ad9a;}.css-o6ar0x .namespace{opacity:0.7;}.css-o6ar0x .tag,.css-o6ar0x .operator,.css-o6ar0x .number{color:#063289;}.css-o6ar0x .property,.css-o6ar0x .function{color:#b29762;}.css-o6ar0x .tag-id,.css-o6ar0x .selector,.css-o6ar0x .atrule-id{color:#2d2006;}.css-o6ar0x .attr-name{color:#896724;}.css-o6ar0x .boolean,.css-o6ar0x .string,.css-o6ar0x .entity,.css-o6ar0x .url,.css-o6ar0x .attr-value,.css-o6ar0x .keyword,.css-o6ar0x .control,.css-o6ar0x .directive,.css-o6ar0x .unit,.css-o6ar0x .statement,.css-o6ar0x .regex,.css-o6ar0x .at-rule{color:#728fcb;}.css-o6ar0x .placeholder,.css-o6ar0x .variable{color:#93abdc;}.css-o6ar0x .deleted{text-decoration-line:line-through;}.css-o6ar0x .inserted{text-decoration-line:underline;}.css-o6ar0x .italic{font-style:italic;}.css-o6ar0x .important,.css-o6ar0x .bold{font-weight:700;}.css-o6ar0x .important{color:#896724;}.css-o6ar0x .highlight{background:hsla(0, 0%, 70%, .5);}```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. 😴

Published on December 14th, 2017 in Front End, python, Technical

Semantically similar articles hand-picked by GPT-4

### Senior Mindset Book

Get promoted, earn a bigger salary, work for top companies

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 ❤️

Created by Swizec with ❤️