#include <complex.h>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <map>
#include <sstream>

class Number;

class SymbolTable
{
public:
    int matches(char c, const Number* number)
    {
        std::map<char, const Number*>::const_iterator i = _table.find(c);
        if (i != _table.end())
            return (i->second == number) ? 1 : 0;
        _table[c] = number;
        return 1;
    }
private:
    std::map<char, const Number*> _table;
};

class Number
{
public:
    virtual Complex<double> value() const = 0;
//    Complex<double> value() const { return _x; }

    virtual bool lessThan(const Number* other) const = 0;
    virtual void print() const = 0;

    bool matches(const char* pattern) const
    { 
        SymbolTable table;
        return matches(pattern, strlen(pattern), &table) != 0;
    }
    virtual int matches(const char* pattern, int length, SymbolTable* table) const = 0;
    virtual int complexity() const = 0;
//protected:
//    Complex<double> _x;
};

class Zero : public Number
{
public:
    Zero()
    {
        //_x = 0; 
    }
    Complex<double> value() const { return 0; }
    bool lessThan(const Number* other) const { return other != this; }
    void print() const { printf("0"); }
    int matches(const char* pattern, int length, SymbolTable* table) const
    { 
        char p = pattern[length-1];
        if (p == '0')
            return 1;
        if (p >= 'A' && p <= 'Z')
            return table->matches(p, this);
        return 0;
    }
    int complexity() const { return 1; }
};

class Unary : public Number
{
public:
    Unary(const Number* parent)
      : _parent(parent)
    { }
    void print() const { _parent->print(); printf("%c",character()); }
    int matches(const char* pattern, int length, SymbolTable* table) const
    {
        char p = pattern[length-1];
        if (p == character()) {
            if (length == 1)
                return 1;
            int n = _parent->matches(pattern, length-1, table);
            if (n == 0)
                return 0;
            return 1 + n;
        }
        if (p >= 'A' && p <= 'Z')
            return table->matches(p, this);
        return 0;
    }
    int complexity() const { return 1 + _parent->complexity(); }
protected:
    Complex<double> parentValue() const { return _parent->value(); }

    virtual char character() const = 0;

    bool parentLessThanOtherParent(const Unary* other) const { return _parent->lessThan(other->_parent); }
private:
    const Number* _parent;
};

class Exp : public Unary
{
public:
    Exp(const Number* parent)
      : Unary(parent)
    {
        //_x = exp(parentValue());
    }
    Complex<double> value() const { return exp(parentValue()); }
protected:
    char character() const { return 'e'; }
    bool lessThan(const Number* other) const
    {
        if (dynamic_cast<const Zero*>(other) != 0)
            return false;
        const Exp* e = dynamic_cast<const Exp*>(other);
        if (e == 0)
            return true;
        return parentLessThanOtherParent(e);
    }
};

class Log : public Unary
{
public:
    Log(const Number* parent)
      : Unary(parent)
    {
        //_x = log(parentValue());
    }
    Complex<double> value() const { return log(parentValue()); }
protected:
    char character() const { return 'g'; }
    bool lessThan(const Number* other) const
    {
        if (dynamic_cast<const Zero*>(other) != 0 || dynamic_cast<const Exp*>(other) != 0)
            return false;
        const Log* l = dynamic_cast<const Log*>(other);
        if (l == 0)
            return true;
        return parentLessThanOtherParent(l);
    }
};

class Neg : public Unary
{
public:
    Neg(const Number* parent)
      : Unary(parent)
    {
        //_x = -parentValue();
    }
    Complex<double> value() const { return -parentValue(); }
protected:
    char character() const { return '-'; }
    bool lessThan(const Number* other) const
    {
        if (dynamic_cast<const Zero*>(other) != 0 || dynamic_cast<const Exp*>(other) != 0 || dynamic_cast<const Log*>(other) != 0)
            return false;
        const Neg* n = dynamic_cast<const Neg*>(other);
        if (n == 0)
            return true;
        return parentLessThanOtherParent(n);
    }
};

