#include <iostream>
#include <string>
#include <vector>
#include <assert.h>
#include <fstream>
#include <unordered_map>
#include <unordered_set>

using namespace std;

string ToUpper(string s) {
  for(int i = 0; i < s.length(); i++) {
    s[i] = toupper(s[i]);
  }

  return s;
}
// ----------------------------------------------------

typedef unordered_set<string> StringSet;

// returns true if string 's' exists in set already.
bool ExistsInSet(const StringSet &set, const string &s) {
  auto it = set.find(s);
  return it != set.end();
}

void AddToSet(StringSet &set, const string &s) {
  assert(!ExistsInSet(set, s));
  set.insert(s);
}

// ----------------------------------------------------
// -Point
struct Point {
  Point() {}
  Point(int r, int c) : row(r), col(c) {}

  friend ostream& operator<<(ostream& os, const Point& p);
  
  int row = 0;
  int col = 0;
};

ostream &operator<<(ostream& os, const Point &p) {
  os << "(" << p.row << ", " << p.col << ")";
  return os;
}


// ----------------------------------------------------
// -Span
struct Span {
  Span(Point p, int l, bool v) : point(p), len(l), vert(v) {}

  Point GetPoint(int i) const {
    assert(i >= 0 && i < len);

    if(vert) {
      return Point(point.row + i, point.col);
    } else {
      return Point(point.row, point.col + i);
    }
  }
  
  friend ostream& operator<<(ostream& os, const Span& s);
  
  Point point;
  int len;
  bool vert;
};

typedef vector<Span> Spans;

ostream &operator<<(ostream& os, const Span &s) {
  cout << "[" << s.point << " len =" << s.len << " vert=" << s.vert << "]";
  return os;
}


// ----------------------------------------------------
// -Word
struct Word {
  // need to use map with Word as value
  Word() {} 
  
  Word(string s) : word(s) {}
  int len() const { return word.length(); }
  
  string word;
};

typedef vector<Word*> Words;
typedef unordered_map<string, Words> WordMap;

// ----------------------------------------------------
// -Library
class Library {
public:
  Library() {}

  ~Library() {
    for(Word* w: words_) {
      delete w;
    }
  }

  // returns NULL if can't find any matches to the given pattern
  const Words* FindWord(const string& s) const {
    auto it = word_map_.find(s);
    if(it != word_map_.end()) {
      return &it->second;
    } else {
      return NULL;
    }
  }

  bool IsWord(string s) const {
    auto it = word_map_.find(s);

    if(it == word_map_.end()) {
      return false;
    } else {
      return true;
    }
  }
  
  void ComputeStats() {
    assert(counts_.empty()); // make sure its first call
    counts_.resize(18);

    for(const Word* s: words_) {
      int len = s->word.length();

      if(len < 18) {
	counts_[len]++;
      }
    }
  }

  void PrintStats() const {
    cout << "There are the counts_ of each word length\n";
    for (int i = 1; i < counts_.size(); i++) {
      cout << "[" << i << "] " << counts_[i] << "\n";
    }
  }

  string GetWord(int i) const {
    assert(i >= 0 && i < words_.size());
    return words_[i]->word;
  }

  void CreatePatternHash(Word* w) {
    int len = w->len();
    
    // compute 2^len
    int num_patterns = 1 << len; 

    // cout << "PATTERN HASH on " << w->word << "\n";
    for(int i = 0; i < num_patterns; i++) {
      // cout << " " << i << "\n";
      string temp = w->word;
      for (int j = 0; j < len; j++) {
	// check if the j-th bit of i is 1
	if((i >> j) & 1) {
	  temp[j] = '-';
	}
      }

      // cout << "   " << temp << "\n";
      word_map_[temp].push_back(w);
    }
  }
  
  void ReadFromFile(string filename, int max_size) {
    ifstream f;
    string line;
    
    f.open(filename);
    while (f.is_open() && !f.eof()) {
      getline(f, line);
      
      if(!line.empty()) {
	line = ToUpper(line);

	// trim /r if present
	if(line.find("\r") != string::npos) {
	  line.erase(line.size() - 1);
	}
	
	if(line.length() <= max_size) {
	  Word *w = new Word(line);
	  words_.push_back(w);
	  CreatePatternHash(w);
	}
      }
    }
  
    cout << "Read " << words_.size() << " words_ from file '"
	 << filename << "'\n";
  }

