using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace RegexNegativePatternsForString
{
	internal class Program
	{
		public static void Main()
		{
			int maxLengthNGWord = 5;
			foreach (var nChar in Enumerable.Range(1, maxLengthNGWord))
			{
				string ngWord = new string(Enumerable.Range(0, nChar).Select(it => Convert.ToChar('a' + it)).ToArray());
				string pattern = string.Format("^{0}$", RegexPatternGenerator.GenerateNegativePattern(ngWord));
				Regex regex = new Regex(pattern);
				TestNeg(regex, ngWord);
			}
		}

		private static void TestNeg(Regex regex, string ngWord)
		{
			Console.WriteLine("==================== NG-word: {0} ====================", ngWord);

			var alphabets = Enumerable.Range(0, ngWord.Length + 1).Select(it => Convert.ToChar('a' + it));
			StringBuilder sb = new StringBuilder();
			int nCases = 0;

			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets))
			{
				sb.Clear();
				sb.Append(item.Item1);
				sb.Append(item.Item2);

				string input = sb.ToString();
				TestNeg(input, regex, ngWord);
				nCases++;
			}
			Console.WriteLine("---------- any 2-length word: {0} cases", nCases);

			nCases = 0;
			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets))
			{
				sb.Clear();
				sb.Append(item.Item1);
				sb.Append(item.Item2);
				sb.Append(item.Item3);

				string input = sb.ToString();
				TestNeg(input, regex, ngWord);
				nCases++;
			}
			Console.WriteLine("---------- any 3-length word: {0} cases", nCases);

			nCases = 0;
			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets, alphabets))
			{
				sb.Clear();
				sb.Append(item.Item1);
				sb.Append(item.Item2);
				sb.Append(item.Item3);
				sb.Append(item.Item4);

				string input = sb.ToString();
				TestNeg(input, regex, ngWord);
				nCases++;
			}
			Console.WriteLine("---------- any 4-length word: {0} cases", nCases);

			nCases = 0;
			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets, alphabets, alphabets))
			{
				sb.Clear();
				sb.Append(item.Item1);
				sb.Append(item.Item2);
				sb.Append(item.Item3);
				sb.Append(item.Item4);
				sb.Append(item.Item5);

				string input = sb.ToString();
				TestNeg(input, regex, ngWord);
				nCases++;
			}
			Console.WriteLine("---------- any 5-length word: {0} cases", nCases);

			nCases = 0;
			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets, alphabets, alphabets, alphabets))
			{
				sb.Clear();
				sb.Append(item.Item1);
				sb.Append(item.Item2);
				sb.Append(item.Item3);
				sb.Append(item.Item4);
				sb.Append(item.Item5);
				sb.Append(item.Item6);

				string input = sb.ToString();
				TestNeg(input, regex, ngWord);
				nCases++;
			}
			Console.WriteLine("---------- any 6-length word: {0} cases", nCases);
		}

		private static void TestNeg(string input, Regex regex, string ng)
		{
			bool actual = regex.IsMatch(input);
			bool expected = !input.Contains(ng);

			if (actual != expected)
			{
				string strActual = "was " + (actual ? "accepted" : "not accepted");
				string strExpected = expected ? "does not contain" : "contains";
				string errMsg = string.Format("Assertion failure! '{0}' {1} but it {2} '{3}'. input: {4}, regex: {5}, NG-word: {6}", input, strActual, strExpected, ng, input, regex.ToString(), ng);
				throw new Exception(errMsg);
			}
		}
	}

	internal static class RegexPatternGenerator
	{
		public static string GenerateNegativePattern(string ngWord)
		{
			if (string.IsNullOrEmpty(ngWord))
			{
				throw new Exception();
			}

			string head = ngWord[0].ToString();
			if (ngWord.Length == 1)
			{
				return string.Format("[^{0}]*", head);
			}

			string part1 = Part1(ngWord);
			string part2 = Part2(ngWord);
			string part3 = Part3(ngWord);
			string part4 = Part4(ngWord);
			return string.Format("([^{0}]|{0}({1})*({2}))*(({3}){4})?", head, part1, part2, part3, part4);
		}

		private static string Part1(string ngWord)
		{
			if (ngWord.Length < 2)
			{
				throw new Exception();
			}

			char head = ngWord[0];
			string result = head.ToString();
			for (int i = ngWord.Length - 1; 2 <= i; i--)
			{
				result = string.Format("{0}|{1}({2})", head, ngWord[i - 1], result);
			}
			return result;
		}

		private static string Part2(string ngWord)
		{
			if (ngWord.Length < 2)
			{
				throw new Exception();
			}

			char head = ngWord[0];
			string result = string.Format("[^{0}{1}]", head, ngWord[ngWord.Length - 1]);
			for (int i = ngWord.Length - 1; 2 <= i; i--)
			{
				result = string.Format("[^{0}{1}]|{1}({2})", head, ngWord[i - 1], result);
			}
			return result;
		}

		private static string Part3(string ngWord)
		{
			if (ngWord.Length < 2)
			{
				throw new Exception();
			}
			else if (ngWord.Length == 1)
			{
				return string.Empty;
			}

			char head = ngWord[0];
			string part1 = Part1(ngWord);
			if (ngWord.Length == 2)
			{
				return string.Format("{0}*", part1);
			}
			else
			{
				return string.Format("{0}({1})*", head, part1);
			}
		}

		private static string Part4(string ngWord)
		{
			if (ngWord.Length < 2)
			{
				throw new Exception();
			}
			else if (ngWord.Length == 2)
			{
				return string.Empty;
			}

			string result = string.Format("({0})?", ngWord[ngWord.Length - 2]);
			for (int i = ngWord.Length - 1; 3 <= i; i--)
			{
				result = string.Format("({0}{1})?", ngWord[i - 2], result);
			}
			return result;
		}
	}

	internal static class DirectProductEnumerator
	{
		public static IEnumerable<Tuple<T1, T2>> DP<T1, T2>(IEnumerable<T1> set1, IEnumerable<T2> set2)
		{
			foreach (var item1 in set1)
			{
				foreach (var item2 in set2)
				{
					yield return Tuple.Create(item1, item2);
				}
			}
		}

		public static IEnumerable<Tuple<T1, T2, T3>> DP<T1, T2, T3>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3)
		{
			foreach (var item1 in set1)
			{
				foreach (var item2 in set2)
				{
					foreach (var item3 in set3)
					{
						yield return Tuple.Create(item1, item2, item3);
					}
				}
			}
		}

		public static IEnumerable<Tuple<T1, T2, T3, T4>> DP<T1, T2, T3, T4>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3, IEnumerable<T4> set4)
		{
			foreach (var item1 in set1)
			{
				foreach (var item2 in set2)
				{
					foreach (var item3 in set3)
					{
						foreach (var item4 in set4)
						{
							yield return Tuple.Create(item1, item2, item3, item4);
						}
					}
				}
			}
		}

		public static IEnumerable<Tuple<T1, T2, T3, T4, T5>> DP<T1, T2, T3, T4, T5>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3, IEnumerable<T4> set4, IEnumerable<T5> set5)
		{
			foreach (var item1 in set1)
			{
				foreach (var item2 in set2)
				{
					foreach (var item3 in set3)
					{
						foreach (var item4 in set4)
						{
							foreach (var item5 in set5)
							{
								yield return Tuple.Create(item1, item2, item3, item4, item5);
							}
						}
					}
				}
			}
		}

		public static IEnumerable<Tuple<T1, T2, T3, T4, T5, T6>> DP<T1, T2, T3, T4, T5, T6>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3, IEnumerable<T4> set4, IEnumerable<T5> set5, IEnumerable<T6> set6)
		{
			foreach (var item1 in set1)
			{
				foreach (var item2 in set2)
				{
					foreach (var item3 in set3)
					{
						foreach (var item4 in set4)
						{
							foreach (var item5 in set5)
							{
								foreach (var item6 in set6)
								{
									yield return Tuple.Create(item1, item2, item3, item4, item5, item6);
								}
							}
						}
					}
				}
			}
		}
	}
}