class Add : public Number
{
public:
    Add(const Number* left, const Number* right)
      : _left(left),
        _right(right)
    {
        //_x = left->value() + right->value();
    }
    Complex<double> value() const { return _left->value() + _right->value(); }
    void print() const { _left->print(); _right->print(); printf("+"); }
    int matches(const char* pattern, int length, SymbolTable* table) const
    { 
        char p = pattern[length-1];
        if (p == '+') {
            if (length == 1)
                return 1;
            int right = _right->matches(pattern, length-1, table);
            if (right == 0)
                return 0;
            int left = _left->matches(pattern, (length-1)-right, table);
            if (left == 0)
                return 0;
            return 1 + left + right;
        }
        if (p >= 'A' && p <= 'Z')
            return table->matches(p, this);
        return 0;
    }
    int complexity() const { return 1 + _left->complexity() + _right->complexity(); }
protected:
    bool lessThan(const Number* other) const
    {
        const Add* a = dynamic_cast<const Add*>(other);
        if (a == 0)
            return false;
        if (_left->lessThan(a->_left))
            return true;
        if (_left!=a->_left)
            return false;
        if (_right->lessThan(a->_right))
            return true;
        return false;
    }
private:
    const Number* _left;
    const Number* _right;
};

class ComplexityClass
{
public:
    void add(const Number* number) { _numbers.push_back(number); }
    std::vector<const Number*>::const_iterator begin() const { return _numbers.begin(); }
    std::vector<const Number*>::const_iterator end() const { return _numbers.end(); }
    int size() const { return _numbers.size(); }
private:
    std::vector<const Number*> _numbers;
};

class NumberHolder
{
public:
    NumberHolder(Number* number)
      : _number(number)
    { }
    void release() { _number = 0; }
    Number* number() const { return _number; }
    ~NumberHolder() { if (_number != 0) delete _number; }
    bool matches(const char* pattern) { return _number->matches(pattern); }
private:
    Number* _number;
};

class NumberStore
{
public:
    NumberStore() { }
    const Number* add(NumberHolder& number)
    {
        Number* n = number.number();
        _store.push_back(n);
        number.release();
        return n;
    }
    ~NumberStore()
    {
        for (std::vector<Number*>::const_iterator i = _store.begin(); i != _store.end(); ++i)
            if (*i != 0)
                delete *i;
    }
private:

    std::vector<Number*> _store;

    NumberStore(const NumberStore& other);
    const NumberStore& operator=(const NumberStore& other);
};

