Skip to content

Instantly share code, notes, and snippets.

@salel

salel/four_fours.cpp

Created May 24, 2020
Embed
What would you like to do?
#include <iostream>
#define _USE_MATH_DEFINES
#include <cmath>
#include <map>
#include <vector>
#include <memory>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
using ftype = long double;
struct Op {
// Value of operation
virtual ftype get() = 0;
// Number of fours used
virtual int fourCost()=0;
// Number of total operations of inner operations
virtual int opCost() { return 0; }
// Score of answer
ftype score() {
return -log10(abs(M_PI - get()))/opCost();
}
// Somewhat pretty printing, needs overhaul
virtual string print()=0;
};
using opl = shared_ptr<Op>;
// Binary Operations
enum binop {
Plus=0, Minus, Mul, Div, Log, Power, Root, BSize
};
struct BinOp : public Op {
BinOp(binop op, opl l, opl r) : op(op), l(l), r(r) {}
virtual ftype get() {
switch (op) {
case binop::Plus: return l->get()+r->get();
case binop::Minus: return l->get()-r->get();
case binop::Mul: return l->get()*r->get();
case binop::Div: return l->get()/r->get();
case binop::Log: return log(l->get())/log(r->get());
case binop::Power: return pow(l->get(), r->get());
case binop::Root: return pow(l->get(), 1/r->get());
default: return 0;
}
}
virtual int fourCost() {
return l->fourCost() + r->fourCost();
}
virtual int opCost() {
return 1+l->opCost()+r->opCost();
}
virtual string print() {
auto pl = l->print();
auto pr = r->print();
switch (op) {
case binop::Plus: return pl + "+" + pr;
case binop::Minus: return pl + "-" + pr;
case binop::Mul: return pl + "*" + pr;
case binop::Div: return pl + "/" + pr;
case binop::Log: return string("log_{") + pr + "}" + pl;
case binop::Power: return pl + "^" + pr;
case binop::Root: return string("sqrt[") + pr + "]" + pl;
default: return "";
}
}
binop op;
opl l,r;
};
// Unary Operations
enum unop {
Neg=0, Sqrt, Floor, Ceil, Fact, USize
};
struct UnOp : public Op {
UnOp(unop op, opl o) : op(op), o(o) {}
virtual ftype get() {
switch (op) {
case unop::Neg: return -o->get();
case unop::Sqrt: return sqrt(o->get());
case unop::Floor: return floor(o->get());
case unop::Ceil: return ceil(o->get());
case unop::Fact: {
auto a = o->get();
// Sorry long double can't represent everything
// In case of precision errors manually check the result
if (a > 170) throw runtime_error("");
ftype r = 1;
for (int i=2;i<=a;i++) {
r *= i;
}
return r;
}
default: return 0;
}
}
virtual int fourCost() {
return o->fourCost();
}
virtual int opCost() {
return 1+o->opCost();
}
virtual string print() {
auto ol = o->print();
switch (op) {
case unop::Neg: return string("-") + ol;
case unop::Sqrt: return string("sqrt ") + ol;
case unop::Floor: return string("floor ") + ol;
case unop::Ceil: return string("ceil ") + ol;
case unop::Fact: return ol + "!";
default: return "";
}
}
unop op;
opl o;
};
// Four or concatenation of fours
struct NumOp : public Op {
// N the number of concatenated fours
NumOp(int n) : number(n) {}
virtual ftype get() {
int s = 4;
for (int i=1;i<number;i++) {
s = s*10+4;
}
return s;
}
virtual int fourCost() { return number; }
virtual string print() {
std:string s;
for (int i=0;i<number;i++) s += "4";
return s;
}
int number;
};
// All possible operations
// rem is the number of remaining fours to place
// remops is the number of remaining operations
// should be called with first = true outside of the function
vector<opl> genOp(int rem, int remops, bool first = false) {
// Prune if no more remaining fours or operations
if (!rem || !remops) return {};
vector<opl> o;
// Generate binops
for (auto l : genOp(rem, remops-1)) {
auto cost = l->fourCost();
auto opcost = l->opCost();
for (auto r : genOp(rem-cost, remops-1-opcost)) {
for (int op=binop::Plus;op!=binop::BSize;op++) {
o.push_back(opl(new BinOp((binop)op, l, r)));
}
}
}
// Generate unops
for (auto l : genOp(rem, remops-1)) {
for (int op=unop::Neg;op!=unop::USize;op++) {
o.push_back(opl(new UnOp((unop)op, l)));
}
}
// Generate fours
for (int i=1;i<=rem;i++) {
o.push_back(opl(new NumOp(i)));
}
// Keep answer with right amount of operations
if (first) {
o.erase(remove_if(o.begin(), o.end(),
[=](auto o) { return (o->opCost() != remops-1); }
), o.end());
}
return o;
}
// First argument optional ; wanted number of operations
int main(int argc, char** argv) {
// Number of operations
int ops = 2;
if (argc > 1) {
stringstream ss(argv[1]);
ss >> ops;
}
// Get all solutions for given amount of operations
auto solutions = genOp(4,ops+1, true);
vector<opl> best;
double bestScore;
// Get scores from solutions and keep the best ones
for (auto o : solutions) {
try {
auto score = o->score();
if (score > bestScore || best.empty()) {
best = {o};
bestScore = score;
} else if (score == bestScore) {
best.push_back(o);
}
} catch (runtime_error e) {}
}
// Display best solutions
for (auto o : best) {
cout << o->print() << " = " << o->get() << "; score = " << o->score() << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment