Logic for MetaNet

#include <math.h>

long long K = 1, S = 3;

double Kliment(double alpha) { K++; return alpha*(1-alpha); }

double Serafimov(double x) { S++; return 1/(1+exp(-x)); }

/* Code written by Kliment Serafimov */

#include <fstream>
#include <iomanip>
#include <iostream>

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <time.h>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>

#define P push
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define DEC 0.00000001
#define MAX 2139062143
#define MAX_63  1061109567
#define MAXll 9187201950435737471
#define bp(a) __builtin_popcount(a)
#define rand(a, b) ((rand()%(b-a+1))+a)
#define MEM(a, b) memset(a, b, sizeof(a))
#define sort_v(a) sort(a.begin(), a.end())
#define rev_v(a)  reverse(a.begin(), a.end())

//#define fin cin
//#define fout cout
using namespace std;
//ifstream fin(".in");
//ofstream fout(".out");

int getBit(int bit, int at)
{
    assert(0<=at&&at<=30);
    return ((bit&(1<<at))!=0);
}


double LEARNING_RATE = 1;
int number_of_dimesions = 3;

void longestSubstring_dai_di_is_0
(int &numInputs, int &numOutputs, int &sampleSize, string &type, vector<vector<double> > &in, vector<vector<double> > &out)
{
    type = "longestSubstring_dai_di_is_0";

    assert(1<=numInputs&&numInputs<=30);

    int universe = (1<<numInputs);
    sampleSize = 0;
    numOutputs = numInputs;

    for(int i=0; i<universe; i++, sampleSize++)
    {
        vector<double> sample;
        vector<double> sampleOut;

        for(int j=0; j<numInputs; j++)
        {
            int a = getBit(i, j);
            if(a==0)
            {
                a=-1;
            }
            sample.pb(a);
        }
        rev_v(sample);
        int ret = 1, pos = 0, now = 1;
        for(int j=1; j<numOutputs; j++)
        {
            if(sample[j-1]==sample[j])
            {
                now++;
                if(ret <= now)
                {
                    pos = j;
                    ret = now;
                }
            }
            else
            {
                now = 1;
            }
        }
        for(int j=0; j<numOutputs; j++)
        {
            if(pos-ret<j&&j<=ret)
            {
                sampleOut.pb(1);
            }
            else
            {
                sampleOut.pb(0);
            }
        }
        in.pb(sample);
        out.pb(sampleOut);
    }
}

void longestSubstring_ai_is_1
(int &numInputs, int &numOutputs, int &sampleSize, string &type, vector<vector<double> > &in, vector<vector<double> > &out)
{
    type = "longestSubstring_ai_is_1";

    assert(1<=numInputs&&numInputs<=30);

    int universe = (1<<numInputs);
    sampleSize = 0;
    numOutputs = numInputs+1;

    for(int latice=0; latice<universe; latice++, sampleSize++)
    {
        vector<double> sample;
        vector<double> sampleOut;

        for(int j=0; j<numInputs; j++)
        {
            int a = getBit(latice, j);
            if(a==0)
            {
                a=-1;
            }
            sample.pb(a);
        }
        rev_v(sample);
        int ret = 0, pos = -1, now = 0;
        for(int j=0; j<numInputs; j++)
        {
            if(sample[j]==1)
            {
                now++;
                if(ret <= now)
                {
                    pos = j;
                    ret = now;
                }
            }
            else
            {
                now = 0;
            }
        }
        for(int j=0; j<numOutputs; j++)
        {
            if(j==ret)
            {
                sampleOut.pb(1);
            }
            else
            {
                sampleOut.pb(0);
            }
        }
        in.pb(sample);
        out.pb(sampleOut);
    }
}

void a_i_is_a_i_plus_one_for_all
(int &numInputs, int &numOutputs, int &sampleSize, string &type, vector<vector<double> > &in, vector<vector<double> > &out)
{
    type = "a_i_is_a_i_plus_one_for_all";
    assert(1<=numInputs&&numInputs<=30);

    int universe = (1<<numInputs);
    sampleSize = 0;
    numOutputs = numInputs-1;

    for(int i=0; i<universe; i++, sampleSize++)
    {
        vector<double> sample;
        vector<double> sampleOut;

        for(int j=0; j<numInputs; j++)
        {
            int a = getBit(i, j);
            if(a==0)
            {
                a=-1;
            }
            sample.pb(a);
        }
        rev_v(sample);
        for(int j=0; j<numOutputs; j++)
        {
            if(sample[j]==sample[j+1])
            {
                sampleOut.pb(1);
            }
            else
            {
                sampleOut.pb(0);
            }
        }
        in.pb(sample);
        out.pb(sampleOut);
    }
}

void nullFunction(int &numInputs, int &numOutputs, int &sampleSize, string &type, vector<vector<double> > &in, vector<vector<double> > &out){}

void input_is_output(int &numInputs, int &numOutputs, int &sampleSize, string &type, vector<vector<double> > &in, vector<vector<double> > &out)
{
    type = "input_is_output";
    sampleSize = (1<<numInputs);
    numOutputs = numInputs;
    for(int i=0;i<sampleSize;i++)
    {
        vector<double> sample;
        vector<double> sampleOut;
        for(int j=0;j<numInputs;j++)
        {
            double x = ((i&(1<<j))!=0);
            sampleOut.pb(x);
            x -= (x==0);
            sample.pb(x);
        }
        rev_v(sample);
        rev_v(sampleOut);
        in.pb(sample);
        out.pb(sampleOut);
    }
}
typedef void (*Learneble) (int &numInputs, int &numOutputs, int &sampleSize, string &type, vector<vector<double> > &in, vector<vector<double> > &out);
pair<string, Learneble /**for 0<i<15*/> Functions[5] =
{
    mp("a_i_is_a_i_plus_one_for_all", a_i_is_a_i_plus_one_for_all),
    mp("longestSubstring_dai_di_is_0", longestSubstring_dai_di_is_0),
    mp("longestSubstring_ai_is_1", longestSubstring_ai_is_1),
    mp("input_is_output", input_is_output),
    mp("end", nullFunction)
};


class Data
{
public:
    int sampleSize;

    int numInputs;
    int numOutputs;

    vector<vector<double> > in;
    vector<vector<double> > out;

    string type;

    void make_binary()
    {
        for(int i=0;i<in.size();i++)
        {
            for(int j=0;j<in[i].size();j++)
            {
                if(in[i][j] == -1)
                {
                    in[i][j] = 0;
                }
            }
        }
    }

    Data()
    {

    }

    void generateData(int &ret_numInputs, int &ret_numOutputs, string &ret_type, vector<int> order)
    {
        in.clear();
        out.clear();

        numInputs = ret_numInputs;

        type = ret_type;

        int functionId = 0;

        while(Functions[functionId].f!="end")
        {
            if(Functions[functionId].f == type)
            {
                Functions[functionId].s(numInputs, numOutputs, sampleSize, type, in, out);
            }
            functionId++;
        }
        assert(in.size()==out.size());
        if(order.size()>0)
        {
            assert(order.size()==in.size());
            vector<vector<double> > new_in, new_out;
            for(int i=0;i<order.size();i++)
            {
                new_in.pb(in[order[i]]);
                new_out.pb(out[order[i]]);
            }
            in = new_in;
            out = new_out;
            sampleSize = order.size();
        }

        ret_type = type;
        ret_numInputs = numInputs;
        ret_numOutputs = numOutputs;
    }

    void generateData(int &ret_numInputs, int &ret_numOutputs, string &ret_type)
    {
        vector<int> default_order;
        generateData(ret_numInputs, ret_numOutputs, ret_type, default_order);
    }

    void printTest(int id)
    {

        cout << "Hint number: " << id <<endl;
        cout << "in : ";
        for(int j=0; j<in[id].size(); j++)
        {
            cout << in[id][j]+(in[id][j]==-1)<<" ";
        }
        cout << endl<<"out: ";
        for(int i=0; i<out[id].size(); i++)
        {
            cout << out[id][i]<<" ";
        }
        cout << endl;
    }
    void printTest(int id, vector<double> prediction )
    {
        printTest(id);
        cout << "try: ";
        for(int j=0; j<prediction.size(); j++)
        {
            cout << (bool)(prediction[j]>0.5)<<" ";
        }
        cout << endl;
    }

    string printVector(vector<double> v)
    {
        string ret;
        for(int i=0;i<v.size();i++)
        {
            ret+=((v[i]+(v[i]==-1))+'0');
        }
        return ret;
    }
    string printInput(int id)
    {
        return printVector(in[id]);
    }
    string printOutput(int id)
    {
        return printVector(out[id]);
    }
    void seeData()
    {
        cout << "Sample size: " << sampleSize << endl;
        for(int i=0;i<sampleSize;i++)
        {
            cout << printInput(i) <<" "<< printOutput(i) <<endl;
        }
    }
    int count_wrong_bits(int id, vector<double> predict)
    {
        assert(out[id].size()==predict.size());
        int ret = 0;
        for(int i=0; i<predict.size(); i++)
        {
            if((predict[i]>0.5)!=(out[id][i]>0.5))
            {
                ret++;
            }
        }
        return ret;
    }
    bool checkPrediction(int id, vector<double> predict)
    {
        return count_wrong_bits(id, predict) == 0;
    }
};


