Advent of Code 2017 Reflection

Well, it’s December, so that means it’s Advent Of Code Season again. While I’m working on 2022, I also want to try and hit my yearly goal of 360 stars.

I started this Advent of Code way back in 2017, got stuck for like five years, and decided to come back and crack some problems. This year was a C++ year ( I was working at ADTRAN at the time) and now that I’m back to writing C++, I figured it was a good year to try and finish up. As usual, I have my thoughts about each problem listed below, as well as how hard I thought they were, and my personal rating out of 5. You can find the repository at https://github.com/pviafore/advent-of-code-2017.

One thing to note: I started off trying to write C++ without raw loops to try and get better at the std::algorithm. Towards the end, I abandoned that and started to try to get C++20 concepts better. Looking back, it’s not the best or idiomatic C++

Read more: Advent of Code 2017 Reflection

Day 1

Type of Problem: Iteration

Difficulty: Easy

Rating: 4/5

A nice gentle introduction to AoC, as usual. This is a great opportunity to loop through input and get a feel for the problem. If you want to get adventurous, you can use a zip function, but a normal for loop works pretty well.

Part 2 was just as straightforward, with a check using a modulus operator, which gives people a better idea on how to do cyclical data structures. I also like the theme of being inside the computer throughout this year’s puzzles

Day 2

Type of Problem: Iteration

Difficulty: Easy

Rating: 3/5

Another simple iteration problem to kick things off (I think in later years, there is more variation in the first few problems). In this case, we are just looping through some numbers and either finding the difference or something that is evenly divisible.

MVP for this problem was std::minmax_element, which gives you both the min and the max element

auto getDifference(const std::vector<int>& numbers) {
    auto [min,max] = std::minmax_element(numbers.begin(), numbers.end());
    return *max - *min;
}

Day 3

Type of Problem: Grid Manipulation / Memoization

Difficulty: Medium

Rating: 4/5