unsigned char RGBspec[]=
{0xF3,0xFE,0xFF,0xF4,0xFF,0xFD,0xF4,0xFF,0xFD,0xF4,0xFF,0xFC,0xF4,0xFF,0xFC,0xF5,
0xFF,0xFA,0xF5,0xFF,0xFA,0xF6,0xFF,0xF9,0xF6,0xFF,0xF9,0xF6,0xFF,0xF7,0xF6,0xFF,
0xF7,0xF7,0xFF,0xF6,0xF7,0xFF,0xF6,0xF7,0xFF,0xF4,0xF7,0xFF,0xF4,0xF8,0xFF,0xF2,
0xF8,0xFF,0xF2,0xF8,0xFF,0xF1,0xF8,0xFF,0xF1,0xF9,0xFF,0xEF,0xF9,0xFF,0xEF,0xF9,
0xFF,0xED,0xF9,0xFF,0xED,0xFA,0xFF,0xEC,0xFA,0xFF,0xEC,0xFA,0xFF,0xEA,0xFA,0xFF,
0xEA,0xFB,0xFF,0xE8,0xFB,0xFF,0xE8,0xFC,0xFF,0xE7,0xFC,0xFF,0xE7,0xFC,0xFF,0xE5,
0xFC,0xFF,0xE5,0xFD,0xFF,0xE3,0xFD,0xFF,0xE3,0xFD,0xFF,0xE1,0xFD,0xFF,0xE1,0xFE,
0xFF,0xE0,0xFE,0xFF,0xE0,0xFF,0xFE,0xDE,0xFF,0xFE,0xDE,0xFF,0xFD,0xDB,0xFF,0xFD,
0xDB,0xFF,0xFD,0xD9,0xFF,0xFD,0xD9,0xFF,0xFC,0xD7,0xFF,0xFC,0xD7,0xFF,0xFC,0xD4,
0xFF,0xFC,0xD4,0xFF,0xFB,0xD2,0xFF,0xFB,0xD2,0xFF,0xFA,0xD0,0xFF,0xFA,0xD0,0xFF,
0xFA,0xCE,0xFF,0xFA,0xCE,0xFF,0xF9,0xCB,0xFF,0xF9,0xCB,0xFF,0xF8,0xC9,0xFF,0xF8,
0xC9,0xFF,0xF8,0xC6,0xFF,0xF8,0xC6,0xFF,0xF7,0xC4,0xFF,0xF7,0xC4,0xFF,0xF6,0xC2,
0xFF,0xF6,0xC2,0xFF,0xF5,0xBF,0xFF,0xF5,0xBF,0xFF,0xF5,0xBC,0xFF,0xF5,0xBC,0xFF,
0xF4,0xBA,0xFF,0xF4,0xBA,0xFF,0xF3,0xB7,0xFF,0xF3,0xB7,0xFF,0xF2,0xB5,0xFF,0xF2,
0xB5,0xFF,0xF2,0xB2,0xFF,0xF2,0xB2,0xFF,0xF0,0xB0,0xFF,0xF0,0xB0,0xFF,0xF0,0xAD,
0xFF,0xF0,0xAD,0xFF,0xEF,0xAB,0xFF,0xEF,0xAB,0xFF,0xEE,0xA8,0xFF,0xEE,0xA8,0xFF,
0xED,0xA6,0xFF,0xED,0xA6,0xFF,0xEC,0xA3,0xFF,0xEC,0xA3,0xFF,0xEB,0xA0,0xFF,0xEB,
0xA0,0xFF,0xEA,0x9E,0xFF,0xEA,0x9E,0xFF,0xE9,0x9B,0xFF,0xE9,0x9B,0xFF,0xE9,0x99,
0xFF,0xE9,0x99,0xFF,0xE8,0x96,0xFF,0xE8,0x96,0xFF,0xE7,0x93,0xFF,0xE7,0x93,0xFF,
0xE6,0x91,0xFF,0xE6,0x91,0xFF,0xE5,0x8E,0xFF,0xE5,0x8E,0xFF,0xE4,0x8C,0xFF,0xE4,
0x8C,0xFF,0xE3,0x89,0xFF,0xE3,0x89,0xFF,0xE1,0x86,0xFF,0xE1,0x86,0xFF,0xE0,0x84,
0xFF,0xE0,0x84,0xFF,0xDF,0x81,0xFF,0xDF,0x81,0xFF,0xDE,0x7E,0xFF,0xDE,0x7E,0xFF,
0xDD,0x7C,0xFF,0xDD,0x7C,0xFF,0xDC,0x79,0xFF,0xDC,0x79,0xFF,0xDB,0x76,0xFF,0xDB,
0x76,0xFF,0xDA,0x74,0xFF,0xDA,0x74,0xFF,0xD9,0x71,0xFF,0xD9,0x71,0xFF,0xD7,0x6E,
0xFF,0xD7,0x6E,0xFF,0xD6,0x6C,0xFF,0xD6,0x6C,0xFF,0xD5,0x69,0xFF,0xD5,0x69,0xFF,
0xD4,0x66,0xFF,0xD4,0x66,0xFF,0xD3,0x63,0xFF,0xD3,0x63,0xFF,0xD1,0x61,0xFF,0xD1,
0x61,0xFF,0xD0,0x5E,0xFF,0xD0,0x5E,0xFF,0xCF,0x5C,0xFF,0xCF,0x5C,0xFF,0xCE,0x59,
0xFF,0xCE,0x59,0xFF,0xCC,0x56,0xFF,0xCC,0x56,0xFF,0xCB,0x53,0xFF,0xCB,0x53,0xFF,
0xC9,0x51,0xFF,0xC9,0x51,0xFF,0xC8,0x4E,0xFF,0xC8,0x4E,0xFF,0xC6,0x4B,0xFF,0xC6,
0x4B,0xFF,0xC5,0x49,0xFF,0xC5,0x49,0xFF,0xC3,0x46,0xFF,0xC3,0x46,0xFF,0xC2,0x44,
0xFF,0xC2,0x44,0xFF,0xC0,0x41,0xFF,0xC0,0x41,0xFF,0xBF,0x3E,0xFF,0xBF,0x3E,0xFF,
0xBD,0x3C,0xFF,0xBD,0x3C,0xFF,0xBC,0x39,0xFF,0xBC,0x39,0xFF,0xBA,0x37,0xFF,0xBA,
0x37,0xFF,0xB8,0x34,0xFF,0xB8,0x34,0xFF,0xB7,0x32,0xFF,0xB7,0x32,0xFF,0xB5,0x2F,
0xFF,0xB5,0x2F,0xFF,0xB3,0x2D,0xFF,0xB3,0x2D,0xFF,0xB1,0x2A,0xFF,0xB1,0x2A,0xFF,
0xB0,0x28,0xFF,0xB0,0x28,0xFF,0xAE,0x26,0xFF,0xAE,0x26,0xFF,0xAC,0x23,0xFF,0xAC,
0x23,0xFF,0xAA,0x21,0xFF,0xAA,0x21,0xFF,0xA8,0x1E,0xFF,0xA8,0x1E,0xFF,0xA6,0x1C,
0xFF,0xA6,0x1C,0xFF,0xA4,0x1A,0xFF,0xA4,0x1A,0xFF,0xA2,0x17,0xFF,0xA2,0x17,0xFF,
0xA0,0x15,0xFF,0xA0,0x15,0xFF,0x9E,0x13,0xFF,0x9E,0x13,0xFF,0x9C,0x11,0xFF,0x9C,
0x11,0xFF,0x9A,0x0F,0xFF,0x9A,0x0F,0xFF,0x98,0x0D,0xFF,0x98,0x0D,0xFF,0x96,0x0B,
0xFF,0x96,0x0B,0xFF,0x93,0x09,0xFF,0x93,0x09,0xFF,0x91,0x07,0xFF,0x91,0x07,0xFF,
0x8F,0x05,0xFF,0x8F,0x05,0xFF,0x8D,0x03,0xFF,0x8D,0x03,0xFF,0x8A,0x01,0xFF,0x8A,
0x01,0xFF,0x88,0x00,0xFF,0x88,0x00,0xFF,0x85,0x00,0xFF,0x85,0x00,0xFF,0x83,0x00,
0xFF,0x83,0x00,0xFF,0x80,0x00,0xFF,0x80,0x00,0xFF,0x7D,0x00,0xFF,0x7D,0x00,0xFF,
0x7B,0x00,0xFF,0x7B,0x00,0xFF,0x78,0x00,0xFF,0x78,0x00,0xFF,0x76,0x00,0xFF,0x76,
0x00,0xFF,0x73,0x00,0xFF,0x73,0x00,0xFF,0x70,0x00,0xFF,0x70,0x00,0xFF,0x6D,0x00,
0xFF,0x6D,0x00,0xFF,0x6A,0x00,0xFF,0x6A,0x00,0xFF,0x68,0x00,0xFF,0x68,0x00,0xFF,
0x64,0x00,0xFF,0x64,0x00,0xFF,0x61,0x00,0xFF,0x61,0x00,0xFF,0x5E,0x00,0xFF,0x5E,
0x00,0xFF,0x5B,0x00,0xFF,0x5B,0x00,0xFF,0x58,0x00,0xFF,0x58,0x00,0xFF,0x54,0x00,
0xFF,0x54,0x00,0xFF,0x51,0x00,0xFF,0x51,0x00,0xFF,0x4E,0x00,0xFF,0x4E,0x00,0xFF,
0x4A,0x00,0xFF,0x4A,0x00,0xFF,0x47,0x00,0xFF,0x47,0x00,0xFF,0x44,0x00,0xFF,0x44,
0x00,0xFF,0x40,0x00,0xFF,0x40,0x00,0xFF,0x3C,0x00,0xFF,0x3C,0x00,0xFF,0x39,0x00,
0xFF,0x39,0x00,0xFF,0x36,0x00,0xFF,0x36,0x00,0xFF,0x31,0x00,0xFF,0x31,0x00,0xFF,
0x2E,0x00,0xFF,0x2E,0x00,0xFF,0x2A,0x00,0xFF,0x2A,0x00,0xFF,0x26,0x00,0xFF,0x26,
0x00,0xFF,0x22,0x00,0xFF,0x22,0x00,0xFF,0x1E,0x00,0xFF,0x1E,0x00,0xFF,0x1A,0x00,
0xFF,0x1A,0x00,0xFF,0x16,0x00,0xFF,0x16,0x00,0xFF,0x12,0x00,0xFF,0x12,0x00,0xFF,
0x0E,0x00,0xFF,0x0E,0x00,0xFF,0x0A,0x00,0xFF,0x0A,0x00,0xFF,0x06,0x00,0xFF,0x06,
0x00,0xFF,0x02,0x00,0xFF,0x02,0x00,0xFF,0x00,0x00,0xFF,0x00,0x00,0xFF,0x00,0x00,
0xFF,0x00,0x00};