bool check(vector<double> correct, vector<double> predict)
{
    assert(correct.size()==predict.size());
    for(int i=0; i<predict.size(); i++)
    {
        if((predict[i]>0.5)!=(correct[i]>0.5))
        {
            return false;
        }
    }
    return true;
}

double rate = 1;

double set_random_w()
{
    double lb = -0.5, hb = 0.5;
    return (double)rand((int)(lb*100), (int)(hb*100))/100.0;
}

class neuron
{
public:
    vector<double> w;
    double t;
    int num_in;
    double prevOutput;
    vector<double> previn;
    neuron(int _num_in)
    {
        num_in = _num_in;
        t = set_random_w();
        for(int i=0; i<num_in; i++)
        {
            w.pb(set_random_w());
        }
    }
    void addInput(int n)
    {
        num_in+=n;
        for(int i=0; i<n; i++)
        {
            w.pb(set_random_w());
        }
    }
    double output(vector<double> input, bool remember)
    {
        assert(input.size()==num_in);

        double sum = -t;
        if(remember)previn.clear();
        for(int j=0; j<num_in; j++)
        {
            if(remember)previn.pb(input[j]);
            sum += input[j]*w[j];
        }
        double ret = Serafimov(sum);
        if(remember)prevOutput = ret;
        return ret;
    }
    vector<double> updateWeights(double prevDer)
    {
        vector<double> ret;
        rate = LEARNING_RATE;
        for(int i=0; i<num_in; i++)
        {
            ret.pb(prevDer*Kliment(prevOutput)*w[i]);
            w[i]+=rate*prevDer*Kliment(prevOutput)*previn[i];

        }
        t+=rate*prevDer*Kliment(prevOutput)*(-1);
        return ret;
    }
    void printWeights()
    {
        for(int i=0; i<num_in; i++)
        {
            cout <<w[i] <<" ";
        }
        cout << "t: " << t << endl;
        cout << endl;
    }

};

class layer
{
public:
    int num;
    int n_in;
    vector<neuron> neurons;
    layer(int _in_per_neuron, int _num_neurons)
    {
        num = _num_neurons;
        n_in = _in_per_neuron;
        for(int i=0; i<num; i++)
            neurons.pb(neuron(n_in));
    }
    void addOutput(int n)
    {
        num+=n;
        for(int i=0; i<n; i++)
        {
            neurons.pb(neuron(n_in));
        }
    }
    void addInput(int n)
    {
        n_in+=n;
        for(int i=0; i<num; i++)
        {
            neurons[i].addInput(n);
        }
    }
    vector<double> output(vector<double> input, bool remember)
    {
        vector<double> layerOutput;
        for(int i=0; i<num; i++)
        {
            layerOutput.pb(neurons[i].output(input, remember));
        }
        return layerOutput;
    }
    vector<double> updateWeights(vector<double> derivatives)
    {
        vector<double> sumDerivatives(n_in, 0);
        for(int i=0; i<num; i++)
        {
            vector<double> oneDerivative = neurons[i].updateWeights(derivatives[i]);
            for(int j=0; j<n_in; j++)
            {
                sumDerivatives[j]+=oneDerivative[j];
            }
        }
        return sumDerivatives;
    }
    void printWeights()
    {
        for(int i=0; i<num; i++)
        {
            neurons[i].printWeights();
        }
        cout << endl;
    }
};


string toString(int n, int k)
{
    string ret = "";
    int init_n = n;
    while(n>0)
    {
        ret+=((n%k)+'0');
        n/=k;
    }
    if(k==2)
    {
        while(ret.size()<number_of_dimesions)
        {
            ret+="0";
        }
    }
    else if(init_n == 0)
    {
        ret = "0";
    }
    rev_v(ret);
    return ret;
}

string toBinaryString(int n)
{
    return toString(n, 2);
}
string toDecimalString(int n)
{
    return toString(n, 10);
}

vector<double> delta(vector<double> x, vector<double> y)
{
    assert(x.size()==y.size());
    vector<double> ret;
    for(int i = 0;i<x.size();i++)
    {
        int diff = -(x[i]>0.5) + (y[i]>0.5);
        ret.pb(diff);
    }
    return ret;
}

int totalCycles = 0;

int printCycle = false;
int printItteration = false;
int printFullOrder = false;
int printTopologicalOrder = false;
int printMST = false;
int printStateActionReward = false;
int printMistakes = false;

vector<pair<vector<layer>, int> >  evolve;

typedef pair<int, vector<double> > deltaPredict;
typedef pair<pair<deltaPredict, deltaPredict>, vector<double> > deltaState;

class net
{
public:
    map<pair<pair<int, int>, pair<int, int> >, int> state_action_change;
    map<deltaState, int> delta_knowledge_graph;// [actor, actor_deltaPredict, state, state_deltaPredict, delta_actor_state]
    map<pair<pair<int, vector<double> >, vector<double> >, int> new_neurons;
    map<vector<double>, set<deltaState> > clasify_neurons;
    map<vector<double>, int> count_neuron_activation;
    vector<layer> niz;

    int stress;

    int numInputs;
    int numOutputs;

    vector<double> forwardPropagate(vector<double> input, bool remember)
    {
        count_feedforward+=remember;
        vector<double> layerOutput = input;
        for(int j=0; j<niz.size(); j++)
        {
            layerOutput = niz[j].output(layerOutput, remember);
        }
        return layerOutput;
    }
    void backwardPropagate(vector<double> desiredOutput, vector<double> predicted)
    {
        count_backprop++;
        vector<double> Derivatives;
        double sum = 0;
        bool correct = true;

        for(int j=0; j<desiredOutput.size(); j++)
        {
            double difference = (desiredOutput[j]-predicted[j]);
            sum+=difference*difference;

            if((desiredOutput[j]>0.5)!=(predicted[j]>0.5))
            {
                correct = false;
            }
            else
            {
                //difference = 0;
            }
            Derivatives.pb(difference);
        }
        for(int j=niz.size()-1; j>=0; j--)
        {
            Derivatives = niz[j].updateWeights(Derivatives);
        }
    }
    void init()
    {
        K = 1;
        S = 3;
        stress = 1;
    }
    net()
    {
        init();
    }
    net(int in_bits, int *hiddenLayers, int out_bits)
    {
        init();
        numInputs = in_bits;
        numOutputs = out_bits;
        constructNN(hiddenLayers);
    }
    int count_backprop;
    int count_feedforward;
    void train(Data *latice, string type)
    {
        count_backprop = 0;
        count_feedforward = 0;
        if(type == "stupid train")
        {
            stupidTrain(latice);
        }
        else if(type == "queue train")
        {
            queueTrain(latice);
        }
        else if(type == "stack train")
        {
            stackTrain(latice);
        }
        else if(type == "rek train")
        {
            rekTrain(latice, latice->sampleSize-1);
        }
        else
        {
            cout << "none type"<<endl;
            assert(0);
        }
        cout << "backprop: " << count_backprop <<endl;
        cout << "feedforward: "<< count_feedforward << endl;
    }

    bool update_and_test(Data *latice, int id, vector<double> &predict)
    {
        vector<pair<int, vector<double> > > last_state = test(latice).f;
        backwardPropagate(latice->out[id], predict);
        vector<pair<int, vector<double> > > new_state = test(latice).f;

        vector<double> newPredict = forwardPropagate(latice->in[id], 1);
        vector<double> deltaPredict_actor = delta(predict, newPredict);
        deltaPredict delta_actor = mp(id, deltaPredict_actor);

        bool correct = check(latice->out[id], newPredict);
        assert(new_state.size()==last_state.size());
        if(correct)
        {
            for(int i=0;i<last_state.size();i++)
            {
                if(last_state[i].f==0&&new_state[i].f!=0)
                {
                    vector<double> deltaPredict_hint = delta(last_state[i].s, new_state[i].s);
                    deltaPredict delta_hint = mp(i, deltaPredict_hint);
                    vector<double> delta_actor_hint = delta(latice->in[id], latice->in[i]);
                    deltaState delta_state= mp(mp(delta_actor, delta_hint), delta_actor_hint);
                    delta_knowledge_graph[delta_state]++;
                    new_neurons[mp(mp(i, deltaPredict_hint), delta_actor_hint)]++;
                    clasify_neurons[delta_actor_hint].insert(delta_state);
                    count_neuron_activation[delta_actor_hint]++;
                }
                state_action_change[mp(mp(id,last_state[i].f==0), mp(new_state[i].f==0, i))]++;
            }
        }
        predict = newPredict;
        return correct;
    }

    bool rekTrain(Data *latice, int last_id)
    {
        if(last_id<0)return true;
        for(int id=0;id<=last_id;id++)
        {
            vector<double> predict = forwardPropagate(latice->in[id], 1);
            bool correct = check(latice->out[id], predict);
            while(!correct)
            {
                while(!correct)
                {
                    correct = update_and_test(latice, id, predict);
                }
                rekTrain(latice, id-1);
                predict = forwardPropagate(latice->in[id], 1);
                correct = check(latice->out[id], predict);
            }
        }
        return true;
    }

    void stackTrain(Data *latice)
    {
        assert(0);
    }
    void queueTrain(Data *latice)
    {
        queue<int> q_init;
        queue<int> q_error;
        queue<int> q_correct;

        clearQueue(&q_init);
        clearQueue(&q_error);
        clearQueue(&q_correct);

        int Learning = 0;
        bool Learned = false;

        int totalErrors = 0;
        int totalCorrect = 0;
        int passedErrors = 0;
        int passedCorrect = 0;

        int setStress = 1;
        int cycleErrors = 0;

        int currentErrors = (1<<30);
        int lastCycleErrors = (1<<30);

        int trainSetSize = latice->sampleSize;

        int c = 0;
        int cycle = 0;


        for(int i=0; i<trainSetSize; i++)
        {
            c++;
            q_init.P(i);
        }

        while(!Learned&&(!q_init.empty()||!q_error.empty()||!q_correct.empty()))
        {
            int id;
            if(!q_init.empty())
            {
                id = q_init.front();
                q_init.pop();
            }
            else if(!q_error.empty()&&((passedCorrect>passedErrors)||q_correct.empty()))
            {
                id = q_error.front();
                q_error.pop();
                passedErrors++;
            }
            else if(!q_correct.empty())
            {
                id = q_correct.front();
                q_correct.pop();
                passedCorrect++;
            }
            else
            {
                assert(0);
            }

            c--;

            vector<double> predict = forwardPropagate(latice->in[id], 1);
            bool correct = check(latice->out[id], predict);

            stress = setStress;
            while(!correct&&stress--)
            {
                correct = update_and_test(latice, id, predict);

                Learning = false;
                cycleErrors++;
            }


            if(!correct)
            {
                q_error.P(id);
                totalErrors++;
            }
            else
            {
                q_correct.P(id);
                totalCorrect++;
            }

            currentErrors = totalErrors - passedErrors;

            if(printItteration)
            {
                pair<vector<pair<int, vector<double> > >, int> currentKnowledge = test(latice);
                for(int i=0;i<currentKnowledge.f.size();i++)
                {
                    cout << (currentKnowledge.f[i].f==0);
                }
                cout << " id : " << id << " correct: " << trainSetSize-currentKnowledge.s << endl;
                //latice->printTest(id);
            }
            currentErrors = totalErrors - passedErrors;
            if(c==0)
            {
                cycle++;
                c = trainSetSize;

                if(printCycle)
                    cout << cycle <<  ": currentErrors = "<< currentErrors << " CycleErrors = " << cycleErrors << " delta = " << lastCycleErrors-cycleErrors << endl;

                lastCycleErrors = cycleErrors;
                cycleErrors = 0;

                //analyzeMistakes();
            }

            Learning += (currentErrors == 0);
            Learned = (Learning > trainSetSize);
        }
        cout <<"numCycles: "<< cycle <<endl;
        totalCycles+=cycle;
    }


    pair<vector<pair<int, vector<double> > >, int>  test(Data *testData)
    {
        vector<pair<int, vector<double> > > ret;
        int num_wrong = 0;
        int num_correct = 0;
        for(int i=0; i<testData->in.size(); i++)
        {
            vector<double> predict = forwardPropagate(testData->in[i], 0);
            vector<double> delta_predict_out = delta(testData->out[i], predict);
            int num_bits_wrong = 0;
            for(int j=0;j<delta_predict_out.size();j++)
            {
                num_bits_wrong+=delta_predict_out[j];
            }
            if(num_bits_wrong>0)
            {
                num_wrong++;
            }
            else
            {
                num_correct++;
            }
            ret.pb(mp(num_bits_wrong, predict));
        }
        return mp(ret, num_wrong);
    }

    void test(Data *testData, string action)
    {
        if(action == "print result")
        {
            pair<vector<pair<int, vector<double> > >, int> result = test(testData);reportTest(testData, result.s);
        }
        else
        {
            cout << "WTF" <<endl;
        }
    }

    void reportTest(Data *testData, int wrong)
    {
        cout << "correct: " <<  testData->sampleSize-wrong <<" out of " << testData->sampleSize << endl;
        if(wrong!=0)
        {
            cout << wrong <<" wrong " << endl;
        }
    }

    void constructNN(int *hiddenLayer)
    {
        int neuronsPerLayer[20] ={numInputs};
        int c = 1;
        while(hiddenLayer[c-1]!=-1)
        {
            neuronsPerLayer[c] = hiddenLayer[c-1];
            c++;
        }

        neuronsPerLayer[c] = numOutputs;
        neuronsPerLayer[c+1] = -1;

        int at_layer = 0;
        while(neuronsPerLayer[at_layer+1]!=-1)
        {
            niz.pb(layer(neuronsPerLayer[at_layer], neuronsPerLayer[at_layer+1]));
            at_layer++;
        }
    }

    void printBrainStructure()
    {
        cout << niz.size() <<" Layers" << endl;
        for(int i=0;i<niz.size();i++)
        {
            cout << niz[i].neurons.size() <<" ";
        }
        cout << endl;
    }

    void stupidTrain(Data *latice)
    {
        cout << "Stupud Train"<<endl;
        bool Learned = false;
        int numCycles = 0;
        int itterations = 0;
        while(!Learned)
        {
            numCycles++;
            Learned = true;
            for(int id=0;id<latice->sampleSize;id++)
            {
                itterations++;
                vector<double> predict = forwardPropagate(latice->in[id], 1);
                bool correct = check(latice->out[id], predict);

                if(!correct)
                {
                    Learned = false;
                    //latice->printTest(id, predict);
                    backwardPropagate(latice->out[id], predict);
                }
            }
        }
        cout << "numCycles = " <<numCycles <<endl;
        totalCycles+=numCycles;
        //cout << "itterations = " << itterations << endl;
    }

    void clearQueue(queue<int> *q)
    {
        while(!q->empty())
        {
            q->pop();
        }
    }

    void announceTrain(Data *latice)
    {
        cout << "Start train on: bits: " << numInputs <<" samples: "<< latice->sampleSize <<endl;
    }

    void printWeights()
    {
        cout << endl;
        for(int i=0; i<niz.size(); i++)
        {
            niz[i].printWeights();
            cout << "NEW LAYER " <<endl;
        }
    }

    void analyzeEvolve()
    {
        cout << "Analyze Evolve: " << endl;
        vector<double> prev = evolve[0].f[evolve[0].f.size()-1].neurons[0].w;
        for(int i=1;i<evolve.size();i++)
        {
            vector<double> w = evolve[i].f[evolve[i].f.size()-1].neurons[0].w;
            cout << evolve[i].s <<" :: ";
            for(int w_id = 0;w_id<w.size();w_id++)
            {
                string buf = "";
                if(w[w_id] >= 0) buf = " ";
                cout << fixed << setprecision(6) << buf << w[w_id] << " ";
                prev[w_id] = w[w_id];
            }
            cout << endl;
        }
    }

    void dfs(int at, int c)
    {
        color[at] = c;
        sorted_samples.pb(at);

        for(int i=0;i<MST[at].size();i++)
        {
            int next = MST[at][i].f;
            if(color[next]==0)
            {
                dfs(next, c);
            }
            else
            {

            }
        }
    }

    vector<int> color;
    vector<int> sorted_samples;
    vector<vector<pair<int, int> > > MST;
    vector<vector<pair<int, int> > > fullOrder;
    vector<int> father;

    int Find(int x)
    {
        if(x==father[x])
            return x;
        return father[x] = Find(father[x]);
    }

    void unite(int x, int y)
    {
        father[Find(x)] = Find(y);
    }
    void MST_of_samples(Data *latice)
    {
        /*

        todo: create categories

        */

        sort_v(state_action_reward);
        //rev_v(state_action_reward);
        MST.clear();
        father.clear();
        fullOrder.clear();
        for(int i=0;i<latice->sampleSize;i++)
        {
            vector<pair<int, int> > v;
            MST.pb(v);
            father.pb(i);
            fullOrder.pb(v);
        }
        int taken_edge = 0;
        for(int i=0;i<state_action_reward.size();i++)
        {
            int reward = state_action_reward[i].f;
            int x = state_action_reward[i].s.f, y = state_action_reward[i].s.s;
            if(reward>0)
            {
                fullOrder[x].pb(mp(y, reward));
                fullOrder[y].pb(mp(x, reward));
            }
            if(printStateActionReward)
            {
                cout << toBinaryString(x) <<" "<< toBinaryString(y) <<" " << reward << endl;
            }
            if(Find(x)!=Find(y))
            {
                unite(x, y);
                MST[x].pb(mp(y, reward));
                MST[y].pb(mp(x, reward));
                taken_edge++;
            }
            else
            {
            }
        }
        if(printFullOrder)
        {
            cout << "Full order " << fullOrder.size() <<endl;
            for(int i=0;i<fullOrder.size();i++)
            {
                 cout <<latice->printInput(i) << ": ";
                for(int j=0;j<fullOrder[i].size();j++)
                {
                    cout << latice->printInput(fullOrder[i][j].f) << " " << fullOrder[i][j].s <<" | ";
                }
                cout << endl;
            }
        }
        if(printMST)
        {
            cout << "MST " << MST.size() << endl;
            for(int i=0;i<MST.size();i++)
            {
                latice->printInput(i); cout << ": ";
                for(int j=0;j<MST[i].size();j++)
                {
                    latice->printInput(MST[i][j].f); cout << " " << MST[i][j].s <<" | ";
                }
                cout << endl;
            }
        }
    }

    vector<pair<int, pair<int, int> > > state_action_reward;
    vector<pair<int, pair<int, int> > > similar;
    vector<pair<int, pair<int, int> > > different;
    string printVector(vector<double> v)
    {
        string ret = "";
        for(int i=0;i<v.size();i++)
        {
            if(v[i]==1)
            {
                ret+='+';
            }
            else if(v[i]==0)
            {
                ret+='_';
            }
            else if(v[i]==-1)
            {
                ret +='-';
            }
            else
            {
                assert(0);
            }
        }
        return ret;
    }
    void printDeltaState(deltaState at, Data* latice)
    {
        deltaPredict deltaActor = at.f.f, deltaHint = at.f.s;
        cout << "learned: " << latice->printInput(deltaActor.f) <<" at "<< printVector(deltaActor.s);
        cout <<" | unlearned: " << latice->printInput(deltaHint.f) <<" at "<< printVector(deltaHint.s) <<" | mask: "<< printVector(at.s);
    }
    void printNewNeuron(pair<pair<int, vector<double> >, vector<double> > at, Data* latice)
    {
        cout << "Change in predict :: hint: " << latice->printInput(at.f.f) <<" at "<< printVector(at.f.s) <<" | mask: "<< printVector(at.s);
    }
    void analyzeMistakes(Data *latice)
    {
        vector<pair<int, deltaState> > sorted_nodes;
        vector<pair<int, pair<pair<int, vector<double> >, vector<double> > > > sorted_neurons;
        if(printMistakes)
        {
            for(map<deltaState, int>::iterator it = delta_knowledge_graph.begin(); it != delta_knowledge_graph.end(); it++)
            {
                deltaState at = (*it).f;
                int rez = (*it).s;
                sorted_nodes.pb(mp(rez, at));
            }
            sort_v(sorted_nodes);
            rev_v(sorted_nodes);

            cout << "delta_knowledge_graph : " << delta_knowledge_graph.size() <<endl;
            for(int i=0;i<sorted_nodes.size();i++)
            {
                printDeltaState(sorted_nodes[i].s, latice);
                cout << " = " << sorted_nodes[i].f <<endl;
            }
            /*
            for(map<pair<pair<int, vector<double> >, vector<double> >, int>::iterator it = new_neurons.begin(); it != new_neurons.end(); it++)
            {
                pair<pair<int, vector<double> >, vector<double> > at = (*it).f;
                int rez = (*it).s;
                sorted_neurons.pb(mp(rez, at));
            }
            cout << endl;
            cout << "new neurons: " << new_neurons.size() << endl;
            sort_v(sorted_neurons);
            rev_v(sorted_neurons);
            for(int i=0;i<sorted_neurons.size();i++)
            {
                printNewNeuron(sorted_neurons[i].s, latice);
                cout << " = " << sorted_neurons[i].f <<endl;
            }
            cout << endl;*/
            cout << "clasify neurons: "<< clasify_neurons.size() <<endl;
            for(map<vector<double>, set<deltaState> >::iterator it = clasify_neurons.begin();it!=clasify_neurons.end();it++)
            {
                vector<double> new_neuron = (*it).f;
                set<deltaState> knowledge = (*it).s;
                cout << printVector(new_neuron) <<" :: "<<endl;;
                for(set<deltaState>::iterator i=knowledge.begin();i!=knowledge.end();i++)
                {
                    cout << " ";
                    printDeltaState((*i), latice);
                    cout << " = "<< delta_knowledge_graph[(*i)] <<endl;
                }
            }
            vector<pair<int, vector<double> > > important_neurons;
            for(map<vector<double>, int>::iterator it = count_neuron_activation.begin();it!=count_neuron_activation.end();it++)
            {
                important_neurons.pb(mp((*it).s, (*it).f));
            }
            cout << endl;
            sort_v(important_neurons);
            rev_v(important_neurons);
            cout << "important neurons: " << important_neurons.size() << endl;
            for(int i = 0;i<important_neurons.size();i++)
            {
                cout << printVector(important_neurons[i].s) <<" :: "<< important_neurons[i].f <<endl;
            }
        }


        state_action_reward.clear();
        for(int i=0;i<latice->sampleSize;i++)
        {
            for(int j=i+1;j<latice->sampleSize;j++)
            {
                int type_ij_11 = state_action_change[mp(mp(i, 1), mp(1, j))];
                int type_ji_11 = state_action_change[mp(mp(j, 1), mp(1, i))];
                int type_ij_01 = state_action_change[mp(mp(i, 0), mp(1, j))];
                int type_ij_10 = state_action_change[mp(mp(i, 1), mp(0, j))];
                int type_ji_01 = state_action_change[mp(mp(j, 0), mp(1, i))];
                int type_ji_10 = state_action_change[mp(mp(j, 1), mp(0, i))];
                int type_ji_00 = state_action_change[mp(mp(j, 0), mp(0, i))];
                int type_ij_00 = state_action_change[mp(mp(i, 0), mp(0, j))];

                //    TODO: implement dynamic tree builing based on training's current state

                int reward = type_ij_01  + type_ji_01;
                reward*=(type_ji_10 + type_ij_10 == 0);
                reward -= type_ji_10 + type_ij_10 ;
                state_action_reward.pb(mp(reward, mp(i, j)));
            }
        }

    }

    vector<int> topologicalSortOfSamples(Data *latice)
    {
        analyzeMistakes(latice);

        assert(state_action_reward.size()>=latice->sampleSize);

        MST_of_samples(latice);

        sorted_samples.clear();

        color.assign(latice->sampleSize, 0);

        dfs(state_action_reward[0].s.f, 1);

        if(printTopologicalOrder)
        {
            cout << "Topological Order: "<< sorted_samples.size() <<endl;
            for(int i=0;i<sorted_samples.size();i++)
            {
                cout << toBinaryString(sorted_samples[i]) <<" ";
            }
            cout << endl;
        }
        return sorted_samples;
    }

};


class edge
{
public:
    int from;
    int to;
    edge(int _from, int _to)
    {
        from = _from;
        to = _to;
    }
};

class origin
{
public:
    string origin_label;

    string code;
    bool is_code_generated;

    bool has_local_id;
    int local_id;

    bool hardbits;

    bool is_input_node;
    bool is_output_node;

    bool is_not_node;
    bool is_generalization_node;
    bool is_specification_node;
    bool is_other_category_node;

    int operand;
    vector<int> operands;

    origin & operator=(const origin &rhs)
    {
        origin_label = rhs.origin_label;

        code = rhs.code;
        is_code_generated = rhs.is_code_generated;

        has_local_id = rhs.has_local_id;
        local_id = rhs.local_id;

        hardbits = rhs.hardbits;

        is_input_node = rhs.is_input_node;
        is_output_node = rhs.is_output_node;

        is_not_node = rhs.is_not_node;
        is_generalization_node = rhs.is_generalization_node;
        is_specification_node = rhs.is_specification_node;
        is_other_category_node = rhs.is_other_category_node;

        operand = rhs.operand;
        operands = rhs.operands;
    }

