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

#define TESTING_EXECUTE_CNBF 1

class bignum
{
public:
	bignum()
	{
		for (int i = 0; i < _size; i++)
			_v[i] = 0;
		_overflow = false;
	}
	bignum& operator=(long i)
	{
		_v[0] = i;
		for (int i = 1; i < _size; i++)
			_v[i] = 0;
		_overflow = false;
		return *this;
	}
	bool isZero()
	{
		if (_v[0] != 0 || _overflow)
			return false;
		for (int i = 1; i < _size; i++)
			if (_v[i] != 0)
				return false;
		return true;
	}
	void inc()
	{
		if (_overflow)
			return;
		_v[0]++;
		if (_v[0] < _max)
			return;
		_v[0] -= _max;
		_overflow = true;
		for (int i = 1; i < _size; i++)
		{
			_v[i]++;
			if (_v[i] < _max)
			{
				_overflow = false;
				break;
			}
			_v[i] -= _max;
		}
	}
	void dec()
	{
		if (_overflow)
			return;
		if (_v[0] > 0)
		{
			_v[0]--;
			return;
		}
		_v[0] = _max-1;
		for (int i = 1; i < _size; i++)
		{
			if (_v[i] > 0)
			{
				_v[i]--;
				return;
			}
			_v[i] = _max-1;
		}
	}
	bignum& operator+=(const bignum& rhs)
	{
		if (_overflow || rhs._overflow)
		{
			_overflow = true;
			return *this;
		}
		
		for (int i = 0; i < _size; i++)
		{
			_v[i] += rhs._v[i];
			if (_overflow)
			{
				_v[i]++;
				_overflow = false;
			}
			if (_v[i] > _max)
			{
				_v[i] -= _max;
				_overflow = true;
			}
		}
			
		return *this;
	}
	bool operator<(unsigned long l)
	{
		if (_overflow || _v[0] >= l)
			return false;
		for (int i = 1; i < _size; i++)
		{
			if (_v[i] != 0)
				return false;
		}
		return true;
	}
	bool operator>(unsigned long l)
	{
		if (_overflow || _v[0] > l)
			return true;
		for (int i = 1; i < _size; i++)
		{
			if (_v[i] != 0)
				return true;
		}
		return false;
	}
	bool operator<(const bignum& rhs)
	{
		for (int i = _size-1; i >= 0; i--)
			if (_v[i] < rhs._v[i])
				return true;
			else if (_v[i] > rhs._v[i])
				return false;
		return false;
	}
	bool operator!=(unsigned long l)
	{
		if (_overflow || _v[0] != l)
			return false;
		for (int i = 1; i < _size; i++)
		{
			if (_v[i] != 0)
				return false;
		}
		return true;
	}
	unsigned long longValue() { return _v[0]; }
	bool overflow() { return _overflow; }
	void setOverflow() { _overflow = true; }
	const char* toString()
	{
		if (_overflow)
			return "overflow";
		static char buffer[_size * 20];
			
		int l = 0;
		for (int i = 0; i < _size; i++)
			if (_v[i] != 0)
				l = i;
		sprintf(buffer, "%ld", _v[l]);
		while (l > 0)
		{
			l--;
			sprintf(buffer + strlen(buffer), "%06ld", _v[l]);
		}
		return buffer;	
	}
	
private:
    static const unsigned long _max = 1000000;
	static const int _size = 1000;
	unsigned long _v[_size];
	bool _overflow;
};

#define SIZE  10000
int cnbf_l[SIZE+1];
char *cnbf_s[SIZE+1];
bignum min_lcnbf[100];
char *max_lcnbf_s[100];
bignum max_lcnbf[100];
#define STRCPY(D,S) D = (char*)malloc(sizeof(char)*(strlen(S)+1)); strcpy(D,S)

/****** execute CNBF program: start code ********/

#define MEM_SIZE 30

#define EXE_OKAY    0
#define EXE_NEG     1
#define EXE_MEM     2
#define EXE_ILL_CLOSE    3
#define EXE_ILL_OPEN     4 
#define EXE_NOT_AT_FIRST  5
#define EXE_NOT_ALL_ZERO  6
#define EXE_OVERFLOW 7
#define EXE_ILL_CHAR  8