  void DebugBuckets() const {
    for (int i = 0; i < word_map_.bucket_count(); i++) {
      cout << "[" << i << "] " << word_map_.bucket_size(i) << "\n";
    }
  }
  
private:
  // master vector of words
  Words words_;
  
  // patternhash ("D--" returns vector of all DAD,
  // DUD, ...)
  WordMap word_map_;
  
  vector<int> counts_;
};

Library lib; // global variable

// ----------------------------------------------------
// -Attr
// Attributes of a slot
struct Attr {
  bool is_empty() const {return has_blanks && !has_letters;}
  bool is_partial() const {return has_blanks && has_letters;}
  bool is_full() const {return !has_blanks && has_letters;}
  
  bool has_letters = false;
  bool has_blanks = false;
};

// ----------------------------------------------------
// -Grid
struct Grid {
  
  Grid(string n) {
    name = n;
  }
  
  int rows() const { return lines.size(); }
  int cols() const {
    if(lines.empty()) {
      return 0;
    } else {
      return lines[0].size();
    }
  }

  int max_size() const { return max(rows(), cols()); }

  // returns character value of the box at point 'p', where 'p' is
  // assumed to be in bounds.
  char box(const Point& p) const {
    assert(in_bounds(p));
    return lines[p.row][p.col];
  }

  void write_box(const Point& p, char c) {
    assert(in_bounds(p));
    lines[p.row][p.col] = c;
  }
  
  // Returns true if the point p is a '.' "block" in the grid, where
  // 'p' is assumed to be in bounds.
  bool is_block(const Point& p) const {
    return box(p) == '.';
  }

  bool is_blank(const Point& p) const {
    return box(p) == '-';
  }
  
  bool is_letter(const Point& p) const {
    char c = box(p);
    return c>= 'A' && c <= 'Z';
  }

  bool in_bounds(const Point& p) const {
    return p.row >= 0 && p.row < rows() && p.col >= 0 && p.col < cols();
  }

  // returns the string specified in a span on the grid.
  // fills in attributes of the string
  string GetString(const Span& s, Attr& attr) const {
    int len = s.len;
    string temp;
    temp.resize(len);
    
    for(int i = 0; i < len; i++) {
      Point p = s.GetPoint(i);
      char c = box(p);

      if(c >= 'A' && c <= 'Z') {
	attr.has_letters = true;
      } else if(c == '-') {
	attr.has_blanks = true;
      }
      
      temp[i] = box(p);
    }

    return temp;
  }

  void WriteString(const Span& span, const string& t) {
    int len = span.len;
    assert(t.length() == len);
    
    for(int i = 0; i < len; i++) {
      Point p = span.GetPoint(i);
      write_box(p, t[i]);
    }
  }

  // Increment the point across the grid one box at a time. It returns
  // true if point is still in bounds
  bool Next(Point& p, bool vert) const {

    if(vert) {
      // increment vertically
      p.row += 1;

      // do we have to move to the next column?
      if(p.row >= rows()) {
	p.row = 0;
	p.col += 1;
      }
      
    } else {
      // increment horizontally
      p.col += 1;

      // do we have to move to the next row?
      if(p.col >= cols()) {
	p.col = 0;
	p.row++;
      }
    }

    return in_bounds(p);
  }

  void FillSpans(bool vert) {
    Point p;

    while(in_bounds(p)){

      while(in_bounds(p) && is_block(p)) {
	Next(p, vert);
      }

      if (!in_bounds(p)) return;

      // cout << "SPAN START: " << p << "\n";
      
      Point startp = p;
      int startpRow = p.row;
      int startpCol = p.col;
      int len = 0;
      
      do {
	Next(p, vert);
	len++;
      } while (in_bounds(p) && !is_block(p) &&
               !((vert && startpCol != p.col) || (!vert && startpRow != p.row)));


      // cout << "END OF SPAN!! len=" << len << "\n";

      spans.push_back(Span(startp, len, vert));
    }
  }

