AdventOfCode2017 Day 3

So this day was a tad bit rougher.  I wasn’t expecting the sudden difficulty increase on day 3.  The problems were straight-forward enough, but I didn’t want to brute force my way through them.  Unfortunately, I didn’t get the math worked out, so brute force became one of my last options

However, on the bright side, I got to play with std::optional, so I got that going for me.

 

I’m going to have a tough time explaining the problem any better than advent of code, so I’m just going to link you there instead

Here’s the entirety of the code (I’ll break it down after)


#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <tuple>
#include <vector>

using Position = std::pair<int, int>;

auto getWidth(unsigned int level) {
    return 2 * level + 1;
}

auto getTargetLevel(unsigned int target) { 
    auto level = 1u;
    auto ret = std::make_pair(1u, 1u);
    while(target > ret.second)
    {
        const auto numbers = 4*getWidth(level) - 4;
        ret = std::make_pair(ret.second+1, ret.second+numbers);
        ++level;
    }
    return std::make_tuple(level, ret.first, ret.second);
}

auto getNumberOfSteps(unsigned int target){
    const auto [level, min, max] = getTargetLevel(target);
    const auto width = getWidth(level);

    auto distanceToMidpoint = [target, level](auto n1, auto n2) { return abs((n1 + n2)/2 - target) + level; };
    
    const auto lowerLeft = (max - width + 1 ); 
    if (target >= lowerLeft) {
        return distanceToMidpoint(max, lowerLeft);
    }

    const auto upperLeft = (lowerLeft - width + 1);
    if (target >= upperLeft) {
        return distanceToMidpoint(upperLeft, lowerLeft);
    }

    const auto upperRight = (upperLeft - width + 1);
    if (target >= upperRight) {
        return distanceToMidpoint(upperRight, upperLeft);
    }
    
    return distanceToMidpoint(min-1, upperRight);     
}

Position addPairs(Position p1, Position p2) {
    return Position(p1.first + p2.first, p1.second + p2.second);
}

class LookupCache {
public:
    explicit LookupCache(unsigned int target) : target(target) {
        cache[Position(0, 0)] = 1;
    }

    auto calculate(auto p) {
        auto addPairLookup = [p, this](auto sum, auto m){ return sum + lookup(addPairs(p,m));};
        const auto sum = std::accumulate(modifiers.begin(), modifiers.end(), 0u, addPairLookup);
        if (sum > target && !answer.has_value()) {
            answer = sum;
        }
        cache[p] = sum;
        return sum;
    }

    auto hasReachedTarget() const {
        return answer.has_value();
    }

    auto getAnswer() const {
        return answer.value_or(0u);
    }
    
private:

    unsigned int lookup(auto p) const{
        const auto match = cache.find(p);
        return (match == cache.end()) ? 0 : match->second;
    }

    std::map<Position, unsigned int> cache;
    const unsigned int target;
    std::optional<unsigned int> answer;
    const std::vector<Position> modifiers = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };
};

class PositionIterator {
public:
    explicit PositionIterator(LookupCache& lookupCache) : lookupCache(lookupCache) {}

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

    void updatePosition(Direction direction) {
        switch (direction) {
            case Direction::RIGHT: position.first++; break;
            case Direction::UP: position.second--; break;
            case Direction::LEFT: position.first--; break;
            case Direction::DOWN: position.second++; break;
        }
    } 

    void move(Direction direction, unsigned int numberOfTimes=1) {
        for(int i = 0; i < numberOfTimes; ++i){
            updatePosition(direction);
            lookupCache.calculate(position);
        }
    }

private:
    LookupCache & lookupCache;
    Position position = Position(0,0);
};

auto findNextLargestCumulativeValueWritten(unsigned int target) {
    LookupCache lookupCache(target);
    PositionIterator position(lookupCache);

    auto level = 1u;
    while(!lookupCache.hasReachedTarget()) {
        const auto width = getWidth(level);
        position.move(PositionIterator::Direction::RIGHT);
        position.move(PositionIterator::Direction::UP, width - 2);
        position.move(PositionIterator::Direction::LEFT, width - 1);
        position.move(PositionIterator::Direction::DOWN, width - 1);
        position.move(PositionIterator::Direction::RIGHT, width - 1);
        level++;
    }

    return lookupCache.getAnswer();
}

int main() {
    auto steps = getNumberOfSteps(325489);
    std::cout << steps << "\n";

    auto answer = findNextLargestCumulativeValueWritten(325489);
    std::cout << answer << "\n";
    
    return 0;
}

 

So first up, for the first half of the problem, we needed to find out the Manhattan Distance from a certain number back to the center.  I first found out what level it was on (by level, I mean : 1 is the first level, 2 is the 8 numbers surrounding 1, 3 is the 20 numbers surrounding those, etc).  The amount of number in each ring is 4*side_length_of_square – 4 (subtract out the corners, since they get counted twice)


