Skip to content

Instantly share code, notes, and snippets.

@hakomo

hakomo/ImageFromBlocks.cpp

Created May 23, 2019 14:37
Show Gist options
  • Save hakomo/f560b344986fff6c8ee0d87ff66d32ab to your computer and use it in GitHub Desktop.
Save hakomo/f560b344986fff6c8ee0d87ff66d32ab to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ImageFromBlocks.cpp
#if 1
#pragma GCC optimize "O3"
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <random>
#include <cassert>
#include <cmath>
#include <cstring>
#include <chrono>
using namespace std;
using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using f32 = float; using f64 = double;
template <class T> inline T sq(T a) { return a * a; }
template <class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; }
template <class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
void _u() { cerr << endl; } template <class H, class... T> void _u(H&& h, T&&... t) { cerr << h << ", "; _u(move(t)...); }
#define _polyfill(v) v
#define _overload3(a, b, c, d, ...) d
#define _rep3(i, a, b) for (i32 i = i32(a); i < i32(b); ++i)
#define _rep2(i, b) _rep3(i, 0, b)
#define _rep1(i) for (i32 i = 0; ; ++i)
#define rep(...) _polyfill(_overload3(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__))
#define A(a) begin(a), end(a)
#define S(a) i32((a).size())
#define U(...) { cerr << #__VA_ARGS__ << ": "; _u(__VA_ARGS__); }
#define lin U(__LINE__)
#define exi exit(0);
#endif
constexpr bool Deterministic = 0;
class rando {
unsigned y;
public:
rando(unsigned y) : y(y) {}
unsigned next() {
return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
}
int next(int b) {
return next() % b;
}
int next(int a, int b) {
return next(b - a) + a;
}
double nextDouble(double b = 1) {
return b * next() / 4294967296.0;
}
double nextDouble(double a, double b) {
return nextDouble(b - a) + a;
}
int operator() (int b) {
return next(b);
}
} rando(Deterministic ? 2463534242 : random_device()());
i32 W, H, discard;
f64 predictedPerPos[100][100];
map<vector<i32>, array<f64, 10>> as;
f64 kk[10][4][102];
pair<i32, f64> yp[10][4][102];
i32 id;
pair<array<f64, 10>, i32> ll[102][5];
i32 backupRealYs[102];
struct {
f64 normalizer;
i32 score[100][100][3][256];
f64 eval(i32 x, i32 y, u8 c[]) const {
return sq(1 - (score[y][x][0][c[0]] + score[y][x][1][c[1]] + score[y][x][2][c[2]]) * normalizer);
}
} evaluator;
struct Mino {
i32 i, r, n, m, w, h, x[4], y[4], top[4], bot[4];
bool contains(i32 a, i32 b) const {
rep (i, n) {
if (x[i] == a && y[i] == b) return true;
}
return false;
}
} minos[10][4];
struct {
i32 w, h, s;
u8 c[800][800][3];
void colorize(const Mino& m, u8 a[][3]) const {
i32 x0 = rando.next(w);
i32 y0 = rando.next(h);
rep (i, m.n) {
i32 x1 = rando.next(max(0, x0 - s), min(w, x0 + s + 1));
i32 y1 = rando.next(max(0, y0 - s), min(h, y0 + s + 1));
memcpy(a[i], c[y1][x1], sizeof(a[0]));
}
}
} colorizer;
struct powt {
f64 _[4], a[12];
powt() {
rep (i, -4, 12) {
a[i] = pow(0.5, i);
}
}
} powt;
struct Board {
i32 r, x;
f64 score0, score1;
f64 score, predicted;
f64 scoresPerMino[10];
struct {
i32 r, v;
} ys[104];
i32 calcVirtualY(i32 x) const {
return ys[x - 1].r | (ys[x].r - 1) | ys[x + 1].r ? min(ys[x].r, max(ys[x - 1].r, ys[x + 1].r) + 2) : 0;
}
void drop(const Mino& m, u8 colors[][3], i32 x, i32 y) {
this->r = m.r;
this->x = x;
rep (i, m.n) {
score += evaluator.eval(x + m.x[i] - 2, y + m.y[i], colors[i]);
}
predicted = yp[m.i][m.r & (m.m - 1)][x].second;
rep (i, m.w) {
ys[x + i].r = y + m.top[i];
}
rep (i, -1, m.w + 1) {
ys[x + i].v = calcVirtualY(x + i);
}
}
void updateScores0(i32 bx, i32 ex, f64 scores[]) const {
memset(scores, 0, sizeof(f64) * 10);
for (auto& ms : minos) {
rep (ri, ms[0].m) {
auto& m = ms[ri];
rep (x, max(2, bx - m.w - 1), min(W - m.w + 3, ex + 2)) {
scores[m.i] += kk[m.i][ri][x];
}
}
}
}
void g() {
for (auto& ms : minos) {
i32 c = 4 / ms[0].m;
rep (ri, ms[0].m) {
auto& m = ms[ri];
rep (x, 2, W - m.w + 3) {
i32 y = ys[x].r - m.bot[0];
rep (i, 1, m.w) {
chmin(y, ys[x + i].r - m.bot[i]);
}
if (y <= 0) {
yp[m.i][m.r][x].first = -1;
kk[m.i][m.r][x] = 0;
continue;
}
--y;
rep (i, m.w) {
ys[x + i].r = y + m.top[i];
}
f64 p = predicted;
i32 sm = 0;
for (i32 i : { -1, m.w }) {
i32 by = calcVirtualY(x + i);
sm += ys[x + i].v - by;
rep (y, by, ys[x + i].v) {
p += predictedPerPos[y][x - 2];
}
}
rep (i, m.w) {
i32 by = calcVirtualY(x + i);
sm += ys[x + i].v - by - m.bot[i] - 1;
rep (y, by, ys[x + i].v) {
p += predictedPerPos[y][x - 2];
}
}
yp[m.i][m.r][x] = { y, p };
kk[m.i][m.r][x] = sm < 12 ? powt.a[sm] * c : 0;
rep (i, m.w) {
ys[x + i].r = backupRealYs[x + i];
}
}
}
}
}
void updateScores1(i32 bx, i32 ex, f64 scores[]) {
rep (x, max(2, bx - 4 - 1), min(W - 1 + 3, ex + 5)) {
backupRealYs[x] = ys[x].r;
}
for (auto& ms : minos) {
i32 c = 4 / ms[0].m;
rep (ri, ms[0].m) {
auto& m = ms[ri];
rep (x, max(2, bx - m.w - 1), min(W - m.w + 3, ex + 2)) {
i32 y = ys[x].r - m.bot[0];
rep (i, 1, m.w) {
chmin(y, ys[x + i].r - m.bot[i]);
}
if (y <= 0) continue;
--y;
rep (i, m.w) {
ys[x + i].r = y + m.top[i];
}
i32 sm = 0;
for (i32 i : { -1, m.w }) {
sm += ys[x + i].v - calcVirtualY(x + i);
}
rep (i, m.w) {
sm += ys[x + i].v - calcVirtualY(x + i) - m.bot[i] - 1;
}
if (sm < 12) {
scores[m.i] += powt.a[sm] * c;
}
rep (i, m.w) {
ys[x + i].r = backupRealYs[x + i];
}
}
}
}
}
void dropAndUpdateScores(const Mino& m, u8 colors[][3], i32 x, i32 y) {
if (ll[x][m.w].second != id) {
ll[x][m.w].second = id;
updateScores0(x, x + m.w, ll[x][m.w].first.data());
}
rep (i, 10) {
scoresPerMino[i] -= ll[x][m.w].first[i];
}
drop(m, colors, x, y);
static vector<i32> a;
a = { x };
rep (i, m.w) {
a.emplace_back(ys[x + i].r);
}
if (!as.count(a)) {
updateScores1(x, x + m.w, as[a].data());
}
{
auto& s = as[a];
rep (i, 10) {
scoresPerMino[i] += s[i];
}
}
static f64 c[]{
1.0 / (W * 2 + (W - 1) * 2),
1.0 / (W * 2 + (W - 2) * 2),
1.0 / ((W - 1) * 4),
1.0 / (W * 2 + (W - 3) * 2),
1.0 / ((W - 1) * 4),
1.0 / ((W - 2) * 2 + (W - 1) * 2),
1.0 / ((W - 2) * 2 + (W - 1) * 2),
1.0 / ((W - 2) * 2 + (W - 1) * 2),
1.0 / ((W - 2) * 2 + (W - 1) * 2),
1.0 / ((W - 2) * 2 + (W - 1) * 2),
};
f64 scores[10];
rep (i, 10) {
scores[i] = scoresPerMino[i] * c[i];
}
sort(A(scores));
score1 = 0;
rep (i, 10) {
score1 += scores[i] * powt.a[i];
}
score0 = score / predicted;
}
};
Board rootbo;
vector<Board> nextbos;
struct ImageFromBlocks {
string init(i32 imageH, i32 blockS, i32 maxDiscard, const vector<i32>& image) const {
i32 imageW = S(image) / imageH;
W = imageW / blockS;
H = imageH / blockS;
discard = maxDiscard;
colorizer.w = imageW;
colorizer.h = imageH;
colorizer.s = blockS;
rep (y, colorizer.h) {
rep (x, colorizer.w) {
rep (t, 3) {
colorizer.c[y][x][t] = image[y * colorizer.w + x] >> t * 8 & 255;
}
}
}
{
evaluator.normalizer = 1.0 / 765 / sq(blockS);
i32 a[257], b[257];
rep (y0, H) {
rep (x0, W) {
rep (t, 3) {
fill(A(a), 0);
fill(A(b), 0);
rep (y1, y0 * blockS, (y0 + 1) * blockS) {
rep (x1, x0 * blockS, (x0 + 1) * blockS) {
i32 c = image[y1 * imageW + x1] >> t * 8 & 255;
a[c + 1] += c;
++b[c + 1];
}
}
rep (c, 256) {
a[c + 1] += a[c];
b[c + 1] += b[c];
}
rep (c, 256) {
evaluator.score[y0][x0][t][c] = c * (b[c] - b[0]) - (a[c] - a[0]) + (a[256] - a[c]) - c * (b[256] - b[c]);
}
}
}
}
}
{
unordered_map<i32, i32> mp;
for (i32 c : image) {
++mp[c];
}
vector<pair<i32, i32>> a(A(mp));
i32 s = min(S(a), 50000000 / (W * H));
random_shuffle(A(a), rando);
f64 sm = 0;
rep (i, s) {
sm += a[i].second;
}
sm = 1 / sm;
rep (y, H) {
rep (x, W) {
predictedPerPos[y][x] = 0;
f64 s2 = 0;
rep (i, s) {
u8 c[3];
rep (t, 3) {
c[t] = a[i].first >> (t << 3) & 255;
}
f64 sc = evaluator.eval(x, y, c);
predictedPerPos[y][x] += sc * a[i].second;
s2 += sq(sc) * a[i].second;
}
predictedPerPos[y][x] *= sm;
predictedPerPos[y][x] += 0.5 - 0.1 * y / (H - 1) + sqrt(s2 * sm - sq(predictedPerPos[y][x])) * 2;
}
}
}
{
vector<vector<vector<i32>>> a{
{{0,1}},
{{0,1,2}},
{{0,-1},{1,2}},
{{0,1,2,3}},
{{0,1},{2,3}},
{{-1,0,-1},{1,2,3}},
{{0,1,-1},{-1,2,3}},
{{-1,0,1},{2,3,-1}},
{{0,-1,-1},{1,2,3}},
{{-1,-1,0},{1,2,3}}
};
rep (i, S(a)) {
auto& b = a[i];
i32 n = 0;
rep (y, S(b)) {
rep (x, S(b[0])) {
n += b[y][x] != -1;
}
}
rep (r, 4) {
auto& m = minos[i][r];
m.i = i;
m.r = r;
m.n = n;
m.w = S(b[0]);
m.h = S(b);
rep (x, m.w) {
i32 y = 0;
for (; b[y][x] == -1; ++y);
m.top[x] = y;
y = m.h - 1;
for (; b[y][x] == -1; --y);
m.bot[x] = y;
}
rep (y, m.h) {
rep (x, m.w) {
if (b[y][x] != -1) {
m.x[b[y][x]] = x;
m.y[b[y][x]] = y;
}
}
}
vector<vector<i32>> c(m.w, vector<i32>(m.h));
rep (y, m.h) {
rep (x, m.w) {
c[x][m.h - 1 - y] = b[y][x];
}
}
b = c;
}
}
rep (ri, 4) {
minos[0][ri].m = 2;
minos[1][ri].m = 2;
minos[2][ri].m = 4;
minos[3][ri].m = 2;
minos[4][ri].m = 1;
minos[5][ri].m = 4;
minos[6][ri].m = 2;
minos[7][ri].m = 2;
minos[8][ri].m = 4;
minos[9][ri].m = 4;
}
}
rootbo.score = rootbo.predicted = 0;
rep (x, W + 4) {
rootbo.ys[x].r = rootbo.ys[x].v = 2 <= x && x < W + 2 ? H : 0;
}
rootbo.updateScores1(2, W + 2, rootbo.scoresPerMino);
return "";
}
string placePiece(i32 h, const vector<i32>& piece, i32 _) const {
i32 w = S(piece) / h;
i32 mi = 0;
for (; ; ++mi) {
auto& m = minos[mi][0];
bool ok = true;
rep (y, h) {
rep (x, w) {
if (piece[y * w + x] == -1) {
if (m.contains(x, y)) {
ok = false;
break;
}
} else {
if (!m.contains(x, y)) {
ok = false;
break;
}
}
}
if (!ok) break;
}
if (ok) break;
}
auto& ms = minos[mi];
u8 colors[4][3];
{
auto& m = ms[0];
rep (i, m.n) {
i32 c = piece[m.y[i] * m.w + m.x[i]];
rep (t, 3) {
colors[i][t] = c >> t * 8 & 255;
}
}
}
rep (x, 2, W + 2) {
backupRealYs[x] = rootbo.ys[x].r;
}
rootbo.g();
struct Neighbor {
i32 r, x, y;
Neighbor() {}
Neighbor(i32 r, i32 x, i32 y) : r(r), x(x), y(y) {}
};
f64 mn0 = 1 << 30, mx0 = -1 << 30;
static vector<Neighbor> neighbors;
neighbors.clear();
for (auto& m : ms) {
rep (x, 2, W - m.w + 3) {
auto& p = yp[m.i][m.r & (m.m - 1)][x];
i32 y = p.first;
f64 predicted = p.second;
if (y == -1) continue;
neighbors.emplace_back(m.r, x, y);
f64 score = rootbo.score;
rep (i, m.n) {
score += evaluator.eval(x + m.x[i] - 2, y + m.y[i], colors[i]);
}
chmin(mn0, score / predicted);
chmax(mx0, score / predicted);
}
}
if (discard) {
constexpr i32 n = 50;
f64 sm = 0.5;
f64 rm = 0;
rep (x, 2, W + 2) {
rm += rootbo.ys[x].v;
}
rm = discard / (discard + rm / 3.6) / 1.25 * (n + 1);
rep (_, n) {
auto& ms = minos[rando.next(10)];
f64 mx = 0;
u8 colors[4][3];
colorizer.colorize(ms[0], colors);
for (auto& m : ms) {
rep (x, 2, W - m.w + 3) {
auto& p = yp[m.i][m.r & (m.m - 1)][x];
i32 y = p.first;
f64 predicted = p.second;
if (y == -1 || mx * predicted > rootbo.score + m.n) continue;
f64 score = rootbo.score;
rep (i, m.n) {
score += evaluator.eval(x + m.x[i] - 2, y + m.y[i], colors[i]);
}
if (mx * predicted < score) {
mx = score / predicted;
if (mx > mx0) goto END;
}
}
}
END:
if (mx < mx0) {
sm += 1;
} else if (mx == mx0) {
sm += 0.5;
}
if (rm < sm) break;
}
if (rm > sm) {
--discard;
return "d";
}
}
nextbos.clear();
++id;
as.clear();
f64 mn1 = 1 << 30, mx1 = -1 << 30;
for (auto& n : neighbors) {
nextbos.emplace_back(rootbo);
auto& bo = nextbos.back();
bo.dropAndUpdateScores(ms[n.r], colors, n.x, n.y);
chmin(mn1, bo.score1);
chmax(mx1, bo.score1);
}
if (S(nextbos) == 0) {
return "0 0";
} else if (S(nextbos) == 1) {
auto& bo = nextbos[0];
rootbo = bo;
return to_string(bo.r) + ' ' + to_string(bo.x - 2);
}
auto& bo = *max_element(A(nextbos), [&](const Board& a, const Board& b) {
constexpr f64 co = 0.013;
return (a.score0 - mn0) / (mx0 - mn0) + (a.score1 - mn1) / (mx1 - mn1) * co
< (b.score0 - mn0) / (mx0 - mn0) + (b.score1 - mn1) / (mx1 - mn1) * co;
});
rootbo = bo;
return to_string(bo.r) + ' ' + to_string(bo.x - 2);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment