Day22_2.cpp

#pragma region Includes
#include <iostream>
#include <string>
#include <sstream>
#include <fstream>

#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <tuple>
#include <cassert>
#include "Helpers.h"
#pragma endregion
using namespace std;

#pragma region InputFile
fstream get_input()
{
	fstream f("input.txt", ios::in);
	return f;
}
#pragma endregion

struct Vec3
{
	int x;
	int y;
	int z;

	Vec3() : x(0), y(0), z(0) {}
	Vec3(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}

	bool operator<(const Vec3& rhs) const noexcept
	{
		return (x + y + z < rhs.x + rhs.y + rhs.z);
	}

	Vec3 operator+(Vec3& rhs) const noexcept
	{
		return Vec3(x + rhs.x, y + rhs.y, z + rhs.z);
	}

	Vec3 operator-(Vec3& rhs) const noexcept
	{
		return Vec3(x - rhs.x, y - rhs.y, z - rhs.z);
	}

	bool operator==(const Vec3& rhs)
	{
		return x == rhs.x && y == rhs.y && z == rhs.z;
	}
};

typedef tuple<int, int, int> iii;

struct Box;
map<long, Box*> boxmap;
map<iii, long> pos_to_owning_box;

bool nullcheck_pos(Vec3& v)
{
	return (pos_to_owning_box.find({v.x, v.y, v.z}) != pos_to_owning_box.end());
}

struct Box
{
	vector<Vec3> cubes;
	vector<long> supporters;
	vector<long> supporting;
	Vec3 min_edge;
	Vec3 max_edge;

	long id = 0;

	Box(Vec3& _min, Vec3& _max) :
		min_edge(_min), max_edge(_max)
	{
		set<Vec3> bricks_to_add; //should handle dupes
		for (int x = min_edge.x; x <= max_edge.x; x++)
		{
			for (int y = min_edge.y; y <= max_edge.y; y++)
			{
				for (int z = min_edge.z; z <= max_edge.z; z++)
				{
					bricks_to_add.insert(Vec3(x, y, z));
				}
			}
		}

		cubes.clear();
		cubes.resize(bricks_to_add.size());
		std::copy(bricks_to_add.begin(), bricks_to_add.end(), cubes.begin());
	}

	void init_pos()
	{
		if (cubes.empty())
		{
			cerr << "Cubes is empty - shouldn't call init_pos!" << endl;
		}

		Vec3 up(0, 0, 1);
		for (Vec3& c : cubes)
		{
			pos_to_owning_box[{c.x, c.y, c.z}] = id;
		}
	}

	void init_supports()
	{
		Vec3 up(0, 0, 1);
		set<long> s_above;
		set<long> s_below;
		for (Vec3& c : cubes)
		{
			//are we being supported by anyone?
			//are we supporting anyone?
			Vec3 above = c + up;
			Vec3 below = c - up;

			if (nullcheck_pos(above))
			{
				iii v = { above.x, above.y, above.z };
				if (pos_to_owning_box[v] != id)
				{
					s_above.insert(pos_to_owning_box[v]);
				}
			}
			
			if (nullcheck_pos(below))
			{
				iii v = { below.x, below.y, below.z };
				if (pos_to_owning_box[v] != id)
				{
					s_below.insert(pos_to_owning_box[v]);
				}
			}
		}

		supporters.clear();
		supporters.resize(s_below.size());
		std::copy(s_below.begin(), s_below.end(), supporters.begin());

		supporting.clear();
		supporting.resize(s_above.size());
		std::copy(s_above.begin(), s_above.end(), supporting.begin());
	}

	bool can_disintegrate()
	{
		if (supporting.size() == 0)
		{
			return true;
		}

		for (long s : supporting)
		{
			if (!boxmap[s])
			{
				exit(1);
			}

			if (!boxmap[s]->is_supported_without(id))
			{
				return false;
			}
		}
		return true;
	}

	bool is_supported_without(long c)
	{
		return supporters.size() != 1;
	}
};

int main()
{
	fstream f = get_input();

	string ln;

	vector<Box> boxes;
	long c = 0;
	while (getline(f, ln))
	{
		size_t tilde_pos = ln.find('~');

		string _min = ln.substr(0, tilde_pos);
		string _max = ln.substr(tilde_pos + 1);

		stringstream ss(_min);
		string num;
		vector<int> coords;
		while (getline(ss, num, ','))
		{
			coords.push_back(stoi(num));
		}
		Vec3 min_edge(coords[0], coords[1], coords[2]);

		ss = stringstream(_max);
		coords.clear();
		while (getline(ss, num, ','))
		{
			coords.push_back(stoi(num));
		}
		Vec3 max_edge(coords[0], coords[1], coords[2]);

		//cout << min_edge << " -> " << max_edge << endl;

		Box b(min_edge, max_edge);
		b.id = c++;
		b.init_pos();

		boxes.push_back(b);
	}

	for (Box& b : boxes)
	{
		b.init_supports();
		boxmap[b.id] = &b;
	}

	
	long tot = 0;
	for (Box& b : boxes)
	{	
		if (boxmap[b.id]->can_disintegrate())
		{
			continue;
		}

		set<long> fallers;
		fallers.insert(b.id);
		
		map<long, bool> visited;
		queue<long> q;
		q.push(b.id);

		while (!q.empty())
		{
			long nx = q.front();
			q.pop();

			if (visited[nx])
			{
				continue;
			}

			bool bNotFalling = false;
			for (long x : boxmap[nx]->supporters)
			{
				if (nx == b.id) break;

				if (fallers.find(x) == fallers.end())
				{
					bNotFalling = true;
				}
			}

			if (bNotFalling)
			{
				continue;
			}

			fallers.insert(nx);

			for (long x : boxmap[nx]->supporting)
			{
				q.push(x);
			}

			visited[nx] = true;
		}

		cout << "for box id " << b.id << ": " << fallers.size() - 1 << " boxes fall when it disintegrates!" << endl;
		tot += fallers.size() - 1; //-1 because the disintegrated brick is in there.
		fallers.clear();
	}

	
	cout << "Part 2: " << tot << endl;
	
	
}