auto getTargetLevel(unsigned int target) { 
    auto level = 1u;
    auto ret = std::make_pair(1u, 1u);
    while(target > ret.second)
    {
        const auto numbers = 4*getWidth(level) - 4;
        ret = std::make_pair(ret.second+1, ret.second+numbers);
        ++level;
    }
    return std::make_tuple(level, ret.first, ret.second);
}

Once I have the level, as well as the minimum and maximum number that can be represented on that level, I can figure out just what side it is on.  From there, I calculate distance to the midpoint of that side length, and then just go straight on in towards the center


auto getNumberOfSteps(unsigned int target){
    const auto [level, min, max] = getTargetLevel(target);
    const auto width = getWidth(level);

    auto distanceToMidpoint = [target, level](auto n1, auto n2) { return abs((n1 + n2)/2 - target) + level; };
    
    const auto lowerLeft = (max - width + 1 ); 
    if (target >= lowerLeft) {
        return distanceToMidpoint(max, lowerLeft);
    }

    const auto upperLeft = (lowerLeft - width + 1);
    if (target >= upperLeft) {
        return distanceToMidpoint(upperLeft, lowerLeft);
    }

    const auto upperRight = (upperLeft - width + 1);
    if (target >= upperRight) {
        return distanceToMidpoint(upperRight, upperLeft);
    }
    
    return distanceToMidpoint(min-1, upperRight);     
}

 

For part 2, I couldn’t just use straight-up math to jump ahead a few levels (I’m sure it exists, I just didn’t figure it out).  I tried looking for a dynamic programming algorithm, but I couldn’t figure out how to traverse the graph in the correct order.  So, instead, I created a loop that did the spiral for me.


auto findNextLargestCumulativeValueWritten(unsigned int target) {
    LookupCache lookupCache(target);
    PositionIterator position(lookupCache);

    auto level = 1u;
    while(!lookupCache.hasReachedTarget()) {
        const auto width = getWidth(level);
        position.move(PositionIterator::Direction::RIGHT);
        position.move(PositionIterator::Direction::UP, width - 2);
        position.move(PositionIterator::Direction::LEFT, width - 1);
        position.move(PositionIterator::Direction::DOWN, width - 1);
        position.move(PositionIterator::Direction::RIGHT, width - 1);
        level++;
    }

    return lookupCache.getAnswer();
}

 

I created two classes to help me out here – a PositionIterator that kept track of where I was using an X,Y coordinate system (the center is 0,0), and a LookupCache, that calculated the new position for each coordinate based on adjacent coordinates, and saved it for later (memoization for the win).

 

Here’s the position iterator (nothing fancy here other than an enum class)



class PositionIterator {
public:
    explicit PositionIterator(LookupCache& lookupCache) : lookupCache(lookupCache) {}

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

    void updatePosition(Direction direction) {
        switch (direction) {
            case Direction::RIGHT: position.first++; break;
            case Direction::UP: position.second--; break;
            case Direction::LEFT: position.first--; break;
            case Direction::DOWN: position.second++; break;
        }
    } 

    void move(Direction direction, unsigned int numberOfTimes=1) {
        for(int i = 0; i < numberOfTimes; ++i){
            updatePosition(direction);
            lookupCache.calculate(position);
        }
    }

private:
    LookupCache & lookupCache;
    Position position = Position(0,0);
};

 

The LookupCache on the other hand was a bit more interesting.  It contains the logic to calculate adjacent values (by storing a modifiers coordinate list, and applying each of those to the current pair), as well as storing the answer when it comes across it.  I liked using a std::optional here, since the variable should be “empty” until I find an answer



class LookupCache {
public:
    explicit LookupCache(unsigned int target) : target(target) {
        cache[Position(0, 0)] = 1;
    }

    auto calculate(auto p) {
        auto addPairLookup = [p, this](auto sum, auto m){ return sum + lookup(addPairs(p,m));};
        const auto sum = std::accumulate(modifiers.begin(), modifiers.end(), 0u, addPairLookup);
        if (sum > target && !answer.has_value()) {
            answer = sum;
        }
        cache[p] = sum;
        return sum;
    }

    auto hasReachedTarget() const {
        return answer.has_value();
    }

    auto getAnswer() const {
        return answer.value_or(0u);
    }
    
private:

    unsigned int lookup(auto p) const{
        const auto match = cache.find(p);
        return (match == cache.end()) ? 0 : match->second;
    }

    std::map cache;
    const unsigned int target;
    std::optional answer;
    const std::vector modifiers = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };
};

 

 

Alright, that’s it for me.  Let me know if you have any questions.  For now, I’m 30 minutes away from the Day 4 problem.  I hope it isn’t as hard.

 

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s