#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <math.h>
#include <algorithm>

using namespace std;

class Map
{
    public:
        Map();
        Map(string seed);
        int width;
        int height;
        string values;
        char value_at(int x, int y);
        void set_value_at(int x, int y, char val);
        bitset<24> observe(int x, int y);
};

Map::Map(string seed)
{
    string delim = ":";
    int start = 0U;
    int end = seed.find(delim);
    string rows = seed.substr(start, end - start);
    
    height = stoi(rows);

    start  = end + delim.length();
    end = seed.find(delim, start);
    string cols = seed.substr(start, end-start);
    
    width = stoi(cols);

    start  = end + delim.length();
    end = seed.find(delim, start);

    values = seed.substr(start, end);
}

void Map::set_value_at(int x, int y, char val)
{
    if (x < 0 || y < 0 || x >= height || y >= width){
        return;
    }
    values[x*width + y] = val;
    return;
}

char Map::value_at(int x, int y)
{
    if (x < 0 || y < 0 || x >= height || y >= width){
        char temp = '*';
        return temp;
    }
    return values.at(x*width + y);
}

bitset<24> Map::observe(int x, int y)
{
    /*
    *
    * There are 8 zones around the rat, four close zones and four far zones
    * The close zones are the squares in a given quadrant that are 1 away 
    * (e.g. to my left, to my top-left, and above me are the one away squares in
    * the -x, -y  or NW quadrant)
    * The far zones are the squares from each quadrant that are 2 or 3 moves away
    * (e.g. the squares with distance (-3,0), (0, -3), (-3, -3) are the outer 
    * corners of the NW quadrant.
    * The quadrants are always ordered NW then NE then SW then SE first 
    * close and then far.
    * This method outputs 24 0/1 values, first the 8 zones are asked if they have
    * an obstacle "*" those 8 answers will be senses[0] through senses[7] in the 
    * above mentioned order
    * Then each of the 8 zones is asked is they have food, "$", again 8 answers.
    * Finally each zone is asked if it contains a pit "X".
    * These will act as the rat's "senses".
    */
    string targets = "*$X";
    string close[4] = {"","","",""};
    string far[4] = {"","","",""};
    int quadrant[4][2] = {{-1,-1},{-1,1},{1,-1},{1,1}};
    for (int dx = 0; dx < 4; dx++)
    {
        for (int dy = 0; dy < 4; dy++)
        {
            for (int qi = 0; qi < 4; qi++)
            {
                int sign_x = quadrant[qi][0];
                int sign_y = quadrant[qi][1];
                if (dx == 0 && dy == 0){
                    break;
                } else if (dx > 1 || dy > 1){
                    far[qi] += value_at(x + sign_x*dx, y + sign_y*dy);
                } else {
                    close[qi] += value_at(x + sign_x*dx, y + sign_y*dy);
                }
            }
        }
    }
    int counter = 0;
    bitset<24> senses;
    bool bit_value = 0;
    size_t found;
    for (int i = 0; i < 3; i++)
    {
        char target = targets.at(i);
        for (int qi = 0; qi < 4; qi++)
        {
            bit_value = 0;
            found = close[qi].find(target);
            if (string::npos != found)
            {
                bit_value = 1;
            }
            senses.set(counter, bit_value);
            counter++;
        }
        for (int qi = 0; qi < 4; qi++)
        {
            bit_value = 0;
            found = far[qi].find(target);
            if (string::npos != found)
            {
                bit_value = 1;
            }
            senses.set(counter, bit_value);
            counter++;
        }
    }
    return senses;
}

class NeuralNet
{
    public:
        NeuralNet();
        void setWeights(vector<double> weights);
        static vector<double> translateGenome(string genome);
        static string translateWeights(vector<double> weights);
        static const int n_i = 25;
        static const int n_h = 10;
        static const int n_o = 4;
        bitset<n_o> makeChoices(bitset<n_i> inputs);
        double W_ih[n_i][n_h];
        double W_ho[n_h][n_o];
};

NeuralNet::NeuralNet(){};