  //  Add to 'span's vector with all viable spans in the grid.
  void FillSpans() {
    assert(spans.empty());
    FillSpans(false); // horiz
    FillSpans(true);  // vert
  }
  
  void LoadFromFile(string filename) {
    ifstream f;
    string line;
    
    f.open(filename);
    while (f.is_open() && !f.eof()) {
      // strips LF symbol but leave CR if reading a windows file
      getline(f, line);
      // cout << line << "    (" << line.length() << ")\n";

      if(!line.empty() && line.find("#") == string::npos) {
	lines.push_back(line);
      }
    }
  }

  // check that each row has the same number of columsn
  void Check() const {
    for (string s : lines) {
      assert(s.size() == cols());
    }
  }
  
  void Print() {
    cout << "Grid: " << name 
	 << " (rows=" << rows()
	 << ", cols=" << cols() << " )\n";

    for (string s: lines) {
      cout << "  " << s << "\n";
    }
  }

  void PrintSpans() {
    cout << "Spans:\n";
    for(const Span& s: spans) {
      Attr attr;
      cout << "  " << s << " " << GetString(s, attr) << "\n";
    }
  }

  string name;
  vector<string> lines;
  Spans spans;
};

// ----------------------------------------------------
// -Slot

struct Slot {
  Slot(Span s, string p) : span(s), pattern(p) {}

  friend ostream& operator<<(ostream& os, const Slot& s);
  
  Span span;
  string pattern;
};

ostream &operator<<(ostream& os, const Slot &s) {
  os << s.span << " '" << s.pattern << "'";
  return os;
}


typedef vector<Slot> Slots;

// ----------------------------------------------------
// -Solver
class Solver {
public:
  Solver() { }

  void Solve(const Grid& grid) {
    cout << "Solving this grid:\n";
    Loop(grid, 0);
  }
  

private:
  void Loop(Grid grid, int depth) {
    depth++;

    Slots empty_slots;
    Slots partial_slots; // these are the ones we want to work on
    Slots full_slots;
    
    for (const Span& s : grid.spans) {
      Attr attr;
      string temp = grid.GetString(s, attr);

      // correctly classify the type of span
      if(attr.is_empty()) {
	empty_slots.push_back(Slot(s, temp));
      } else if(attr.is_partial()) {
	partial_slots.push_back(Slot(s, temp));
      } else if(attr.is_full()) {
	full_slots.push_back(Slot(s, temp));
      }      
    }

    int num_empty = empty_slots.size();
    int num_partials = partial_slots.size();

    // check that all words inserted so far are valid
    for(const Slot& s : full_slots) {
      if(!lib.IsWord(s.pattern)) {
	// word is not valid, abort
	return;
      }
    }

    // check that all words so far are unique
    StringSet set;
    for(const Slot& s : full_slots) {
      if(!ExistsInSet(set, s.pattern)) {
	AddToSet(set, s.pattern);
      } else {
	// found duplicate
	return;
      }
    }

    // check if a solution was found
    if(num_partials == 0 && num_empty == 0) {
      cout << "SOLUTION!!\n";
      grid.Print();
      return;
    }

    // choose next slot to work on
    const Slot& slot = num_partials > 0 ? partial_slots[0] : empty_slots[0];
    const Words* words = lib.FindWord(slot.pattern);

    if(words) {
      // for each possible word that matches the pattern
      for (const Word* w: *words) {
	// -- commit the new word, and
	grid.WriteString(slot.span, w->word);
	// -- solve recursively remaining grid
	Loop(grid, depth);
      }      
    }
  }

};

// ----------------------------------------------------
int main() {
  Grid grid("MY GRID");
  grid.LoadFromFile("../data/crossword_1");
  grid.Check();
  grid.FillSpans();

  // remember lib is defined in the global scope
  lib.ReadFromFile("../data/top_12000.txt", grid.max_size());
  
  Solver solver;
  solver.Solve(grid);

  return 0;
}