/*#############################################################################
()=()
(^;^)
C   C
()_()
###############################################################################

     ()-() Preprocessor
_____(0:0)_/____________________*/

#include <iostream>
#include <ctime>
#include <cstdlib>

#define w 16
#define h 16
#define nothing '.'


using namespace std;

/*   ()-() Prototype
_____(0:0)_/____________________*/

class tripletown
{
public:
    char * map;     //this is the map ptr, only an array of char
    int ww,         //width of the map
        hh,         //height of the map
		size,		//size of the array
        stSize,     //size of the stack
        stIndex,    //stack index , increment every push
        * stack;    //the stack itself is pointed here
    //stack operation
    void stPush(int );  //stack push
    bool stFind(int );  //find if the int is present in the stack
    void stClear();     //empty the stack
    //map operation
    int offset(int , int );             //offset for X,Y coordinate
    char next(char );                   //evolution of tile
    int neightboor(int , int , char );  //recursive function of merging
    int neightboor(int , char);
    //constructor destructor
    tripletown(int ,int , char);
    ~tripletown();
	int find(char,int);
    char get(int );
    void put(int , char );
    void select();
    void put(char);
	int nFree();
};


/*   ()-() Main Program
_____(0:0)_/____________________*/

int main()
{
    //init
    tripletown map(w,h,'.');
    srand((unsigned)time(0));
    for (int i=0;i<500;i++)
        map.put(rand()%(w*h),'1');
    char c = 0;
    //main
    while (c != 'q' || map.nFree() != 0)
    {
        //show
        cout << "\ntripletown\n";
        cout << map.map << '\n';
        //input
        c = cin.get();
        switch (c)
        {
            case 'a':
                map.select();
                break;
            case 'z':
                map.put('1');
                break;
        }
    }
    //end
    //delete map;
    return 0;
}

/*   ()-() Class
_____(0:0)_/____________________*/
//public construtor (width, height, filling character)
tripletown::tripletown(int _w,int _h, char fill)
{

    ww = _w+1;
    hh = _h;
	size = ww*hh;
    stSize = ww*hh;
    stIndex = 0;
    stack = new int(ww*hh);
    map = new (nothrow) char[ww*hh];
    for (int i=0; i<ww*hh; i++)
    {
        if (i%ww==0 && i!=0)
            *(map+i) = '\n';
        else
            *(map+i) = nothing;
    }
    *(map+ww*hh/2-ww/2) = '_';
    *(map+ww*hh) = 0;
}
//public destructor
tripletown::~tripletown()
{
    delete map;
    delete stack;
}
//stack push , will add the offset to a pool
void tripletown::stPush(int a)
{
    *(stack+stIndex) = a;
    stIndex++;
}
//stack find , will return true if offset is present in stack
bool tripletown::stFind(int a)
{
    for (int i=0;i<stIndex;i++)
    {
        if (*(stack+i) == a)
            return true;
    }
    return false;
}
//stack clear , will empty the stack in a very fast way
void tripletown::stClear()
{
    stIndex = 0;
}
//return offset from given x,y
int tripletown::offset(int x, int y)
{
    if (x>=0 && y>=0 && x<ww && y<hh)
        return x+y*ww;
    return -1;
}
//return next character from given character. upgrate hiearchy
char tripletown::next(char c)
{
    if ((c>='1' && c<'9') || (c>='a' && c<'z') || (c>='A' && c<'Z'))
        return c+1;
    else if (c=='9' || c=='z' || c=='Z')
        return '$';
    else
        return nothing;
}
//find the character in the map
int tripletown::find(char c,int i)
{
    int o = i+1;
    while (o!=i && *(map+o)!=c)
    {
        if (o==size)
            o=0;
        else
            o++;
    }
    return o;
}
//recursive neightborhood merging, all the rule of triple town
//in this stripped down pathfinding algorithm
int tripletown::neightboor(int o, char c)
{
    int cnt = 1;
    if (!stFind(o))
    {
    stPush(o);
    if (get(o-ww)==c)
        cnt += neightboor(o-ww,c);
    if (get(o+ww)==c)
        cnt += neightboor(o+ww,c);
    if (get(o-1)==c)
        cnt += neightboor(o-1,c);
    if (get(o+1)==c)
        cnt += neightboor(o+1,c);
    return cnt;
    }
    return 0;
}
//will put the character to a given offset if the tile is empty
void tripletown::put(int offs, char t)
{
    if (offs<0 || offs>ww*hh || offs%ww==0)
        return;
    if (*(map+offs) == '.')
	{
        *(map+offs) = t;
		if (neightboor(offs,t) > 2)
		{
			for (int i=0;i<stIndex;i++)
			{
				*(map+*(stack+i)) = nothing;
			}
			stClear();
			put(offs,next(t));
		}
		stClear();
	}
}

char tripletown::get(int offs)
{
    if (offs< ww*hh)
    {
        return *(map+offs);
    }
    return 0;
}

void tripletown::select()
{
    int o = find('_',0);
    *(map+o)='.';
    o = find('.',o);
    *(map+o)='_';
}

void tripletown::put(char c)
{
    int o = find('_',0);
    *(map+o) = '.';
    put(o,c);
    o = find('.',o);
    *(map+o) = '_';
}

int tripletown::nFree()
{
	int i = 0,
		n = 0;
	while(i<size)
	{
		if (*(map+i) == '.')
			n++;
		i++;
	}
	return n;
}