#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <map>
#include <utility>

#include <cctype>
#include <cmath>
#include <ctime>

int word_mask (const std::string& word) {
  int mask = 0;
  
  for (size_t i=0; i<word.size(); i++) {
    const int c = tolower(word[i]);
    if (c < 'a' || c > 'z') return 0;
    const int m = 1 << (c - 'a');
    if (m & mask) return 0;
    mask |= m;
  }
  
  return mask;
}

typedef std::map <int, std::vector<std::string> > wordmap_t;

void search (int mask, std::vector<int>& words, const wordmap_t& wmap, std::vector<std::vector<int> >& all_others, size_t length, int minmask, int maxmask) {
  static long cycle = 0;
  
  if (++cycle == 500000) {
    cycle = 0;
    double start = log(double(minmask)), end = log(double(maxmask));
    std::cerr
      << std::fixed << std::setprecision(1) << std::setw(5)
      << (log(double(words[0])) - start) * 100. / (end - start) << "%";
    for (const int w : words) {
      std::cerr << ", " << wmap.find(w)->second.front();
    }
    std::cerr << std::endl;
  }
  
  std::vector<int>& others = all_others[length-1];
    
  if (length <= 1) {
    for (const int lastword : others) {
      words.push_back(lastword);
    
      const char* sep1 = "";
      for (const int w : words) {
        std::cout << sep1;
        sep1 = ", ";
        
        const char* sep2 = "";
        for (const std::string& option : wmap.find(w)->second) {
          std::cout << sep2 << option;
          sep2 = "/";
        }
      }
      std::cout << std::endl;
      
      words.pop_back();
    }
    return;
  }
  
  std::vector<int>& newothers = all_others[length-2];

  for (size_t i=0, N=others.size(); i<N; i++) {
    const int newword = others[i];
    const int newmask = mask | newword;
    
    newothers.clear();
    for (size_t j=i+1; j<N; j++) {
      const int word = others[j];
      if (!(newmask & word)) newothers.push_back(word);
    }
    
    if (newothers.size()) {
      words.push_back(newword);
      search (newmask, words, wmap, all_others, length - 1, minmask, maxmask);
      words.pop_back();
    }
  }
}

void search (const wordmap_t& wmap, size_t length) {
  std::vector<int> words;
  words.reserve(length);
  
  std::vector<std::vector<int> > all_others(length);
  std::vector<int>& others = all_others[length-1];
  int minmask = 1 << ('z'-'a'+1), maxmask = 0;
  
  for (const wordmap_t::value_type& p : wmap) {
    const int word = p.first;
    others.push_back(word);
    if (word < minmask) minmask = word;
    if (word > maxmask) maxmask = word;
  }
  
  search(0, words, wmap, all_others, length, minmask, maxmask);
}

int main (int argc, char** argv) {
  const char* filename = argc > 1 ? argv[1] : "words_alpha.txt";
  
  const size_t NLETTERS = 5, NWORDS = 5;
  
  clock_t start = clock();
  
  std::ifstream f(filename);
  wordmap_t wordmap;
  
  if (f) {
    std::string line;
    
    while (std::getline(f, line)) {
      if (line.size() != NLETTERS) continue;
      int mask = word_mask(line);
      if (mask) wordmap[mask].push_back(line);
    }
    
    f.close();
  }
  
  clock_t prep_end = clock();
  std::cerr << "Preparation: " << float(prep_end - start) / CLOCKS_PER_SEC << "s" << std::endl;
  
  std::cerr << "There are " << wordmap.size() << " unique words" << std::endl;
  
  search(wordmap, NWORDS);
  
  clock_t end = clock();
  std::cerr << std::setprecision(3);
  std::cerr << "Processing: " << float(end - prep_end) / CLOCKS_PER_SEC << "s" << std::endl;
  std::cerr << "Full time: " << float(end - start) / CLOCKS_PER_SEC << "s" << std::endl;
}