AdventOfCode2017 Day 5 and 6

Another two days down, no sweat (minus a segfault on day 6, but shhhh.)

Day 5’s challenge was to take a list of jump offsets and determine how many jumps you need to take before exiting the block of code (modifying the jump offsets each time)

Day 6’s challenge was to take a list of memory banks, run through a balancing algorithm regarding allocations, and count how many steps until an infinite loop.

Let’s take a look at the code, as they clock in at <40 lines apiece.

Day 5:


#include <iostream>
#include <string>

#include "algo.h"
#include "input.h"

auto getStepsPart1(auto numbers) {
    auto index = 0u;
    auto steps = 0u;
    while(index < numbers.size()) {
        index += numbers[index]++;
        steps++;
    }
    return steps;
}

auto getStepsPart2(auto numbers) {
    auto index = 0u;
    auto steps = 0u;
    while(index = 3)  ? -1 : 1;
        auto old_index = index;
        index += numbers[old_index];
        numbers[old_index] += modifier;
        steps++;
    }
    return steps;
}

int main() {
    auto numbers = algo::map(input::readMultiLineFile("input/input05.txt"), input::toNumber);
    std::cout << getStepsPart1(numbers) << "\n";
    std::cout << getStepsPart2(numbers) << "\n";
    return 0;
}

For the first part, every jump went up by 1 during each jump, and for the second part, you had to check if the jump offset was greater than 3, in which case you either added one or subtracted one from the offset.  Most of my code is just a while loop, that does some straight-forward calculations (check if we are out of bounds, modify the jump offset and move an instruction pointer.  Not much to see here.

Day 6:

Day 6 took me a little while longer, as I had to write a new common algorithm for use, and I ran into a segfault since I wasn’t passing a container by value (silly me).


#include <algorithm>
#include <assert.h>
#include <iostream>
#include <vector>

#include "algo.h"
#include "input.h"

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);
    
}

int main() {
    auto numbers = input::toNumbers(input::readSingleLineFile("input/input06.txt"));
    
    auto answer = getNumberOfTimesBeforeSeeingDuplicates(numbers);
    std::cout << answer.first << " " << answer.second << "\n";
    
    return 0;
}

The main idea here is to keep track of everything you’ve seen using a vector (I originally used a set, but part 2 required me to keep things in order of insertion, so a vector was needed).  Whenever I hit a set of values I’ve seen before, I know that I’m in for an infinite loop.

During each loop, I find the maximum element, zero it out, and then just cycle around adding 1.

Let’s take a look at apply_cyclically


auto apply_cyclically(auto &container, auto current, size_t numberOfTimes, auto operation) {
        while(numberOfTimes-- != 0) {
            if(current == container.end()) {
                current = container.begin();
            }

            operation(*current);
            current++;
        }
    }

Given a container, and an iterator in that container, apply the function a certain number of times, rotating back to the beginning if I reach the end (here’s where I had my segmentation fault btw – as I forgot to pass by reference, which means the copy of my container had a different end pointer than what my “Current” iterator was)

 

And that was it.  Another two quick problems.  I’m glad I’m slowly building up a library of functions that I can use (It’d be terrible if I had to keep writing the same input functions again and again). It will be interesting to see what the next ones shape up to be.

 

Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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