solution3.cc

#pragma once

#include "solution.h"

using namespace advent;

namespace advent2019 {
class Solution3 : public Solution {
 public:
  using Point = std::pair<int, int>;

  void Parse() override {
    std::string line;
    std::getline(input_, line);
    line1_ = ComputeLine(line);
    std::getline(input_, line);
    line2_ = ComputeLine(line);
  }

  void Part1(std::ostream &out) override {
    auto line1 = line1_;
    std::sort(line1.begin(), line1.end());
    auto line2 = line2_;
    std::sort(line2.begin(), line2.end());
    std::set_intersection(line1.begin(), line1.end(), line2.begin(),
                          line2.end(), std::back_inserter(intersect_));
    int dist = std::numeric_limits<int>::max();
    for (const auto &p : intersect_) {
      dist = std::min(dist, Dist(p, {0, 0}));
    }
    out << dist;
  }
  void Part2(std::ostream &out) override {
    size_t dist = std::numeric_limits<size_t>::max();
    for (const auto &p : intersect_) {
      size_t i = 0, j = 0;
      for (; i < line1_.size(); i++) {
        if (line1_[i] == p) {
          break;
        }
      }
      for (; j < line2_.size(); j++) {
        if (line2_[j] == p) {
          break;
        }
      }
      size_t d = i + j + 2;
      dist = std::min(dist, d);
    }
    out << dist;
  }

 private:
  std::vector<Point> line1_;
  std::vector<Point> line2_;
  std::vector<Point> intersect_;

  std::vector<Point> ComputeLine(const std::string &line) {
    std::vector<Point> points;
    int x = 0, y = 0;
    std::istringstream is(line);
    for (std::string tok; std::getline(is, tok, ',');) {
      char dir = tok[0];
      int num = std::stoi(tok.substr(1));
      assert(num > 0);
      for (int i = 0; i < num; i++) {
        switch (dir) {
          case 'U':
            y++;
            break;
          case 'D':
            y--;
            break;
          case 'L':
            x--;
            break;
          case 'R':
            x++;
            break;
          default:
            assert(false);  // not reached
        }
        points.emplace_back(x, y);
      }
    }
    return points;
  }

  int Dist(const Point &p1, const Point &p2) {
    return std::abs(p1.first - p2.first) + std::abs(p1.second - p2.second);
  }
};
}  // namespace advent2019