char *explain_execute_cnbf_status(int s)
{
  switch(s)
  { case EXE_OKAY: return "Okay";
    case EXE_NEG: return "Negative number";
    case EXE_MEM: return "Illegale memory access";
    case EXE_ILL_CLOSE: return "] without matching [";
    case EXE_ILL_OPEN: return "[ without matching ]";
    case EXE_NOT_AT_FIRST: return "pointer not at first memory location";
    case EXE_NOT_ALL_ZERO: return "not all except first memory location are zero";
    case EXE_OVERFLOW: return "overflow";
    case EXE_ILL_CHAR: return "illegal character";
    default: return "??";
  }
}    	

int nr_transfers_used;

int execute_cnbf(char *cnbf, bignum *result)
{
 bignum a[MEM_SIZE];
 int p;
 char *open_br[MEM_SIZE];
 char nr_open_br = 0;

 nr_transfers_used = 0;

 for (p = 0; p < MEM_SIZE; p++)
    a[p] = 0;

 p = 0;

 while (*cnbf != '\0')
   switch(*cnbf)
   {
     case '+':
       if (a[p].overflow())
         return EXE_OVERFLOW;
       a[p].inc();
       cnbf++;
       break;
     case '-':
       if (a[p].isZero())
         return EXE_NEG;
       a[p].dec();
       cnbf++;
       break;
     case '<':
       if (p == 0)
         return EXE_MEM;
       p--;
       cnbf++;
       break;
     case '>':
       if (p+1 == MEM_SIZE)
         return EXE_MEM;
       p++;
       cnbf++;
       break;
     case ']':
       if (nr_open_br == 0)
         return EXE_ILL_CLOSE;
       if (a[p].isZero())
       {
         nr_open_br--;
         cnbf++;
       }  
       else
         cnbf = open_br[nr_open_br-1];
       break;
     case '[':
       if (a[p].isZero())
       {
          int skip_br = 1;
          while (skip_br)
          {
            cnbf++;
            if (*cnbf == '\0')
              return EXE_ILL_OPEN;
            else if (*cnbf == '[')
              skip_br++;
            else if (*cnbf == ']')
              skip_br--;
          }
          cnbf++;
       }
       else
       { 
         int is_transfer = 1;
         char *s;
         int pos = 0;
         int nr_dec = 0;
         
         for (s = cnbf + 1; *s != ']' && is_transfer; s++)
           switch(*s)
           {
             case '+':
               if (pos == 0)
                 is_transfer = 0;
               break;
             case '-':
               if (pos != 0)
                 is_transfer = 0;
               else
                 nr_dec++;
               break;
             case '<':
               pos--;
               break;
             case '>':
               pos++;
               break;
             default:
               is_transfer = 0;
               break;
           }
         if (*s == ']' && is_transfer && nr_dec == 1 && pos == 0)
         {
           bignum v = a[p];
           a[p] = 0;
           for (cnbf++; cnbf < s; cnbf++)
             switch(*cnbf)
             {
               case '+':
                 a[p] += v;
                 if (a[p].overflow())
         		   return EXE_OVERFLOW;
         		 break;
         	   case '>':
         	     p++;
         	     break;
         	   case '<':
         	     p--;
         	     break;
         	   default:
         	     break;
             }
           cnbf++;
           nr_transfers_used++;
         }
         else
         {
           cnbf++;
           open_br[nr_open_br++] = cnbf;
         }
       }
       break;
	 default:
       return EXE_ILL_CHAR;
   }
 *result = a[0];
 if (nr_open_br > 0)
   return EXE_ILL_OPEN;
 if (p != 0)
   return EXE_NOT_AT_FIRST;  
 for (p = 1; p < MEM_SIZE; p++)
   if (!a[p].isZero())
     return EXE_NOT_ALL_ZERO;
 return EXE_OKAY;
}

/****** execute CNBF program: start unit test ********/


void test_a_execute_cnbf(FILE *f, char *test,
                         char *cnbf, int exp_status, unsigned long exp_result)
{
#if TESTING_EXECUTE_CNBF == 1	
  int status;
  bignum result;
  status = execute_cnbf(cnbf, &result);
  if (status != exp_status || result != exp_result)
  {
     fprintf(f, "test '%s' failed: ", test);
     if (status != exp_status)
       fprintf(f, "Returned status '%s', expect '%s'", 
               explain_execute_cnbf_status(status), 
               explain_execute_cnbf_status(exp_status));
     else
       fprintf(f, "Result returned is %s, expect %ld", result.toString(), exp_result);
     fprintf(f, "\n");
  }
#endif  
}

