crossword maker

crossword.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <unordered_set>

using std::cin;
using std::ifstream;
using std::cout;
using std::vector;
using std::string;
using std::endl;
using std::unordered_set;

#define HORIZONTAL 1
#define VERTICAL -1

int depth = -1;

// Thoughts:
// - Get words needs to be better 
// - Use trie?
// - change which slot is looked at when
// - look at related slots next
// - constraint solving?
// - multi-threading
// - backtracking more than one layer
// - run get_words on all 

unordered_set<string> not_words;

typedef struct {
    int start_col;
    int start_row;
    int direction;
    int length;
} slot_t;

void read_dic(string filepath, unordered_set<string> &dic) {

    string line;
    ifstream myfile (filepath);

    if (myfile.is_open()) {
        while (myfile.good()) {
            getline (myfile, line);
            dic.insert(line);

        }
        myfile.close();
    }

    else cout << "Unable to open file";
}

void fill_grid(string filepath, vector<vector<string>> &grid) {
    int m;
    vector<string> col;
    string str;
    ifstream myfile (filepath);

    if (myfile.is_open()) {
        myfile >> m;
        for(int j = 0; j < m; j++) {
            for(int i = 0; i < m ; i++) {
                myfile >> str;
                col.push_back(str);
            }
            grid.push_back(col);
            col.clear();
        }
    }

}

void print_grid(vector<vector<string> > grid) {
    for(int i = 0; i < grid.size() ; i++) {
        for(int j = 0; j < grid.size() ; j++) {
            cout << grid[i][j] << "";
        }
        cout << endl;
    }
}

string get_str(vector<vector<string>> grid, slot_t* slot) {
    string word = "";
    if(slot->direction == HORIZONTAL) {
        for(int i = 0; i < slot->length; i++)
            word += grid[slot->start_row][i + slot->start_col];
    }

    if(slot->direction == VERTICAL) {
        for(int i = 0; i < slot->length; i++)
            word += grid[slot->start_row + i][slot->start_col];
    }
    return word;
}

bool empty_unit(vector< vector<string> > grid, slot_t* slot) {
    return(get_str(grid, slot).find('_') != string::npos);
}

vector<slot_t*> find_slots(vector<vector<string>> grid) {
    vector<slot_t*> slots;
    slot_t* slot;

    int n = grid.size();

    for(int row = 0; row < n; row++) {

        for ( int col = 0; col < n ; col++) {

            if (grid[row][col] != "*") {
                if(row == 0 || grid[row-1][col] == "*"){
                    //Vertical search for slots
                    for (int word_row = row ; word_row < n; word_row++) {
                        if ((grid [word_row][col] == "*" ) || word_row == n - 1) {
                            int word_len = word_row - row + 1;
                            if (grid[word_row][col] == "*" )
                                word_len = word_row - row;

                            if ( word_len > 1) {
                                slot = new slot_t;
                                slot->start_row = row;
                                slot->start_col = col;
                                slot->direction = VERTICAL;
                                slot->length = word_len;
                                slots.push_back(slot);
                                cout << "Slot >> " << slot->start_row << " " << slot->start_col << " " << slot->direction << " " << slot->length << endl;
                            }
                            break;
                        }
                    }
                }

                if(col == 0 || grid[row][col-1] == "*"){
                    //Horizontal search for slots
                    for (int word_col = col ; word_col < n; word_col++) {
                        if (grid [row][word_col] == "*" || word_col == n - 1) {
                            int word_len = word_col - col + 1;
                            if (grid[row][word_col] == "*" )
                                word_len = word_col - col;

                            if (word_len > 1 ) {
                                slot = new slot_t;
                                slot->start_row = row;
                                slot->start_col = col;
                                slot->direction = HORIZONTAL;
                                slot->length = word_len;
                                slots.push_back(slot);
                                cout << "Slot >> " << slot->start_row << " " << slot->start_col << " " << slot->direction << " " << slot->length << endl;
                            }
                            break;
                        }
                    }
                }
            }
        }
    }
    //std::random_shuffle(slots.begin(), slots.end());
    return slots;
}