    void init()
    {
        is_code_generated = false;

        has_local_id = false;
        local_id = -1;

        hardbits = false;

        is_input_node = false;
        is_output_node = false;

        is_not_node = false;
        is_generalization_node = false;
        is_specification_node = false;
        is_other_category_node = false;

        operand = -1;
    }
    void init(string _origin_label)
    {
        init();
        origin_label = _origin_label;
        if(origin_label == "in")
        {
            is_input_node = true;
        }
        else if(origin_label == "out")
        {
            is_output_node = true;
        }
        else if(origin_label == "is")
        {
            is_specification_node = true;
        }
        else if(origin_label == "!is")
        {
            is_not_node = true;
            is_other_category_node = true;
        }
        else if(origin_label == "hardcode")
        {
            hardbits = true;
        }
        else if(origin_label == "bucket")
        {
            is_generalization_node = true;
        }
        else if(origin_label == "!")
        {
            is_not_node = true;
        }
        else if(origin_label == "generalize")
        {
            is_generalization_node = true;
        }
        else if(origin_label == "specify")
        {
            is_specification_node = true;
        }
        else
        {
            cout <<origin_label<<endl;
            assert(0);
        }
    }
    void init(pair<string, int> _code_local_id)
    {
        init(_code_local_id.first);
        local_id = _code_local_id.second;
        has_local_id = true;
    }
    void end_init()
    {
        //code = get_origin_label();
        //is_code_generated = true;
    }
    origin(){init();}
    origin(string _code){init(_code);end_init();}
    origin(pair<string, int> _code_local_id){init(_code_local_id);end_init();}
    origin(string _code, int _operand)
    {
        init(_code);
        operands.pb(_operand);
        end_init();
    }
    origin(string _code, vector<int> _operands)
    {
        init(_code);
        operands = _operands;
        end_init();
    }

    origin(pair<string, int> _code_local_id, int _operand)
    {
        init(_code_local_id);
        operand = _operand;
        operands.pb(operand);
        end_init();
    }

    string get_origin_label()
    {
        string ret = origin_label;
        if(has_local_id)
        {
            if(hardbits)
            {
                ret+="_"+toBinaryString(local_id);
            }
            else
            {
                ret +="_"+toDecimalString(local_id);
            }
        }
        else
        {

        }
        return ret;
    }
};

class computation
{
public:
    string operation_label;

    //int num_inputs;
    int judge;

    bool has_logic_input;
        bool has_logic_output;
            bool is_and_node;
            bool is_or_node;

        bool is_equals_node;
        bool is_different_node;

    bool is_read_node;


    string code;
    bool is_code_generated;

    computation & operator=(const computation &rhs)
    {
        operation_label = rhs.operation_label;
        judge = rhs.judge;
        //num_inputs = rhs.num_inputs;

        has_logic_output = rhs.has_logic_output;
            has_logic_input = rhs.has_logic_input;
                is_and_node = rhs.is_and_node;
                is_or_node = rhs.is_or_node;

            is_equals_node = rhs.is_equals_node;
            is_different_node = rhs.is_different_node;

        is_read_node = rhs.is_read_node;

        code = rhs.code;
        is_code_generated = rhs.is_code_generated;
    }

    void init()
    {

        has_logic_input = false;
            has_logic_output = false;
                is_and_node = false;//todo
                is_or_node = false;//todo

            is_equals_node = false;
            is_different_node = false;


        is_read_node = false;

        is_code_generated = false;
    }

    computation()
    {
        init();
    }
    void init(string _operation_label)
    {
        init();
        operation_label = _operation_label;
        code = operation_label;
        is_code_generated = true;
        if(operation_label=="==")
        {
            is_equals_node = true;
        }
        else if(operation_label=="!=")
        {
            is_different_node = true;
        }
        else if(operation_label=="or")
        {
            is_or_node = true;
            judge = 1;
        }
        else if(operation_label=="and")
        {
            is_and_node = true;
            judge = 0;
        }
        else if(operation_label=="read")
        {
            is_read_node = true;
        }
        else
        {
            assert(0);
        }
        has_logic_output = is_equals_node||is_or_node||is_and_node;
        has_logic_input = is_or_node||is_and_node;
    }
    computation(string _operation_label, int _judge)
    {
        assert(_operation_label == "=="||_operation_label=="!=");
        init(_operation_label);
        judge = _judge;
    }
    computation(string _operation_label)
    {
        init(_operation_label);
    }
    string get_operation()
    {
        return operation_label;
    }
    computation inverse_operation()
    {
        assert(is_or_node+is_and_node == 1);
        if(is_or_node)
        {
            return computation("and");
        }
        if(is_and_node)
        {
            return computation("or");
        }
    }
    computation same_operation()
    {
        assert(is_or_node+is_and_node == 1);
        return operation_label;
    }
    void assertLogicNode(computation *to_check)
    {
        assert(to_check->is_or_node+to_check->is_and_node == 1);
    }
    bool is_same_operation(computation rhs)
    {
        assertLogicNode(this);
        assertLogicNode(&rhs);
        return is_or_node == rhs.is_or_node;
    }
};

class node
{
public:
    int id;
    vector<int> edges_in;

    double output;
    int memmo_iteration;

    int not_id;

    origin lineage;

    computation compute;

    int specify_itteration;
    int not_specify_itteration;
    int specify_count;

    void init()
    {
        id = -1;
        not_id = -1;
        memmo_iteration = -1;
        output = -1;
        lineage.code = "undefined";
        specify_itteration = -1;
        not_specify_itteration = -1;
        specify_count = 0;
    }
    node(){init();}
    node(int _id){init(_id);}
    void init(int _id)
    {
        init();
        id = _id;
    }
    void init(int _id, computation _compute, origin _lineage)
    {
        init(_id);
        assert(_compute.is_code_generated);
        compute = _compute;
        assert(compute.is_code_generated);
        lineage = _lineage;
    }
    node(int _id, computation _compute, origin _lineage)
    {
        init(_id, _compute, _lineage);
    }
    void addInputEdge(int new_edge_id)
    {
        edges_in.pb(new_edge_id);
        compute.is_code_generated = false;
        if(compute.is_and_node)
        {
            compute.judge++;
        }
    }
    void removeEdge(int edge_id)
    {
        edges_in.erase(remove(edges_in.begin(), edges_in.end(), edge_id), edges_in.end());
        compute.judge = max(compute.judge-1.0, 1.0);
        compute.is_code_generated = false;
    }
    void setOutput(int value, int iteration)
    {
        memmo_iteration = iteration;
        output = value;
    }
    void updateCompute(string new_operation, vector<string> operands)
    {
        assert(0);
    }
    string get_operation()
    {
        return compute.get_operation();
    }

};

bool printlineage = true;

class metaNet
{
public:
    int n;
    vector<node> nodes;
    //vector<node_type> semantic;

    vector<edge> edges;

    vector<int> inputNodes;
    vector<int> outputNodes;

    vector<vector<int> > net;

    vector<int> v_init_net;

    int iteration;
    metaNet()
    {
        iteration = 0;
        n = 0;
        specify_itteration = 0;
    }
    int return_and_increment(int &number)
    {
        net.pb(v_init_net);
        int ret = number;
        number++;
        return ret;
    }

    int initNode(computation compute, origin lineage)
    {
        nodes.pb(node(n, compute, lineage));
        return return_and_increment(n);
    }

    string fullcode(int node_id)
    {
        bool tmp = printlineage;
        printlineage = true;
        pair<string, string> parts = generatecode(node_id, true);
        string ret;
        ret+=parts.f;
        if(parts.f!=""&&parts.s!="")ret+="<=";
        ret+=parts.s;
        printlineage = tmp;
        return ret;
    }

    pair<string, string> generatecode(int node_id, bool returnlineage)
    {
        assertNode(node_id);
        string lineage = "";
        if((returnlineage||nodes[node_id].lineage.is_input_node)&&!nodes[node_id].lineage.hardbits)
        {
            if(nodes[node_id].lineage.is_code_generated)
            {
                lineage = nodes[node_id].lineage.code;
            }
            else
            {
                lineage = nodes[node_id].lineage.get_origin_label();
                if(nodes[node_id].lineage.operands.size()>0)
                {
                    lineage+="(";
                    for(int i=0;i<nodes[node_id].lineage.operands.size();i++)
                    {
                        if(i!=0)
                        {
                            lineage+=",";
                        }
                        assert(node_id!=nodes[node_id].lineage.operands[i]);
                        pair<string, string> tmp;
                        if(!nodes[nodes[node_id].lineage.operands[i]].lineage.is_input_node)
                        {
                            tmp.f = toDecimalString(nodes[node_id].lineage.operands[i]);
                        }
                        else
                        {
                            tmp = generatecode(nodes[node_id].lineage.operands[i], printlineage);
                        }
                        lineage+=tmp.f;
                        if(tmp.f!=""&&tmp.s!="")lineage+="<=";
                        lineage+=tmp.s;
                    }
                    lineage+=")";
                }
                nodes[node_id].lineage.code = lineage;
                nodes[node_id].lineage.is_code_generated = true;
            }
        }
        string computation = "";
        if(nodes[node_id].compute.has_logic_input)
        {

            if(nodes[node_id].compute.is_code_generated)
            {
                computation = nodes[node_id].compute.code;
            }
            else
            {
                computation+=nodes[node_id].get_operation();
                vector<pair<bool, pair<int, int> > >  labels;
                string components = "";
                for(int i=0;i<nodes[node_id].edges_in.size();i++)
                {
                    if(i!=0)
                    {
                        components+=",";
                    }
                    int prev_node_id = edges[nodes[node_id].edges_in[i]].from;
                    pair<string, string> tmp = generatecode(prev_node_id, printlineage);
                    components += tmp.f;
                    if(tmp.f!=""&&tmp.s!="")components+="<=";
                    components+=tmp.s;
                    if(nodes[prev_node_id].lineage.operands.size()>0&&nodes[prev_node_id].lineage.has_local_id)
                    {
                        labels.pb(mp(nodes[prev_node_id].lineage.is_specification_node||nodes[prev_node_id].lineage.is_other_category_node,
                                        mp(nodes[prev_node_id].lineage.local_id+1*(!nodes[prev_node_id].compute.is_equals_node),
                                                nodes[nodes[prev_node_id].lineage.operand].lineage.local_id)));
                    }
                }
                sort_v(labels);
                if(labels.size()>0&&labels.size()==nodes[node_id].edges_in.size()&&labels[0].f && labels[labels.size()-1].f)
                {
                    vector<int> tmp;
                    components = "";
                    for(int i=0;i<inputNodes.size();i++)
                    {
                        components+="_";
                    }
                    for(int i=0;i<labels.size();i++)
                    {
                        tmp.pb(labels[i].s.f);
                        components[labels[i].s.s] = (labels[i].s.f+'0');
                    }
                }
                computation += "("+components+")";
                nodes[node_id].compute.code = computation;
                nodes[node_id].compute.is_code_generated = true;
            }
        }
        return mp(lineage, computation);
    }

