diff options
| -rw-r--r-- | .gitignore | 4 | ||||
| -rw-r--r-- | Makefile | 27 | ||||
| -rw-r--r-- | main.cpp | 558 | ||||
| -rw-r--r-- | svg.cpp | 29 | ||||
| -rw-r--r-- | svg.h | 35 |
5 files changed, 653 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..772f252 --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +obj/ +compile_commands.json +tri +*.svg diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..c4913e7 --- /dev/null +++ b/Makefile @@ -0,0 +1,27 @@ +CXX = g++ +CXXFLAGS = -Wall -Wextra -std=c++17 -O2 -g +LDFLAGS = +TARGET = tri + +OBJDIR = obj + +.PHONY: all clean + +all: $(TARGET) + +clean: + @echo "Cleaning" + @rm -f $(TARGET) + @rm -rf $(OBJDIR) + + +$(OBJDIR)/%.o: %.cpp $(wildcard *.h) | $(OBJDIR) + @echo "CXX $<" + @$(CXX) $(CXXFLAGS) -c -o $@ $< + +$(TARGET): $(patsubst %.cpp,$(OBJDIR)/%.o,$(wildcard *.cpp)) | $(OBJDIR) + @echo "LD -o $@" + @$(CXX) -o $@ $^ $(LDFLAGS) + +$(OBJDIR): + @mkdir -p $(OBJDIR) diff --git a/main.cpp b/main.cpp new file mode 100644 index 0000000..3da2410 --- /dev/null +++ b/main.cpp @@ -0,0 +1,558 @@ +#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; + } + } +} @@ -0,0 +1,29 @@ +#include <sstream> +#include "svg.h" + + +Polygon::Polygon(std::vector<std::array<double, 2>> pts, std::string bg) + : pts{move(pts)}, bg{move(bg)} +{} + +std::string Polygon::svg() const { + std::ostringstream ss; + ss << "<path d=\""; + for (size_t i = 0; i < pts.size(); i++) { + if (i == 0) ss << 'M'; else ss << 'L'; + ss << pts[i][0] << ' ' << pts[i][1] << ' '; + } + ss << "Z\" stroke=\"black\" fill=\"" << bg << "\" stroke-width=\"0.03px\"/>"; + return ss.str(); +} + +Text::Text(double x, double y, double rotation, std::string text) + : x{x}, y{y}, rotation{rotation}, text{move(text)} +{} + +std::string Text::svg() const { + std::ostringstream ss; + ss << "<text x=\"" << x << "\" y=\"" << y - 0.04 << "\" transform=\"rotate(" << rotation << ")\" style=\"font-size:0.3px\" text-anchor=\"middle\" dominant-baseline=\"middle\">"; + ss << text << "</text>"; + return ss.str(); +} @@ -0,0 +1,35 @@ +#pragma once + +#include <vector> +#include <array> +#include <string> + + +struct Figure { + Figure() = default; + inline virtual ~Figure() {} + Figure(const Figure &other) = default; + Figure(Figure &&other) = default; + Figure& operator=(const Figure &other) = default; + Figure& operator=(Figure &&other) = default; + virtual std::string svg() const = 0; +}; + +struct Polygon final : public Figure { + std::vector<std::array<double, 2>> pts; + std::string bg; + + Polygon(std::vector<std::array<double, 2>> pts, std::string bg); + + std::string svg() const override; +}; + +struct Text final : public Figure { + double x, y; + double rotation; + std::string text; + + Text(double x, double y, double rotation, std::string text); + + std::string svg() const override; +}; |