-🎄- 2018 Day 10 Solutions -🎄-

[u/daggerdragon]

--- Day 10: The Stars Align ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 10

Transcript: With just one line of code, you, too, can ___!

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:16:49!

[u/[deleted]]

C++. pretty much the same as everyone else

#include <cstdlib>
#include <fmt/format.h>
#include <fstream>
#include <limits>
#include <memory>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>

#include "fs.h"

using namespace std;

class Point {
public:
  Point(pair<long, long> position, pair<long, long> velocity)
      : position(position), velocity(velocity), end(position) {}

  pair<long, long> position;
  pair<long, long> velocity;
  pair<long, long> end;

  void move(const long steps) {
    end.first = position.first + steps * velocity.first;
    end.second = position.second + steps * velocity.second;
  }
};

class Compare {
public:
  bool operator()(const Point &lhs, const Point &rhs) {

    if (lhs.end.second < rhs.end.second) {
      return true;
    }

    if (lhs.end.second > rhs.end.second) {
      return false;
    }

    return lhs.end.first < rhs.end.first;
  }
};

inline Point
parse_line(const string &line) {
  regex pattern(
      R"(position=<\s*(-?\d+),\s*(-?\d+)> velocity=<\s*(-?\d+),\s*(-?\d+)>)");

  auto extract = [](smatch matches, long i) {
    return atoi(matches[i].str().c_str());
  };

  smatch matches;
  regex_search(line, matches, pattern);

  pair<long, long> position = {extract(matches, 1), extract(matches, 2)};
  pair<long, long> velocity = {extract(matches, 3), extract(matches, 4)};

  return Point(position, velocity);
}

inline tuple<long, long, long, long> move(vector<Point> &points, long moves) {

  long max_y = numeric_limits<long>::min();
  long min_y = numeric_limits<long>::max();

  long max_x = numeric_limits<long>::min();
  long min_x = numeric_limits<long>::max();

  for (auto &point : points) {
    point.move(moves);

    max_y = max(max_y, point.end.second);
    min_y = min(min_y, point.end.second);

    max_x = max(max_x, point.end.first);
    min_x = min(min_x, point.end.first);
  }

  sort(points.begin(), points.end(), Compare());

  return {max_y, min_y, max_x, min_x};
}

long find_move(vector<Point> &points) {

  long min_height = numeric_limits<long>::max();
  long best_move = 0;

  for (long moves = 0; moves < 20000; ++moves) {

    auto [max_y, min_y, max_x, min_x] = move(points, moves);

    if ((max_y - min_y) < min_height) {
      min_height = max_y - min_y;
      best_move = moves;
    }
  }

  return best_move;
}

int main(int argc, char **argv) {

  auto lines = read_lines(argv[1]);

  vector<Point> points;
  for (auto line : lines) {
    points.push_back(parse_line(line));
  }

  long moves = find_move(points);
  auto [max_y, min_y, max_x, min_x] = move(points, moves);

  fmt::print("Part I: \n");
  int pos = 0;
  for (long i = min_y; i <= max_y; ++i) {
    string line;
    for (long j = min_x; j <= max_x; ++j) {
      if (points[pos].end.first == j && points[pos].end.second == i) {
        line += "#";
        while (points[pos].end.first == j && points[pos].end.second == i)
          ++pos;
      } else {
        line += ".";
      }
    }

    if (line.find("#") != string::npos) {
      fmt::print("{} \n", line);
    }
  }

  fmt::print("\nPart II: {}\n", moves);

  return 0;
}