Skip to content

Instantly share code, notes, and snippets.

@kik kik/gist:6209891
Created Aug 12, 2013

Embed
What would you like to do?
ICFPC 2013 最終コード
#include <unistd.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <iostream>
#include <utility>
#include <string>
#include <random>
#include <memory>
using namespace std;
#define STACK 2
typedef unsigned long long ull;
enum Head {
ZERO = 0x100,
ONE = 0x110,
VAR_1 = 0x120,
VAR_2 = 0x130,
VAR_3 = 0x140,
IF0 = 0x103,
FOLD = 0x213,
NOT = 0x111,
SHL1 = 0x121,
SHR1 = 0x131,
SHR4 = 0x141,
SHR16 = 0x151,
AND = 0x112,
OR = 0x122,
XOR = 0x132,
PLUS = 0x142,
};
static int nchild(Head h) { return h & 0xF; }
static int hsize(Head h) { return h >> 8; }
struct FNode {
Head h;
FNode *next;
};
struct FNode1 : public FNode {
FNode *t1;
};
struct FNode2 : public FNode {
FNode *t1;
FNode *t2;
};
struct FNode3 : public FNode {
FNode *t1;
FNode *t2;
FNode *t3;
};
template<class V>
typename V::ret_t fnode_fold(FNode *tin, typename V::param_t p, V& v)
{
switch (nchild(tin->h)) {
case 0: {
FNode *t = static_cast<FNode *>(tin);
switch (t->h) {
case ZERO:
return v.fold_ZERO(p);
case ONE:
return v.fold_ONE(p);
case VAR_1:
return v.fold_VAR_1(p);
case VAR_2:
return v.fold_VAR_2(p);
case VAR_3:
return v.fold_VAR_3(p);
}
abort();
}
case 1: {
FNode1 *t = static_cast<FNode1 *>(tin);
switch (t->h) {
case NOT:
return v.fold_NOT(t->t1, p);
case SHL1:
return v.fold_SHL1(t->t1, p);
case SHR1:
return v.fold_SHR1(t->t1, p);
case SHR4:
return v.fold_SHR4(t->t1, p);
case SHR16:
return v.fold_SHR16(t->t1, p);
}
abort();
}
case 2: {
FNode2 *t = static_cast<FNode2 *>(tin);
switch (t->h) {
case AND:
return v.fold_AND(t->t1, t->t2, p);
case OR:
return v.fold_OR(t->t1, t->t2, p);
case XOR:
return v.fold_XOR(t->t1, t->t2, p);
case PLUS:
return v.fold_PLUS(t->t1, t->t2, p);
}
abort();
}
case 3: {
FNode3 *t = static_cast<FNode3 *>(tin);
switch (t->h) {
case FOLD:
return v.fold_FOLD(t->t1, t->t2, t->t3, p);
case IF0:
return v.fold_IF0(t->t1, t->t2, t->t3, p);
}
abort();
}
}
abort();
}
#if 0
struct Vex
{
typedef void ret_t;
typedef int param_t;
ret_t r(FNode *t, param_t p)
{
return fnode_fold(t, p, *this);
}
ret_t fold_ZERO(param_t p)
{
}
ret_t fold_ONE(param_t p)
{
}
ret_t fold_VAR_1(param_t p)
{
}
ret_t fold_VAR_2(param_t p)
{
}
ret_t fold_VAR_3(param_t p)
{
}
ret_t fold_NOT(FNode *t1, param_t p)
{
}
ret_t fold_SHL1(FNode *t1, param_t p)
{
}
ret_t fold_SHR1(FNode *t1, param_t p)
{
}
ret_t fold_SHR4(FNode *t1, param_t p)
{
}
ret_t fold_SHR16(FNode *t1, param_t p)
{
}
ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
{
}
ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
{
}
ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
{
}
ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
{
}
ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
}
ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
}
};
#endif
struct Vdump
{
typedef void ret_t;
typedef ostream& param_t;
ret_t r(FNode *t, param_t p)
{
return fnode_fold(t, p, *this);
}
ret_t fold_ZERO(param_t p)
{
p << "0";
}
ret_t fold_ONE(param_t p)
{
p << "1";
}
ret_t fold_VAR_1(param_t p)
{
p << "x";
}
ret_t fold_VAR_2(param_t p)
{
p << "y";
}
ret_t fold_VAR_3(param_t p)
{
p << "z";
}
ret_t fold_NOT(FNode *t1, param_t p)
{
p << "(not ";
r(t1, p);
p << ")";
}
ret_t fold_SHL1(FNode *t1, param_t p)
{
p << "(shl1 ";
r(t1, p);
p << ")";
}
ret_t fold_SHR1(FNode *t1, param_t p)
{
p << "(shr1 ";
r(t1, p);
p << ")";
}
ret_t fold_SHR4(FNode *t1, param_t p)
{
p << "(shr4 ";
r(t1, p);
p << ")";
}
ret_t fold_SHR16(FNode *t1, param_t p)
{
p << "(shr16 ";
r(t1, p);
p << ")";
}
ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
{
p << "(and ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
{
p << "(or ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
{
p << "(xor ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
{
p << "(plus ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
p << "(fold ";
r(t1, p);
p << " ";
r(t2, p);
p << " (lambda (y z) ";
r(t3, p);
p << "))";
}
ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
p << "(if0 ";
r(t1, p);
p << " ";
r(t2, p);
p << " ";
r(t3, p);
p << ")";
}
};
static void fdump(FNode *p, ostream& os)
{
Vdump().r(p, os);
}
struct Veval
{
typedef ull ret_t;
typedef const ull *param_t;
ret_t r(FNode *t, param_t p)
{
return fnode_fold(t, p, *this);
}
ret_t fold_ZERO(param_t p)
{
return 0;
}
ret_t fold_ONE(param_t p)
{
return 1;
}
ret_t fold_VAR_1(param_t p)
{
return p[0];
}
ret_t fold_VAR_2(param_t p)
{
return p[1];
}
ret_t fold_VAR_3(param_t p)
{
return p[2];
}
ret_t fold_NOT(FNode *t1, param_t p)
{
return ~r(t1, p);
}
ret_t fold_SHL1(FNode *t1, param_t p)
{
return r(t1, p) << 1;
}
ret_t fold_SHR1(FNode *t1, param_t p)
{
return r(t1, p) >> 1;
}
ret_t fold_SHR4(FNode *t1, param_t p)
{
return r(t1, p) >> 4;
}
ret_t fold_SHR16(FNode *t1, param_t p)
{
return r(t1, p) >> 16;
}
ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
{
return r(t1, p) & r(t2, p);
}
ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
{
return r(t1, p) | r(t2, p);
}
ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
{
return r(t1, p) ^ r(t2, p);
}
ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
{
return r(t1, p) + r(t2, p);
}
ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
ull v1 = r(t1, p);
ull v2 = r(t2, p);
ull nv[3];
nv[0] = p[0];
nv[2] = v2;
for (int i = 0; i < 8; i++) {
nv[1] = v1 & 0xFF;
nv[2] = r(t3, nv);
v1 >>= 8;
}
return nv[2];
}
ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
return r(t1, p) ? r(t3, p) : r(t2, p);
}
};
static ull feval(FNode *t, ull x)
{
ull nv[1] = { x };
return Veval().r(t, nv);
}
struct Vevalc
{
// (value, is_const)
typedef pair<ull, bool> ret_t;
typedef const pair<ull, bool> *param_t;
ret_t r(FNode *t, param_t p)
{
return fnode_fold(t, p, *this);
}
ret_t fold_ZERO(param_t p)
{
return make_pair(0, true);
}
ret_t fold_ONE(param_t p)
{
return make_pair(1, true);
}
ret_t fold_VAR_1(param_t p)
{
return p[0];
}
ret_t fold_VAR_2(param_t p)
{
return p[1];
}
ret_t fold_VAR_3(param_t p)
{
return p[2];
}
ret_t fold_NOT(FNode *t1, param_t p)
{
auto v1 = r(t1, p);
return make_pair(~v1.first, v1.second);
}
ret_t fold_SHL1(FNode *t1, param_t p)
{
auto v1 = r(t1, p);
return make_pair(v1.first << 1, v1.second);
}
ret_t fold_SHR1(FNode *t1, param_t p)
{
auto v1 = r(t1, p);
return make_pair(v1.first >> 1, v1.second);
}
ret_t fold_SHR4(FNode *t1, param_t p)
{
auto v1 = r(t1, p);
return make_pair(v1.first >> 4, v1.second);
}
ret_t fold_SHR16(FNode *t1, param_t p)
{
auto v1 = r(t1, p);
return make_pair(v1.first >> 16, v1.second);
}
ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
{
auto v1 = r(t1, p);
if (v1.second) {
auto v2 = r(t2, p);
return make_pair(v1.first & v2.first, v1.second && v2.second);
} else {
return v1;
}
}
ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
{
auto v1 = r(t1, p);
if (v1.second) {
auto v2 = r(t2, p);
return make_pair(v1.first | v2.first, v1.second && v2.second);
} else {
return v1;
}
}
ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
{
auto v1 = r(t1, p);
if (v1.second) {
auto v2 = r(t2, p);
return make_pair(v1.first ^ v2.first, v1.second && v2.second);
} else {
return v1;
}
}
ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
{
auto v1 = r(t1, p);
if (v1.second) {
auto v2 = r(t2, p);
return make_pair(v1.first + v2.first, v1.second && v2.second);
} else {
return v1;
}
}
ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
auto v1 = r(t1, p);
auto v2 = r(t2, p);
pair<ull, bool> nv[3];
nv[0] = p[0];
nv[2] = v2;
for (int i = 0; i < 8; i++) {
nv[1] = make_pair(v1.first & 0xFF, v1.second);
nv[2] = r(t3, nv);
v1.first >>= 8;
}
return nv[2];
}
ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
{
auto v1 = r(t1, p);
if (v1.second) {
return v1.first ? r(t3, p) : r(t2, p);
} else {
return v1;
}
}
};
static pair<ull, bool> fevalc(FNode *t)
{
pair<ull, bool> nv[3] = { make_pair(0, false), make_pair(0, false), make_pair(0, false) };
return Vevalc().r(t, nv);
}
template<class FN>
struct Alloc {
FN *next;
Alloc() : next(0) {
}
FN *alloc()
{
if (!next) {
FN *p = new FN[2048];
for (int i = 0; i < 2048; i++) {
p[i].next = next;
next = &p[i];
}
}
FN *p = next;
next = static_cast<FN *>(next->next);
return p;
}
FN *free(FN *p)
{
p->next = next;
next = p;
}
};
static Alloc<FNode1> falloc1;
static Alloc<FNode2> falloc2;
static Alloc<FNode3> falloc3;
//
// fnodes[0][size]: use x
// fnodes[1][size]; use x, y, z
//
static vector<FNode *> fnodes[STACK];
static void addLeafNode(int s, int v, Head h)
{
FNode *p = new FNode();
p->h = h;
p->next = fnodes[v][s];
fnodes[v][s] = p;
}
static void addFoldNode(int s, int v, FNode *t1, FNode *t2, FNode *t3)
{
FNode3 *p = falloc3.alloc();
p->h = FOLD;
p->t1 = t1;
p->t2 = t2;
p->t3 = t3;
p->next = fnodes[v][s];
fnodes[v][s] = p;
}
static void addIf0Node(int s, int v, FNode *t1, FNode *t2, FNode *t3)
{
FNode3 *p = falloc3.alloc();
p->h = IF0;
p->t1 = t1;
p->t2 = t2;
p->t3 = t3;
p->next = fnodes[v][s];
fnodes[v][s] = p;
}
static void addOp2Node(int s, int v, Head h, FNode *t1, FNode *t2)
{
FNode2 *p = falloc2.alloc();
p->h = h;
p->t1 = t1;
p->t2 = t2;
p->next = fnodes[v][s];
fnodes[v][s] = p;
}
static void addOp1Node(int s, int v, Head h, FNode *t1)
{
FNode1 *p = falloc1.alloc();
p->h = h;
p->t1 = t1;
p->next = fnodes[v][s];
fnodes[v][s] = p;
}
static FNode *c_zero;
static FNode *c_one;
static FNode *c_var_1;
static FNode *c_var_2;
static FNode *c_var_3;
static pair<int, bool> fhead1(FNode *t)
{
if (nchild(t->h) == 1) {
switch (t->h) {
case NOT:
return make_pair(0, true);
case SHL1:
return make_pair(-1, false);
case SHR1:
return make_pair(1, false);
case SHR4:
return make_pair(4, false);
case SHR16:
return make_pair(16, false);
}
} else {
return make_pair(0, false);
}
}
static void initFixed(int size)
{
for (int i = 0; i < STACK; i++) fnodes[i].resize(size + 1, NULL);
addLeafNode(1, 0, ZERO);
c_zero = fnodes[0][1];
addLeafNode(1, 0, ONE);
c_one = fnodes[0][1];
addLeafNode(1, 0, VAR_1);
c_var_1 = fnodes[0][1];
addLeafNode(1, 1, VAR_2);
c_var_2 = fnodes[1][1];
addLeafNode(1, 1, VAR_3);
c_var_3 = fnodes[1][1];
for (int s = 2; s <= size; s++) {
if (s >= 5) {
for (int s1 = 1; s1 <= s - 4; s1++) {
for (int s2 = 1; s2 <= s - s1 - 3; s2++) {
int s3 = s - s1 - s2 - 2;
for (int v12 = 0; v12 < STACK - 1; v12++) {
for (int v3 = 0; v3 <= v12 + 1; v3++) {
for (FNode *t3 = fnodes[v3][s3]; t3; t3 = t3->next) {
auto c3 = fevalc(t3);
if (c3.second) continue;
if (t3 == c_var_3) continue;
for (FNode *t1 = fnodes[v12][s1]; t1; t1 = t1->next) {
for (FNode *t2 = fnodes[v12][s2]; t2; t2 = t2->next) {
addFoldNode(s, v12, t1, t2, t3);
}
}
}
}
}
}
}
}
if (s >= 4) {
for (int s1 = 1; s1 <= s - 3; s1++) {
for (int s2 = 1; s2 <= s - s1 - 2; s2++) {
int s3 = s - s1 - s2 - 1;
for (int v1 = 0; v1 < STACK; v1++) {
for (int v2 = 0; v2 < STACK; v2++) {
for (int v3 = 0; v3 < STACK; v3++) {
int v = max(v1, max(v2, v3));
for (FNode *t1 = fnodes[v1][s1]; t1; t1 = t1->next) {
auto c1 = fevalc(t1);
if (c1.second) continue;
for (FNode *t2 = fnodes[v2][s2]; t2; t2 = t2->next) {
for (FNode *t3 = fnodes[v3][s3]; t3; t3 = t3->next) {
addIf0Node(s, v, t1, t2, t3);
}
}
}
}
}
}
}
}
}
if (s >= 3) {
for (int s1 = 1; s1 <= s - 2; s1++) {
int s2 = s - s1 - 1;
for (int v1 = 0; v1 < STACK; v1++) {
for (int v2 = 0; v2 < STACK; v2++) {
int v = max(v1, v2);
for (FNode *t1 = fnodes[v1][s1]; t1; t1 = t1->next) {
auto c1 = fevalc(t1);
FNode *t2;
if (v1 == v2 && s1 == s2) {
t2 = t1->next;
} else {
t2 = fnodes[v2][s2];
}
for (; t2; t2 = t2->next) {
bool e_and = true;
bool e_or = true;
bool e_xor = true;
bool e_plus = true;
if (c1.second) {
switch (c1.first) {
case 0ULL:
continue;
case ~0ULL:
e_and = e_or = e_xor = false;
break;
}
}
auto c2 = fevalc(t2);
if (c2.second) {
switch (c1.first) {
case 0ULL:
continue;
case ~0ULL:
e_and = e_or = e_xor = false;
break;
}
}
if (c1.second && c2.second) {
switch (c1.first & c2.first) {
case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
e_and = false;
}
switch (c1.first | c2.first) {
case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
e_or = false;
}
switch (c1.first ^ c2.first) {
case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
e_xor = false;
}
switch (c1.first + c2.first) {
case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
e_plus = false;
}
}
auto h1 = fhead1(t1);
auto h2 = fhead1(t2);
if (h1.second && h2.second) {
// (op (not ...) (not ...))
e_and = e_or = e_xor = false;
}
if (h1 == h2) {
if (h1.first < 0) {
// (op (... << 1) (... << 1))
continue;
}
if (h1.first > 0) {
// (op (... >> 1) (... >> 1))
e_and = e_or = e_xor = false;
}
}
if (e_and) addOp2Node(s, v, AND, t1, t2);
if (e_or) addOp2Node(s, v, OR, t1, t2);
if (e_xor) addOp2Node(s, v, XOR, t1, t2);
if (e_plus) addOp2Node(s, v, PLUS, t1, t2);
}
}
}
}
}
}
{
int s1 = s - 1;
for (int v1 = 0; v1 < STACK; v1++) {
int v = v1;
for (FNode *t1 = fnodes[v1][s1]; t1; t1 = t1->next) {
bool e_not = true;
bool e_shl1 = true;
bool e_shr1 = true;
bool e_shr4 = true;
bool e_shr16 = true;
auto c1 = fevalc(t1);
if (c1.second) {
if (c1.first == 0ULL) {
e_shl1 = e_shr1 = e_shr4 = e_shr16 = false;
} else if (c1.first <= 2ULL) {
e_shr1 = e_shr4 = e_shr16 = false;
} else if (c1.first <= 0x10uLL) {
e_shr4 = e_shr16 = false;
} else if (c1.first <= 0x10000) {
e_shr16 = false;
}
switch (~c1.first) {
case 0ULL: case 1ULL: e_not = false;
}
}
if (nchild(t1->h) == 1) {
switch (t1->h) {
case SHR1:
e_shr4 = e_shr16 = false;
break;
case SHR4:
e_shr16 = false;
break;
}
}
if (e_not) addOp1Node(s, v, NOT, t1);
if (e_shl1) addOp1Node(s, v, SHL1, t1);
if (e_shr1) addOp1Node(s, v, SHR1, t1);
if (e_shr4) addOp1Node(s, v, SHR4, t1);
if (e_shr16) addOp1Node(s, v, SHR16, t1);
}
}
}
}
}
static vector<pair<ull, ull> > evalResults;
static void doEval(const vector<ull>& v)
{
for (auto i = v.begin(); i != v.end();) {
cout << 'E';
int n = 0;
for (auto j = i; j != v.end() && n < 256; j++, n++) {
if (j != i) cout << " ";
cout << *j;
}
cout << endl;
auto j = i;
for (int k = 0; k < n; k++, j++) {
ull v;
cin >> v;
evalResults.push_back(make_pair(*j, v));
}
cin.ignore(256, '\n');
i = i + n;
}
}
static int doGuess(FNode *p)
{
cout << 'G';
cout << "(lambda (x) ";
fdump(p, cout);
cout << ")";
cout << endl;
int c = cin.get();
if (c == 'W') {
cin.ignore(256, '\n');
return 1;
} else if (c == 'M') {
ull x, y, z;
cin >> x >> y >> z;
evalResults.push_back(make_pair(x, y));
cin.ignore(256, '\n');
}
return 0;
}
struct DyNode;
typedef shared_ptr<DyNode> PyNode;
struct DyNode {
Head h;
PyNode cs[3];
FNode *t;
DyNode(Head h) : h(h), t(0)
{
}
DyNode(FNode *p) : h(p->h), t(p)
{
}
};
static PyNode start_modify(FNode *t)
{
PyNode p(new DyNode(t->h));
switch (nchild(t->h)) {
case 0:
break;
case 1: {
FNode1 *x = static_cast<FNode1 *>(t);
p->cs[0] = start_modify(x->t1);
break;
}
case 2: {
FNode2 *x = static_cast<FNode2 *>(t);
p->cs[0] = start_modify(x->t1);
p->cs[1] = start_modify(x->t2);
break;
}
case 3: {
FNode3 *x = static_cast<FNode3 *>(t);
p->cs[0] = start_modify(x->t1);
p->cs[1] = start_modify(x->t2);
p->cs[2] = start_modify(x->t3);
break;
}
}
p->t = 0;
return p;
}
static PyNode pdup(PyNode t)
{
if (t->t) {
return start_modify(t->t);
} else {
PyNode p(new DyNode(t->h));
for (int i = 0; i < nchild(p->h); i++) {
p->cs[i] = pdup(t->cs[i]);
}
p->t = 0;
return p;
}
}
template<class V>
typename V::ret_t pnode_fold(PyNode t, typename V::param_t p, V& v)
{
if (t->t) {
return v.fold_Fixed(t->t, p);
}
switch (nchild(t->h)) {
case 0: {
switch (t->h) {
case ZERO:
return v.fold_ZERO(p);
case ONE:
return v.fold_ONE(p);
case VAR_1:
return v.fold_VAR_1(p);
case VAR_2:
return v.fold_VAR_2(p);
case VAR_3:
return v.fold_VAR_3(p);
}
abort();
}
case 1: {
switch (t->h) {
case NOT:
return v.fold_NOT(t->cs[0], p);
case SHL1:
return v.fold_SHL1(t->cs[0], p);
case SHR1:
return v.fold_SHR1(t->cs[0], p);
case SHR4:
return v.fold_SHR4(t->cs[0], p);
case SHR16:
return v.fold_SHR16(t->cs[0], p);
}
abort();
}
case 2: {
switch (t->h) {
case AND:
return v.fold_AND(t->cs[0], t->cs[1], p);
case OR:
return v.fold_OR(t->cs[0], t->cs[1], p);
case XOR:
return v.fold_XOR(t->cs[0], t->cs[1], p);
case PLUS:
return v.fold_PLUS(t->cs[0], t->cs[1], p);
}
abort();
}
case 3: {
switch (t->h) {
case FOLD:
return v.fold_FOLD(t->cs[0], t->cs[1], t->cs[2], p);
case IF0:
return v.fold_IF0(t->cs[0], t->cs[1], t->cs[2], p);
}
abort();
}
}
abort();
}
struct VPdump
{
typedef void ret_t;
typedef ostream& param_t;
ret_t r(PyNode t, param_t p)
{
return pnode_fold(t, p, *this);
}
ret_t fold_Fixed(FNode *t1, param_t p)
{
fdump(t1, p);
}
ret_t fold_ZERO(param_t p)
{
p << "0";
}
ret_t fold_ONE(param_t p)
{
p << "1";
}
ret_t fold_VAR_1(param_t p)
{
p << "x";
}
ret_t fold_VAR_2(param_t p)
{
p << "y";
}
ret_t fold_VAR_3(param_t p)
{
p << "z";
}
ret_t fold_NOT(PyNode t1, param_t p)
{
p << "(not ";
r(t1, p);
p << ")";
}
ret_t fold_SHL1(PyNode t1, param_t p)
{
p << "(shl1 ";
r(t1, p);
p << ")";
}
ret_t fold_SHR1(PyNode t1, param_t p)
{
p << "(shr1 ";
r(t1, p);
p << ")";
}
ret_t fold_SHR4(PyNode t1, param_t p)
{
p << "(shr4 ";
r(t1, p);
p << ")";
}
ret_t fold_SHR16(PyNode t1, param_t p)
{
p << "(shr16 ";
r(t1, p);
p << ")";
}
ret_t fold_AND(PyNode t1, PyNode t2, param_t p)
{
p << "(and ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_OR(PyNode t1, PyNode t2, param_t p)
{
p << "(or ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_XOR(PyNode t1, PyNode t2, param_t p)
{
p << "(xor ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_PLUS(PyNode t1, PyNode t2, param_t p)
{
p << "(plus ";
r(t1, p);
p << " ";
r(t2, p);
p << ")";
}
ret_t fold_FOLD(PyNode t1, PyNode t2, PyNode t3, param_t p)
{
p << "(fold ";
r(t1, p);
p << " ";
r(t2, p);
p << " (lambda (y z) ";
r(t3, p);
p << "))";
}
ret_t fold_IF0(PyNode t1, PyNode t2, PyNode t3, param_t p)
{
p << "(if0 ";
r(t1, p);
p << " ";
r(t2, p);
p << " ";
r(t3, p);
p << ")";
}
};
static void pdump(PyNode t1, ostream& os)
{
VPdump().r(t1, os);
}
static int doPGuess(PyNode p, bool tfold)
{
cout << 'G';
if (tfold) {
cout << "(lambda (x) (fold x 0 (lambda (y z) ";
pdump(p, cout);
cout << ")))";
} else {
cout << "(lambda (x) ";
pdump(p, cout);
cout << ")";
}
cout << endl;
int c = cin.get();
if (c == 'W') {
cin.ignore(256, '\n');
return 1;
} else if (c == 'M') {
ull x, y, z;
cin >> x >> y >> z;
evalResults.push_back(make_pair(x, y));
cin.ignore(256, '\n');
}
return 0;
}
static int doBGuess(FNode *ifp, FNode *thp, FNode *elp)
{
cout << 'G';
cout << "(lambda (x) (if0 ";
fdump(ifp, cout);
cout << " ";
fdump(thp, cout);
cout << " ";
fdump(elp, cout);
cout << "))";
cout << endl;
int c = cin.get();
if (c == 'W') {
cin.ignore(256, '\n');
return 1;
} else if (c == 'M') {
ull x, y, z;
cin >> x >> y >> z;
evalResults.push_back(make_pair(x, y));
cin.ignore(256, '\n');
}
return 0;
}
static void dumpConst(ull v, ostream& os)
{
// (or 1 (shl1 (shl1 (or 1 ...))))
for (int i = 0; i < 64; i++) {
if (v & (1ULL << i)) {
os << "(or 1 (shl1 ";
} else {
os << "(shl1 ";
}
}
cout << "0";
for (int i = 0; i < 64; i++) {
if (v & (1ULL << i)) {
os << "))";
} else {
os << ")";
}
}
}
static int doBGuess1(const vector<pair<ull, ull> >& ex, FNode *thp, FNode *elp)
{
cout << 'G';
cout << "(lambda (x) (if0 ";
//// if (if (x ^ ex[0]) 0 (if (x ^ ex[1]) 0 (if ... 0 1))) thp elp
for (auto i = ex.begin(); i != ex.end(); ++i) {
cout << "(if0 (xor x ";
dumpConst(i->first, cout);
cout << ") 0 ";
}
cout << "1";
for (auto i = ex.begin(); i != ex.end(); ++i) {
cout << ")";
}
cout << " ";
fdump(thp, cout);
cout << " ";
fdump(elp, cout);
cout << "))";
cout << endl;
int c = cin.get();
if (c == 'W') {
cin.ignore(256, '\n');
return 1;
} else if (c == 'M') {
ull x, y, z;
cin >> x >> y >> z;
evalResults.push_back(make_pair(x, y));
cin.ignore(256, '\n');
}
return 0;
}
struct VPeval
{
typedef ull ret_t;
typedef const ull *param_t;
ret_t r(PyNode t, param_t p)
{
return pnode_fold(t, p, *this);
}
ret_t fold_Fixed(FNode *t, param_t p)
{
return Veval().r(t, p);
}
ret_t fold_ZERO(param_t p)
{
return 0;
}
ret_t fold_ONE(param_t p)
{
return 1;
}
ret_t fold_VAR_1(param_t p)
{
return p[0];
}
ret_t fold_VAR_2(param_t p)
{
return p[1];
}
ret_t fold_VAR_3(param_t p)
{
return p[2];
}
ret_t fold_NOT(PyNode t1, param_t p)
{
return ~r(t1, p);
}
ret_t fold_SHL1(PyNode t1, param_t p)
{
return r(t1, p) << 1;
}
ret_t fold_SHR1(PyNode t1, param_t p)
{
return r(t1, p) >> 1;
}
ret_t fold_SHR4(PyNode t1, param_t p)
{
return r(t1, p) >> 4;
}
ret_t fold_SHR16(PyNode t1, param_t p)
{
return r(t1, p) >> 16;
}
ret_t fold_AND(PyNode t1, PyNode t2, param_t p)
{
return r(t1, p) & r(t2, p);
}
ret_t fold_OR(PyNode t1, PyNode t2, param_t p)
{
return r(t1, p) | r(t2, p);
}
ret_t fold_XOR(PyNode t1, PyNode t2, param_t p)
{
return r(t1, p) ^ r(t2, p);
}
ret_t fold_PLUS(PyNode t1, PyNode t2, param_t p)
{
return r(t1, p) + r(t2, p);
}
ret_t fold_FOLD(PyNode t1, PyNode t2, PyNode t3, param_t p)
{
ull v1 = r(t1, p);
ull v2 = r(t2, p);
ull nv[3];
nv[0] = p[0];
nv[2] = v2;
for (int i = 0; i < 8; i++) {
nv[1] = v1 & 0xFF;
nv[2] = r(t3, nv);
v1 >>= 8;
}
return nv[2];
}
ret_t fold_IF0(PyNode t1, PyNode t2, PyNode t3, param_t p)
{
return r(t1, p) ? r(t3, p) : r(t2, p);
}
};
static ull peval(PyNode t1, ull v, bool tfold)
{
ull nv[3] = { v, 0, 0 };
if (tfold) {
ull v1 = v;
nv[2] = 0;
for (int i = 0; i < 8; i++) {
nv[1] = v1 & 0xFF;
nv[2] = VPeval().r(t1, nv);
v1 >>= 8;
}
return nv[2];
} else {
VPeval().r(t1, nv);
}
}
static size_t psize(PyNode t1)
{
size_t n;
n += hsize(t1->h);
for (int i = 0; i < 3; i++) {
if (t1->cs[i]) {
n += psize(t1->cs[i]);
}
}
return n;
}
struct Solver
{
bool isBonus;
bool isTFold;
bool enableFold, enableIf0;
bool enableNot, enableShl1, enableShr1, enableShr4, enableShr16;
bool enableAnd, enableOr, enableXor, enablePlus;
Solver()
{
isBonus = false;
isTFold = false;
enableFold = false;
enableIf0 = false;
enableNot = false;
enableShl1 = false;
enableShr1 = false;
enableShr4 = false;
enableShr16 = false;
enableAnd = false;
enableOr = false;
enableXor = false;
enablePlus = false;
}
mt19937_64 mt;
void initialEval()
{
vector<ull> v;
v.push_back(0x0123456789ABCDEFull);
v.push_back(0xFEDCBA9876543210ull);
for (int i = 0; i < 32; i++) {
if (isBonus) {
v.push_back(mt() & 0x000000FFFF000000uLL);
} else {
v.push_back(mt());
}
}
for (int i = 0; i < 64; i++) {
v.push_back(1ULL << i);
}
doEval(v);
}
bool ev(FNode *p, const pair<ull, ull>& v)
{
if (feval(p, v.first) != v.second) {
return false;
}
return true;
}
int norm(ull v)
{
return __builtin_popcountll(v);
}
ull evptop(PyNode p, ull v)
{
return peval(p, v, isTFold);
}
int evnorm(FNode *p, const pair<ull, ull>& v)
{
return norm(feval(p, v.first) ^ v.second);
}
int evpnorm(PyNode p, const pair<ull, ull>& v)
{
return norm(evptop(p, v.first) ^ v.second);
}
template<class I>
bool ev(FNode *p, I begin, I end)
{
for (auto i = begin; i != end; ++i) {
if (!ev(p, *i)) return false;
}
return true;
}
template<class I>
bool evTfold(FNode *p, I begin, I end)
{
FNode3 tf;
tf.h = FOLD;
tf.next = NULL;
tf.t1 = c_var_1;
tf.t2 = c_zero;
tf.t3 = p;
return ev(&tf, begin, end);
}
template<class I>
double evnorm(FNode *p, I begin, I end)
{
int v = 0;
if (begin == end) return 0;
for (auto i = begin; i != end; ++i) {
int n = evnorm(p, *i);
v += n;
}
return v / (double)(end - begin);
}
template<class I>
double evpnorm(PyNode p, I begin, I end)
{
int v = 0;
if (begin == end) return 0;
for (auto i = begin; i != end; ++i) {
int n = evpnorm(p, *i);
v += n;
}
return v / (double)(end - begin);
}
bool solveSmall(bool fstonly)
{
vector<FNode *> candidates;
if (isTFold) {
for (int v = 0; v < STACK; v++) {
for (auto i = fnodes[v].begin(); i != fnodes[v].end(); ++i) {
for (auto p = *i; p; p = p->next) {
if (evTfold(p, evalResults.begin(), evalResults.end())) {
candidates.push_back(p);
if (fstonly) goto found;
}
}
}
}
} else {
for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
for (auto p = *i; p; p = p->next) {
if (ev(p, evalResults.begin(), evalResults.end())) {
candidates.push_back(p);
if (fstonly) goto found;
}
}
}
}
found:
size_t checked = evalResults.size();
while (candidates.size() > 0) {
cerr << candidates.size() << " entries" << endl;
if (isTFold) {
FNode3 tf;
tf.h = FOLD;
tf.next = NULL;
tf.t1 = c_var_1;
tf.t2 = c_zero;
tf.t3 = candidates[0];
if (doGuess(&tf)) {
return true;
}
} else {
if (doGuess(candidates[0])) {
return true;
}
}
vector<FNode *> newC;
for (auto ci = candidates.begin(); ci != candidates.end(); ++ci) {
if (isTFold) {
if (evTfold(*ci, evalResults.begin() + checked, evalResults.end())) {
newC.push_back(*ci);
}
} else {
if (ev(*ci, evalResults.begin() + checked, evalResults.end())) {
newC.push_back(*ci);
}
}
}
candidates.swap(newC);
checked = evalResults.size();
}
return false;
}
template<class I>
FNode *findBest(I begin, I end)
{
FNode *best = 0;
double m = 0;
for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
for (auto p = *i; p; p = p->next) {
double x = evnorm(p, begin, end);
if (!best || m > x) {
best = p;
m = x;
}
}
}
cerr << m << endl;
return best;
}
PyNode best_reform;
double best_reform_score;
PyNode reform_top;
void eval_reform()
{
double x = evpnorm(reform_top, evalResults.begin(), evalResults.end());
//cerr << "reform: ";
//pdump(reform_top, cerr);
//cerr << endl;
if (!best_reform || best_reform_score > x) {
best_reform = pdup(reform_top);
best_reform_score = x;
}
}
void reform_rec(PyNode cur, int v)
{
size_t size = psize(cur);
for (int v1 = 0; v1 <= v; v1++) {
if (!(size + 1 < fnodes[v1].size())) continue;
for (auto i = fnodes[v1].begin() + size + 1; i != fnodes[v1].end(); ++i) {
for (auto p = *i; p; p = p->next) {
cur->t = p;
eval_reform();
cur->t = NULL;
}
}
}
if (cur->h == FOLD) {
reform_rec(cur->cs[0], v);
reform_rec(cur->cs[1], v);
if (v == 0) {
reform_rec(cur->cs[0], 1);
}
} else {
for (int i = 0; i < nchild(cur->h); i++) {
reform_rec(cur->cs[i], v);
}
}
}
PyNode reform(PyNode p)
{
cerr << "reforming: ";
pdump(p, cerr);
cerr << endl;
best_reform.reset();
best_reform_score = 0;
reform_top = p;
for (int i = 0; i < 3; i++) {
if (p->cs[i])
reform_rec(p->cs[i], isTFold ? 1 : 0);
}
cerr << "reformed: " << best_reform_score << endl;
pdump(best_reform, cerr);
cerr << endl;
return best_reform;
}
bool solveLarge()
{
FNode *init_best = findBest(evalResults.begin(), evalResults.begin() + 32);
cerr << "best match: ";
fdump(init_best, cerr);
cerr << endl;
PyNode templ = start_modify(init_best);
for (int c = 0; c < 5; c++) {
templ = reform(templ);
if (doPGuess(templ, isTFold)) {
return true;
}
}
return false;
}
void moreData()
{
vector<ull> v;
for (int i = 0; i < 32; i++) {
v.push_back(mt());
}
doEval(v);
}
bool solveBonus()
{
for (int cnt = 0; cnt < 10; cnt++) {
FNode *fst_term = findBest(evalResults.begin(), evalResults.end());
vector<pair<ull, ull> > mustFst;
vector<pair<ull, ull> > notFst;
for (auto i = evalResults.begin(); i != evalResults.end(); ++i) {
if (ev(fst_term, *i)) {
//fstResult.push_back(*i);
} else {
notFst.push_back(*i);
}
}
for (int cnt2 = 0; cnt2 < 4; cnt2++) {
vector<FNode *> candidates;
for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
for (auto p = *i; p; p = p->next) {
if (ev(p, notFst.begin(), notFst.end()))
candidates.push_back(p);
}
}
if (candidates.size() == 0) {
moreData();
goto search_fst;
}
cerr << "cand: " << candidates.size() << endl;
for (auto sndp = candidates.begin(); sndp != candidates.end(); ++sndp) {
cerr << "search " << endl;
FNode *snd_term = *sndp;
FNode *if_term = NULL;
bool reverse = false;
for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
for (auto p = *i; p; p = p->next) {
for (auto k = mustFst.begin(); k != mustFst.end(); ++k) {
if (feval(p, k->first) != 0) goto fail;
}
for (auto k = notFst.begin(); k != notFst.end(); ++k) {
if (feval(p, k->first) == 0) goto fail;
}
for (auto k = evalResults.begin(); k != evalResults.end(); k++) {
if (feval(p, k->first)) {
if (!ev(snd_term, *k)) goto fail;
} else {
if (!ev(fst_term, *k)) goto fail;
}
}
if_term = p;
goto ok;
fail:
for (auto k = mustFst.begin(); k != mustFst.end(); ++k) {
if (feval(p, k->first) == 0) goto fail2;
}
for (auto k = notFst.begin(); k != notFst.end(); ++k) {
if (feval(p, k->first) != 0) goto fail2;
}
for (auto k = evalResults.begin(); k != evalResults.end(); k++) {
if (feval(p, k->first)) {
if (!ev(fst_term, *k)) goto fail2;
} else {
if (!ev(snd_term, *k)) goto fail2;
}
}
if_term = p;
reverse = true;
goto ok;
fail2:;
}
}
ok:
if (if_term) {
if (reverse) {
if (doBGuess(if_term, fst_term, snd_term)) return true;
} else {
if (doBGuess(if_term, snd_term, fst_term)) return true;
}
auto miss = evalResults.back();
bool f = feval(if_term, miss.first) == 0;
if (reverse) f = !f;
if (f) {
// snd_term
if (ev(fst_term, miss)) {
// f has problem
cerr << "bad f" << endl;
mustFst.push_back(miss);
} else {
// snd hint
cerr << "snd update" << endl;
}
} else {
// fst_term
cerr << "not fst" << endl;
notFst.push_back(miss);
break;
}
}
break;
}
}
search_fst:;
}
return false;
}
void run()
{
initialEval();
if (isBonus && solveBonus()) {
return;
}
if (solveSmall(true)) {
return;
}
if (solveSmall(false)) {
return;
}
//solveLarge();
}
};
int main(int argc, char **argv)
{
alarm(4 * 60);
Solver sv;
int size = atoi(argv[2]);
cerr << "size: " << size << endl;
for (int i = 3; i < argc; i++) {
string s = argv[i];
cerr << "enable: " << s << endl;
if (s == "bonus") {
sv.isBonus = true;
} else if (s == "tfold") {
sv.isTFold = true;
} else if (s == "fold") {
sv.enableFold = true;
} else if (s == "if0") {
sv.enableIf0 = true;
} else if (s == "not") {
sv.enableNot = true;
} else if (s == "shl1") {
sv.enableShl1 = true;
} else if (s == "shr1") {
sv.enableShr1 = true;
} else if (s == "shr4") {
sv.enableShr4 = true;
} else if (s == "shr16") {
sv.enableShr16 = true;
} else if (s == "and") {
sv.enableAnd = true;
} else if (s == "or") {
sv.enableOr = true;
} else if (s == "xor") {
sv.enableXor = true;
} else if (s == "plus") {
sv.enablePlus = true;
} else {
cerr << "unknown option" << endl;
exit(1);
}
}
cerr << "initialize constant terms..." << endl;
if (sv.isBonus) {
initFixed(7);
} else {
initFixed(9);
}
cerr << "done" << endl;
sv.run();
//fdump(fnodes[0][8], cout);
//cout << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.