Advent of Code is an annual coding puzzle.
We're going to deal with AoC 2022 Day 05: Supply Stacks.
The straightforward solution is a stack-based simulation.
On some inputs - which we'll see later - this approach is quite slow:
Disclaimer: It wasn't ever supposed to be run on this input.
Tenet is a Hollywood movie about super-determinism.
Can this Hollywood movie help us?
First, the straightforward solution
The puzzle is about modeling stacks of crates, and moving them around:
That's just the syntax level though. The semantical meaning is what matters.
Commands are like pops and pushes on stacks:
A straightforward solution is "do literally the pushes and pops to the stacks, end of story":
The straightforward solution works well on basic inputs.
The problem
But our input isn't always that easy...
Our actual input:
- has a lot of lines,
- commands moving thousands of crates at once.
Due to its sheer size, it takes a LOT OF TIME for the computer to chug through that huge input:
There's nothing wrong with the algorithm.
Simply the algorithm didn't expect that the input would look like Juarez.
Can you think of a better way?
No idea yet?
The idea is: You are not shooting the bullet; You are catching it.
A different approach
Let's start thinking backwards!
First, let's create a coordinate system which describes our problem:
If you think of the problem as simply mapping points to points, it becomes a geometry problem.
What we want to do is start at the end and trace back only the necessary crates to the beginning:
We can do this, because each command is a bijection, aka it has an inverse function. But what is the inverse function in this case?
Can we make a pure mathematical inverse function which just maps points to points, without stacks?
Inverse function
Before diving head in, let's plan out what cases must the inverse function have:
There are 4 cases, and we'll go over each case separately, to keep it simple.
Case: Those which don't change
Case: Those which slide down
Case: Those which slide up
Case: Those which switch stacks
Together
Together these cases form a pure function which maps a (x, y) coordinate to a (x', y') coordinate.
But, at the end we must figure out the letter for that coordinate from the initial state...
And it is a bit problematic because we just assumed that at the end each stack will be non-empty.
What happens when our assumption is wrong?
What happens if we trace back a non-existing point?
If an end position after mapping does not correspond to a letter, it just means that end position will not exist.
So, in the final lookup, just filter out points which don't map to anything in the input hashmap/array. This way they won't even make it to the newspapers in El Paso.
Implementation in Python
A Python implemenation can be something like:
#!/usr/bin/env python3
# Just turn the top part of the text input into stacks
def parse_stacks(text: str):
lines = text.splitlines()[:-1] # drop numbering
return [
"".join(
line[i] for line in lines
if i < len(line) and line[i].isalpha()
)
for i in range(1, len(lines[-1]), 4)
]
# Just turn the bottom part of the text input into (n, i, j) tuples
def parse_commands(body: str):
def to_command(line):
parts = line.split()
n = int(parts[1])
i = int(parts[3]) - 1
j = int(parts[-1]) - 1
return (n, i, j)
return [to_command(line) for line in body.splitlines()]
# Our inverse function
def inverse(n: int, i: int, j: int, p: tuple[int, int]):
x, y = p
if x != i and x != j:
return (x, y)
if x == i:
return (x, y + n)
if x == j and y >= n:
return (x, y - n)
return (i, n - y - 1)
def main():
with open("input.txt") as f:
content = f.read()
state_txt, commands_txt = content.split("\n\n")
stacks = parse_stacks(state_txt)
commands = parse_commands(commands_txt)
result = ""
# Loop over each stack
for x0 in range(len(stacks)):
xy = (x0, 0) # (x0, 0) is the top of the x0 stack
# Loop backwards over all commands and apply their inverses
for (n, i, j) in reversed(commands):
xy = inverse(n, i, j, xy)
x, y = xy
stack_x = stacks[x]
result += stack_x[y] if len(stack_x) > y else ""
print(result)
##############################################################################
if __name__ == "__main__":
main()
The difference between the stack-based and the backtracing solution is not a clear cut asymptotical O(N^3) vs O(N) thing...
What's the order of N?
N is the number of stacks. Each stack is labeled by a single base-10 digit:
[D]
[N] [C]
[Z] [M] [P]
1 2 3
So N is at most 10, easy peasy.
M is the number of crates moved in a single command.
M is made up of digits in base 10.
Q: How many digits?
A: Yes.
If we use this backtracing approach we'll get a slightly lower runtime on that specific input, because the backtrace's time complexity is different from the straightforward solution's:
Essentially we just abuse the fact that there's a huge difference between N and M's upper bounds.
The stack-based solution simply choked on a ton of move 38413 from 1 to 6-like commands.
There's a Part 2 of this problem too, where we put back the picked up elements in the same order.
I'm quite sure you'd be able to do Part 2 too.
Or maybe you were the one who solved it for me?
Github runner
There's a Netflix dev who makes funny videos.
What's important is that he has a YouTube channel ThePrimeagen, where he posted a hilarious video about Github runner sleeps.
He argued that the below code is a bad way to implement a sleep:
SECONDS=0
while [[ $SECONDS != $1 ]]; do
:
done
But he also wrote the stack based solution in Rust, where he did a much more clever sleep:
The sleep is organically weaved into the algorithm itself. It does not rely on shell magic, as the sleep is a natural part of the fabric of Rust.
Compared to the Python, Rust does a better sleep:
The sleep is still adjustable, scalable, according to demand:
Silver Tier isn't available due to a one-off error. I'm not good with numbers neither with Python.
Ok, in reality, the Rust author is on one hand funny, but more importantly: he has good intentions, and he's probably a good engineer (I cannot judge as I am not).
He's pretty adamant about his ways though, so he would probably first invert our inverse function:
Then he'd probably see that the original stack based function was impure, because it mutated the stacks:
On the other hand his handy new move function is pure:
So he'd take advantage of it, by splitting it into separate parallel workloads. For simplicity's sake below I split them by stacks:
Each i-th thread needs just a single array to hold the boxes of the i-th stack.
But this is just one thing. Another thing is that the function is pure, so it can be tabulated:
The moved crates' order is not switched in Part 2 for example, this is why there's no reordering in the illustration.
The truth of the matter is: we are just permuting stuff.
So, given his experience, he would even be able to do more interesting stuff, or might decide that the added overhead of backtrace/parallel/tabulation is not worth it if he gets reliable information about the expected input size, but for us, this is enough. (For backtrace you'd need to be either an offline algorithm, or get the input backwards.)
Back to the original sleep topic though...
I quite liked that engineer's Rust. But the more important thing is that he shared his code. So we are able to see it.
This engineer said that the Github runner's sleep is deranged. One could say that... that shell sleep from the video has shining, just like my Python from Slopistan. But that's shining code which you can see.
How about a suite of software which:
- you cannot see,
- is deranged,
- costs you monthly,
- you subscribe by being born,
- you cannot migrate to a different vendor?
Government agencies have code and you are billed by IRS.
All in all:
The original Rust code of that Netflix dev had a function call:
crane_time_me_daddy(file)?;
This kicked off the whole simulation, which - for actual, normal, sane inputs - resulted in good wall-clock times.
Given all of this pure function nonsense we got into...
A slightly more important thing is this, because Netflix daddy dev already made us halfway happy.
Top comments (0)