I was surprised to see this one so early. I thought it was a legitimately steeper difficulty curve for day 3. You have to calculate values going around a spiral (I’m pretty sure there’s a deterministic way to do this. However, I was not as smart mathematically at the time (and still might now be 🙂 ), so I just figured out what “ring/level” the target number was (each level is one perfect square to another), then figured out where it was relation to origin, making the manhattan distance easy to make.

For Part 2, I just calculated the spiral manually, with a memoized lookup cache to make sure I was not calculating things more than once. When writing code for these sort of problems, I like to make sure I have enums to make it clear what values are possible, as well as make it easier for the compiler to find things.

 enum class Direction {
        RIGHT, UP, LEFT, DOWN
    };

Day 3

Type of Problem: Grid Manipulation / Memoization

Difficulty: Medium

Rating: 4/5

I was surprised to see this one so early. I thought it was a legitimately steeper difficulty curve for day 3. You have to calculate values going around a spiral (I’m pretty sure there’s a deterministic way to do this. However, I was not as smart mathematically at the time (and still might not be 🙂 ), so I just figured out what “ring/level” the target number was (each level is one perfect square to another), then figured out where it was relation to origin, making the manhattan distance easy to make.

For Part 2, I just calculated the spiral manually, with a memoized lookup cache to make sure I was not calculating things more than once. When writing code for these sort of problems, I like to make sure I have enums to make it clear what values are possible, as well as make it easier for the compiler to find things.

 enum class Direction {
        RIGHT, UP, LEFT, DOWN
    };

Day 3

Type of Problem: Grid Manipulation / Memoization

Difficulty: Medium

Rating: 4/5

I was surprised to see this one so early. I thought it was a legitimately steeper difficulty curve for day 3. You have to calculate values going around a spiral (I’m pretty sure there’s a deterministic way to do this. However, I was not as smart mathematically at the time (and still might now be 🙂 ), so I just figured out what “ring/level” the target number was (each level is one perfect square to another), then figured out where it was relation to origin, making the manhattan distance easy to make.

For Part 2, I just calculated the spiral manually, with a memoized lookup cache to make sure I was not calculating things more than once. When writing code for these sort of problems, I like to make sure I have enums to make it clear what values are possible, as well as make it easier for the compiler to find things.

 enum class Direction {
        RIGHT, UP, LEFT, DOWN
    };

Day 4

Type of Problem: Iteration

Difficulty: Easy

Rating: 5/5

I like a nice quick solution with an elegant implementation. std::unique and std::sort makes quick work of this problem, and you’ll notice that I have my own custom algo library (I rewrite my libraries each year) for transformations (these days I’d use a range), and my input library for string splitting (which is still a pain in c++). Minus headers, here is the entirety of my program for part 2

 
std::string sortString(std::string s) {
    std::sort(s.begin(), s.end());
    return s;
}

bool isUnique(const std::string& passphrase) {
    auto words = algo::map(input::split(passphrase), sortString);
    std::sort(words.begin(), words.end());
    return words.end() == std::unique(words.begin(), words.end());
}

int main() {
    auto passPhrases = input::readMultiLineFile("input/input04.txt");
    auto count = std::count_if(passPhrases.begin(), passPhrases.end(), isUnique);
    std::cout << count << "\n";
    return 0;
}

Day 5

Type of Problem: Computer Simulation / Iteration

Difficulty: Easy

Rating: 4/5

The first computer simulation of the year and it wasn’t too bad: just simulating jump offsets with some custom instruction pointer math after each jump. I don’t have too much interesting to say on this one.

 
std::string sortString(std::string s) {
    std::sort(s.begin(), s.end());
    return s;
}

bool isUnique(const std::string& passphrase) {
    auto words = algo::map(input::split(passphrase), sortString);
    std::sort(words.begin(), words.end());
    return words.end() == std::unique(words.begin(), words.end());
}

int main() {
    auto passPhrases = input::readMultiLineFile("input/input04.txt");
    auto count = std::count_if(passPhrases.begin(), passPhrases.end(), isUnique);
    std::cout << count << "\n";
    return 0;
}

Day 6

Type of Problem: Computer Simulation / Iteration

Difficulty: Easy-Medium

Rating: 4/5

I feel like this year has some nice introductions to ideas that are used in later problems. Day 5 had instruction pointer / jump offset calculation, which you have to do for any computer simulation problem. Here, we have cycle detection, which is an important optimization strategy any time you have something that has billions of iterations to go through.

My main piece of code is a function that both figures out the number of times through the loop, and how long the loop itself is. I used a liberal amount of stdlib functions as well as some of my own algorithms.

 auto getNumberOfTimesBeforeSeeingDuplicates(const auto &input) {
    auto numbers = input;
    std::vector<decltype(numbers)> v;
    
    auto numberOfTimesThroughLoop = 0u;
    while(std::find(v.begin(), v.end(), numbers) == v.end()) {
        v.push_back(numbers);
        auto max_element = std::max_element(numbers.begin(), numbers.end());

        assert(max_element != numbers.end());

        const auto max_value = *max_element;
        *max_element = 0;
        algo::apply_cyclically(numbers, max_element+1, max_value, [](auto& s) { s += 1;});

        numberOfTimesThroughLoop++;
    }
    auto distance = std::distance(std::find(v.begin(), v.end(), numbers), v.end());
    return std::make_pair(numberOfTimesThroughLoop, distance);
    
}

Day 7

Type of Problem: Recursion

Difficulty: Medium-Hard

Rating: 5/5

Recursion problems are some of those magical problems that once you figure out how to sub-compose, you get really happy with how things happen. This involved finding weights of towers and figuring out properties of a tree.

Here’s my recursive function for finding which disc of the tower is imbalanced.

 std::string findImbalancedTower(const auto & towerLookup, const std::string& baseTowerName) {
    const auto &currentTower = towerLookup.at(baseTowerName);
    auto subTowers = algo::map(currentTower.subTowers, [&towerLookup](const std::string& s) { return towerLookup.at(s);});

    if(subTowers.size() == 1) {
        return findImbalancedTower(towerLookup, subTowers[0].name);
    }
    if(std::all_of(subTowers.begin(), subTowers.end(), [weight = subTowers[0].totalWeight](const InputTower& t) { return t.totalWeight == weight; })){
        return currentTower.name;
    }

    bool firstTwoTowersHaveEqualWeight = subTowers[0].totalWeight == subTowers[1].totalWeight;
    if (firstTwoTowersHaveEqualWeight) {
        auto inequal = std::find_if(subTowers.begin(), subTowers.end(), [expectedWeight = subTowers[0].totalWeight](const InputTower& tower) { return tower.totalWeight != expectedWeight;});
        assert(inequal != subTowers.end());
        return findImbalancedTower(towerLookup, inequal->name);
    }
    return (subTowers[0].totalWeight == subTowers[2].totalWeight) ? findImbalancedTower(towerLookup, subTowers[1].name) : findImbalancedTower(towerLookup, subTowers[0].name);
}

Day 8

Type of Problem: Computer Simulation

Difficulty: Medium

Rating: 3/5

We had something with just jumps earlier, now it’s just register manipulation. You put them together, you get a computer :). The hardest part of this is probably the parsing, as shown below. Other than that, it’s just running all the instructions, and latching the maximum register value, and checking the register value at the end.

 explicit Instruction(const std::string & str) {
        auto words = input::split(str);
        assert(words.size() == 7);

        registerName = words[0];
        op = getOp(words[1]);
        offset = std::stoi(words[2]);

        assert(words[3] == "if");
        targetRegister = words[4];

        using namespace std::placeholders;
        condition = std::bind(getFunction(words[5]), _1, std::stoi(words[6]));
    }

 Op getOp(const std::string& opString) {
        if (opString == "inc") return Op::INC;
        if (opString == "dec") return Op::DEC;
        throw std::runtime_error("Invalid operation");
    }

    std::function<bool(int, int)> getFunction(const std::string& func) {
        if (func == ">") return std::greater<int>();
        if (func == ">=") return std::greater_equal<int>();
        if (func == "<") return std::less<int>();
        if (func == "<=") return std::less_equal<int>();
        if (func == "==") return std::equal_to<int>();
        if (func == "!=") return std::not_equal_to<int>();
        throw std::runtime_error("Invalid function");
    }

Day 9

Type of Problem: Parsing

Difficulty: Easy-medium

Rating: 2/5

Generally I’m not a fan of parsing unless it has a recursive structure. Since garbage cancels out any < in this problem, it really just becomes finding matching pairs after you’ve escaped out and removed certain characters.

Here is my heavy lifter (which really should have been a for loop, not a while loop)

auto removeGarbage(const std::string &s) {
    std::string returnValue;
    auto numberOfGarbageCharacters = 0u;
    auto it = s.begin();
    while (it != s.end()) {
        auto startGarbage = std::find(it, s.end(), '<');
        auto endGarbage = std::find(startGarbage, s.end(), '>');
        returnValue.append(it, startGarbage);
        it = endGarbage;

        auto garbageDistance = std::distance(startGarbage, endGarbage);
        if (garbageDistance >= 1) {
            numberOfGarbageCharacters += garbageDistance-1;
        }

        if(it != s.end()){
            ++it;
        }
    }
    return make_pair(returnValue, numberOfGarbageCharacters);
}

Day 10

Type of Problem: Data Structure

Difficulty: Medium

Rating: 2/5

It’s been a few years, but I don’t remember liking this one. For one, part 2 was massive. One redeeming quality was writing a circular buffer, which I’ve used to represent our data. I have my hashed circular buffer to do the reverse/shift/increase logic for the knot hash. Then I create the dense hash (part 2). Than goodness for some bit_xor and accumulate to make this code nice and compact.

    std::unique_ptr<containers::CircularBuffer<unsigned int, 256>> createHashedCircularBuffer(const std::vector<int> & lineLengths, unsigned int rounds){
        auto cb = createCircularBuffer();
        auto skipSize = 0u;
        auto start = 0u;
            for(auto i = 0u; i < rounds; ++i){
            for(auto lineLength: lineLengths) {
                auto range = cb->range(start, start+lineLength);
                std::reverse(range.begin(), range.end());
                for(auto i = 0; i < lineLength; ++i) {
                    (*cb)[start+i] = range[i];
                }
                start += lineLength + skipSize++;

            }
        }
        return cb;
    }

    std::vector<unsigned int> calculateDenseHash(const std::string& input) {

        auto newLineLengths = algo::map(input, [](char c){ return static_cast<int>(c);});
        newLineLengths.push_back(17);
        newLineLengths.push_back(31);
        newLineLengths.push_back(73);
        newLineLengths.push_back(47);
        newLineLengths.push_back(23);
        
        auto values = createHashedCircularBuffer(newLineLengths, 64u)->range(0,256);
        std::vector<unsigned int> out;
        for(auto i = 0; i < 16; ++i){
            auto xorValue = std::accumulate(values.begin()+i*16, values.begin()+i*16+16, 0u, std::bit_xor<unsigned int>());
            out.push_back(xorValue);
        }
        return out;
    }

Day 11

Type of Problem: Grid Manipulation

Difficulty: Easy-Medium

Rating: 4/5

Woo, hex grids! Settlers of Catan fans unite! I figured out a trick during my Project Euler days for hex grids where moving diagonal moves a half unit in the x an a half unit in the y direction, while moving horizontally is a full unit in the x direction. Using that, it’s really easy to figure out the distance with a modified manhattan distance function

   auto findShortestPath(const Coordinate& childLocation) {
    auto tempPosition = Coordinate(abs(childLocation.first), abs(childLocation.second));
    auto numSteps = 0u;
    if(tempPosition.first < tempPosition.second) {
        while(tempPosition.first != 0) {
            tempPosition.first -= 5;
            tempPosition.second -= 5;
            numSteps++;
        }
        numSteps += tempPosition.second/10;

    }
    else {
        while(tempPosition.second >= 10) {
            tempPosition.first -= 5;
            tempPosition.second -= 5;
            numSteps++;
        }
        numSteps += tempPosition.first/5;
    }
    return numSteps;
}

Day 12

Type of Problem: Graph Theory

Difficulty: Medium

Rating: 4/5

Almost halfway through until our first Graph Theory problem. As with most graph problems, Djikstra’s Algorithm will suffice (and our input s pretty much an adjacency list), no need for an A* search. As far as finding the number of disjoint groups, you just find all the nodes that are connected, remove them from the list, and keep going until there are no more nodes

   auto getNodesConnected(const auto& connections, const std::string& start) {
    std::set<std::string> nodesSeen;
    std::deque<std::string> nodesToCheck;
    nodesToCheck.push_front(start);

    while(!nodesToCheck.empty()) {
        const auto& node = nodesToCheck.front();
        nodesToCheck.pop_front();
        if(nodesSeen.find(node) == nodesSeen.end()) {
            const auto& nextConnections = connections.at(node);
            std::copy(nextConnections.begin(), nextConnections.end(), std::back_inserter(nodesToCheck));
        }
        nodesSeen.insert(node);
    }
    return nodesSeen;
}

auto getGroups(auto connections) {
    auto numberOfGroups = 0u;
    while(!connections.empty()) {
        auto group = getNodesConnected(connections, connections.begin()->first);
        ++numberOfGroups;
        auto alreadySeen = [&group](const auto& connection) { return group.find(connection.first) != group.end(); };
        algo::erase_if(connections, alreadySeen);
    }
    return numberOfGroups;
}

Day 13

Type of Problem: Modular Arithmetic / Iteration

Difficulty: Medium

Rating: 3/5

This reminded me of the bus schedule problem a few years back and I was wondering if I would have to coordinate different modular systems, but lo and behold, I could be lazy and just count cycles seeing when I’d be able to pass.

Day 14

Type of Problem: Grid Manipulation

Difficulty: Medium

Rating: 3/5

I’m glad I had that dense hash function separate out previously, so that I could reuse it for this problem. Also, I’m not a fan of solutions that rely on previous day solutions (looking at you INTCODE), just because I don’t think they are as accessible for people picking and choosing problems that meet their fancy.

As far as the problem itself goes, it seemed pretty straightforward, but some bonus points for grouping regions. This is a common theme for grid manipulation problems, and I’ve always liked it. I also with I could rewrite my code with ranges to give it a true collection pipeline feel.

 auto getBitstring(const std::string& input) {
    auto range = algo::getNumericRange(0,SIZE);
    auto strings = algo::map(range, [input](int i) { return input + "-" + std::to_string(i);});
    auto knotHashes = algo::map(strings, crypto::calculateDenseHash );
    auto binaryStrings = algo::map(knotHashes, toBinaryString);
    return input::join(binaryStrings);
}

Day 15

Type of Problem: Iteration

Difficulty: Medium

Rating: 2/5

I feel like this problem was one where I hit, and then just stopped for a bit because it was not an interesting problem to me. All I have to say is that I’m super glad that C++ is fairly zippy, because my solution did not take a long time to run through 40 million checks. I also leveraged the fact that I didn’t have to divide by 4 and 8 (which is slow), and instead just looked for bit patterns to see if my values were a multiple of a power of 2.

 
unsigned int get_matching_pairs(unsigned int factorA, unsigned int factorB, unsigned int times,
                                unsigned int maskA = 0x0, unsigned int maskB = 0x0) {
    unsigned long generatorA = 516;
    unsigned long generatorB = 190;
    unsigned int count = 0u;
    for(auto _ = 0u; _ < times; ++_){
        do{
            generatorA = generatorA * factorA % 2147483647;
        } while((generatorA & maskA) != 0);
        do {
            generatorB = generatorB * factorB % 2147483647;
        } while((generatorB & maskB) != 0);
        if ((generatorA & 0xFFFF) == (generatorB & 0xFFFF)){
            ++count;
        }
    }
    return count;
}

Day 16

Type of Problem: Iteration / Optimization

Difficulty: Medium

Rating: 4/5

This was at least an interesting problem to me, especially after last one. I liked the idea of different dance steps, and how one dance transferred into the others. There was a good example earlier this year about having to track when you’ve seen cyclic patterns, and I mentioned that it’s always a good strategy when you have a billion iterations, and look! Lo and behold, this is just the case for keeping track of when I’ve seen a dance before (a dance is always deterministic to the next dance).

I think this might be my first usage of std::variant in C++ code ever, which ugly as it is, I prefer to inheritance for things that are not truly substitutable. Also props to rotate and swap for making this easy.

using Step = std::variant<Spin,Exchange,Partner>;

void dance_step(std::string& programs, const Step& step){
    std::visit(overloaded {
        [&programs](const Spin& spin){ std::rotate(programs.rbegin(), programs.rbegin()+spin.times, programs.rend()); },
        [&programs](const Exchange& exchange){ std::swap(programs[exchange.pos1], programs[exchange.pos2]); },
        [&programs](const Partner& partner){
            auto pos1 = programs.find(partner.program1);
            auto pos2 = programs.find(partner.program2);
            std::swap(programs[pos1], programs[pos2]);
        }
    }, step);
}

Day 17

Type of Problem: Iteration / Optimization

Difficulty: Medium-Hard

Rating: 4/5

Back to back optimization problems. Oof. Optimization problems I always consider hard, because it’s not typically enough to grab one of your usual tools, such as Djikstra, cycle detection, or dynamic programming. You have to understand the problem a lot better, and try to find the trick to minimize data structure reallocation. In this case, we are tracking hurricanes. The first part you could brute force with a pure circular buffer, but as soon as I saw 50 million iterations for part 2, I knew I couldn’t keep inserting into a cache-unfriendly data structure and get away with it.

So, instead, I kept track of where zero was and where my insert was at each stage. I didn’t have to track every number’s position relative to each other, just those two. I ended up with this algorithm:

class AngrySpinlockAlgorithm {

public:
    void insertNext() {
        lastPosition = ((SPINS + lastPosition) % numbersInserted) + 1;

        if (lastPosition == zeroPosition+1){
            valueAfterZero = numbersInserted;
        }
        if (lastPosition <= zeroPosition) {
            ++zeroPosition;
        }
        ++numbersInserted;
    }

    unsigned int getNumberAfterZero() {
        return valueAfterZero;
    }


private:
    unsigned int zeroPosition = 0;
    unsigned int lastPosition = 0;
    unsigned int numbersInserted = 1;
    unsigned int valueAfterZero = 0;

};

Day 18

Type of Problem: Computer Simulation

Difficulty: Medium

Rating: 5/5

I know INTCODE gets a lot of flak, but I love computer simulations. This one was cool, as it it immediately made me think of Elixir message-passing. The first half was pretty easy, as it was just simple tracking of registers and simple conditional logic. However, the second half was a nice twist, as the snd and rcv are send and receive, not sound and recover.

The trick is to build computers that can be paused and wait on signalling. I made a base class to handle both SoundComputer and MessagingComputer, and let the snd/rcv instructions be virtual. The only other trick was detecting when both computers were deadlocked, which I did with this code

void rcv(const Rcv& rcv) {
        if(messages.empty()){
            waiting = true;
            if (partner && partner->waiting){
                halted = true;
                partner->halted = true;
            }
        }
        else {
            registers[rcv.registerName] = messages.front();
            messages.pop();
            ++instructionPointer;
        }
    }

Day 19

Type of Problem: Simulation

Difficulty: Medium

Rating: 5/5

This was another fun problem, back to back with the last one. You have to parse a giant map of railways and track intersections. As long as you treat it as a giant grid, it’s not too bad, but then you have to find your way through the network, while tracking the number of steps and which intersections you hit.


Day 20

Type of Problem: 3d Simulation

Difficulty: Hard

Rating: 3/5

There is typically one problem during the last week which is the hardest of the year. For 2017, this was Day 20. As a matter of fact, this is the one that I stopped doing in 2017, and I just picked it back up this year. You are simulating particles as they move about in 3d space, trying to figure out which one is closest to the origin after an infinite amount of time.

Obviously, you can’t wait an infinite amount of time, so you have to figure out how they tend until time. There are three big tricks I utilized for this. 1) The way I did this was to run until all particles are moving away from the origin (when their velocity, position, and acceleration have the same sign). This means that every particle is never going to get closer at this point. 2), you can calculate when any two particles intersect and determine which one is closer one tick later by using quadratic formula shenanignas. 3) you can use an equation figure out the exact position of a particle at any given time ( I first tried to do it with continuous calculus, but with discrete math, the equation is a bit different). Here’s some code showing off the tricks

XYZ getPositionAtTime(uint64_t time) const{
        // 1/2 at^2 + (v0 + a) t + -V0 P0
        return {
            static_cast<int64_t>((0.5 * this->acc.x * time*time) + (this->startingVel.x + .5 * this->acc.x)*time + this->startingPos.x),
            static_cast<int64_t>((0.5 * this->acc.y * time*time) + (this->startingVel.y + .5 * this->acc.y)*time + this->startingPos.y),
            static_cast<int64_t>((0.5 * this->acc.z * time*time) + (this->startingVel.z + .5 * this->acc.z)*time + this->startingPos.z)
        };
}


std::optional<int> getLargestQuadraticSolution(int64_t acc1, int64_t acc2, int64_t startingVel1, int64_t startingVel2, int64_t startingPos1, int64_t startingPos2, uint64_t time){
    auto a = 0.5*acc1 - 0.5*acc2;
    auto b = (startingVel1 + .5*acc1) - (startingVel2 + .5*acc2);
    auto c = startingPos1 - startingPos2;

    auto determinant = b*b - 4*a*c;
    if(determinant < 0){
        return {};
    }

    auto answer1 = (-1*b + sqrt(determinant)) / (2*a);
    if (determinant == 0){
        return {answer1};
    }

    auto answer2 = (-1*b - sqrt(determinant)) / (2*a);
    return {std::max(answer1, answer2)};
}

