path: root/main.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <array>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <random>
#include <algorithm>
#include <memory>
#include <cassert>
#include <cmath>
#include <climits>
#include <signal.h>
#include "svg.h"

constexpr const int MAXNUM = 5;
constexpr const int TOTAL_TILES = (MAXNUM + 1) * (MAXNUM + 2) * (MAXNUM + 3) / 6;
static_assert(TOTAL_TILES <= (1 << 25));

/*
   __0__  __1__  __2__  __3__
                                 number order:
0    T^7    T^7    T^7    T^7      0    1---2
0     V      V      V      V      / \    \ /
                                 2___1    0
1   A      A      A      A 
1  /_\    /_\    /_\    /_\     adjacents order:
                                   .        1
2  T^7    T^7    T^7    T^7     2 / \ 0   .---.
2   V      V      V      V       /___\   0 \ / 2
                                   1        V
3     A      A      A      A 
3    /_\    /_\    /_\    /_\

*/


static std::default_random_engine g_randengine{std::random_device{}()};

template <typename T>
const T& random_choice(const std::vector<T> &v) {
	assert(v.size() > 0);
	size_t idx = std::uniform_int_distribution<size_t>{0, v.size() - 1}(g_randengine);
	return v[idx];
}

struct Pos {
	unsigned x, y;
	bool operator==(const Pos &other) const { return x == other.x && y == other.y; }
	bool operator!=(const Pos &other) const { return !operator==(other); }
};

template <>
struct std::hash<Pos> {
	size_t operator()(Pos pos) const {
		return h(pos.x) ^ (h(pos.y) << 32);
	}
private: hash<unsigned> h;
};

std::ostream& operator<<(std::ostream &os, Pos pos) {
	return os << '(' << pos.x << ',' << pos.y << ')';
}

constexpr std::array<Pos, 3> adjacents(Pos p) {
	switch (p.y % 4) {
		case 0: return { Pos{p.x, p.y+1}, Pos{p.x, p.y-1}, Pos{p.x+1, p.y+1} };
		case 1: return { Pos{p.x, p.y-1}, Pos{p.x, p.y+1}, Pos{p.x-1, p.y-1} };
		case 2: return { Pos{p.x-1, p.y+1}, Pos{p.x, p.y-1}, Pos{p.x, p.y+1} };
		case 3: return { Pos{p.x+1, p.y-1}, Pos{p.x, p.y+1}, Pos{p.x, p.y-1} };
	}
	__builtin_unreachable();
}

struct Triangle2D {
	static constexpr const double side_length = 1.0;
	static double tri_height;

	std::array<std::array<double, 2>, 3> pts;
	std::array<int, 3> nums;

	// Will construct clockwise
	Triangle2D(double basey, double basex1, double basex2, std::array<int, 3> nums)
		: pts{
			std::array<double, 2>{basex1, basey},
			{basex2, basey},
			{(basex1 + basex2) / 2, basey + (basex2 - basex1) / 2 * std::sqrt(3)}
		},
		nums{nums}
	{}

	Triangle2D(Pos pos, std::array<int, 3> nums)
		: Triangle2D(
			(pos.y + 1) / 2 * (std::sqrt(3) / 2),
			pos.x + 0.5 * (pos.y % 4 == 1) - 0.5 * (pos.y % 4 == 2) + (pos.y % 4 == 3),
			pos.x + (pos.y % 4 == 0) - 0.5 * (pos.y % 4 == 1) + 0.5 * (pos.y % 4 == 2),
			nums
		)
	{}

