day8b.cpp

#include <string>
#include <vector>
#include <sstream>
#include <fstream>
#include <cassert>
#include <algorithm>
#include <array>
#include <iostream>
#include <set>
#include <cmath>

namespace day8b
{
	int main()
	{
		// BEGIN BOILERPLATE
		std::string input0;
		//std::ifstream ifile("day8_sample.txt");
		std::ifstream ifile("day8.txt");
		if (ifile.is_open())
		{
			while (!ifile.eof())
			{
				std::string line;
				std::getline(ifile, line);
				input0 += line + '\n';
			}
			assert(input0.back() == '\n');
			input0.pop_back(); // no trailing newline character please
			//__debugbreak();
		}
		else
		{
			assert(0);
		}

		std::vector<std::string> values;
		std::string temp;
		for (char c : input0)
		{
			if (c == '\n')
			{
				values.push_back(temp);
				temp = "";
				continue;
			}
			temp += c;
		}
		values.push_back(temp);

		struct coordinate
		{
			uint64_t x;
			uint64_t y;
			uint64_t z;
			coordinate(int xx, int yy, int zz) // because we are using C++14 with emplace_back we don't have improved aggregate initialization ;(
			{
				x = xx;
				y = yy;
				z = zz;
			}
			uint64_t distance(const coordinate& c)
			{
				uint64_t dx = std::max(x, c.x) - std::min(x, c.x);
				uint64_t dy = std::max(y, c.y) - std::min(y, c.y);
				uint64_t dz = std::max(z, c.z) - std::min(z, c.z);

				uint64_t temp = dx * dx + dy * dy + dz * dz;
				return temp;

				//return std::sqrt(temp);
			}
			bool operator==(const coordinate& c) const
			{
				if (x == c.x && y == c.y && z == c.z)
					return true;
				return false;
			}
			bool operator<(const coordinate& c) const // forgot to make it const...
			{
				bool test;
				if (x < c.x)
					test = true;
				else if (c.x < x) // it's supposed to be other is LESS than!!!
					test = false;
				else if (y < c.y)
					test = true;
				else if (c.y < y)
					test = false;
				else if (z < c.z)
					test = true;
				else if (c.z < z)
					test = false;
				else
					test = false;

				bool test2;
				if (x != c.x)
					test2 = x < c.x;
				else if (y != c.y)
					test2 = y < c.y;
				else
					test2 = z < c.z;
				assert(test == test2);
					
				return test;
			}
		};

		std::vector<coordinate> coordinates;
		for (auto& s : values)
		{
			int x;
			int y;
			int z;
			char c;
			std::istringstream iss{ s };
			iss >> x;
			iss >> c;
			iss >> y;
			iss >> c;
			iss >> z;
			coordinates.emplace_back(x, y, z);
		}

		struct distance_pair
		{
			uint64_t distance;
			int i;
			int j;
		};
		std::vector<distance_pair> distances2;

		for (int i = 0; i < coordinates.size() - 1; i++)
		{
			for (int j = i + 1; j < coordinates.size(); j++)
			{
				distance_pair d;
				d.distance = coordinates[i].distance(coordinates[j]);
				d.i = i;
				d.j = j;
				distances2.push_back(d);
			}
		}
		std::sort(distances2.begin(), distances2.end(), [](auto& a, auto& b) -> bool { return a.distance < b.distance; });

		std::vector<std::set<coordinate>> circuits;

		int total_distances = 0;

		for (int p = 0; p < 4000; p++)
		{
			int i = total_distances;
			std::set<coordinate> s;
			int i0 = distances2[i].i;
			int i1 = distances2[i].j;
			auto c0 = coordinates[i0];
			auto c1 = coordinates[i1];
			s.insert(c0);
			s.insert(c1);
			circuits.push_back(s);
			total_distances++;
		}

		while (true)
		{
			{
				int i = total_distances;
				std::set<coordinate> s;
				int i0 = distances2[i].i;
				int i1 = distances2[i].j;
				auto c0 = coordinates[i0];
				auto c1 = coordinates[i1];
				s.insert(c0);
				s.insert(c1);
				circuits.push_back(s);
			}


			for (int i = 0; i < circuits.size() - 1; i++)
			{
				for (int j = i + 1; j < circuits.size(); j++)
				{
					auto& c0 = circuits[i];
					auto& c1 = circuits[j];
					auto c2 = c0;
					c2.insert(c1.begin(), c1.end());
					if (c2.size() < c0.size() + c1.size())
					{
						circuits.erase(circuits.begin() + j);
						circuits.erase(circuits.begin() + i);
						circuits.push_back(c2);
						i--;
						break;
					}
				}
			}

			int total_boxes = 0;
			for (int i = 0; i < circuits.size(); i++)
			{
				total_boxes += circuits[i].size();
			}
			if (total_distances % 100 == 0)
			{
				std::cout << total_boxes << '\n';
			}

			if (total_boxes == coordinates.size())
			{
				int i = total_distances;
				int i0 = distances2[i].i;
				int i1 = distances2[i].j;
				auto c0 = coordinates[i0];
				auto c1 = coordinates[i1];

				uint64_t result = c0.x * c1.x;
				__debugbreak();
			}

			total_distances++;
		}

		__debugbreak();
		return 0;
	}

}