uint64_t getIntersectionTimeFloor(const Particle& particle2) const{
        // ax^2 + bx + c - solve both equations
        assert(this->time == particle2.time);
        auto xTime = getLargestQuadraticSolution(this->acc.x, particle2.acc.x, this->startingVel.x, particle2.startingVel.x, this->startingPos.x, particle2.startingPos.x, this->time);
        auto yTime = getLargestQuadraticSolution(this->acc.y, particle2.acc.y, this->startingVel.y, particle2.startingVel.y, this->startingPos.y, particle2.startingPos.y, this->time);
        auto zTime = getLargestQuadraticSolution(this->acc.z, particle2.acc.z, this->startingVel.z, particle2.startingVel.z, this->startingPos.z, particle2.startingPos.z, this->time);

        return std::max({floor(xTime.value_or(this->time)), floor(yTime.value_or(this->time)), floor(zTime.value_or(this->time))});

}

Day 21

Type of Problem: Grid Manipulation

Difficulty: Medium-Hard

Rating: 4/5

This reminded me of one of my favorite AoC challenges (the one about finding sea monsters in tiles), but it unfortunately wasn’t quite as fun. In this challenge, you are repeatedly zoom-and-enhance a set of tiles, using a set of predefined rules.

The first twist is that you have to account for flips and rotates, but thanks to previous challenges, I knew that there are only 8 ways to rotate/flip an image, so I just added 8 different images to a lookup map at a time.

The other trick was realizing that when you change a 2×2 into a 3×3, it still might be divisible by 4 ( say if you have 12 blocks across). You also need to make sure you have a way to split out and reconstitute blocks (which was not straightforward in my code; it was quite ugly)

Blocks transform(const Blocks& pattern, const RulesMapping& rulesMapping) {
    Blocks out;
    auto subblockSize = std::distance(pattern.begin()->begin(), pattern.begin()->begin() + pattern.begin()->find("/"));
    auto bigBlockSize = static_cast<int>(sqrt(pattern.size()) * subblockSize);
    auto blocksPerRow = bigBlockSize / subblockSize;

    for(size_t rowIndex=0; rowIndex<pattern.size(); rowIndex += blocksPerRow){
        Blocks topRow;
        Blocks bottomRow;
        for(int blockIndex=0; blockIndex < blocksPerRow; ++blockIndex){

            auto newBlocks = rulesMapping.at(pattern[rowIndex+blockIndex]);
            topRow.push_back(newBlocks[0]);
            if(newBlocks.size() == 4) {
                topRow.push_back(newBlocks[1]);
                bottomRow.push_back(newBlocks[2]);
                bottomRow.push_back(newBlocks[3]);
            }
        }
        out.insert(out.end(), topRow.begin(), topRow.end());
        out.insert(out.end(), bottomRow.begin(), bottomRow.end());
    }
    return recombine(out);
}

