day6.cpp

/*
 * ============================================================================
 *
 *       Filename:  day6.cpp
 *
 *    Description:  Day 6 of Advent of Code solution
 *
 *        Version:  1.0
 *        Created:  12/7/2019 12:30:12 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  invakid404
 *
 * ============================================================================
 */


#include <bits/stdc++.h>

#define ENDL '\n';
#define IN_PATH R"(D:\Coding\Problems\adventofcode\in\day6.txt)"
#define INF 100000

#define RANGE(i, a, b) for(auto i = a; i < b; ++i)
#define SQUARED(i, j, a, b) RANGE(i, a, b) RANGE(j, a, b)
#define QUBED(i, j, k, a, b) SQUARED(i, j, a, b) RANGE(k, a, b)

#define SET_IF_ABSENT(m, k, v) { \
	auto it = m.find(k); \
	if(it == m.end()) { \
		m[k] = ++v; \
	} \
}

namespace {
	typedef std::unordered_map<std::string, unsigned> lookup_map;
	typedef std::vector<std::vector<int>> dynamic_matrix;

	lookup_map     name_to_idx;
	dynamic_matrix g;

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

	auto initialize_matrix(int n) -> void {
		g.resize(n);
		for(auto& val : g) {
			val = std::vector<int>(n);
		}
	}

	// Uses Floyd's algorithm to find the shortest path between all nodes
	// Complexity: O(N^3)
	auto calculate_paths() -> void {
		SQUARED(i, j, 0UL, g.size()) {
			if(g[i][j] == 0) {
				g[i][j] = INF;
			}
		}

		QUBED(k, i, j, 0UL, g.size()) {
			if(g[i][j] > g[i][k] + g[k][j]) {
				g[i][j] = g[i][k] + g[k][j];
			}
		}
	}

	auto part_one() -> int {
		auto sum = 0;

		auto target = name_to_idx["COM"];

		RANGE(i, 1UL, g.size()) {
			if(i == target) {
				continue;
			}
			
			if(g[i][target] != INF) {
				sum += g[i][target];
			}
		}
		
		return sum;
	}

	auto part_two() -> int {
		auto start = name_to_idx["YOU"];
		auto end   = name_to_idx["SAN"];

		return g[start][end] - 2;
	}
}

int main() {
	auto start = std::chrono::high_resolution_clock::now();

	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::ifstream f_in;

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

	std::string curr;
	auto curr_idx = 0;

	std::vector<std::string> data;

	while(f_in >> curr) {
		data.emplace_back(curr);

		auto parts = split(curr, ')');
		SET_IF_ABSENT(name_to_idx, parts[0], curr_idx);
		SET_IF_ABSENT(name_to_idx, parts[1], curr_idx);
	}

	initialize_matrix(name_to_idx.size() + 1);

	for(auto& val : data) {
		auto parts = split(val, ')');

		auto i = name_to_idx[parts[0]];
		auto j = name_to_idx[parts[1]];

		g[i][j] = 1;
		g[j][i] = 1;
	}

	calculate_paths();

	std::cout << part_one() << ENDL;
	std::cout << part_two() << ENDL;

	auto end = std::chrono::high_resolution_clock::now();

	std::cout << std::chrono::duration_cast<std::chrono::milliseconds>
		(end - start).count() << ENDL;

	return 0;
}