AdventOfCode2017 Days 1 and 2

It’s December and you know what that means!  Advent Of Code is back!.

This year, I’m not going to try the 25 languages in 25 days, but instead focus on my C++ skills.  More specifically, here are the constraints I am putting on myself.

  • Use C++17 where I can if it makes sense
  • Avoid raw loops on containers unless I have a performance concern
  • If there are any raw loops needed, see if it can be abstracted into a generic algorithm

So Challenge 1: here we go.

Challenge 1

The first challenge always feels like a warm-up.  In this case, given a set of numbers, we wanted to sum up all numbers where the next number was identical to it (the second half of the challenge was the next n/2 number, where n is the size of numbers).  In this case, I decided to do something a bit more general.


#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>

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

//a raw loop probably is way more readable in this case, since you loop indexes and (compare index+distance) % size
//however, I wanted to see what it would be like without raw loops in the code
//So, I'm instead rotating a copy by the distance, zipping the strings into a pair, and accumulating any pairs that match

auto getSum(const std::string &input, size_t distance=1) {
    auto next = input;
    std::rotate(next.rbegin(), next.rbegin() + distance,  next.rend());

    auto zipped = algo::zip(input, next);
    auto addValueIfMatching = [](auto sum, auto zipPair) { return sum + ( zipPair.first == zipPair.second ? zipPair.first - '0' : 0); };
    return std::accumulate(zipped.begin(), zipped.end(), 0u, addValueIfMatching);
}

int main() {
    auto input = input::readSingleLineFile("input/input01.txt");
    std::cout << getSum(input) << "\n";
    std::cout << getSum(input, input.size()/2) << "\n";
    return 0;
}

So I know that it is probably more readable to loop through indices, then just check the value at (number + index_to_advance) % size_of_numbers.  But I’m trying to avoid raw loops.

In this code, I’m made a library for reading input from a single file (because I knew I’d need it again).  Then I take that string, make a copy, rotate to the right however much the problem calls for it (1 for the first half of the problem, size/2 for the second half of the problem).  Then I just zip up the original input and the rotated, and then accumulate through the pairs, only adding them if they match.

I got to use a lambda for the addValueIfMatching function, and a little bit of auto type deduction, but most of the C++ 11/14/17 comes from the zip function.


auto zip(auto container1, auto container2) {
        auto iter1 = container1.begin();
        auto iter2 = container2.begin();

        using TypePair = std::pair;
        std::vector<TypePair> out;
        while(iter1 != container1.end() && iter2 != container2.end()) {
            out.emplace_back(*iter1++, *iter2++);
        }
        return out;
    }  

Here’s where it gets fun.  I can start using auto deduction for parameters and return values, and not have to worry about any template mess (that happens under the hood still though, but I’m finding this a lot easier to write).

First I get an iterator to each collection.  Then I set up a new vector to store the results in.  This took me a little bit to get, since I’m new to decltype and all that fun stuff.  I needed to find a way to create a pair of the types.  So I decltype to find what the type of the iterators are, and then just get their value_type (so an iterator would return just int).

Now that I have a pair, it is trivial to iterate through the two containers and just emplace the pair into my out vector

Challenge 2

Challenge 2 was not too bad either.  Given rows of numbers, find the difference between max and min of and sum them up.  The second half was find the two numbers that are evenly divisible and sum up their quotients.

So I knew I wanted to have a general algorithm -> read each line as a vector of numbers, perform an operation, and sum it up.

Here’s the code I have :


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

#include <algorithm>
#include <iostream<
#include <numeric<

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

auto getEvenlyDivisible(const std::vector<int>& numbers) { 
    auto pairs = algo::find_matching_pairs(numbers, [](auto num1, auto num2) { return num1 % num2 == 0; });
    assert(pairs.size() == 1);
    return pairs[0].first / pairs[0].second;
}

auto getSumOfRowOperations(auto numbers, auto rowOperation){
    auto rowValues = algo::map(numbers, rowOperation);
    return std::accumulate(rowValues.begin(), rowValues.end(), 0u);
}

int main() {
    auto numbers = algo::map(input::readMultiLineFile("input/input02.txt"), input::toNumbers);
    std::cout << getSumOfRowOperations(numbers, getDifference) << "\n";
    std::cout << getSumOfRowOperations(numbers, getEvenlyDivisible) << "\n";
}

I got to use std::minmax_element (in conjunction with structured binding) for the first time to easily find the difference of elements.

From there, I can just map over my input to get the difference, and it’s another simple accumulate away to get an answer.

Getting the second half of the challenge was a bit trickier.  I had to write an algorithm that would give me a set of matching pairs of elements.



    auto find_matching_pairs(auto container, auto filterOperation) {
        using ContainerType = typename decltype(container.begin())::value_type; 
        std::vector<std::pair<ContainerType, ContainerType>> out;
        for (auto iter1 = container.begin(); iter1 != container.end(); ++iter1) {
            for(auto iter2 = iter1+1; iter2 != container.end(); ++iter2) {
                if (filterOperation(*iter1, *iter2)){
                    out.emplace_back(*iter1, *iter2);
                } 
                if (filterOperation(*iter2, *iter1)) {
                    out.emplace_back(*iter2, *iter1);
                }
            }
        }
        return out;
    }

Once I had the matching pairs, it was easy to make sure that I only had one element in the match and figure out the quotient.

Lastly, I used a mapping function (since I feel transform is a little more clunky)


    auto map(auto container, auto rowOperation) {
        using ContainerType = typename decltype(container.begin())::value_type; 
        using ReturnType = typename std::invoke_result_t<decltype(rowOperation), ContainerType>;
        std::vector<ReturnType> v;
        std::transform(container.begin(), container.end(), std::back_inserter(v), rowOperation);
        return v;
    }

So that’s it for the first two days.  As expected, lambdas abound, but I also got to play with minmax_element, decltype, and some more advanced generic programming.

Stay tuned for the next ones!

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 )

w

Connecting to %s