    void init(int numInputs, int numOutputs)
    {
        assert(numInputs>0&&numOutputs>0);
        for(int i=0;i<numInputs;i++)
        {
            inputNodes.pb(initNode(computation("read"), origin(mp("in", i))));
        }
        for(int i=0;i<numOutputs;i++)
        {
            string code = toDecimalString(i);
            outputNodes.pb(initNode(computation("or"), origin(mp("out", i))));
        }
    }
    int addEdge(int from, int to)
    {
        assertNode(from);
        assertNode(to);
        net[from].pb(edges.size());
        nodes[to].addInputEdge(edges.size());
        int ret_edge_id = edges.size();
        edges.pb(edge(from, to));
        return ret_edge_id;
    }
    void addEdges_out(int node_id, vector<int> to)
    {
        for(int i=0;i<to.size();i++)
        {
            addEdge(node_id, to[i]);
        }
    }

    void addEdges_in(vector<int> from, int newNode_id)
    {
        for(int i = 0; i<from.size();i++)
        {
            addEdge(nodes[from[i]].id, newNode_id);
        }
    }


    void set_nots(int node_id, int not_node_id)
    {
        nodes[node_id].not_id = not_node_id;
        nodes[not_node_id].not_id = node_id;
    }
    void add_hardcode_node(vector<double> input_values, vector<double> output_values)
    {
        assert(inputNodes.size()==input_values.size()&&outputNodes.size()==output_values.size());
        vector<int> from_node_ids;
        for(int i=0;i<inputNodes.size();i++)
        {
            assert(input_values[i]==0||input_values[i]==1);
            bool exists = false;
            for(int j=0;j<net[inputNodes[i]].size();j++)
            {
                int case_node = edges[net[inputNodes[i]][j]].to;
                if(nodes[case_node].compute.is_equals_node&&nodes[case_node].compute.judge == input_values[i])
                {
                    assert(!exists);
                    from_node_ids.pb(case_node);
                    exists = true;
                }
                else if(nodes[case_node].compute.is_different_node&&nodes[case_node].compute.judge != input_values[i])
                {
                    assert(!exists);
                    from_node_ids.pb(case_node);
                    exists = true;
                }
            }
            if(!exists)
            {
                int new_case_node = initNode(computation("==", input_values[i]), origin(mp("is", input_values[i]), inputNodes[i]));
                addEdge(inputNodes[i], new_case_node);
                int new_not_case_node = initNode(computation("!=", input_values[i]), origin(mp("!is", input_values[i]), inputNodes[i]));
                addEdge(inputNodes[i], new_not_case_node);
                set_nots(new_case_node, new_not_case_node);
                from_node_ids.pb(new_case_node);
            }
        }


        int hardcode_if_node_id = initNode(computation("and"), origin("hardcode"));
        addEdges_in(from_node_ids, hardcode_if_node_id);

        vector<int> to_node_ids;
        for(int i=0;i<output_values.size();i++)
        {
            assert(output_values[i]==0||output_values[i]==1);
            if(output_values[i]==1)
            {
                to_node_ids.pb(outputNodes[i]);
            }
        }
        int hardcode_then_node_id = find_node_to(to_node_ids);
        if(hardcode_then_node_id == -1)
        {
            hardcode_then_node_id = initNode(computation("or"), origin("bucket"));
            addEdges_out(hardcode_then_node_id, to_node_ids);
        }
        addEdge(hardcode_if_node_id, hardcode_then_node_id);
    }
    int find_node_to(vector<int> to)
    {
        map<int, int> candidate_ids;
        for(int i=0;i<to.size();i++)
        {
            for(int j = 0;j<nodes[to[i]].edges_in.size();j++)
            {
                int candidate_id = edges[nodes[to[i]].edges_in[j]].from;
                candidate_ids[candidate_id]++;
            }
        }
        int ret = -1;
        for( map<int, int>::iterator it = candidate_ids.begin();it!=candidate_ids.end();it++)
        {
            if((*it).s==to.size()&&net[(*it).f].size()==to.size())
            {
                assert(ret == -1);
                ret = (*it).f;
            }
        }
        return ret;
    }

    void assertEdge(int edge_id)
    {
        assert(0<=edge_id&&edge_id<edges.size());
    }
    void updateEdge(int edge_id, int newFrom, int newTo)
    {
        assertNode(newFrom);
        assertNode(newTo);
        assertEdge(edge_id);
        if(edges[edge_id].from != newFrom)
        {
            int node_id_from = edges[edge_id].from;
            int node_id_to = edges[edge_id].to;

            net[node_id_from].erase(remove(net[node_id_from].begin(), net[node_id_from].end(), edge_id), net[node_id_from].end());

            edges[edge_id].from = newFrom;
            net[newFrom].pb(edge_id);
        }
        if(edges[edge_id].to != newTo)
        {
            cout << "not tested"<<endl;;
            assert(0);
            int node_id_to = edges[edge_id].to;
            nodes[node_id_to].edges_in.erase(remove(nodes[node_id_to].edges_in.begin(), nodes[node_id_to].edges_in.end(), edge_id), nodes[node_id_to].edges_in.end());
            edges[edge_id].to = newTo;
            nodes[newTo].edges_in.pb(edge_id);
        }
    }


    void assertNode(int node_id)
    {
        assert(0<=node_id&&node_id<n);
    }

