[HaBo]

// bruteforce.cpp --> iterative and recursive bruteforce algorithm

// ---------------------- (C) HACKSE 2006 ----------------------

#include <iostream>

using namespace std;

//***************************** GLOBAL MEMBERS ******************************//

const char SPACE = char(32);
const unsigned short MAX_LEN=30; // max. len. of bstring
char bstring[MAX_LEN];           // bruteforce string
unsigned short len=0;            // current length ob bstring
unsigned int recdepths=0;	 // depths of recursive algorithm

//****************************** PROTOTYPES *********************************//

// getting next bruteforce-ascii-symbol
char next(char);

// initialization for <bruteforce()>
void init();

// appends ascii-symbol to bstring and inc. len by 1
bool append();

// recursive calculation of next bruteforce string (causes STACK OVERFLOW !!!)
void bruteforce_recu(unsigned short i=(len-1));

// iterative version of bruteforce algorithm
void bruteforce_iter();

// sets whole bstring to next permutation (for <bruteforce_iter)
bool next_permutation();

//**************************** MAIN-FUNCTION ********************************//

int main (int argc, char *argv[]) {
  init();
  cout<<" *** BRUTEFORCE *** (c) Hackse 2006"<<endl;
  cout<<" **********************************"<<endl<<endl;
  char reply=0;
  do {
    cout<<"(i)terative or (r)ecursive?: "; 
    cin>>reply;
  } while (reply != 'i' && reply !='r');  
  if (reply=='i'){
    cout<<"Starting iterative version of bruteforce ..."<<endl;
    sleep(2);
    bruteforce_iter();
  } else {
      cout<<"Starting recursive version of bruteforce until ";
      cout<<"STACK-OVERFLOW! ..."<<endl;
      sleep(2);
      bruteforce_recu();
  }
  return 0;
};

//********************* FUNCTION IMPLEMENTATION *****************************//

char next(char s){
  switch (s) { 
    case SPACE :   return 'a';   break;
    case 'z'   :   return 'A';   break;
    case 'Z'   :   return '0';   break;
    case '9'   :   return SPACE; break;
    default    :   return  1+s;
  }
}

void init(){  
  for (int i=0; i<MAX_LEN; i++)
    (i==0)?bstring[i]=SPACE:bstring[i]=0;
  len=1;  
  recdepths=0;
};

bool append(){
  if (len>=MAX_LEN) 
    return false;
  bstring[len]=SPACE;
  len++;
  return true;
};

void bruteforce_recu(unsigned short i){
  cout<<bstring<<" --> recursion depths: " <<++recdepths<<endl;
  bstring[i]=next(bstring[i]);         // calc. next bstring
  if (bstring[i] == SPACE){            // carry?
    if (i==0) {                        // first pos.?
      append();                        // append element to bstring
      bruteforce_recu(len-1);          // recursive call on last index
   }
   else
        bruteforce_recu(i-1);          // recursive call on "prev." index
  }
  else
        bruteforce_recu(len-1);        // recursive call on last index
  recdepths--;
};

bool next_permutation(){  
  for (int i=len-1; i>=0; i--){
    bstring[i]=next(bstring[i]);       // set next bstring 
    if (bstring[i]!=SPACE)             // check for carry 
      return true;                     // exit if no carry
    else
      if (i==0)                        // on first char ...  
        if (append())                  // try to append char on carry-event
	  return true;                 // appending char was successful
	else
	  return false;                // length of bstring exceeds MAX_LEN
  }
}

void bruteforce_iter(){
  do  
    cout<<bstring<<endl;
  while (next_permutation());
}