#include #include #include #include #include #include #include #include #include #include using Int = std::int64_t; using UInt = std::uint64_t; using Location = std::pair; using Direction = std::pair; constexpr Direction north = std::make_pair(0, -1); constexpr Direction east = std::make_pair(1, 0); constexpr Direction south = std::make_pair(0, 1); constexpr Direction west = std::make_pair(-1, 0); auto operator+(Location const& loc, Direction const& dir) -> Location { return std::make_pair(loc.first + dir.first, loc.second + dir.second); } struct Beam { Beam(Location loc, Direction dir) : loc_(std::move(loc)), dir_(std::move(dir)) { } [[nodiscard]] auto hash() const noexcept -> std::size_t { return std::hash{}( ((loc_.first * 1000 + loc_.second) * 4 + (dir_.first + 1)) * 4 + (dir_.second + 1)); } [[nodiscard]] auto operator==(Beam const& rhs) const noexcept -> bool { return loc_ == rhs.loc_ && dir_ == rhs.dir_; } Location loc_; Direction dir_; }; template<> struct std::hash { [[nodiscard]] auto operator()(Beam const& beam) const noexcept -> std::size_t { return beam.hash(); } }; template<> struct std::hash { [[nodiscard]] auto operator()(Location const& loc) const noexcept -> std::size_t { return std::hash{}(loc.first * 1000 + loc.second); } }; struct Grid { void push_line(std::string const& line) { grid_.push_back(line); } [[nodiscard]] auto energised() const -> UInt { // The energised set includes directions - so we need to build a set that just includes locations. std::unordered_set locs; std::vector energy_grid(grid_.size(), std::string(grid_[0].size(), '.')); for (auto const [loc, dir] : energised_) { locs.insert(loc); energy_grid[loc.second][loc.first] = '#'; } for (auto const& row : energy_grid) { std::cout << row << '\n'; } return locs.size(); } [[nodiscard]] auto loc_valid(Location const& loc) const noexcept -> bool { if (loc.first < 0) { return false; } if (loc.second < 0) { return false; } if (loc.second >= grid_.size()) { return false; } if (loc.first >= grid_[loc.second].size()) { return false; } return true; } void energise() { std::list beams; beams.emplace_back(std::make_pair(0, 0), east); while (!beams.empty()) { auto beam{beams.front()}; beams.pop_front(); if (!loc_valid(beam.loc_)) { continue; } // Insert into hash of energised locations. If that fails we've done this before and don't // need to do it again. if (auto [it, success] = energised_.insert(beam); !success) { continue; } switch (grid_[beam.loc_.second][beam.loc_.first]) { case '.': break; case '\\': if (beam.dir_ == north) { beam.dir_ = west; } else if (beam.dir_ == east) { beam.dir_ = south; } else if (beam.dir_ == south) { beam.dir_ = east; } else if (beam.dir_ == west) { beam.dir_ = north; } else { std::abort(); } break; case '/': if (beam.dir_ == north) { beam.dir_ = east; } else if (beam.dir_ == east) { beam.dir_ = north; } else if (beam.dir_ == south) { beam.dir_ = west; } else if (beam.dir_ == west) { beam.dir_ = south; } else { std::abort(); } break; case '|': if (beam.dir_ == east || beam.dir_ == west) { Beam beam2{beam}; beam2.dir_ = north; beam2.loc_ = beam2.loc_ + beam2.dir_; beams.push_back(beam2); beam.dir_ = south; } break; case '-': if (beam.dir_ == north || beam.dir_ == south) { Beam beam2{beam}; beam2.dir_ = east; beam2.loc_ = beam2.loc_ + beam2.dir_; beams.push_back(beam2); beam.dir_ = west; } break; default: std::abort(); } beam.loc_ = beam.loc_ + beam.dir_; beams.push_back(beam); } } private: std::vector grid_; std::unordered_set energised_; }; auto main() -> int try { std::string line; Grid grid; while (std::getline(std::cin, line)) { grid.push_line(line); } grid.energise(); UInt count = grid.energised(); std::cout << "Total: " << count << '\n'; return EXIT_SUCCESS; } catch (...) { std::cerr << "Uncaught exception.\n"; return EXIT_FAILURE; }