    void add_not(int node_id)
    {
        assertNode(node_id);
        if(nodes[node_id].not_id!=-1)
        {
            return;
        }
        if(!nodes[node_id].compute.has_logic_input)
        {
            return;
        }
        vector<int> from_not_ids;
        for(int i=0;i<nodes[node_id].edges_in.size();i++)
        {
            int prev_node_id = edges[nodes[node_id].edges_in[i]].from;

            if(nodes[prev_node_id].not_id==-1)
            {
                add_not(prev_node_id);
            }
            assert(nodes[prev_node_id].not_id != -1);
            from_not_ids.pb(nodes[prev_node_id].not_id);
        }

        int newNode_id = initNode(nodes[node_id].compute.inverse_operation(), origin("!", node_id));

        addEdges_in(from_not_ids, newNode_id);
        nodes[node_id].not_id = newNode_id;
        nodes[newNode_id].not_id = node_id;
    }
    void generalize(int node_id)
    {
        if(nodes[node_id].edges_in.size()<=1)
        {
            return;
        }
        vector<vector<int> > find_overlap;
        vector<int> possibly_removable_edges_ids;
        for(int i=0;i<nodes[node_id].edges_in.size();i++)
        {
            int edge_id = nodes[node_id].edges_in[i];
            int prev_node_id = edges[edge_id].from;
            if(!nodes[prev_node_id].lineage.is_input_node)
            {
                vector<int> prev_prev_nodes_ids;
                for(int j=0;j<nodes[prev_node_id].edges_in.size();j++)
                {
                    int prev_prev_node_id = edges[nodes[prev_node_id].edges_in[j]].from;
                    if(!nodes[prev_prev_node_id].lineage.is_input_node)
                    {
                        prev_prev_nodes_ids.pb(prev_prev_node_id);
                    }
                }
                if(prev_prev_nodes_ids.size()>=1)
                {
                    sort_v(prev_prev_nodes_ids);
                    find_overlap.pb(prev_prev_nodes_ids);
                    possibly_removable_edges_ids.pb(edge_id);
                }
            }
        }
        if(find_overlap.size()<=1)
        {
            return;
        }
        vector<pair<vector<int>, pair<int, int> > > to_generalize;
        int count_c = 0;
        for(int i=0;i<find_overlap.size();i++)
        {
            for(int j=i+1;j<find_overlap.size();j++)
            {
                vector<int> common;
                vector<int> not_common;
                for(int k=0, l=0;k<find_overlap[i].size()||l<find_overlap[j].size();)
                {
                    count_c++;
                    if(l==find_overlap[j].size())
                    {
                        not_common.pb(find_overlap[i][k]);
                        k++;
                    }
                    else if(k==find_overlap[i].size())
                    {
                        not_common.pb(find_overlap[j][l]);
                        l++;
                    }
                    else
                    {
                        if(find_overlap[i][k]==find_overlap[j][l])
                        {
                            common.pb(find_overlap[i][k]);
                            k++;
                            l++;
                        }
                        else
                        {
                            if(find_overlap[i][k]>find_overlap[j][l])
                            {
                                not_common.pb(find_overlap[j][l]);
                                l++;
                            }
                            else
                            {
                                not_common.pb(find_overlap[i][k]);
                                k++;
                            }
                        }
                    }
                }
                if(not_common.size()==2)
                {
                    if(nodes[not_common[0]].not_id == not_common[1])
                    {
                        assert(nodes[not_common[1]].not_id == not_common[0]);
                        to_generalize.pb(mp(common, mp(possibly_removable_edges_ids[i], possibly_removable_edges_ids[j])));
                    }
                }
            }
        }

        for(int i=0;i<to_generalize.size();i++)
        {
            int removeEdge_id[2] = {to_generalize[i].s.f, to_generalize[i].s.s};
            int case_node_id = edges[to_generalize[i].s.f].to;

            assert(edges[removeEdge_id[0]].to == edges[removeEdge_id[1]].to);

            remove_edge(removeEdge_id[0]);
            remove_edge(removeEdge_id[1]);

            vector<int> generalizeedNodes;
            generalizeedNodes.pb(edges[removeEdge_id[0]].from);
            generalizeedNodes.pb(edges[removeEdge_id[1]].from);


            int newNode_id = initNode(nodes[generalizeedNodes[0]].compute.same_operation(), origin("generalize", generalizeedNodes));

            addEdges_in(to_generalize[i].f, newNode_id);
            addEdge(newNode_id, case_node_id);
        }
    }
    int specify_itteration;
    void specify(int node_id)
    {
        if(!nodes[node_id].compute.has_logic_input)
        {
            return ;
        }
        if(nodes[node_id].edges_in.size()==1)
        {
            return ;
        }
        int not_node_id = nodes[node_id].not_id;
        assert(not_node_id!=-1);
        specify_itteration++;
        for(int i=0;i<nodes[not_node_id].edges_in.size();i++)
        {
            int not_operand_id = edges[nodes[not_node_id].edges_in[i]].from;
            for(int j=0;j<net[not_operand_id].size();j++)
            {
                int not_covered_id = edges[net[not_operand_id][j]].to;
                nodes[not_covered_id].not_specify_itteration = specify_itteration;
            }
        }
        vector<int> to_specify_ids;
        vector<int> duplicates;
        for(int i=0;i<nodes[node_id].edges_in.size();i++)
        {
            int prev_node_id = edges[nodes[node_id].edges_in[i]].from;
            for(int j=0;j<net[prev_node_id].size();j++)
            {
                int next_node_id = edges[net[prev_node_id][j]].to;
                if
                    (
                        next_node_id != node_id &&
                        nodes[next_node_id].edges_in.size()>=2 &&
                        nodes[node_id].compute.is_same_operation(nodes[next_node_id].compute)
                    )
                    {
                        if(nodes[next_node_id].not_specify_itteration!=specify_itteration)
                        {
                            if(nodes[next_node_id].specify_itteration != specify_itteration)
                            {
                                nodes[next_node_id].specify_itteration = specify_itteration;
                                nodes[next_node_id].specify_count = 1;
                            }
                            else
                            {
                                nodes[next_node_id].specify_count++;
                                if(nodes[next_node_id].specify_count == nodes[node_id].edges_in.size() && nodes[node_id].edges_in.size() == nodes[next_node_id].edges_in.size())
                                {
                                    duplicates.pb(next_node_id);
                                }
                                else if(nodes[next_node_id].specify_count == nodes[next_node_id].edges_in.size())
                                {
                                    to_specify_ids.pb(next_node_id);
                                }
                            }
                        }
                    }
            }
        }
        if(duplicates.size()>=1)
        {
            map<int, vector<int> > add_edge_ids;
            //cout << "duplicates of "<< fullcode(node_id) <<endl;
            for(int i=0;i<duplicates.size();i++)
            {
                //cout << fullcode(duplicates[i]) <<endl;
                for(int j=0;j<net[duplicates[i]].size();j++)
                {
                    int to = edges[net[duplicates[i]][j]].to;
                    add_edge_ids[to].pb(net[duplicates[i]][j]);
                }
                nodes[duplicates[i]].edges_in.clear();
            }
            //cout << endl;
            for(int i=0;i<net[node_id].size();i++)
            {
                int to = edges[net[node_id][i]].to;
                if(add_edge_ids.find(to)!=add_edge_ids.end())
                {
                    vector<int> edge_ids = add_edge_ids[to];
                    assert(edge_ids.size()>0);
                    add_edge_ids[to].clear();
                    for(int j = 0;j<edge_ids.size();j++)
                    {
                        remove_edge(edge_ids[j]);
                    }
                }
            }
            for(map<int, vector<int> >::iterator it = add_edge_ids.begin();it!=add_edge_ids.end();it++)
            {
                vector<int> edge_ids = (*it).s;
                for(int i=0;i<edge_ids.size();i++)
                {
                    int to = edges[edge_ids[i]].to;
                    int edge_id = edge_ids[i];
                    assert(node_id!=to);
                    if(node_id!=to)
                    {
                        updateEdge(edge_id, node_id, to);
                    }
                }

            }
            for(int i=0;i<duplicates.size();i++)
            {
                assert(net[duplicates[i]].size()==0);
                assert(nodes[duplicates[i]].edges_in.size()==0);
            }
        }
        if(to_specify_ids.size()<=0)
        {
            return ;
        }
        vector<int> from_node_ids;
        vector<int> edge_in_ids;
        vector<int> covered;
        vector<vector<int> > covered_edge_ids;
        for(int i=0;i<nodes[node_id].edges_in.size();i++)
        {
            from_node_ids.pb(edges[nodes[node_id].edges_in[i]].from);
            edge_in_ids.pb(nodes[node_id].edges_in[i]);
            covered.pb(0);
            vector<int> v_empty;
            covered_edge_ids.pb(v_empty);
        }

        addEdges_in(to_specify_ids, node_id);

        assert(to_specify_ids.size()==0||!nodes[node_id].compute.is_code_generated);
        vector<int> new_node_from_ids;
        vector<int> covered_k;

        for(int i=0;i<to_specify_ids.size();i++)
        {
            for(int j=0;j<nodes[to_specify_ids[i]].edges_in.size();j++)
            {
                for(int k=0;k<from_node_ids.size();k++)
                {
                    if(from_node_ids[k]==edges[nodes[to_specify_ids[i]].edges_in[j]].from)
                    {
                        covered[k]++;
                        covered_edge_ids[k].pb(nodes[to_specify_ids[i]].edges_in[j]);
                        if(covered[k]==to_specify_ids.size())
                        {
                            new_node_from_ids.pb(edges[nodes[to_specify_ids[i]].edges_in[j]].from);
                            covered_k.pb(k);
                        }
                    }
                }
            }
        }

        for(int i=0;i<covered.size();i++)
        {
            if(covered[i]>0)
            {
                remove_edge(edge_in_ids[i]);
            }
        }
        if(new_node_from_ids.size()>=2&&to_specify_ids.size()>=2)
        {
            int newNode_id = initNode(nodes[node_id].compute.same_operation(), origin("specify", to_specify_ids));
            addEdges_in(new_node_from_ids, newNode_id);
            addEdges_out(newNode_id, to_specify_ids);
            for(int i=0;i<covered_k.size();i++)
            {
                for(int j=0;j<covered_edge_ids[covered_k[i]].size();j++)
                {
                    int remove_edge_id = covered_edge_ids[covered_k[i]][j];
                    remove_edge(remove_edge_id);
                }
            }
        }
    }
    void remove_edge(int edge_id)
    {
        int node_id_from = edges[edge_id].from;
        int node_id_to = edges[edge_id].to;

        net[node_id_from].erase(remove(net[node_id_from].begin(), net[node_id_from].end(), edge_id), net[node_id_from].end());

        nodes[node_id_to].removeEdge(edge_id);
    }
    void induce_specify()
    {
        for(int i=n-1;i>=0;i--)
        {
            if(nodes[i].edges_in.size()>0)
            specify(i);
        }
    }
    void induce_not()
    {
        for(int i=0;i<n;i++)
        {
            if(nodes[i].edges_in.size()>0)
            add_not(i);
        }
    }
    void induce_generalize()
    {
        for(int i=0;i<n;i++)
        {
            if(nodes[i].edges_in.size()>0)
            generalize(i);
        }
    }
    void build_lookup_table(Data *entity)
    {

        printNodes = false;
        printlineage = true;
        init(entity->numInputs, entity->numOutputs);
        printNet();
        for(int i=0;i<entity->sampleSize;i++)
        {
            add_hardcode_node(entity->in[i], entity->out[i]);
        }
        printNet();

        induce_not();induce_generalize();induce_not();induce_specify();printNet();
        induce_not();induce_generalize();induce_not();induce_specify();printNet();
        induce_not();induce_generalize();induce_not();induce_specify();printNet();
        induce_not();induce_generalize();induce_not();induce_specify();printNet();
        induce_not();induce_generalize();induce_not();induce_specify();printNet();
        printNodes = true;
        printNet();
    }

