fuckingDay3.cpp

#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;
}