#define PROBLEM_VERSION_DIV1 1
#define PROBLEM_VERSION_DIV2 2
#define PROBLEM_VERSION PROBLEM_VERSION_DIV1
#define PROBLEM_NAME "forbidden-words"
#define TEST_STR "%03d"
#include "gentools.h"
#include <cassert>
#include <set>
#include <string>
#include <vector>

#ifdef WIN32
#define INT64 "%I64d"
#else
#define INT64 "%lld"
#endif

#ifdef DEBUG
#define eprintf(...) fprintf (stderr, __VA_ARGS__)
#else
#define eprintf(...) assert (true)
#endif

using namespace std;

int const MIN_N   =       1;
int const MAX_N   =  100000;
int const MAX_LEN = 3000000;
#if PROBLEM_VERSION == PROBLEM_VERSION_DIV1
int const LET = 26;
#else
int const LET = 10;
#endif

unsigned const C0 = 0x55555555u;
unsigned const C1 = 0x33333333u;
unsigned const C2 = 0x0F0F0F0Fu;
unsigned const C3 = 0x00FF00FFu;
unsigned const C4 = 0x0000FFFFu;

unsigned popcount (unsigned x)
{
	x = (x & C0) + ((x >>  1) & C0);
	x = (x & C1) + ((x >>  2) & C1);
	x = (x & C2) + ((x >>  4) & C2);
	x = (x & C3) + ((x >>  8) & C3);
	x = (x & C4) + ((x >> 16) & C4);
	return x;
}

set <string> c;
vector <string> s;


void do_nothing (void)
{
// do nothing
}

void open_test (void)
{
	c.clear ();
	s.clear ();
}

void close_test (void)
{
	do_nothing ();
}

void log_test (void)
{
	int n = (int) s.size ();
	fprintf (flog, "n = %d", n);
}

void shuffle_test (void)
{
	int n = (int) s.size ();
	rndshuffle (&s[0], &s[0] + n);
}

void verify_test (void)
{
	int n = (int) s.size ();
	assert (MIN_N <= n && n <= MAX_N);

	set <string> c;
	int len = 0;
	for (int i = 0; i < n; i++)
	{
		string & t = s[i];
	        int cur = (int) s[i].length ();
	        len += cur;
	        assert (len <= MAX_LEN);
	        for (int p = 0; p < cur; p++)
	        {
	        	assert ('a' <= t[p] && t[p] < 'a' + LET);
	        }
		assert (c.find (t) == c.end ());
		c.insert (t);
	} 
}

void output_test (void)
{
	FILE * fout;

	fout = fopen (cur_test_str, "wt");
	assert (fout != NULL);

	int n = (int) s.size ();
	fprintf (fout, "%d\n", n);
	for (int i = 0; i < n; i++)
	{
		fprintf (fout, "%s\n", s[i].c_str ());
	}
	
	fclose (fout);
}


void add_word (string t)
{
	int n = (int) s.size ();
	assert (n < MAX_N);
	if (c.find (t) != c.end ())
	{
		return;
//		printf ("%s\n", t.c_str ());
	}
//	assert (c.find (t) == c.end ());
	c.insert (t);
	s.push_back (t);
}

void add_set (int p, int len = 30)
{
	assert (p != 0);
	string x;
	for (int i = 0; i < LET; i++)
	{
		if (p & (1 << i))
		{
			x += char ('a' + i);
		}
	}
	string y;
	for (int i = (int) x.size (); i < len; i++)
	{
		y += x[rndvalue ((int) x.size ())];
	}
	y += x;
	if (shuffle_flag)
	{
		rndshuffle (&y[0], &y[0] + (int) y.length ());
	}
	add_word (y);
}

void add_random_word (int len = 30)
{
	int p = rndvalue (1, (1 << LET) - 1);
	add_set (p, len);
}

void add_random_word_and (int and_mask = (1 << LET) - 1, int len = 30)
{
	int p;
	do
	{
		p = rndvalue (1, (1 << LET) - 1);
		p &= and_mask;
	}
	while (p == 0);
	add_set (p, len);
}

void add_random_word_or (int or_mask = 0, int len = 30)
{
	int p = rndvalue (1, (1 << LET) - 1);
	p |= or_mask;
	add_set (p, len);
}


void gen_samples (void)
{
	shuffle_flag = false;

	START_TEST ("first example");
	add_word ("a");
	add_word ("ab");
	END_TEST ();

	START_TEST ("second example");
	add_word ("da");
	add_word ("dee");
	add_word ("ea");
	END_TEST ();
}

