Someone Commented on My STL Post — Here's the Follow-Up

I wrote "Stop Using Arrays for Everything" and someone in the comments said: "Cool, now solve Advent of Code 2022 Day 5 your way." Challenge accepted.

The problem

Day 5 of AoC 2022: you have 9 stacks of crates. The input gives you the initial stacks, then a list of moves like "move 3 from stack 1 to stack 2". Move crates one at a time, maintaining order.

Here's what a beginner (past me) might write:

char stacks[9][100];  // fixed size, wasted space
int tops[9] = {0};    // manually track height for each stack

// Push a crate
stacks[from][tops[from]++] = 'A';  // off-by-one nightmare

You're managing two parallel arrays and a bunch of indices. It works but it's messy, rigid, and the code doesn't match the problem description at all.

The right tool exists

The problem literally calls them "stacks." C++ has std::stack. Use it.

#include <stack>
#include <vector>

vector<stack<char>> stacks(9);

// Push a crate
stacks[from].push('A');

// Pop a crate
char c = stacks[from].top();
stacks[from].pop();

No manual tops[] array. No fixed capacity. push() and pop() are exactly the words the problem statement uses. The code reads like English.

The full move logic

for (int i = 0; i < count; i++) {
    stacks[to].push(stacks[from].top());
    stacks[from].pop();
}

Three lines. If you wrote this with raw arrays, it would be twice as long and you'd spend half your time debugging an index.

Why this matters

The Advent of Code commenter was right — it's the perfect demo. When the problem says "stack," and your language has a stack class, the default should be to use it, not to reinvent it with arrays "because I know arrays."

Picking the right container isn't about being fancy. It's about writing code that you can look at two weeks later and still understand instantly.

My GitHub: https://github.com/Cn-Alanwu

Top comments (6)

algorhymer • Jul 24

Thanks!

This is a real good first step towards the solution.
I think now you understand the problem enough to start thinking about it in a chalkboard kind of, theoretical way.

A) How many stacks can there be? 10 at most as they are numbered with digits in the input (more digits would break the input format).
B) The move commands on the other hand follow a pattern 'move N from A to B', where A and B are stack indices.
What is N? The number of crates to move.
What is the upper bound of N?
C) What if I gave an input which has 80 000 lines of commands like 'move 14392462 from 1 to 2'?
Please believe me, even a llvm optimized Rust will have problems with it.
I know this because a famous Ex-Netflixer wrote such a Rust. And it TLE-d on the monster input.

So the real question is: Can you somehow - in a really purely elegant way - change the time and space complexity? By somehow thinking outside the box?

algorhymer • Jul 25 • Edited

Sorry, I came back to set one thing straight.

This is the title of your article:

Someone Commented on My STL Post

I think you are a bit confused about who I am.
In order to alleviate that burden, feel free to check out my latest article.
It clearly defines this point, but it also gives a deeper philosophical foundation for our interaction, Jon.

Tha a' gheamhradh làn uamhasan.

move 543676575139134536912939233423 from 1 to 2

EDIT: Hihi silly me 😅 I almost forgot! This contains a helpful tip related to both STL, this puzzle and life in general.