Advent of Languages 2024, Day 2: C++

W ell, Day 1 went swimmingly, more or less, so let’s push on to Day 2: C++! C++, of course, is famous for being what happens when you take C and answer “Yes” to every question that starts “Can I have” and ends with a language feature. Yes, you can have classes and inheritance. Yes, even multiple inheritance. Yes, you can have constructors and destructors. Yes, you can have iterators (sorta).1

Yes, you can have metaprogramming. Yes, you can have move semantics. Yes, you can also have raw pointers, why not?

It’s ubiquitous in any context requiring a) high performance and b) a large codebase, such as browsers and game engines. It has a reputation for nightmarish complexity matched only by certain legal codes and the Third Edition of Dungeons & Dragons.2

If using C is like firing a gun with a strong tendency to droop toward your feet any time your focus slips, then using C++ is like firing a Rube Goldberg machine composed of a multitude of guns which may or may not be pointed at your feet at any given time, and the only way to know is to pull the trigger.

How better, then, to spend Day 2 of Advent of Code?

Will It Blend Compile?

I seem to recall hearing somewhere that C++ is a superset of C, so let’s just start with the same hello-world as last time:

#include "stdio.h"

int main() {
    printf("hello, world!");
}

$ cpp 02.cpp

>>> # 0 "02.cpp"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "02.cpp"
# 1 "/usr/include/stdio.h" 1 3 4
# 27 "/usr/include/stdio.h" 3 4

(...much more in this vein)

Oh. Oh dear. That’s not what I was hoping for at all.

So it seems that cpp doesn’t produce executable code as its immediate artifact the way cc does. Actually, it looks kind of like it just barfs out C (non-++) code, and then you have to compile that with a separate C compiler? Let’s try that.

$ cpp 02.cpp | cc

>>> cc: error: -E or -x required when input is from standard input

Hmm, well, that’s progress, I guess? According to cc --help, -E tells it to “Preprocess only; do not compile, assemble or link”, so that’s not what I’m looking for. But wait, what’s this?

-x <language>   Specify the language of the following input files.
                Permissible languages include: c c++ assembler none
                'none' means revert to the default behavior of
                guessing the language based on the file's extension.

Oho! Wait, does that mean I can just—

$ cc 02.cpp && ./a.out

>>> hello, world!

Well. That was a lot less complicated than I expected.3

I’ve got to say, I was expecting hours of frustration just getting the basic compiler toolchains to work with these OG languages like C and C++, but so far it’s been surprisingly simple. I’m sure all of that goes right out the window the moment you need to make use of third-party code (beyond glibc that is), but for straightforward write-everything-yourself-the-old-fashioned-way work it’s refreshingly simple.

Of course, after a little looking around I see that this isn’t the idomatic way of outputting text in C++. That would be something more like this:

#include <iostream>

int main() {
    std::cout << "hello, world!";
}

$ cc 02.cpp && ./a.out