int main()
{
    NumberStore store;
    std::vector<ComplexityClass> classes;
    std::vector<int> pic(1280*1280,0);
    for (int length=0;length<20;++length) {
        ComplexityClass c;
        if (length==0) {
            NumberHolder h(new Zero());
            c.add(store.add(h));
        }
        else {
            ComplexityClass p = classes[length-1];
            
            for (std::vector<const Number*>::const_iterator i = p.begin(); i != p.end(); ++i) {
                NumberHolder h(new Exp(*i));
                if (h.matches("ge")) continue;
                if (h.matches("e-g-e")) continue;
                c.add(store.add(h));
            }

            for (std::vector<const Number*>::const_iterator i = p.begin(); i != p.end(); ++i) {
                NumberHolder h(new Log(*i));
                if (h.matches("0g")) continue;
                if (h.matches("eg")) continue;
                c.add(store.add(h));
            }

            for (std::vector<const Number*>::const_iterator i = p.begin(); i != p.end(); ++i) {
                NumberHolder h(new Neg(*i));
                if (h.matches("0-")) continue;
                if (h.matches("--")) continue;
                if (h.matches("PQ-+-")) continue;
                if (h.matches("P-Q+-")) continue;
                c.add(store.add(h));
            }

            for (int n=1;n<length-2;++n) {
                ComplexityClass p = classes[n];
                ComplexityClass q = classes[(length-2)-n];
                for (std::vector<const Number*>::const_iterator i = p.begin(); i != p.end(); ++i)
                    for (std::vector<const Number*>::const_iterator j = q.begin(); j != q.end(); ++j) {
                        if ((*i)!=(*j) && !((*i)->lessThan(*j)))
                            continue;
                        NumberHolder h(new Add(*i, *j));
                        if (h.matches("PP-+")) continue;
                        if (h.matches("P-P+")) continue;
                        if (h.matches("P-P-+")) continue;
                        if (h.matches("0e0e-g+")) continue;
                        c.add(store.add(h));
                    }
            }
        }

        classes.push_back(c);

        printf("Length %i: (%i)\n\n", length+1, c.size());
        //for (std::vector<const Number*>::const_iterator i = c.begin(); i != c.end(); ++i) {
        //    (*i)->print();
        //    printf("  (%8lf,%8lf)\n",(*i)->value().x, (*i)->value().y);
        //}
        //printf("\n\n");

        int max = 0;
        for (std::vector<const Number*>::const_iterator i = c.begin(); i != c.end(); ++i) {
            int x = static_cast<int>(floor((*i)->value().x*20.0+0.5))+640;
            int y = static_cast<int>(floor((*i)->value().y*20.0+0.5))+640;
            if (x>=0 && x<1280 && y>=0 && y<1280) {
                ++pic[y*1280+x];
                if (pic[y*1280+x]>max)
                    ++max;
            }
        }
        std::ostringstream fn;
        fn << "pic" << length << ".raw";
        FILE* out = fopen(fn.str().c_str(), "wb");
        for (int i=0;i<1280*1280;++i) {
            int c = (int)(455.0*exp(-(log((double)pic[i]+1))/7.0));
            if (c<305) {
                fputc(RGBspec[c*3], out);
                fputc(RGBspec[c*3+1], out);
                fputc(RGBspec[c*3+2], out);
            }
            else {
                fputc(0xff-(c-305)*255/150, out);
                fputc(0, out);
                fputc(0, out);
            }                
        }
        fclose(out);
    }
}