Day 22

Type of Problem: Grid Manipulation

Difficulty: Medium

Rating: 4/5

Day 22 had us checking how a virus moves about in a grid as it changes states of a node. It kinda reminded me of a 2-dimensional Turing machine. The directions were pretty clear (which I appreciate, as sometimes these sort of problems have super complicated rules).

The big trick here is not to store the entire grid. Instead, you can just store values in a set for each state (Your biggest state, such as clean nodes, don’t have to be stored, as you can just make sure that point doesn’t show up in any of the other sets)

 for(unsigned int iterations=0; iterations < numberOfMoves; ++iterations){
        bool isInfected = infected.find(virusPosition) != infected.end();
        bool isWeakened = weakened.find(virusPosition) != weakened.end();
        bool isFlagged = flagged.find(virusPosition) != flagged.end();

        if(!isInfected && !isWeakened && !isFlagged){
            virusDirection = turnLeft(virusDirection);
            weakened.insert(virusPosition);
        }
        else if(isWeakened) {
            numberOfActiveBursts++;
            weakened.erase(virusPosition);
            infected.insert(virusPosition);
        }
        else if(isInfected) { 
            virusDirection = turnRight(virusDirection);
            infected.erase(virusPosition);
            flagged.insert(virusPosition);
        }
        else if(isFlagged) {
            virusDirection = reverse(virusDirection);
            flagged.erase(virusPosition);
        }

        virusPosition = move(virusPosition, virusDirection);

    }

