Skip to content

Instantly share code, notes, and snippets.

@willkill07
Last active December 14, 2016 00:28
Show Gist options
  • Save willkill07/ed0322631db2daba959383399c6d0016 to your computer and use it in GitHub Desktop.
Save willkill07/ed0322631db2daba959383399c6d0016 to your computer and use it in GitHub Desktop.
Advent of Code Day 13 C++14
#include <iostream>
#include <string>
#include <array>
#include <map>
#include <set>
// A point is just an array of two elements
using Point = std::array<int, 2>;
// We need to add two points to make a new point, so let's write operator+
inline Point operator+(const Point& p1, const Point& p2) {
return {{std::get<0>(p1) + std::get<0>(p2), std::get<1>(p1) + std::get<1>(p2)}};
}
// usage: ./Day13 <number> <1|2>
int main(int argc, char* argv[]) {
// only solve one part at a time
const bool part2{std::stoi(argv[2]) == 2};
// go until we reach limit; read number for maze generation from stdin
const int LIMIT{50}, NUM{std::stoi(argv[1])};
// we can possibly go left, right, up, or down
const std::array<Point, 4> DIRS{{{{-1, 0}}, {{1, 0}}, {{0, -1}}, {{0, 1}}}};
const Point INIT{{1, 1}}, TARGET{{39, 31}};
auto valid = [NUM](const Point& p) -> bool {
// valid if >= 0 and not a wall -- optimize computation by minimizing multiplications
return p[0] >= 0 && p[1] >= 0 && !(__builtin_popcount(p[1] * (p[1] + 3) + p[0] * (p[1] + p[1] + p[0] + 1) + NUM) & 0x1);
};
int steps{0};
// queue starts at initial position
std::set<Point> queue{{INIT}}, seen{queue}, next;
// while we can search AND (if part 1: continue until TARGET seen) (if part 2: continue until LIMIT reached)
while (queue.size() != 0 && (part2 || !seen.count(TARGET)) && (!part2 || steps != LIMIT)) {
// check all positions in queue
for (const auto& q : queue)
// iterate across all directions
for (const auto& d : DIRS)
// if new position is valid and has not been seen, queue it up and add it to seen
if (valid(q + d) && !seen.count(q + d))
next.emplace(q + d), seen.emplace(q + d);
// next queue becomes current queue; increment step count
next.swap(queue), next.clear(), ++steps;
}
// since a solution must exist, steps will tell us how far away the target is for part 1
// and the number of elements in the seen set will tell us our coverage for part 2
std::cout << (part2 ? seen.size() : steps) << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment