day3.cpp

/*
 * ===========================================================================
 *
 *       Filename:  day3.cpp
 *
 *    Description:  Day 3 of Advent of Code solution
 *
 *        Version:  1.0
 *        Created:  12/3/2019 5:04:05 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  invakid404
 *
 * ===========================================================================
 */


#include <bits/stdc++.h>

#define IN_PATH R"(D:\Coding\Problems\adventofcode\in\day3.txt)"
#define ENDL '\n';
#define RANGE(i, a, b, s) for(auto i = a; i < b; i += s)

#define ABS_SUM(a, b) (std::abs(a) + std::abs(b))
#define PUT_IF_ABSENT(map, key, val) { \
	auto it = map.find(key); \
	if(it == map.end()) { \
		map.emplace_hint(it, key, val); \
	} \
}

template<class K, class V>
using umap = std::unordered_map<K, V>;

template<class K>
using uset = std::unordered_set<K>;

typedef std::string wire_data;
typedef std::vector<wire_data> wire;

typedef std::valarray<int> point;
typedef	uset<point> points;

typedef umap<char, point> dir_map;

namespace std {
	template<>
	struct hash<point> {
		auto operator()(const point& p) const -> std::size_t {
			return p[0] * 31 + p[1];
		}
	};

	template<>
	struct equal_to<point> {
		auto operator()(
			const point& a, 
			const point& b
		) const -> bool {
			return a[0] == b[0] &&
			       a[1] == b[1];
		}
	};
}

typedef umap<point, int> point_map;

namespace {
	dir_map directions = {
		{'L', { -1,  0 }}, 
		{'R', {  1,  0 }},
		{'U', {  0,  1 }},
		{'D', {  0, -1 }}
	};

	auto split(const std::string& s, char d) -> std::vector<std::string> {
		std::vector<std::string> result;

		std::stringstream ss(s);
		std::string curr;

		while(std::getline(ss, curr, d)) {
			result.emplace_back(curr);
		}

		return result;
	}

	template<class K, class V>
	auto get_keys(const umap<K, V>& map) -> uset<K> {
		uset<K> res;

		for(auto& val : map) {
			res.emplace(val.first);
		}

		return res;
	}

	template<class K>
	auto intersect(const uset<K>& a, const uset<K>& b) -> uset<K> {
		uset<K> res;

		for(auto& val : a) {
			if(b.count(val) > 0) {
				res.emplace(val);
			}
		}

		return res;
	}

	auto get_points_info(const wire& w) -> point_map {
		point_map res;

		point p = {0, 0};

		auto len = 0;
		for(auto& val : w) {
			auto op = val[0];
			auto n  = std::stoi(val.substr(1));

			RANGE(i, 0, n, 1) {
				p += directions[op];
				++len;

				PUT_IF_ABSENT(res, p, len);
			}
		}

		return res;
	}

	template<class unary_operation>
	auto solve(const points& p, unary_operation op) -> int {
		std::vector<int> vec(p.size());

		std::transform(p.begin(), p.end(), vec.begin(), op);

		return *std::min_element(vec.begin(), vec.end());
	}

	auto part_one(const points& p) -> int {
		return solve(p, [](const auto& val) {
					return ABS_SUM(val[0], val[1]);
				});
	}

	auto part_two(
		const points& p,
		point_map& p_1, 
		point_map& p_2
	) -> int {
		return solve(p, [&p_1, &p_2](const auto& val) {
					return p_1[val] + p_2[val];
				});
	}
}

int main() {
	std::ifstream f_in;

	f_in.open(IN_PATH);
	if(!f_in) {
		std::cerr << "Failed to open file!" << ENDL;
		return 1;
	}

	wire_data data_1, data_2;
	f_in >> data_1 >> data_2;

	auto wire_1 = split(data_1, ',');
	auto wire_2 = split(data_2, ',');

	auto points_info_1 = get_points_info(wire_1);
	auto points_info_2 = get_points_info(wire_2);

	auto points_1 = get_keys(points_info_1);
	auto points_2 = get_keys(points_info_2);

	auto common = intersect(points_1, points_2);
	
	std::cout << part_one(common) << ENDL;
	std::cout << part_two(common, points_info_1, points_info_2) << ENDL;

	return 0;
}