	std::vector<std::unique_ptr<Figure>> render(std::string bg) const {
		double midx = (pts[0][0] + pts[1][0] + pts[2][0]) / 3.0;
		double midy = (pts[0][1] + pts[1][1] + pts[2][1]) / 3.0;
		std::array<std::array<double, 2>, 3> txtp;
		for (int i = 0; i < 3; i++) {
			txtp[i][0] = 0.4 * pts[i][0] + 0.6 * midx;
			txtp[i][1] = 0.4 * pts[i][1] + 0.6 * midy;
		}

		std::vector<std::unique_ptr<Figure>> v;
		v.emplace_back(new Polygon{std::vector<std::array<double, 2>>{pts.begin(), pts.end()}, bg});
		v.emplace_back(new Text{txtp[0][0], txtp[0][1], 0, std::to_string(nums[1])});
		v.emplace_back(new Text{txtp[1][0], txtp[1][1], 0, std::to_string(nums[2])});
		v.emplace_back(new Text{txtp[2][0], txtp[2][1], 0, std::to_string(nums[0])});
		return v;
	}
};

// std::sqrt is not constexpr, what?
double Triangle2D::tri_height = std::sqrt(3.0) / 2 * side_length;

struct PlacedTile {
	unsigned index : 25;
	unsigned rot : 2;
	unsigned empty : 1;
};

// must be 0-1-2, 1-2-0, or 2-0-1.
constexpr PlacedTile tile(unsigned a, unsigned b, unsigned c) {
	unsigned rot = 0;
	if (a <= b && b <= c) { rot = 0; }  // 0 1 2
	else if (b <= c && c <= a) { int t = a; a = b; b = c; c = t; rot = 1; }  // 2 0 1
	else if (c <= a && a <= b) { int t = c; c = b; b = a; a = t; rot = 2; }  // 1 2 0
	else assert(false);
	// before the tiles with highest number c, there are this many tiles:
	//   \sum_{i=0}^{c-1} ((i + 1) * (c - i)) = c (c + 1) (c + 2) / 6
	const unsigned before_c = c * (c + 1) * (c + 2) / 6;
	// within the tiles with highest number c, before the tiles with middle number b, there are this many tiles:
	//   \sum_{i=1}^b i = b (b + 1) / 2
	const unsigned before_b = b * (b + 1) / 2;
	return PlacedTile{before_c + before_b + a, rot, 0};
}

constexpr bool is_valid_tile(std::array<int, 3> nums) {
	const int a = nums[0], b = nums[1], c = nums[2];
	return (a <= b && b <= c) || (b <= c && c <= a) || (c <= a && a <= b);
}

constexpr PlacedTile tile(std::array<int, 3> nums) {
	return tile(nums[0], nums[1], nums[2]);
}

class RevTileCache {
	std::vector<std::array<int, 3>> arr;
public:
	RevTileCache() {
		arr.resize(TOTAL_TILES);
		for (int c = 0; c <= MAXNUM; c++)
		for (int b = 0; b <= c; b++)
		for (int a = 0; a <= b; a++) {
			unsigned index = tile(a, b, c).index;
			assert(index < TOTAL_TILES);
			arr[index] = {a, b, c};
		}
	}
	std::array<int, 3> operator[](unsigned index) const { return arr[index]; }
} rev_tile_cache;

std::array<int, 3> tile(unsigned index) {
	return rev_tile_cache[index];
}

constexpr std::array<int, 3> rotate(const std::array<int, 3> &nums, unsigned rot) {
	switch (rot) {
		case 0: return nums;
		case 1: return { nums[2], nums[0], nums[1] };
		case 2: return { nums[1], nums[2], nums[0] };
	}
	assert(false);
}

std::ostream& operator<<(std::ostream &os, PlacedTile pt) {
	if (pt.empty) return os << "tile[EMPTY]";
	os << "tile[#" << pt.index << 'r' << pt.rot << '=';
	std::array<int, 3> nums = rotate(tile(pt.index), pt.rot);
	os << nums[0] << '-' << nums[1] << '-' << nums[2] << ']';
	return os;
}

class Table {
	void boundary_add(Pos pos) {
		if (boundary_map.count(pos) == 0) {
			boundary_map[pos] = boundary_list.size();
			boundary_list.push_back(pos);
		}
	}

