#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;

	return 0;
}