Day 23

Type of Problem: Computer Simulation / Reverse Engineering

Difficulty: Medium-Hard

Rating: 5/5

I’m really glad that I’ve been doing The Art Of Computer Programming, as it helps out my assembly reading. Today’s challenge was all about finding out how many times a single instruction was run. I coded up the computer, but unfortunately, it took a super long time to run. So, I had to reverse engineer the assembly/.

The way I reverse engineer is I take a few passes. The first pass is commenting every line to write what’s happening in plain language. Then I mark which variables are const for a certain scope, and I start to write the code as equations (for example, if I see set d g and then mul d e, I can instead just say d=g*e. Then I start looking for higher level constructs, like a while loop, if statements, and do while loops. After writing this out, you can see what the code does in pseudocode. For this, I could see that the code was checking for composite numbers, which made it really easy to analyze just how many multiplications would be needed.


Day 24

Type of Problem: Graph Theory

Difficulty: Medium

Rating: 5/5

Whelp, another Djikstra’s Algorithm to the rescue. We’re matching bridges together (I first thought it might be a dynamic programming problem, and it probably could have been, but my code ran in a few seconds, so it’s fine). When measuing costs, the first half was just checking max strength, and the second one was just checking a pair of {longest/strongest}.

unsigned long getLongestStrongestBridge(std::span<Connector> connectors) {

    auto isCandidateLessThan = [](const auto& candidate1, const auto& candidate2){
        return std::get<1>(candidate1) < std::get<1>(candidate2);
    };
 
    std::priority_queue<NewCandidate, std::vector<NewCandidate>, decltype(isCandidateLessThan)> candidates;
    candidates.push(NewCandidate{0, 0, 0, {connectors.begin(), connectors.end()}});
    std::pair<unsigned long, unsigned long> longestAndStrongest {0, 0};
    while(!candidates.empty()) {
        auto [bridge, length, strength, remaining] = candidates.top();
        candidates.pop();

        auto matches = remaining | std::views::filter([bridge](const auto& c){
            return c.side1 == bridge || c.side2 == bridge;
        });
        
        for(const auto& match : matches){
            std::vector<Connector> newRemaining{remaining};
            newRemaining.erase(std::ranges::find(newRemaining, match));
            unsigned long newBridge = (bridge == match.side1) ? match.side2 : match.side1;
            unsigned long newStrength = strength + match.getStrength();
            longestAndStrongest = std::max(longestAndStrongest, std::make_pair(length + 1, newStrength));
            candidates.emplace(newBridge, length + 1, newStrength, newRemaining);
        }
    }

    return longestAndStrongest.second;
}

Day 25

Type of Problem: Computer Simulation

Difficulty: Medium-Easy

Rating: 5/5

Merry Christmas, we’re simulating a Turing Machine. This was super straight-forward, and instead of keeping a list in memory of all the zeros and ones, you can just track indices of ones in a set. If an index is not in the set, then its a zero, otherwise a one.

 void run() { 
        char state = startingState;
        int position = 0;
        for(unsigned int counter=0;  counter<numberOfSteps; ++counter){
            auto [ifZero, ifOne] = stateToActionMapping[state];
            auto action = (oneValues.find(position) == oneValues.end()) ? ifZero : ifOne;
            if(action.toWrite == '1'){
                oneValues.insert(position);
            }
            else {
                oneValues.erase(position);
            }
            position += (action.direction == Direction::Left) ? -1 : 1;
            state = action.nextState;
        }
    }

Wrap-up

I was glad to finish this in 2022. It’s been 5 years, and while I started it to try to limit raw loops and use C++17, C++20 has come out in the meantime. I didn’t use C++20 as much, but I did learn a lot in how to write better C++. The code is uglier, and more verbose than say, Python. But, it’s way better than C++03 (or even 17).

And that wraps up my 2017 effort. With 2022 in the bag as well (post coming soon), I’m at 364 stars, which is 4 higher than my goal for the year. Hopefully next year I can knock out another 16 or so additional stars, which will put me just 20 shy of all stars!

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s