Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include <array>
#include <algorithm>
#include <cmath>
using Lines = std::vector<std::string>;
Lines read_file(const std::string& file_name)
{
std::ifstream input_file(file_name);
std::string line;
Lines result;
while (std::getline(input_file, line))
{
result.push_back(line);
}
return result;
}
struct Movement
{
Movement(char direction, int amount)
:direction(direction), amount(amount) {}
char direction;
int amount;
};
using Wire = std::vector<Movement>;
Wire read_wire(const std::string& wire_string)
{
std::istringstream input_stream(wire_string);
std::string movement_string;
Wire result;
while (std::getline(input_stream, movement_string, ','))
{
result.emplace_back(movement_string.at(0),stoi(std::string(movement_string.begin() + 1, movement_string.end())));
}
return result;
}
struct Position
{
Position(long int y, long int x, int steps)
:y(y), x(x), steps(steps) {}
bool operator==(const Position& other) const
{
return y == other.y && x == other.x;
}
bool operator< (const Position& other) const
{
return y < other.y ||
(y == other.y && x < other.x) ||
(y == other.y && x == other.x && steps < other.steps);
}
long int y;
long int x;
int steps;
};
using Trace = std::vector<Position>;
Trace trace_wire(const Wire& wire)
{
Trace result;
Position current_position(0, 0, 0);
int total_steps = 0;
for (const auto& movement : wire)
{
int diff_y = 0;
int diff_x = 0;
switch (movement.direction) {
case 'U':
diff_y = 1;
break;
case 'D':
diff_y = -1;
break;
case 'R':
diff_x = 1;
break;
case 'L':
diff_x = -1;
break;
}
for (int i = 0; i < movement.amount; i++)
{
result.emplace_back(
current_position.y + (diff_y * i),
current_position.x + (diff_x * i),
total_steps + i);
}
current_position.y += diff_y * movement.amount;
current_position.x += diff_x * movement.amount;
total_steps += movement.amount;
}
std::sort(result.begin(), result.end());
return result;
}
int manhattan_distance(const Position& position)
{
return std::abs(position.y) + std::abs(position.x);
}
int main()
{
auto lines = read_file("input.txt");
Wire wire1 = read_wire(lines[0]);
Wire wire2 = read_wire(lines[1]);
auto trace1 = trace_wire(wire1);
auto trace2 = trace_wire(wire2);
Trace intersections;
for (const auto& pos1 : trace1)
{
if (pos1.y == 0 && pos1.x == 0)
continue;
auto it = std::lower_bound(trace2.begin(), trace2.end(), pos1);
if (it != trace2.end() && *it == pos1)
{
intersections.emplace_back(
pos1.y,
pos1.x,
pos1.steps + it->steps);
}
}
auto solution = std::min_element(
intersections.begin(),
intersections.end(),
[](const auto& lhs, const auto& rhs) {
return manhattan_distance(lhs) < manhattan_distance(rhs);
});
std::cout << "Solution: " << manhattan_distance(*solution) << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.