#include <stdio.h>
#include <stdlib.h>
#include <string.h>


bool debug_init = true;
class DoubleLinesOutput
{
public:
	DoubleLinesOutput() : col(0), enable(false) {}
	void setEnable(bool v) { enable = v; }
	void add(int i1, int i2, int i3, int i4)
    {
    	if (!enable)
        	return;
    	line1[col] = ' ';
    	line2[col] = ' ';
    	col++;
    	line1[col] = i1;
    	line1[col+1] = i2;
    	line2[col] = i3;
    	line2[col+1] = i4;
    	col += 2;
    	if (col > 64)
        {
        	line1[col] = '\0';
        	line2[col] = '\0';
        	printf("%s\n%s\n\n", line1, line2);
        	col = 0;
        }
    }
	void flush()
    {
    	if (!enable)
        	return;
    	if (col > 0)
        {
        	line1[col] = '\0';
        	line2[col] = '\0';
        	printf("%s\n%s\n", line1, line2);
        	col = 0;
        }
    	printf("\n");
    }
private:
	bool enable;
	int col;
	char line1[100];
	char line2[100];
};



struct Sequence
{
	char c;
	Sequence* next;
	Sequence* sibling;
	bool impossible;
	bool bottom;
	bool top;
	Sequence(char n_c) : c(n_c), next(0), sibling(0), impossible(false), bottom(false), top(false) {}
};
Sequence *all_seq = 0;
Sequence* getPossibleNext(char c, Sequence* siblings)
{
	for (; siblings != 0; siblings = siblings->sibling)
    	if (siblings->c == c)
        	return siblings->impossible ? 0 : siblings;
	return 0;
}
Sequence* addNext(char c, Sequence** ref_siblings)
{
	for (; *ref_siblings != 0; ref_siblings = &(*ref_siblings)->sibling)
	if ((*ref_siblings)->c == c)
    	return (*ref_siblings);
    (*ref_siblings) = new Sequence(c);
	return (*ref_siblings);
}

struct Chain
{
	char t;
	char b;
	Chain* next;
	Chain* sibling;
	bool impossible;
	bool front;
	bool back;
	Chain(char n_t, char n_b) : t(n_t), b(n_b), next(0), sibling(0), impossible(false), front(false), back(false) {}
};
Chain* all_chains = 0;
Chain* getPossibleNext(char t, char b, Chain* siblings)
{
	for (; siblings != 0; siblings = siblings->sibling)
    	if (siblings->t == t && siblings->b == b)
        	return siblings->impossible ? 0 : siblings;
	return 0;
}
Chain* addNext(char t, char b, Chain** ref_siblings)
{
	for (; *ref_siblings != 0; ref_siblings = &(*ref_siblings)->sibling)
    	if ((*ref_siblings)->t == t && (*ref_siblings)->b == b)
        	return (*ref_siblings);
    (*ref_siblings) = new Chain(t, b);
	return (*ref_siblings);
}

void addChain(char lt, char rt, char lb, char rb, DoubleLinesOutput &dlou)
{
	if ((lt == 'a' || rb == 'a') && (rt == 'a' || lb == 'a')) return;
	Chain *chain = addNext(lt, lb, &all_chains);
                   addNext(rt, rb, &chain->next);
	Sequence *tseq = addNext(lt, &all_seq);
                     addNext(rt, &tseq->next);
	Sequence *bseq = addNext(lb, &all_seq);
                     addNext(rb, &bseq->next);
	dlou.add(lt, rt, lb, rb);
}

const char *pattern[] = {
    "          ",
    " a bc     ",
    "          ",
    " d fg jkl ",
    " e hi mno ",
    "          ",
    "   pq ABC ",
    "   rs DEF ",
    "   tu GHI ",
    "          "};
    
int bar[256];
int depthcode[256];
bool leftcode[256];

#define TOP 1
#define LEFT 2
#define RIGHT 4
#define BOTTOM 8