void NeuralNet::setWeights(vector<double> weights)
{
    /* 
    *  Takes in n_i*n_h + n_h*n_o double values where n_i is the number of input
    * neurons (25 in our case the first is "pain" (did the rat just hit an obstacle?)
    * the other 24 are explained above in Map::observe)
    * The n_h (10 by my settings) hidden neurons are there for complex behavior, 
    * they can kind of be thought of as emotional states.
    * The n_o outputs will be an encoding of the rat's next movement choice.
    */
    int pos = 0;
    int tpos = 0;
    int W_ih_size = n_i*n_h;
    int x, y;
    for (vector<double>::iterator it = weights.begin(); it != weights.end(); ++it){
        if (pos < W_ih_size){
            x = int(pos/n_h);
            y = int(pos % n_h);
            W_ih[x][y] = *it;
            pos++;
        } else {
            tpos = pos - W_ih_size;
            x = int(tpos / n_o);
            y = int(tpos % n_o);
            W_ho[x][y] = *it;
            pos++;
        }
    }
}

bitset<4> NeuralNet::makeChoices(bitset<25> inputs)
{
    bitset<n_h> hidden;
    for (int i = 0; i < n_h; i++)
    {
        double res = 0.0;
        for (int j = 0; j < n_i; j++)
        {
            double tval = double(inputs[j])*double(W_ih[j][i]);
            res += tval;
        }
        /* After checking which weights from inputs affect a given hidden neuron
        * If there is more positive than negative we fire it.
        */
        hidden[i] = res > 0;
    }
    bitset<n_o> output;
    for (int i = 0; i < n_o; i++)
    {
        double res = 0.0;
        for (int j = 0; j < n_h; j++)
        {
            double tval = double(hidden[j])*double(W_ho[j][i]);
            res += tval;
        }
        output[i] = res > 0;
    }
    return output;
}

vector<double> NeuralNet::translateGenome(string genome)
{
    vector<double> temp(0);
    for (int i = 0; i < genome.length(); i++)
    {
        char c = genome.at(i);
        double temp_val = double(c) - 82.0;
        temp.push_back(temp_val/40.0);
    }
    return temp;
}

string NeuralNet::translateWeights(vector<double> weights){
    string answer = "";
    int pos = 0;
    double temp = 0.0;
    for (vector<double>::iterator it = weights.begin(); it != weights.end(); ++it){
        temp = *it;
        temp *= 40;
        temp += 82;
        temp = round(temp);
        answer += char(temp);
    }
    return answer;
}

class Rat
{
    public:
        Rat(int start_x, int start_y, string genome);
        int isDead();
        void changeEnergy(int delta);
        bitset<24> observeWorld(Map world);
        bitset<4> makeChoices(bitset<24> senses);
        void enactChoices(bitset<4> choices);
        int x, y;
        bool hit_obstacle;
        int speed_y, speed_x, energy;
    private:
        string genome;
        NeuralNet brain;
};

Rat::Rat(int start_x, int start_y, string genome)
{
    x = start_x;
    y = start_y;
    speed_x = 1;
    speed_y = 1;
    energy = 30;
    hit_obstacle = 0;
    genome = genome;
    brain.setWeights(NeuralNet::translateGenome(genome));
}

int Rat::isDead()
{
    if (energy <= 0){
        return 1;
    } else {
        return 0;
    }
}

void Rat::changeEnergy(int delta)
{
    energy = energy + delta;
}

void Rat::enactChoices(bitset<4> choices)
{
    speed_x = choices[0] - choices[1];
    speed_y = choices[2] - choices[3];
}

bitset<24> Rat::observeWorld(Map world)
{
    bitset<24> observations = world.observe(x, y);
    return observations;
}