void test_execute_cnbf(FILE *f)
{
  test_a_execute_cnbf(f, "empty program", "", EXE_OKAY, 0);
  test_a_execute_cnbf(f, "illegale character", "a", EXE_ILL_CHAR, 0);
  test_a_execute_cnbf(f, "memory -1", "<", EXE_MEM, 0);
  test_a_execute_cnbf(f, "negative number", "-", EXE_NEG, 0);
  test_a_execute_cnbf(f, "memory exceed", ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>", EXE_MEM, 0);
  test_a_execute_cnbf(f, "one", "+", EXE_OKAY, 1);
  test_a_execute_cnbf(f, "three", "+++", EXE_OKAY, 3);
  test_a_execute_cnbf(f, "min", "++--", EXE_OKAY, 0);
  test_a_execute_cnbf(f, "ill close", "]", EXE_ILL_CLOSE, 0);
  test_a_execute_cnbf(f, "ill open skip", "[", EXE_ILL_OPEN, 0);
  test_a_execute_cnbf(f, "ill open enter", "+[-", EXE_ILL_OPEN, 0);
  test_a_execute_cnbf(f, "pointer not at first", "+++>", EXE_NOT_AT_FIRST, 3);
  test_a_execute_cnbf(f, "not all non zero", ">++<", EXE_NOT_ALL_ZERO, 0);
  test_a_execute_cnbf(f, "all", ">++++[<+++>-]<", EXE_OKAY, 12);
  //test_a_execute_cnbf(f, "overflow", "+[+]", EXE_OVERFLOW, 0);
}

/****** execute CNBF program: end ********/


int min_length(char *pattern)
{
  int result = 0;
  for (; *pattern != '\0'; pattern++)
    if (*pattern != 'n' && *pattern != 'p')
      result++;
  return result;
 }

char *expand(char *pattern, int *v)
{
  static char expanded[200];
  char *p = expanded;

  for (; *pattern != '\0'; pattern++)
    /*if (*pattern == 'A')
    {
      char = cnbf_s[*v++];
    }*/
    if (*pattern == 'n' || *pattern == 'p')
    {
       int i = *v++;
       for (; i < 0; i++)
         *p++ = '-';
       for (; i > 0; i--)
         *p++ = '+';
    }
    else
      *p++ = *pattern;
  *p = '\0';
  return expanded;
}

void find_expansions(char *pattern, char *p, int *v, int d, int extra)
{
  while (*p != '\0' && *p != 'n' && *p != 'p')
    p++;

  if (*p == '\0')
  {
    if (extra == 0)
    {	  
      char *expanded = expand(pattern, v);
      bignum value;
      int status = execute_cnbf(expanded, &value);

      if (status == EXE_OKAY)
      { int l = strlen(expanded);
        if (value > (SIZE-1))
          printf(" %s = %s (%d)\n", expanded, value.toString(), nr_transfers_used);
        else 
        { 
          if (cnbf_l[value.longValue()] > l)
          {
	        cnbf_l[value.longValue()] = l; 
		    STRCPY(cnbf_s[value.longValue()], expanded);
	        printf(" %s = %s (%d)\n", expanded, value.toString(), nr_transfers_used);
          }
	      /*else
	        printf(" %s = %lf\n", expanded, value);*/
		}
	    
		if (min_lcnbf[l].isZero() || value < min_lcnbf[l])
          min_lcnbf[l] = value;
		if (max_lcnbf[l] < value)
        {
		  max_lcnbf[l] = value;
		  STRCPY(max_lcnbf_s[l], expanded);
        }
	  }
	  else if (status == EXE_OVERFLOW)
	  {
	    int l = strlen(expanded);
        printf(" %s = overflow (%d)\n", expanded, nr_transfers_used);
	    max_lcnbf[l].setOverflow();
        STRCPY(max_lcnbf_s[l], expanded);
	  }  
      else
        printf(" %s : %s\n", expanded, explain_execute_cnbf_status(status));
	}    
  }
  else if (*p == 'p')
  { int i;

    for (i = 0; i <= extra; i++)
    {
      v[d] = i;
      find_expansions(pattern, p+1, v, d+1, extra - i);
    }
  }
  else
  { int i;

    for (i = 0; i <= extra; i++)
    {
      v[d] = i;
      find_expansions(pattern, p+1, v, d+1, extra - i);

      v[d] = -i;
      if (i > 0)
        find_expansions(pattern, p+1, v, d+1, extra - i);
    }
  }
}

void try_pattern(char *pattern, int len)
{
  int extra;
  int v[20];

  printf("%s %d\n", pattern, len);
  extra = len - min_length(pattern);

  if (extra > 0)
    find_expansions(pattern, pattern, v, 0, extra);

}


void try_patterns(int n)
{
  try_pattern("p", n);
  try_pattern(">++p[<++p>-]<", n);
  try_pattern("++p[>++p<-]>p[<++p>-]<", n);
  try_pattern(">>++p[<++p<+p>>-]<p[<++p>-]<", n);
  try_pattern(">++p[<++p>-]<p[>++p<-]>p[<++p>-]<", n);
  try_pattern("p>>++p[<p<p[>+p<-]p>p[<+p>-]>-]<<", n);
  try_pattern(">+>+>+p<[>[-<[->>+p<<]>>[-<<+p>>]<]<<]>[-<+>]<", n);
  try_pattern(">+>+>+>+p<[>[-<[->>+p<<]>>[-<<+p>>]<]<<]>[-<+>]<", n);
  try_pattern(">>+>>+>>+>+<[->[<<+[->+p<]>[-<+p>]>-]<<<]>[-<+>]<",n);
  try_pattern(">>>+p[-<p<p<p[->p>+p<<]>>[-<<p[->+p<]>[-<+p>]>]>]<<<",n);

  { FILE *f = fopen("results.txt", "w");
    int i;

	for (i = 0; i < SIZE; i++)
      if (cnbf_s[i] != NULL)
	    fprintf(f, "%d: %s  (%d)\n", i, cnbf_s[i], cnbf_l[i]);
    fclose(f);
  }

  { FILE *f = fopen("lcnbf.txt", "w");
    int i;

	for (i = 0; i < 100; i++)
      if (max_lcnbf[i].overflow())
        fprintf(f, "%d  %s = overflow\n", i, max_lcnbf_s[i]);
	  else if (!max_lcnbf[i].isZero())
        fprintf(f, "%d  %s = %s\n", i, max_lcnbf_s[i], max_lcnbf[i].toString());
	for (i = 0; i < 100; i++)
	  if (!min_lcnbf[i].isZero())
        fprintf(f, "min_lcnbf[%d] = %s\n", i, min_lcnbf[i].toString());

	fclose(f);
  }
  { FILE *f = fopen("lcnbf.html", "w");
    int i;
    char *s;
        fprintf(f, "<TABLE BORDER=\"1\" CELLPADDING=\"3\">\n");
        fprintf(f, "<TR><TD>length</TD><TD>program</TD><TD>result</TD></TR>");
	for (i = 0; i < 100; i++)
	  if (!max_lcnbf[i].isZero())
      {
        fprintf(f, "<TR><TD> %d </TD><TD> <TT>", i);
        for (s = max_lcnbf_s[i]; *s != '\0'; s++)
          if (*s == '<') fprintf(f, "&lt;");
          else if (*s == '>') fprintf(f, "&gt;");
          else fprintf(f, "%c", *s);
        fprintf(f, "</TT> </TD><TD> %s </TD></TR>\n", max_lcnbf[i].toString());
	  }
        fprintf(f, "</TABLE>\n");

	fclose(f);
  }
}  
	
	
       

/**********************************/

int main(int argc, char* argv[])
{
  int i;
  int n;	
  test_execute_cnbf(stderr);

  for (i = 0; i < SIZE; i++)
  { 
	cnbf_l[i] = 200;
	cnbf_s[i] = NULL;
  }
  for (i = 0; i < 100; i++)
  {
	min_lcnbf[i] = 0;
	max_lcnbf[i] = 0;
	max_lcnbf_s[i] = "";
  }
  for (n = 46; n < 50; n++)
    try_patterns(n);


  return 0;
}