>>> /usr/bin/ld: /tmp/ccZD7l7S.o: warning: relocation against `_ZSt4cout' in read-only section `.text'
/usr/bin/ld: /tmp/ccZD7l7S.o: in function `main':
02.cpp:(.text+0x15): undefined reference to `std::cout'
/usr/bin/ld: 02.cpp:(.text+0x1d): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
/usr/bin/ld: /tmp/ccZD7l7S.o: in function `__static_initialization_and_destruction_0(int, int)':
02.cpp:(.text+0x54): undefined reference to `std::ios_base::Init::Init()'
/usr/bin/ld: 02.cpp:(.text+0x6f): undefined reference to `std::ios_base::Init::~Init()'
/usr/bin/ld: warning: creating DT_TEXTREL in a PIE
collect2: error: ld returned 1 exit status

Oh. Well, that’s… informative. Or would be, if I knew what to look at.

I think the money line is this: undefined reference to std::cout, but I’m not sure what it means. The language server seemed to think that including iostream would make std::cout available.

Thankfully the ever-helpful Stack Overflow came to the rescue and I was able to get it working by using g++ rather than cc. Ok, I take back some of what I said about the simplicity of C-language toolchains.

Day 2, Part 1

Ok, so let’s look at the actual puzzle.

So we’ve got a file full of lines of space-separated numbers (again), but this time the lines are of variable length. Our job is, for every line, to determine whether or not the numbers as read left to right meet certain criteria. They have to be either all increasing or all decreasing, and they have to change by at least 1 but no more than 3 from one to the next.

Now, I know C++ has a much richer standard library than plain C, starting with std::string, so let’s see what we can make it do. I’ll start by just counting lines, to make sure I’ve got the whole reading-from-file thing working:

#include <fstream>
#include <iostream>
#include <string>

using namespace std;

int main() {
    ifstream file("data/02.txt");
    string line;
    int count = 0;
    while (getline(file, line)) {
        count++;
    }
    cout << count;
}

$ g++ 02.cpp && ./a.out

>>> 0

Oh, uh. Hmm.

Wait, I never actually downloaded my input for Day 2. data/02.txt doesn’t actually exist. Apparently this isn’t a problem? I guess I can see it being ok to construct an ifstream that points to a file that doedsn’t exist (after all, you might be about to create said file) but I’m a little confused that it will happily “read” from a non-existent file like this. If the file were present, but empty, it would presumably do the same thing, so I guess… non-extant and empty are considered equivalent? That’s convenient for Redis, but I don’t know that I approve of it in a language context.

Anyway, downloading the data and running the program again prints 1000, which seems right, so I think we’re cooking with gas now.

Interlude: Fantastic Files and How to Read Them

(I really need to find another joke, this one’s wearing a bit thin.)

If you were wondering, by the way,4

a reference I found says that “Objects of this class maintain a filebuf object as their internal stream buffer, which performs input/output operations on the file they are associated with (if any).” So my guess is that we aren’t actually doing 1000 separate reads from disk here, we’re probably doing a few more reasonably-sized reads and buffering those in memory.

It does bug me a little bit that I’m copying each line for every iteration, but after some tentative looking for some equivalent of Rust’s “iterate over string as a series of &strs” functionality I’m sufficiently cowed5

to just stick with the simple, obvious approach.

One thing’s for sure in C++ world: Given a cat, there are guaranteed to be quite a few different ways to skin it.

The rest of the owl

Anyway, let’s do this.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;


vector<int> parse_line(string line) {
    int start = 0;
    vector<int> result;
    while (start < line.length()) {
        int end = line.find(" ", start);
        if (end == -1) {
            break;
        }

        string word = line.substr(start, end - start);
        int n = stoi(word);
        result.push_back(n);
        start = end + 1;
    }
    return result;
}


bool is_valid(vector<int> report) {
    int *prev_diff = nullptr;
    for (int i = 1; i < report.size(); i++) {
        int diff = report[i] - report[i - 1];
        if (diff < -3 || diff == 0 || diff > 3) {
            return false;
        }

        if (prev_diff == nullptr) {
            *prev_diff = diff;
            continue;
        }

        if ((diff > 0 && *prev_diff < 0) || (diff < 0 && *prev_diff > 0)) {
            return false;
        }
        *prev_diff = diff;
    }
    return true;
}


int main() {
    ifstream file("data/02.txt");
    string line;
    int count = 0;
    while (getline(file, line)) {
        auto report = parse_line(line);
        if (is_valid(report)) {
            count++;
        }
    }
    cout << count;
}

And…6

$ g++ 02.cpp && ./a.out

>>> Segmentation fault (core dumped)

Oh.

Right, ok. I was trying to be fancy and use a pointer-to-an-int as sort of a poor man’s optional<T>, mostly because I couldn’t figure out how to instantiate an optional<T>. But of course, I can’t just declare a pointer to an int as a null pointer, then do *prev_diff = diff, because that pointer still has to point somewhere, after all.

I could declare an int, then a separate pointer which is initially null, but then becomes a pointer to it later, but at this point I realized there’s a much simpler solution:

bool is_valid(vector<int> report) {
    int prev_diff = 0;
    for (int i = 1; i < report.size(); i++) {
        int diff = report[i] - report[i - 1];
        if (diff < -3 || diff == 0 || diff > 3) {
            return false;
        }

        // on the first iteration, we can't compare to the previous difference
        if (i == 1) {
            prev_diff = diff;
            continue;
        }

        if ((diff > 0 && prev_diff < 0) || (diff < 0 && prev_diff > 0)) {
            return false;
        }
        prev_diff = diff;
    }
    return true;
}

This at least doesn’t segfault, but it also doesn’t give me the right answer.

Some debugging, a little frustration, and a few minutes later, though, it all works,7

so it’s time to move on to part 2!

Part 2

In a pretty typical Advent of Code escalation, we now have to determine whether any of the currently-invalid lines would become valid with the removal of any one number. Now, I’m sure there are more elegant ways to do this, but…

while (getline(file, line)) {
        auto report = parse_line(line);
        if (is_valid(report)) {
            count_part1++;
            count_part2++;
        }
        else {
            for (int i = 0; i < report.size(); i++) {
                int n = report[i];
                report.erase(report.begin() + i);
                if (is_valid(report)) {
                    count_part2++;
                    break;
                }
                report.insert(report.begin() + i, n);
            }
        }
    }
    cout << "Part 1: " << count_part1 << "\n";
    cout << "Part 2: " << count_part2 << "\n";
}

The only weird thing here, once again solved with the help of Stack Overflow, was how the erase and insert methods for a vector expect not plain ol’ integers but a const_iterator, which apparently is some sort of opaque type representing an index into a container? It’s certainly not an “iterator” in the sense I’m familiar with, which is a state machine which successively yields values from some collection (or from some other iterator).

I’m just not sure why it needs to exist. The informational materials I can find talk about how this is much more convenient than using integers, because look at this:

for (j = 0; j < 3; ++j) {
    ...
}

Gack! Ew! Horrible! Who could possibly countenance such an unmaintainable pile of crap!

On the other hand, with iterators:

for (i = v.begin(); i != v.end(); ++i) {
    ...
}

Joy! Bliss! Worlds of pure contentment and sensible, consistent programming practices!

Based on further research it seems like iterators are essentially the C++ answer to the standardized iteration interfaces found in languages like Python, and that have since been adopted by virtually every language under the sun because they’re hella convenient. In most languages, though, that takes the form of essentially a foreach loop, which is far and away (in my opinion) the most sensible way of approaching iteration. C++ just had to be different, I guess.8

I should probably hold my criticism, though. After all, I’ve been using this language for less than 24 hours, whereas the C++ standards committee presumably has a little more experience than that. And I’m sure the C++ standards committee has never made a bad decision, so I must just be failing to appreciate the depth and perspicacity of their design choices.

Anyway this all works now, so I guess that’s Day 2 completed. Join us next time when we take on the great-graddad of all systems languages, assembly!

Just kidding, I’m not doing assembly. Not yet, anyway. Maybe next year.