bitset<4> Rat::makeChoices(bitset<24> observations)
{
    bitset<25> pain_and_observations;
    for (int i = 1; i < 25; i++)
    {
        pain_and_observations[i] = observations[i-1];
    }
    pain_and_observations[0] = hit_obstacle;
    bitset<4> choices = brain.makeChoices(pain_and_observations);
    
    /* To see input observations and output decisions uncomment the below code
        cout << "observed "<< pain_and_observations.template to_string<char,
         std::char_traits<char>,
         std::allocator<char> >() << endl;
        cout << "chose to do: "<< choices.template to_string<char,
         std::char_traits<char>,
         std::allocator<char> >() << endl;*/
        /* choices[0] is the choice to move down by 1, choices[1] is to move up by 1, 
        *  choices[2] is to move right by 1, choices[3] is to move left by 1
        * if all four are 1 then the rat doesn't move for example, while if it is 
        * choices[0] = 1, choices[1] = 0, choices[2] = 0 and choices[3] = 1 then it moves 
        * down and left */
    return choices;
}

int simulator(string mapseed, string genome, int start_x, int start_y)
{
    Map board(mapseed);
    Rat arat(start_x, start_y, genome);
    int cur_x, cur_y;
    int target_x, target_y;
    int dx, dy;
    char next_spot;
    int moves = 0;
    while (!arat.isDead())
    {
        moves++;
        cur_x = arat.x;
        cur_y = arat.y;
        cout << "rat at "<< cur_x << " by " << cur_y << " on move " << moves << endl;
        arat.enactChoices(arat.makeChoices(arat.observeWorld(board)));
        target_x = cur_x + arat.speed_x; 
        target_y = cur_y + arat.speed_y; 
        next_spot = board.value_at(target_x, target_y);
        arat.hit_obstacle = 0;
        if (char(next_spot) == char('$'))
        {
            arat.changeEnergy(10);
            board.set_value_at(target_x, target_y, '.');
        } else if (char(next_spot) == char('X'))
        {
            arat.energy = 0;
        } else if (char(next_spot) == char('*'))
        {
            arat.hit_obstacle = 1;
            arat.changeEnergy(-10);
            target_x = cur_x;
            target_y = cur_y;
        }
        arat.changeEnergy(-1);
        arat.x = target_x;
        arat.y = target_y;
    }
    return moves;   
}

int main(void){
    string mapseed = "25:25:..$.$.X.............X....$X.X*..X$..X...*X$..$...X$.$......X.$.X...XX.$.X*.*.*..X..X.**.......X..$$$...........XX.....................$...X...*.$..X..$X..........$.*..X.....$.X..$*.$X......$...X.*X$......$.**.X.X..XX$X..*....*..X.X....$...X...X........$.X....$...*...X$*........X..$*$$......$$...$*..X.$.$......$.$.$...$..X.*.....X..$......$.XX*..X.$.X......X$*.**.....X*...$..XX..X.....$....X....X...X....X.$X$..X..........$...*.X$..X...$*...........*....XXX$$.$.$..*$XX..XX..*.....$......X.XX$..$$..X$.XX.$$..X.*..*......X......$..$.$$..*...X.........$X....$X.$$.*.$.$.$..**.....X.$.$X.*.$.........$**..X.X.X$X.$.*X.X*..$*.";
    string genome = "Sfz2smu:zej,9j:R\\[thR73RzRdP0U.v2TF9-X/PTlOPdYF+k1N;o3`[uTfT>RTq:rsTBk:gYlNq-[@OmMrvVo^U\\z=JV>l.tAq*\\BLM3vJQLfnnpr_mN-7RN;^.-9j4ddZKXN,gvH;x:qYAgPz+tb29Li[qJ/jH+UepmPpV0qC^u2tpvl_/Z-`OTmijR@XW5iJRk0/\\ztnzDHBu+HmsY*,AlZy`aJZ?WFQf*?>3`z6\\TiU+O,MvIH\\7zL?:=/.w^V/XH-`[X+8L7.+zxDBEm;jwW29jp/oj<Y";
    /*Note the escaped backslashes \\ as opposed to just ascii \*/
    int start_row = 12;
    int start_col = 12;
    cout << "Length of genome: " << genome.length() << endl;

    int moves = simulator(mapseed, genome, start_row, start_col);
    /* NOTE that I mistakenly use x for row and y for column throughout the code*/
    cout << "This rat lasted " << moves << " moves." << endl;
    cout << "Its genome is " << NeuralNet::translateWeights(NeuralNet::translateGenome(genome)) << endl;
    return 0;
}