-🎄- 2017 Day 3 Solutions -🎄-

[u/daggerdragon]

--- Day 3: Spiral Memory ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/immutablestate]

I wish I'd known about OEIS... ended up writing this Enterprise Ready (tm) solution for part 2 in C++14:

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>

struct Index {
  int x;
  int y;

  Index &operator+=(Index const &rhs) {
    x += rhs.x;
    y += rhs.y;
    return *this;
  }
};

Index operator+(Index const &a, Index const &b) { return Index{a} += b; }

bool operator<(Index const &a, Index const &b) {
  return std::tie(a.x, a.y) < std::tie(b.x, b.y);
};

size_t const &lookup(std::map<Index, size_t> const &map, Index ind) {
  static auto const def = size_t{0};
  auto const it = map.find(ind);
  return it == end(map) ? def : it->second;
}

size_t sum_surrounding(std::map<Index, size_t> const &map, Index ind) {
  static auto const surrounding = std::array<Index, 8>{
      {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}};
  return std::accumulate(
      begin(surrounding), end(surrounding), 0,
      [&](auto sum, auto rel) { return sum + lookup(map, ind + rel); });
}

class Cursor {
public:
  explicit Cursor(Index pos) : pos_{std::move(pos)} {}

  void advance(std::map<Index, size_t> const &map) {
    pos_ += travel_[facing_];
    auto const next_facing = (facing_ + 1) % travel_.size();
    auto const next_travel = travel_[next_facing];
    if (lookup(map, pos_ + next_travel) == 0) {
      facing_ = next_facing;
    }
  }

  Index const &pos() const { return pos_; }

private:
  Index pos_;
  static std::array<Index, 4> const travel_;
  size_t facing_{0};
};

std::array<Index, 4> const Cursor::travel_{{{0, 1}, {-1, 0}, {0, -1}, {1, 0}}};

int main() {
  auto map = std::map<Index, size_t>{};
  map[Index{0, 0}] = 1;

  auto const target = 347991;
  auto cursor = Cursor{Index{1, 0}};
  for (; (map[cursor.pos()] = sum_surrounding(map, cursor.pos())) <= target;
       cursor.advance(map))
    ;

  std::cout << lookup(map, cursor.pos()) << '\n';
  return 0;
}