	void boundary_remove(Pos pos) {
		auto it = boundary_map.find(pos);
		if (it != boundary_map.end()) {
			size_t idx = it->second;
			// assert(boundary_list[idx] == pos);
			if (idx < boundary_list.size() - 1) {
				boundary_map[boundary_list.back()] = idx;
				std::swap(boundary_list.back(), boundary_list[idx]);
			}
			boundary_list.pop_back();
			boundary_map.erase(it);
		}
	}

public:
	static constexpr const unsigned midpoint_coord = 100;
	PlacedTile bd[200][200];  // bd[y][x]
	std::unordered_set<Pos> taken;
	std::unordered_map<Pos, int> boundary_map;
	std::vector<Pos> boundary_list;

	Table() {
		for (unsigned y = 0; y < sizeof(bd) / sizeof(bd[0]); y++)
			for (unsigned x = 0; x < sizeof(bd[y]) / sizeof(bd[y][0]); x++)
				bd[y][x].empty = 1;
	}

	struct Unsetter {
		Pos pos;
		std::vector<Pos> newbound;
	};

	// Unsetters must be applied in reverse order of creation
	Unsetter set(Pos pos, unsigned index, unsigned rot) {
		// std::cout << "set(" << pos << ", " << index << ", " << rot << ")" << std::endl;
		// assert(taken.count(pos) == 0);
		boundary_remove(pos);
		taken.insert(pos);

		Unsetter unsetter;
		unsetter.pos = pos;

		PlacedTile &pt = bd[pos.y][pos.x];
		pt.index = index;
		pt.rot = rot;
		pt.empty = 0;
		for (auto p2 : adjacents(pos)) {
			// assert(p2 != pos);
			if (taken.count(p2) == 0 && boundary_map.count(p2) == 0) {
				boundary_add(p2);
				unsetter.newbound.push_back(p2);
			}
		}

		// for (Pos pos : boundary_list) {
		//     if (taken.count(pos) != 0) {
		//         std::cout << "ERROR: boundary pos " << pos << " taken!" << std::endl;
		//     }
		// }

		return unsetter;
	}

	void unset(const Unsetter &unsetter) {
		bd[unsetter.pos.y][unsetter.pos.x].empty = 1;
		taken.erase(taken.find(unsetter.pos));
		for (auto p2 : unsetter.newbound) {
			boundary_remove(p2);
		}
	}

	std::vector<std::unique_ptr<Figure>> draw() const {
		std::vector<std::unique_ptr<Figure>> polys;
		for (Pos pos : taken) {
			PlacedTile pt = bd[pos.y][pos.x];
			auto figures = Triangle2D(pos, rotate(tile(pt.index), pt.rot)).render("#ddd");
			for (auto &fig : figures) polys.push_back(move(fig));
		}
		return polys;
	}

	std::string buildSVG() const {
		std::ostringstream ss;
		ss << "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>";
		ss << "<svg width=\"800\" height=\"800\" viewBox=\"90 35 20 20\" xmlns=\"http://www.w3.org/2000/svg\">";
		for (auto &fig : draw()) ss << fig->svg();
		ss << "</svg>";
		return ss.str();
	}
};

std::vector<PlacedTile> possibles(const Table &table, Pos pos) {
	// std::cerr << "[possibles] start for pos=" << pos << std::endl;

	std::array<int, 3> nums = {-1, -1, -1};
#define APPLY(at_, num_) do { \
			/*std::cerr << "[possibles] force [" << (at_) << "] = " << (num_) << std::endl;*/ \
			if (nums[(at_)] == -1) nums[(at_)] = (num_); \
			else if (nums[(at_)] != (num_)) {/*std::cerr << "[possibles] early {}" << std::endl;*/ return {};} \
		} while (0)

	std::array<Pos, 3> adj = adjacents(pos);

	{
		const PlacedTile &pt = table.bd[adj[0].y][adj[0].x];
		if (!pt.empty) {
			const std::array<int, 3> adjnums = rotate(tile(pt.index), pt.rot);
			APPLY(0, adjnums[1]);
			APPLY(1, adjnums[0]);
		}
	}

	{
		const PlacedTile &pt = table.bd[adj[1].y][adj[1].x];
		if (!pt.empty) {
			const std::array<int, 3> adjnums = rotate(tile(pt.index), pt.rot);
			APPLY(1, adjnums[2]);
			APPLY(2, adjnums[1]);
		}
	}

	{
		const PlacedTile &pt = table.bd[adj[2].y][adj[2].x];
		if (!pt.empty) {
			const std::array<int, 3> adjnums = rotate(tile(pt.index), pt.rot);
			APPLY(0, adjnums[2]);
			APPLY(2, adjnums[0]);
		}
	}

#undef APPLY

	// std::cerr << "[possibles] end" << std::endl;

	std::vector<PlacedTile> result;
#define SEQUENCE(at_) do { \
			for (int i_ = 0; i_ <= MAXNUM; i_++) { \
				std::array<int, 3> modified = nums; \
				modified[(at_)] = i_; \
				if (is_valid_tile(modified)) result.push_back(tile(modified)); \
			} \
		} while (0)

	if (nums[0] != -1) {
		if (nums[1] != -1) {
			if (nums[2] != -1) {
				if (is_valid_tile(nums)) return {tile(nums)};
				else return {};
			} else { SEQUENCE(2); return result; };
		} else {
			if (nums[2] != -1) { SEQUENCE(1); return result; }
			else {
				for (int b = 0; b <= MAXNUM; b++) { nums[1] = b; SEQUENCE(2); }
				return result;
			}
		}
	} else {
		if (nums[1] != -1) {
			if (nums[2] != -1) { SEQUENCE(0); return result; }
			else {
				for (int a = 0; a <= nums[1]; a++) { nums[0] = a; SEQUENCE(2); }
				return result;
			}
		} else {
			if (nums[2] != -1) {
				for (int a = 0; a <= nums[1]; a++) { nums[0] = a; SEQUENCE(1); }
				return result;
			} else {
				result.resize(3 * TOTAL_TILES);
				for (unsigned i = 0; i < TOTAL_TILES; i++)
					for (unsigned j = 0; j < 3; j++)
						result[3 * i + j] = PlacedTile{i, j, 0};
				return result;
			}
		}
	}

#undef SEQUENCE
}

// Returns whether a move was possible (and thus made)
bool place_random(Table &table, std::bitset<TOTAL_TILES> &bag) {
	if (table.taken.size() == 0) {
		std::vector<unsigned> poss;
		poss.reserve(TOTAL_TILES);
		for (int i = 0; i < TOTAL_TILES; i++) if (bag[i]) poss.push_back(i);
		unsigned index = random_choice(poss);
		table.set(Pos{table.midpoint_coord, table.midpoint_coord}, index, 0);
		bag[index] = false;
		return true;
	}

	assert(table.boundary_list.size() > 0);

	std::vector<Pos> boundary = table.boundary_list;
	std::shuffle(boundary.begin(), boundary.end(), g_randengine);
	for (Pos pos : boundary) {
		std::vector<PlacedTile> poss = possibles(table, pos);
		poss.erase(
			std::remove_if(poss.begin(), poss.end(), [&bag](const PlacedTile &pt) {
				return !bag[pt.index];
			}),
			poss.end()
		);

		if (poss.size() > 0) {
			PlacedTile pt = random_choice(poss);
			table.set(pos, pt.index, pt.rot);
			bag[pt.index] = false;
			return true;
		}
	}

	return false;
}

#if 0
struct Node {
	float nwin = 0;
	unsigned ntotal = 0;
	struct Move {
		Pos pos;
		PlacedTile pt;
		std::unique_ptr<Node> child;
	};
	std::vector<Move> moves;

	void populate_moves(const Table &table, const std::bitset<TOTAL_TILES> &bag) {
		for (Pos pos : table.boundary_list)
			for (PlacedTile pt : possibles(table, pos))
				if (bag[pt.index])
					moves.push_back(Move{pos, pt, {}});
	}
};

template <typename ScoreFunc>
void mcts(ScoreFunc score_func) {
	std::unique_ptr<Node> root = std::make_unique<Node>();
	root->populate_moves({}, {});

	while (true) {
		std::vector<Node*> stack{&*root};

		float terminal = -1;  // -1=undecided, 0=loss

		Table table;
		std::bitset<TOTAL_TILES> bag;
		Node *curnode = &*root;

		// Selection
		while (true) {
			const float logparent = std::log(curnode->ntotal);

			Node *bestchild = nullptr;
			float maxscore = -1;
			for (Node::Move &mv : curnode->moves) {
				if (mv.child) {
					float score = mv.child->nwin / mv.child->ntotal + M_SQRT2 * std::sqrt(logparent / mv.child->ntotal);
					if (score < maxscore) {
						maxscore = score;
						bestchild = &*mv.child;
					}
				}
			}


		}
	}
}
#endif

Table randomly_place_all() {
	while (true) {
		Table table;
		std::bitset<TOTAL_TILES> bag;
		bag.set();

		while (place_random(table, bag)) {}

		if ((int)table.taken.size() == TOTAL_TILES) return table;
	}
}

int count_circles(const Table &table) {
	int count = 0;

	for (Pos pos : table.taken) {
		if (pos.y % 4 != 0) continue;
		if (table.taken.count(Pos{pos.x, pos.y+1}) != 0 &&
				table.taken.count(Pos{pos.x, pos.y+1}) != 0 &&
				table.taken.count(Pos{pos.x, pos.y+2}) != 0 &&
				table.taken.count(Pos{pos.x, pos.y+3}) != 0 &&
				table.taken.count(Pos{pos.x+1, pos.y+1}) != 0 &&
				table.taken.count(Pos{pos.x+1, pos.y+2}) != 0) {
			count++;
		}
	}

	return count;
}

int gap_loss(const Table &table) {
	int score = 0;

	for (Pos pos : table.boundary_list) {
		int neigh = 0;
		for (Pos p2 : adjacents(pos)) {
			if (table.taken.count(p2) != 0) neigh++;
		}
		score += 100 * (neigh - 1) * (neigh - 1);
	}

	for (Pos pos : table.taken) {
		int neigh = 0;
		for (Pos p2 : adjacents(pos)) {
			if (table.taken.count(p2) != 0) neigh++;
		}
		score -= neigh;
	}

	score -= 50 * count_circles(table);

	return score;
}

int circle_loss(const Table &table) {
	return MAXNUM + 1 - count_circles(table);
}

int together_loss(const Table &table) {
	Pos minpos{999999, 999999}, maxpos{0, 0};
	for (Pos pos : table.taken) {
		minpos.x = std::min(minpos.x, pos.x);
		maxpos.x = std::max(maxpos.x, pos.x);
		minpos.y = std::min(minpos.y, pos.y / 2);
		maxpos.y = std::max(maxpos.y, pos.y / 2);
	}

	return maxpos.x - minpos.x + maxpos.y - minpos.y;
}

int main() {
	int minscore = INT_MAX;
	while (true) {
		Table table = randomly_place_all();
		// int score = gap_loss(table);
		// int score = circle_loss(table);
		int score = together_loss(table);

		if (score < minscore) {
			minscore = score;
			std::string fname = std::to_string(score) + ".svg";
			std::cout << "score " << score << " -> " << fname << std::endl;
			std::ofstream f(fname);
			f << table.buildSVG() << std::endl;
		}
	}
}