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()) {
}
cache[p] = sum;
return sum;
}

auto hasReachedTarget() const {
}

}

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

}

int main() {
auto steps = getNumberOfSteps(325489);
std::cout << steps << "\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++;
}

}

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()) {
}
cache[p] = sum;
return sum;
}

auto hasReachedTarget() const {
}

}

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;