    void evolve()
    {
        return;
        cout << "Set up for logic: " <<endl;
        printNet();
        int numCycles = 5;
        while(numCycles--)
        {
            induce_not();
            printlineage = false;
            cout << "added not: " <<endl;
            printNet();
            induce_specify();
            cout << "clasificatied" <<endl;
            printlineage = false;
            printNet();
            induce_generalize();
            printlineage = false;
            cout << "generalized: " <<endl;
            printNet();

        }
    }
    int printNodes;
    void printNet()
    {
        cout << n<<endl;
        if(printNodes)
        {
            int count_inLinbo = 0;
            for(int i=0;i<n;i++)
            {
                if(net[i].size()==0&&!nodes[i].lineage.is_output_node)
                    count_inLinbo ++;

                if(nodes[i].edges_in.size()>0)
                {
                    pair<string, string> tmp = generatecode(i, true);
                    string output = tmp.f;
                    if(tmp.f!=""&&tmp.s!="") output+="<=";
                    output+=tmp.s;
                    cout << i <<" :: "<< output << endl;
                    cout << "inputs: ";
                    for(int j=0;j<nodes[i].edges_in.size();j++)
                    {
                        cout << edges[nodes[i].edges_in[j]].from <<" ";
                    }
                    cout << endl <<"output: ";
                    for(int j=0;j<net[i].size();j++)
                    {
                        cout << edges[net[i][j]].to <<" ";
                    }
                    cout << endl;
                }
                else
                {
                    cout << i <<" in tbd"<<endl;
                }
            }
            cout << "in Linbo: " << count_inLinbo <<endl;
        }
        cout << endl;
    }
    double getOutput(int node_id, int iteration)
    {
        if(iteration == nodes[node_id].memmo_iteration)
        {
            return nodes[node_id].output;
        }
        int count_in = 0;
        for(int i=0;i<nodes[node_id].edges_in.size();i++)
        {
            assert(edges[nodes[node_id].edges_in[i]].to == node_id);
            int from = edges[nodes[node_id].edges_in[i]].from;
            if(nodes[node_id].compute.is_equals_node)
            {
                count_in+=(getOutput(from, iteration)==nodes[node_id].compute.judge);
            }
            else if(nodes[node_id].compute.is_different_node)
            {
                count_in+=(getOutput(from, iteration)!=nodes[node_id].compute.judge);
            }
            else
            {
                count_in+=getOutput(from, iteration);
            }
        }
        if(nodes[node_id].compute.is_equals_node || nodes[node_id].compute.is_different_node)
        {
            nodes[node_id].output = (count_in == (nodes[node_id].edges_in.size()));
        }
        else
        {
            assert(nodes[node_id].compute.is_and_node||nodes[node_id].compute.is_or_node);
            nodes[node_id].output = (count_in >= nodes[node_id].compute.judge);
        }
        return nodes[node_id].output;
    }

    vector<double> feedForward(vector<double> input)
    {
        iteration++;
        assert(input.size()==inputNodes.size());
        for(int i=0;i<input.size();i++)
        {
            nodes[inputNodes[i]].setOutput(input[i], iteration);
        }
        vector<double> ret;
        for(int i=0;i<outputNodes.size();i++)
        {
            ret.pb(getOutput(outputNodes[i], iteration));
        }
        return ret;
    }
    void test(Data *latice)
    {
        int count_wrong = 0;
        for(int i=0;i<latice->sampleSize;i++)
        {
            vector<double> predict = feedForward(latice->in[i]);
            bool correct = latice->checkPrediction(i, predict);
            if(!correct)
            {
                latice->printTest(i, predict);
            }
            count_wrong+=!correct;
        }
        cout << "wrong: " << count_wrong << endl;
    }


};


void work_meta_net()
{
    //string type = "input_is_output";
    string type = "longestSubstring_ai_is_1";
    //string type = "a_i_is_a_i_plus_one_for_all";
    //string type = "longestSubstring_dai_di_is_0";

    int inputSize = 5;
    number_of_dimesions = inputSize;
    int outputSize;
    Data scripts_neuron_description;
    scripts_neuron_description.generateData(inputSize, outputSize, type);
    scripts_neuron_description.make_binary();
    //scripts_neuron_description.seeData();

    metaNet brain = metaNet();
    brain.build_lookup_table(&scripts_neuron_description);
    brain.evolve();
    //brain.printNet();

    brain.test(&scripts_neuron_description);
}

int work_net()
{

    //string type = "input_is_output";
    string type = "longestSubstring_ai_is_1";
    //string type = "a_i_is_a_i_plus_one_for_all";
    //string type = "longestSubstring_dai_di_is_0";

    int inputSize = 3, outputSize;
    number_of_dimesions = inputSize;
    int inter = 2*inputSize;
    int hiddenLayers[10] =
    {
        inter,
        -1
    };

    printCycle = true;
    printItteration = false;
    printFullOrder = false;
    printMST = false;
    printStateActionReward = false;
    printTopologicalOrder = true;
    printMistakes = true;

    LEARNING_RATE = 1;

    Data oldScripts;
    oldScripts.generateData(inputSize, outputSize, type);

    net teacher = net(inputSize, hiddenLayers, outputSize);
    teacher.train(&oldScripts, "queue train");


    Data testData;
    testData.generateData(inputSize, outputSize, type);
    teacher.test(&testData, "print result");
    cout << endl;

    vector<int> hintOrder = teacher.topologicalSortOfSamples(&oldScripts);

    Data newScripts;
    newScripts.generateData(inputSize, outputSize, type, hintOrder);

    net brain = net(inputSize, hiddenLayers, outputSize);
    brain.train(&newScripts, "queue train");

    hintOrder = brain.topologicalSortOfSamples(&newScripts);

    brain.test(&testData, "print result");

    return 0;
}

int main()
{
    cout << "Meta Net" << endl << endl;
    int t = 1;
    while(t--)
    {
        work_meta_net();
        //work_net();
    }
    cout << endl;
}

/*void splitEdges_out(int node_id)
    {
        if(net[node_id].size()==0)
        {
            return ;
        }
        vector<pair<int, int> > edges_out; //pair<int edge_w, edge_id>
        for(int i=0;i<net[node_id].size();i++)
        {
            int edge_id = net[node_id][i];
            edges_out.pb(mp(edges[edge_id].w, edge_id));
        }
        sort_v(edges_out);
        vector<double> new_edge_w;
        vector<vector<int> > split_edges;
        vector<int> currentClass;

        new_edge_w.pb(edges_out[0].f);
        currentClass.pb(edges_out[0].s);
        for(int i=1;i<edges_out.size();i++)
        {
            if(edges_out[i].f!=edges_out[i-1].f)
            {
                split_edges.pb(currentClass);
                currentClass.clear();
                new_edge_w.pb(edges_out[i].f);
                currentClass.pb(edges_out[i].s);
            }
            else
            {
                currentClass.pb(edges_out[i].s);
            }
        }
        split_edges.pb(currentClass);

        if(split_edges.size()==edges_out.size() || split_edges.size() == 1)
        {
            return ;
        }
        vector<int> split_nodes_ids;
        for(int i=0;i<split_edges.size();i++)
        {
            int newNode_id = initNode(computation("=="), origin(mp("if", i), node_id));
            split_nodes_ids.pb(newNode_id);
            for(int j=0;j<split_edges[i].size();j++)
            {
                int edge_id = split_edges[i][j];
                updateEdge(edge_id, newNode_id, edges[edge_id].to, 1);
            }
        }
        bool add_not = (new_edge_w.size()==2&&new_edge_w[0]==-new_edge_w[1]);
        if(add_not)
        {
            nodes[split_nodes_ids[0]].not_id = split_nodes_ids[1];
            nodes[split_nodes_ids[1]].not_id = split_nodes_ids[0];
        }
        //debug
        //net[node_id].clear();
        addEdges_out(node_id, split_nodes_ids, new_edge_w);
    }
    */