minidc.cc
download raw
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <stdexcept>
#include <string>
#include <unistd.h>
#include <unordered_set>
#include <vector>
#include <boost/multiprecision/gmp.hpp>
const char *minidc_e(const char *src, std::string &output) {
using boost::multiprecision::mpz_int;
using boost::multiprecision::powm;
using boost::multiprecision::pow;
int I = 10, O = 10;
std::vector<mpz_int> stack;
output.clear();
auto push = [&](mpz_int d) { stack.push_back(d); };
auto pop = [&]() -> mpz_int {
if(stack.empty()) throw std::logic_error("stack underflow");
auto r = stack.back();
stack.pop_back();
return r;
};
auto parse_literal = [&](const char *&src) {
mpz_int r = 0;
while( (*src >= 'A' && *src <= 'F') ||
(*src >= '0' && *src <= '9')) {
if(*src >= '0' && *src <= '9')
r = r * I + *src++ - '0';
else
r = r * I + *src++ - 'A' + 10;
}
src--;
return r;
};
auto ndigits = [](mpz_int d) {
int result = 1;
mpz_int m = 1;
while(true) {
auto m1 = m * 1000000000;
if (d < m1) break;
m = m1;
result += 9;
}
while(d > m) { result += 1; m *= 10; }
return result;
};
auto to_string = [&](mpz_int d) {
if(d == 0) { output += "0"; }
if(d < 0) { output += "-"; d = -d; }
auto first = output.size();
while(d) {
auto i = int(d % O); d /= O;
if(i < 10) output += ('0' + i);
else output += ('A' + i - 10);
}
std::reverse(output.begin() + first, output.end());
};
#define BINOP(CODE,OP) \
case CODE: { auto a = pop(); auto b = pop(); push(b OP a); } break
while(*src) {
switch(*src) {
case '0': case '1': case '2': case '3': case '4': case '5':
case '6': case '7': case '8': case '9':
case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
push(parse_literal(src)); break;
case 'I': push(I); break;
case 'O': push(O); break;
case 'd': { auto a = pop(); push(a); push(a); break; }
case 'i': {
auto a = pop();
if(a < 2 || a > 16) return "bad input radix";
I = int(a); break;
}
case 'n': to_string(pop()); break;
case 'o': {
auto a = pop();
if(a < 2 || a > 16) return "bad output radix";
O = int(a); break;
}
case 'p': to_string(pop()); output += "\n"; break;
case 'r': { auto a = pop(); auto b = pop(); push(a); push(b); break; }
BINOP('*', *);
BINOP('+', +);
BINOP('-', -);
case '/': {
auto a = pop();
auto b = pop();
if(!a) return "division by zero";
push(b / a);
break;
}
case '~': {
auto a = pop();
auto b = pop();
if(!a) return "division by zero";
push(b / a);
push(b % a);
break;
}
case '^': {
auto a = pop();
auto b = pop();
if(a > 10000) return "exponent too large";
if(a < 0) return "exponent negative";
push(boost::multiprecision::pow(b, int(a)));
break;
}
case 'v': {
auto a = pop();
if(a < 0) return "square root of negative";
push(sqrt(a));
break;
}
case '|': {
auto a = pop();
auto b = pop();
auto c = pop();
if(!a) return "zero reduction modulus";
if(b < 0) return "negative exponent";
if(c < 0)
return "negative base (dc interprets incompatibly to minidc)";
push(powm(c, b, a));
break;
}
case 'z':
push(stack.size()); break;
case 'Z':
push(ndigits(pop())); break;
case ' ': case '\n': case '\t': break;
default: throw std::logic_error(std::string("unknown opcode ") + *src);
}
src++;
}
return output.c_str();
}
const char *minidc(const char *src, std::string &work) {
try {
return minidc_e(src, work);
} catch(const std::logic_error &e) {
return (work = e.what()).c_str();
}
}
std::unordered_set<int> seen;
struct charset {
char c;
int8_t minstack; // requried stack
int8_t dstack; // net change in stack (-ve pops, +ve pushes)
};
const charset charset[] = {
{' ', 0, 0},
{'~', 2, 0},
{'^', 2, -1},
{'-', 2, -1},
{'/', 2, -1},
{'*', 2, -1},
{'+', 2, -1},
{'|', 3, -2},
{'A', -1, 0},
{'B', -1, 0},
{'C', -1, 0},
{'D', -1, 0},
{'d', 1, 1},
{'E', -1, 0},
{'F', -1, 0},
{'I', 0, 1},
{'i', 1, -1},
{'n', 1, -1},
{'O', 0, 1},
{'o', 1, -1},
{'r', 2, 0},
{'v', 1, 0},
{'Z', 1, 0},
{'z', 0, 1},
};
char c[100];
bool printed;
static void spinner(const char *s, const char *w) {
static unsigned long long i = 0, j = 1000;
if(++i % j == 0) {
fprintf(stderr, "%16lld [%14s] [%14.14s] %zd\r", i, s, w, seen.size()); fflush(stderr);
if(i == j * 10 && j < 1000000) j *= 10;
printed = true;
}
}
static void test(const char *p) {
static std::string work;
auto s = minidc(p, work);
spinner(p, work.c_str());
try {
size_t pos;
auto i = std::stoi(s, &pos);
if(s[pos]) return;
if(i < 0 || i > 1000000) return;
auto r = seen.insert(i);
if(r.second)
{
#ifndef VERIFY
if(strchr(p, 'Z')) {
if (printed)
fprintf(stderr, "\n"); fflush(stderr);
printed = false;
printf("%7d %s\n", i, p);
}
#else
printf("%7d ", i);
fflush(stdout);
char buf[300];
snprintf(buf, sizeof(buf), "echo '%s' | dc 2>&1", p);
system(buf);
printf(" %s\n", p);
#endif
fflush(stdout);
}
} catch(std::exception &e) {}
}
static
void doit(char *st, char *pos, int n, int d) {
if(n == 0) {
pos[0] = 'n';
pos[1] = '\0';
test(st);
return;
}
for(const auto &c : charset) {
if(d < c.minstack) continue;
auto newd = d + c.dstack;
auto lastdig = (pos[-1] >= 'A' && pos[-1] <= 'F');
if(c.c == ' ' && !lastdig) continue;
if(c.minstack == -1 && !lastdig) newd ++;
*pos = c.c;
doit(st, pos+1, n-1, newd);
}
*pos = 0;
}
int main(int argc, char **argv) {
if(argc == 1) {
c[0] = ' ';
for(int i=1; i<11; i++) {
doit(c+1, c+1, i, 0);
}
} else {
for(int i=1; i<argc; i++) {
std::string work;
printf("%-14s [%2zd]: %s\n", argv[i], strlen(argv[i]), minidc(argv[i], work));
}
}
}