class PatternIterator
{
public:
	PatternIterator(const char *sel) : _sel(sel), _more(true) { _next(true); }
	bool more() const { return _more; }
	void next() { _next(false); }
	const char tl() const { return pattern[_i][_j]; }
	const char tr() const { return pattern[_i][_j+1]; }
	const char bl() const { return pattern[_i+1][_j]; }
	const char br() const { return pattern[_i+1][_j+1]; }
	const int i() const { return _i; }
	const int j() const { return _j; }
private:
	void _next(bool init)
    {
    	if (!init) goto _n;
    	for (_i = 0; _i < 9; _i++)
        	for (_j = 0; _j < 9; _j++)
            	if (   (_sel[0] == ' ') == (pattern[_i][_j] == ' ')
                    && (_sel[1] == ' ') == (pattern[_i][_j+1] == ' ')
                    && (_sel[2] == ' ') == (pattern[_i+1][_j] == ' ')
                    && (_sel[3] == ' ') == (pattern[_i+1][_j+1] == ' '))
                {
                	return;
                	_n: ;
                }
    	_more = false;
    }
	const char *_sel;
	bool _more;
	int _i, _j;
};
    



int main(int argc, char* argv[])
{

	for (int i = 1; i < 9; i++)
    	for (int j = 1; j < 9; j++)
        	if (pattern[i][j] != ' ')
            {
            	bar[pattern[i][j]] 
                    = (pattern[i-1][j] != ' ' ? TOP : 0)
                    | (pattern[i][j-1] != ' ' ? LEFT : 0)
                    | (pattern[i][j+1] != ' ' ? RIGHT : 0)
                    | (pattern[i+1][j] != ' ' ? BOTTOM : 0);
            	int k = 1;
            	while (pattern[i+k][j] != ' ')
                	k++;
            	depthcode[pattern[i][j]] = k;
            	leftcode[pattern[i][j]] = pattern[i][j-1] != ' ';
            }

	DoubleLinesOutput doubleLinesOutput;
	doubleLinesOutput.setEnable(debug_init);
    
    // empty
	if (debug_init)
    	printf("empty\n");
	for (PatternIterator pit("xxxx"); pit.more(); pit.next())
    	addChain(pit.tl(), pit.tr(), pit.bl(), pit.br(), doubleLinesOutput);
	doubleLinesOutput.flush();

    // horizontal
	if (debug_init)
    	printf("\nhorizontal\n");
	for (PatternIterator pit1("xx  "); pit1.more(); pit1.next())
    	for (PatternIterator pit2("  xx"); pit2.more(); pit2.next())
        	if (pit1.j() != pit2.j())
            	addChain(pit1.tl(), pit1.tr(), pit2.bl(), pit2.br(), doubleLinesOutput);
	doubleLinesOutput.flush();

    // vertical
	if (debug_init)
    	printf("\nvertical\n");
	for (PatternIterator pit1("x x "); pit1.more(); pit1.next())
    	for (PatternIterator pit2(" x x"); pit2.more(); pit2.next())
        	if (pit1.i() != pit2.i())
            	addChain(pit1.tl(), pit2.tr(), pit1.bl(), pit2.br(), doubleLinesOutput);
	doubleLinesOutput.flush();

    // T
	if (debug_init)
    	printf("\nT\n");
	for (PatternIterator pit1("xx  "); pit1.more(); pit1.next())
    	for (PatternIterator pit2("  x "); pit2.more(); pit2.next())
        	for (PatternIterator pit3("   x"); pit3.more(); pit3.next())
            	if (pit2.i() != pit3.i())
                	addChain(pit1.tl(), pit1.tr(), pit2.bl(), pit3.br(), doubleLinesOutput);
	doubleLinesOutput.flush();

    // T rotated to the left
	if (debug_init)
    	printf("\nT rotated to the left\n");
	for (PatternIterator pit1("x x "); pit1.more(); pit1.next())
    	for (PatternIterator pit2(" x  "); pit2.more(); pit2.next())
        	for (PatternIterator pit3("   x"); pit3.more(); pit3.next())
            	if (pit2.j() != pit3.j())
                	addChain(pit1.tl(), pit2.tr(), pit1.bl(), pit3.br(), doubleLinesOutput);
	doubleLinesOutput.flush();

    // T rotated to the right
	if (debug_init)
    	printf("\nT rotated to the right\n");
	for (PatternIterator pit1("x   "); pit1.more(); pit1.next())
    	for (PatternIterator pit2(" x x"); pit2.more(); pit2.next())
        	for (PatternIterator pit3("  x "); pit3.more(); pit3.next())
            	if (pit1.j() != pit3.j())
                	addChain(pit1.tl(), pit2.tr(), pit3.bl(), pit2.br(), doubleLinesOutput);
	doubleLinesOutput.flush();

    // T upside-down
	if (debug_init)
    	printf("\nT upside-down\n");
	for (PatternIterator pit1("x   "); pit1.more(); pit1.next())
    	for (PatternIterator pit2(" x  "); pit2.more(); pit2.next())
        	for (PatternIterator pit3("  xx"); pit3.more(); pit3.next())
            	if (pit1.i() != pit2.i())
                	addChain(pit1.tl(), pit2.tr(), pit3.bl(), pit3.br(), doubleLinesOutput);
	doubleLinesOutput.flush();
	if (debug_init)
    	printf("\n-----\n\n");

            
    // Loop
	bool impossible = true;
	int n;
	for (n = 3; (impossible || n <= 5) && n < 14; n++)
    {
    	printf("Depth %d\n", n);

    	printf("Generate sequences\n");
        // Generate sequences extensions
    	for (Sequence* seqit = all_seq; seqit != 0; seqit = seqit->sibling) if (!seqit->impossible)
        {
        	class GenerateSequences
            {
        	public:
            	GenerateSequences(Sequence* first, int n_n) : n(n_n) { _seq[0] = first; }
            	void walk(Sequence *back, Sequence *front_siblings, int i)
                {
                	for (Sequence* next_front = front_siblings; next_front != 0; next_front = next_front->sibling) if (!next_front->impossible)
                    {
                    	_seq[i] = next_front;
                    	if (i < n-1)
                        {
                        	Sequence* next_back = getPossibleNext(next_front->c, back->next);
                        	if (next_back != 0)
                            	walk(next_back, next_front->next, i+1);
                        }
                    	else
                        {
                        	addNext(next_front->c, &back->next);                    
                        }
                    }
                }
        	private:
            	int n;
            	Sequence* _seq[20];
            };
        	GenerateSequences generateSequences(seqit, n);
        	generateSequences.walk(seqit, all_seq, 1);
        }

    	impossible = false;
    	for (bool go = true; go;)
        {
        	go = false;
        	printf("Loop\n");
            
            // Try all chain combination
        	for (Chain* chit = all_chains; chit != 0; chit = chit->sibling) if (!chit->impossible)
            {
            	Sequence* top = getPossibleNext(chit->t, all_seq);
            	if (top == 0) continue;
            	Sequence* bottom = getPossibleNext(chit->b, all_seq);
            	if (bottom == 0) continue;
                
            	class GenerateSequences
                {
            	public:
                	GenerateSequences(Chain* first, int n_n) : n(n_n) { _chains[0] = first; }
                	void walk(Chain *back, Chain *front_siblings, Sequence* top, Sequence* bottom, int i)
                    {
                    	for (Chain* next_front = front_siblings; next_front != 0; next_front = next_front->sibling) if (!next_front->impossible)
                        {
                        	_chains[i] = next_front;
                        	Chain* next_back = 0;
                        	if (i < n-1)
                            {
                            	next_back = getPossibleNext(next_front->t, next_front->b, back->next);
                            	if (next_back == 0) continue;
                            }
                        	Sequence* next_top = getPossibleNext(next_front->t, top->next);
                        	if (next_top == 0) continue;
                        	Sequence* next_bottom = getPossibleNext(next_front->b, bottom->next);
                        	if (next_bottom == 0) continue;
                        	if (i < n-1)
                            	walk(next_back, next_front->next, next_top, next_bottom, i+1);
                        	else
                            {
                            	next_front->front = true;
                            	back->back = true;
                            	if (!next_top->top)
                                	next_top->top = true;
                            	if (!next_bottom->bottom)
                                	next_bottom->bottom = true;
                            }
                        }
                    }
            	private:
                	int n;
                	Chain* _chains[20];
                };
            	GenerateSequences generateSequence(chit, n);
            	generateSequence.walk(chit, all_chains, top, bottom, 1);
            }
            
        	printf("Eliminate sequences\n");
            // Eliminate sequences
        	class EliminateSequences
            {
        	public:
            	EliminateSequences(int n_n, bool &n_go) : n(n_n), go(n_go) {}
            	void walk(Sequence *siblings, int i)
                {
                	for (Sequence *seq = siblings; seq != 0; seq = seq->sibling) if (!seq->impossible)
                    {
                    	_seq[i] = seq;
                    	if (i < n-1)
                        	walk(seq->next, i+1);
                    	else
                        {
                        	if (!seq->impossible && (!seq->top || !seq->bottom))
                            {
                            	seq->impossible = true;
                            	if (!seq->top)
                                {
                                	printf("ImpSeq %2d: ", n);
                                	for (int j = 0; j < n; j++)
                                    {
                                    	if (j > 0 && leftcode[_seq[j]->c])
                                        	printf("-");
                                    	printf("%d", depthcode[_seq[j]->c]);
                                    }
                                	printf("\n");
                                }
                            	go = true;
                            }
                        	seq->top = false;
                        	seq->bottom = false;
                        }
                    }
                }
        	private:
            	int n;
            	bool &go;
            	Sequence* _seq[20];
            };
        	EliminateSequences eliminateSequence(n, go);
        	eliminateSequence.walk( all_seq, 0 );
            
        	printf("Eliminate chains\n");
            // Eliminate chains
        	class EliminateChains
            {
        	public:
            	EliminateChains(int n_n, bool &n_go) : n(n_n), go(n_go) {}
            	void walk(Chain *siblings, int i)
                {
                	for (Chain *chain = siblings; chain != 0; chain = chain->sibling) if (!chain->impossible)
                    {
                    	_chains[i] = chain;
                    	if (i < n-2)
                        	walk(chain->next, i+1);
                    	else
                        {
                        	if (!chain->impossible && (!chain->front || !chain->back))
                            {
                            	printf("Impossible: ");
                            	for (int j = 0; j < n-1; j++) printf("%c", _chains[j]->t);
                            	printf("\n            ");
                            	for (int j = 0; j < n-1; j++) printf("%c", _chains[j]->b);
                            	printf("\n\n");
                            	chain->impossible = true;
                            	go = true;
                            }
                        	chain->front = false;
                        	chain->back = false;
                        }
                    }
                }
        	private:
            	int n;
            	bool &go;
            	Chain* _chains[20];
            };
        	EliminateChains eliminateChains(n, go);
        	eliminateChains.walk( all_chains, 0 );
            
        	if (go)
            	impossible = true;
        }

    	printf("Generate chains\n");
        // Generate chains
    	for (Chain* chit = all_chains; chit != 0; chit = chit->sibling) if (!chit->impossible)
        {
        	Sequence* top = getPossibleNext(chit->t, all_seq);
        	if (top == 0) continue;
        	Sequence* bottom = getPossibleNext(chit->b, all_seq);
        	if (bottom == 0) continue;
            
        	class GenerateChains
            {
        	public:
            	GenerateChains(Chain* first, int n_n) : n(n_n) { _chains[0] = first; }
            	void walk(Chain *back, Chain *front_siblings, Sequence* top, Sequence* bottom, int i)
                {
                	for (Chain* next_front = front_siblings; next_front != 0; next_front = next_front->sibling) if (!next_front->impossible)
                    {
                    	Chain* next_back = 0;
                    	if (i < n-1)
                        {
                        	next_back = getPossibleNext(next_front->t, next_front->b, back->next);
                        	if (next_back == 0) continue;
                        }
                    	Sequence* next_top = getPossibleNext(next_front->t, top->next);
                    	if (next_top == 0) continue;
                    	Sequence* next_bottom = getPossibleNext(next_front->b, bottom->next);
                    	if (next_bottom == 0) continue;
                    	_chains[i] = next_front;
                    	if (i < n-1)
                        	walk(next_back, next_front->next, next_top, next_bottom, i+1);
                    	else
                        	addNext(next_front->t, next_front->b, &back->next);
                    }
                }
        	private:
            	int n;
            	Chain* _chains[20];
            };
        	GenerateChains generateChains(chit, n);
        	generateChains.walk(chit, all_chains, top, bottom, 1);
        }
    	printf("Continue\n");
    }
	printf("Done at %d with %s\n", n, impossible ? "impossible" : "no impossible");

}