#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <ctime>
#include <vector>
#include <fstream>

#define MAX_LEGTH 10

using namespace std;

set<string> brute_words;
set<string> optimal_words;

size_t bruteforce(char* input);
size_t optimal(char* input);

int main() {
  srand(time(nullptr));

  size_t counter = 0;
  size_t bad_counter = 0;
  char name_buffer[32];
  char* word = (char*)malloc(MAX_LEGTH + 1);

  char new_char[2];
  new_char[1] = '\0';

  while(bad_counter < 1) {
    word[0] = '\0';

    int length = 3 + rand() % (MAX_LEGTH - 2);
    for(int i = 0; i < length; ++i) {
      new_char[0] = 'a' + rand() % 26;
      strcat(word, new_char);
    }

    size_t brute_result = bruteforce(word);
    size_t optimal_result = optimal(word);

    if(brute_words == optimal_words) {
      cout << "Test: " << counter << '\t' << brute_words.size() << " == " << optimal_words.size() << endl;
    } else {
      cout << "Test: " << counter << '\t' << brute_words.size() << " != " << optimal_words.size() << endl;
      sprintf(name_buffer, "%zu.txt", counter);
      fstream file(name_buffer, ios::out);
      file << word;
      file.close();
      bad_counter++;

      auto brute_it = brute_words.cbegin();
      auto optimal_it = optimal_words.cbegin();

      while(brute_it != brute_words.cend()) {
        cout << *brute_it << endl;
        cout << *optimal_it << endl;

        ++brute_it;
        ++optimal_it;
      }
    }

    counter++;
  }

  free(word);
  return 0;
}

size_t bruteforce(char* input) {
  size_t input_size = strlen(input);

  brute_words.clear();

  // zmienne do tymczasowego przechowania usuwanych znaków
  char i_char;
  char k_char;

  for(size_t i = 0; i < input_size-1; ++i) {
    i_char = input[i];
    input[i] = '\0';

    for(size_t k = i + 1; k < input_size; ++k) {
      k_char = input[k];
      input[k] = '\0';

      // allokacja pamięci na kopię pozbawioną usuwanych znaków
      char* copy = (char*)malloc(input_size);
      snprintf(copy, input_size, "%s%s%s", input, &input[i+1], &input[k+1]);
      brute_words.insert(copy);
      free(copy);

      input[k] = k_char;
    }

    input[i] = i_char;
  }

  return brute_words.size();
}

size_t optimal(char* input) {
  size_t input_size = strlen(input);
  size_t sum = 0;
  char before_window = '\0'; // znak przed pierwszym usuwanym znakiem
  char overwrite_char; // tymczasowe przechowanie pierwszego z usuwanych znaków

  optimal_words.clear();

  for(size_t i = 1; i < input_size; ++i) {
    if (before_window != input[i]) {
      ++sum;
      overwrite_char = input[i-1];
      input[i-1] = '\0';

      char* copy = (char*)malloc(input_size);
      snprintf(copy, input_size, "%s%s\n", input, &input[i+1]);
      optimal_words.insert(copy);
      free(copy);

      input[i-1] = overwrite_char;
    }

    before_window = input[i-1];
  }

  // zmienne do tymczasowego przechowania usuwanych znaków
  char i_char;
  char k_char;

  for(size_t i = 2; i < input_size; ++i) {
    if(input[i] == input[i-1])
      continue;

    i_char = input[i];
    input[i] = '\0';

    for(size_t k = 0; k < i-1; ++k) {
      if(input[k] != input[k+1]) {
        ++sum;
        k_char = input[k];
        input[k] = '\0';

        char* copy = (char*)malloc(input_size);
        snprintf(copy, input_size, "%s%s%s\n", input, &input[k+1], &input[i+1]);
        optimal_words.insert(copy);
        free(copy);

        input[k] = k_char;
      }
    }
    input[i] = i_char;
  }

  return sum;
}