Day 20: Race Condition
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 
2 points
C++ / Boost
Ah, cunning - my favourite one so far this year, I think. Nothing too special compared to the other solutions - floods the map using Dijkstra, then checks “every pair” for how much of a time saver it is. 0.3s on my laptop; it iterates through every pair twice since it does part 1 and part 2 separately, which could easily be improved upon.
spoiler
#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_map.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <cstddef>
#include <fstream>
#include <limits>
#include <queue>
#include <stdexcept>
namespace {
using Loc = std::pair<int, int>;
using Dir = std::pair<int, int>;
template <class T>
using Score = std::pair<size_t, T>;
template <class T>
using MinHeap = std::priority_queue<Score<T>, std::vector<Score<T>>, std::greater<Score<T>>>;
using Map = boost::unordered_flat_set<Loc>;
auto operator+(const Loc &l, const Dir &d) {
return Loc{l.first + d.first, l.second + d.second};
}
auto manhattan(const Loc &a, const Loc &b) {
return std::abs(a.first - b.first) + std::abs(a.second - b.second);
}
auto dirs = std::vector<Dir>{
{0, -1},
{0, 1 },
{-1, 0 },
{1, 0 }
};
struct Maze {
Map map;
Loc start;
Loc end;
};
auto parse() {
auto rval = Maze{};
auto line = std::string{};
auto ih = std::ifstream{"input/20"};
auto row = 0;
while (std::getline(ih, line)) {
for (auto col = 0; col < int(line.size()); ++col) {
auto t = line.at(col);
switch (t) {
case 'S':
rval.start = Loc{col, row};
rval.map.insert(Loc{col, row});
break;
case 'E':
rval.end = Loc{col, row};
rval.map.insert(Loc{col, row});
break;
case '.':
rval.map.insert(Loc{col, row});
break;
case '#':
break;
default:
throw std::runtime_error{"oops"};
}
}
++row;
}
return rval;
}
auto dijkstra(const Maze &m) {
auto unvisited = MinHeap<Loc>{};
auto visited = boost::unordered_flat_map<Loc, size_t>{};
for (const auto &e : m.map)
visited[e] = std::numeric_limits<size_t>::max();
visited[m.start] = 0;
unvisited.push({0, {m.start}});
while (!unvisited.empty()) {
auto next = unvisited.top();
unvisited.pop();
if (visited.at(next.second) < next.first)
continue;
for (const auto &dir : dirs) {
auto prospective = Loc{next.second + dir};
if (!visited.contains(prospective))
continue;
auto pscore = next.first + 1;
if (visited.at(prospective) > pscore) {
visited[prospective] = pscore;
unvisited.push({pscore, prospective});
}
}
}
return visited;
}
using Walk = decltype(dijkstra(Maze{}));
constexpr auto GOOD_CHEAT = 100;
auto evaluate_cheats(const Walk &walk, int skip) {
auto rval = size_t{};
for (auto &start : walk) {
for (auto &end : walk) {
auto distance = manhattan(start.first, end.first);
if (distance <= skip && end.second > start.second) {
auto improvement = int(end.second) - int(start.second) - distance;
if (improvement >= GOOD_CHEAT)
++rval;
}
}
}
return rval;
}
} // namespace
auto main() -> int {
auto p = parse();
auto walk = dijkstra(p);
BOOST_LOG_TRIVIAL(info) << "01: " << evaluate_cheats(walk, 2);
BOOST_LOG_TRIVIAL(info) << "02: " << evaluate_cheats(walk, 20);
}
