Last active
December 14, 2016 00:28
-
-
Save willkill07/ed0322631db2daba959383399c6d0016 to your computer and use it in GitHub Desktop.
Advent of Code Day 13 C++14
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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