summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore4
-rw-r--r--Makefile27
-rw-r--r--main.cpp558
-rw-r--r--svg.cpp29
-rw-r--r--svg.h35
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;
+ }
+ }
+}
diff --git a/svg.cpp b/svg.cpp
new file mode 100644
index 0000000..e855dab
--- /dev/null
+++ b/svg.cpp
@@ -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();
+}
diff --git a/svg.h b/svg.h
new file mode 100644
index 0000000..d3f2120
--- /dev/null
+++ b/svg.h
@@ -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;
+};