vector<string> get_words(unordered_set<string> dic, string s) {
    vector<string> list;
    bool flag;

    for (const auto &elem : dic) {
        if ( elem.size() == s.size()) {
            flag = true;
            for(int j = 0; j < s.size(); j++ ) {
                if (s[j] != '_' && s[j] != elem[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                list.push_back(elem);
            }
        }
    }
    return list;
}

bool only_one_blank_str(string s) {
    return (std::count(s.begin(), s.end(), '_') == 1);
}

bool find_dic(string s, unordered_set<string> dic) {
    if(not_words.find(s) != not_words.end()){
        return false;
    }
    if(dic.find(s) != dic.end()){
        return true;
    } else {
        not_words.insert(s);
        return false;
    }
}

bool check_existence(int curr_row, int curr_col, int direction, vector<vector<string> > grid, char s, unordered_set<string> dic) {
    string word;
    string pre;
    word.push_back(s);
    if(direction == VERTICAL) {
        for( int i = curr_row - 1; i >= 0; i--) {
            if(grid[i][curr_col][0] != '*')
                pre.push_back(grid[i][curr_col][0]);
            else
                break;
        }
        for( int i = curr_row + 1; i < grid.size(); i++ ) {
            if(grid[i][curr_col][0] != '*')
                word.push_back(grid[i][curr_col][0]);
            else
                break;
        }
    }
    if(direction == HORIZONTAL) {
        for( int i = curr_col - 1; i >= 0; i--) {
            if(grid[curr_row][i][0] != '*')
                pre.push_back(grid[curr_row][i][0]);
            else
                break;
        }
        for( int i = curr_col + 1; i < grid.size(); i++ ) {
            if(grid[curr_row][i][0] != '*')
                word.push_back(grid[curr_row][i][0]);
            else
                break;

        }

    }
    reverse(pre.begin(), pre.end());
    word = pre + word;
    if(word.find('_') != std::string::npos){
#ifdef REASON
        cout << "Bad possible word: " << word << endl;
#endif
        return !!(get_words(dic, word).size());
    }
    if(find_dic(word, dic)) {
#ifdef REASON
        cout << "Good Word: " << word << endl;
#endif
        return true;
    }
#ifdef REASON
    cout << "Bad Word: " << word << endl;
#endif
    return false;


}

int enter_in_grid(string s, slot_t* slot, vector<vector<string>>  &grid, unordered_set<string> dic) {
    string prev_str;
    bool undo = false;
    if(slot->direction == HORIZONTAL) {
        for(int i = 0; i < slot->length; i++) {
            prev_str.push_back(grid[slot->start_row][i + slot->start_col][0]);
            grid[slot->start_row][i + slot->start_col] = s[i];
        }
        for(int i = 0; i < slot->length; i++) {
            if( ! check_existence(slot->start_row, slot->start_col + i, VERTICAL, grid, s[i], dic)) {
                undo = true;
#ifdef REASON
                cout << "Reason: Bad crossword (Vertical)" << endl;
#endif
                break;
            }
        }
        if(undo) {
            for(int i = 0; i < slot->length; i++) {
                grid[slot->start_row][i + slot->start_col] = prev_str[i];
            }
            return 0;
        }
    }

    if(slot->direction == VERTICAL) {
        for(int i = 0; i < slot->length; i++) {
            prev_str.push_back(grid[slot->start_row + i][slot->start_col][0]);
            grid[slot->start_row + i][slot->start_col] = s[i];
        }
        for(int i = 0; i < slot->length; i++) {
            if( ! check_existence(slot->start_row + i, slot->start_col, HORIZONTAL, grid, s[i], dic)) {
                undo = true;
#ifdef REASON
                cout << "Reason: Bad crossword (Horizontal)" << endl;
#endif
                break;
            }
        }
        if(undo) {
            for(int i = 0; i < slot->length; i++) {
                grid[i + slot->start_row][slot->start_col] = prev_str[i];
            }
            return 0;
        }
    }

    return 1;
}


void find_solution(vector<vector<string>> grid, unordered_set<string> dic, vector<slot_t*> slots) {
    depth++;
    slot_t* slot = slots[depth];
    cout << "D: " << depth << endl;

    if(slots.size() == 0){
        print_grid(grid);
        cout << "Completed!" << endl;
        exit(1) ;
    }

    cout << "Slot >> " << slot->start_row << " " << slot->start_col << " " << slot->direction << " " << slot->length << endl;

    string word = get_str(grid, slot);
    vector<string> list_words;

    list_words = get_words(dic, word);

    //Prints all the words
#ifdef LIST
    cout << "Word >> " << word << endl;
    cout << "List of words for " << word << endl;
    for( int i = 0 ; i < list_words.size(); i++) {
        cout << i + 1 << " " << list_words[i] << endl;
    }
#endif


    while ( !list_words.empty() ) {
#ifdef CURR
        cout << "CURRENT_WORD for " << word << ": " << list_words.back() << endl;
#endif

        int result = enter_in_grid (list_words.back(), slot, grid, dic);
#ifdef DEBUG
            print_grid(grid);
#endif      
        list_words.pop_back();
        if(!result) {
            continue;
        }
        
        find_solution(grid, dic, slots);
    }
    depth--;
    return;


}

int main(int argc, char* argv[]) {

    unordered_set<string> dic;
    vector <vector <string> > grid;
    vector<slot_t*> slots;

    read_dic(argv[1], dic);
    fill_grid(argv[2], grid);
    slots = find_slots(grid);

    find_solution(grid, dic, slots);

    return 0;
}

test

9
_ _ _ _ * * * * *
_ _ _ _ * _ _ _ _
_ _ _ _ * _ _ _ _
_ _ _ * _ _ _ _ _
* * _ _ _ _ _ * *
_ _ _ _ _ * _ _ _
_ _ _ _ * _ _ _ _
_ _ _ _ * _ _ _ _
* * * * * _ _ _ _