void gen_small (void)
{
	shuffle_flag = false;

	START_TEST ("hand test 1");
	add_word ("j");
	END_TEST ();

	START_TEST ("hand test 2");
	add_word ("a");
	add_word ("b");
	END_TEST ();

	START_TEST ("hand test 3");
	add_word ("f");
	add_word ("abcd");
	add_word ("abce");
	add_word ("abde");
	add_word ("acde");
	add_word ("bcde");
	END_TEST ();

	START_TEST ("hand test 4");
	add_word ("f");
	add_word ("e");
	add_word ("d");
	add_word ("cb");
	add_word ("ca");
	add_word ("ba");
	END_TEST ();

	START_TEST ("hand test 5");
	add_word ("f");
	add_word ("e");
	add_word ("d");
	add_word ("cb");
	add_word ("ca");
	add_word ("cba");
	END_TEST ();

	START_TEST ("hand test 6");
	add_word ("f");
	add_word ("e");
	add_word ("d");
	add_word ("cb");
	add_word ("bca");
	add_word ("ba");
	END_TEST ();

	START_TEST ("hand test 7");
	add_word ("f");
	add_word ("e");
	add_word ("d");
	add_word ("acb");
	add_word ("ca");
	add_word ("ba");
	END_TEST ();
	
	START_TEST ("hand test 8");
	add_word ("j");
	add_word ("jjj");
	add_word ("jj");
	add_word ("jjjj");
	add_word ("g");
	add_word ("gg");
	add_word ("ggg");
	add_word ("gggg");
	END_TEST ();

	for (int i = 1; i < LET; i++)
	{
		START_TEST ("stripe test %d", i);
		for (int j = 1; j <= i; j++)
		{
			add_word (string ("") + char ('a' + j - 1) +
			                        char ('a' + j));
		}
		END_TEST ();
	}
	
	for (int k = LET - 2; k <= LET; k++)
	{
	        for (int t = 0; t <= LET - k; t++)
	        {
			START_TEST ("cyclic stripe %d test %d", k, t + 1);
			for (int j = 1; j < k; j++)
			{
				add_word (string ("") + char ('a' + j - 1) +
				                        char ('a' + j));
			}
			add_word (string ("") + char ('a' + k - 1) +
			                        char ('a' + 0));
			for (int j = 1; j <= t; j++)
			{
				add_word (string ("") + char ('a' + LET - j));
			}
			END_TEST ();
		}
	}
	
#if PROBLEM_VERSION == PROBLEM_VERSION_DIV1
	START_TEST ("full hand test 1");
	add_word ("so");
	add_word ("too");
	add_word ("ts");
	END_TEST ();

	START_TEST ("full hand test 2");
	add_word ("aba");
	add_word ("ac");
	add_word ("dz");
	add_word ("xy");
	add_word ("agkhalbgegb");
	END_TEST ();
#endif
}

void gen_large (void)
{
	shuffle_flag = true;

	START_TEST ("maximal test 1");
	add_random_word_and (1, MAX_LEN);
	END_TEST ();

	for (int t = 0; t < 5; t++)
	{
		START_TEST ("random tiny front test %d", t + 1);
		for (int i = 5; i < LET; i++)
		{
			add_word (string ("") + char ('a' + i));
		}
		int num = rndvalue (2, 5);
		for (int i = 0; i < num; i++)
		{
			int len = rndvalue (25, 19990);
			add_random_word_and (31, len);
		}
		END_TEST ();

		START_TEST ("random tiny back test %d", t + 1);
		for (int i = 0; i < LET - 5; i++)
		{
			add_word (string ("") + char ('a' + i));
		}
		int num = rndvalue (3, 4);
		for (int i = 0; i < num; i++)
		{
			int len = rndvalue (25, 19990);
			add_random_word_and (31 << (LET - 5), len);
		}
		END_TEST ();
	}
	
	for (int t = 0; t < 5; t++)
	{
		START_TEST ("random test %d", t + 1);
		for (int i = 0; i < MAX_N; i++)
		{
			add_random_word (30);
		}
		END_TEST ();
	}

	for (int d = 1; d <= LET; d++)
	{
		if (5 < d && d < LET - 5)
		{
			continue;
		}

		START_TEST ("cover test %d", d);
		for (unsigned p = 0; p < (1 << LET); p++)
		{
			if ((int) popcount (p) == d)
			{
				add_set (p, 40);
			}
		}
		END_TEST ();
	}

	for (int t = 0; t < 5; t++)
	{
		START_TEST ("weighted random test %d", t + 1);
		for (int i = 0; i < MAX_N; i++)
		{
			unsigned q;
			do
			{
				q = rndvalue (1, (1 << LET) - 1);
			}
			while ((int) popcount (q) < 5);
			add_random_word_or (q, 30);
		}
		END_TEST ();
	}

	for (int b = 3; b <= 5; b++)
	{
		for (int t = 0; t < 5; t++)
		{
			int d = LET - 1 - rndvalue (2) * 2;
			START_TEST ("broken %d cover + random test %d",
			            b, t + 1);
			for (unsigned p = 0; p < (1 << LET); p++)
			{
				if ((int) popcount (p) == d)
				{
					add_set (p, 40);
				}
			}
			int n = (int) s.size ();
			n = n - b;
			while ((int) s.size () > n)
			{
				vector <string>::iterator it = s.begin ();
				it += rndvalue ((int) s.size ());
				c.erase (*it);
				s.erase (it);
			}
			for (int i = 0; i < 1000; i++)
			{
				unsigned q;
				do
				{
					q = rndvalue (1, (1 << LET) - 1);
				}
				while ((int) popcount (q) < LET - 21);
				add_set (q, 29);
			}
			END_TEST ();
		}
	}
}


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

	gen_samples ();

	gen_small ();

	gen_large ();

	exit_gen ();
	
	return 0;
}
