worstle/main.cpp at main · Pknakamura/worstle · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <thread>

using namespace std;

const string char_order = "esaoriltnudpmychgbkfwvzjxq";
const int num_threads = 16;
mutex get_handler;
mutex put_handler;
int next_init = 0;

unsigned int encode_string(string word){
    unsigned int val = 0;
    for (char l : word){
        val = val | (1u << char_order.find(l));
    }
    return val;
}

void CartesianRecurse(vector<vector<string>> &accum, vector<string> stack,
    vector<vector<string>> sequences, int index)
{
    vector<string> sequence = sequences[index];
    for (string i : sequence)
    {
        stack.push_back(i);
        if (index == sequences.size() - 1)
            accum.push_back(stack);
        else
            CartesianRecurse(accum, stack, sequences, index + 1);
        stack.pop_back();
    }
}
vector<vector<string>> CartesianProduct(vector<vector<string>> sequences)
{
    vector<vector<string>> accum;
    vector<string> stack;
    if (sequences.size() > 0)
        CartesianRecurse(accum, stack, sequences, 0);
    return accum;
}


void dfs_search(vector<unsigned int> &current,
                vector<unsigned int> candidates,
                int target_len,
                unsigned int restrict,
                map<unsigned int, vector<string>> &words,
                map<unsigned int, vector<string>> &answers,
                fstream &output){
    if(target_len == 0){
        vector<vector<string>> decoded;
        decoded.push_back(answers[current[0]]);
        for (size_t i = 1; i < current.size(); i++){
            decoded.push_back(words[current[i]]);
        }
        vector<vector<string>> permuted = CartesianProduct(decoded);
        for (vector<string> sol : permuted){
            put_handler.lock();
                for (string w : sol){
                    output << w << "; ";
                }
                output << endl;
            put_handler.unlock();
        }

    } else {
        for(size_t i = 0; i < candidates.size(); i++){
            unsigned int word = candidates[i];
            unsigned int new_restrict = restrict | word;

            vector<unsigned int> new_candidates;
            for(size_t j = i + 1; j < candidates.size(); j++){
                if((new_restrict & candidates[j]) == 0){
                    new_candidates.push_back(candidates[j]);
                }
            }

            current.push_back(word);
            dfs_search(current, new_candidates, target_len - 1, new_restrict, words, answers, output);
            current.pop_back();
        }
    }
}

void threadfunc(vector<unsigned int> &inits,
                vector<unsigned int> &candidates,
                map<unsigned int, vector<string>> &words,
                map<unsigned int, vector<string>> &answers,
                fstream &output){
    get_handler.lock();
    while(next_init < inits.size()){
        unsigned int init = inits[next_init++];
        cout << "Checking initial word " << next_init << "/" << inits.size() << endl;
        get_handler.unlock();

        vector<unsigned int> initial{init};
        vector<unsigned int> new_candidates;
        for(size_t j = 0; j < candidates.size(); j++){
            if((init & candidates[j]) == 0){
                new_candidates.push_back(candidates[j]);
            }
        }
        dfs_search(initial, new_candidates, 6, init, words, answers, output);

        get_handler.lock();
    }
    get_handler.unlock();
}

int main(){
    string temp_string;

    fstream ansfs("wordle-answers.txt", fstream::in);
    map<unsigned int, vector<string>> answers;
    vector<unsigned int> initials;
    while(getline(ansfs, temp_string)){
        unsigned int encoding = encode_string(temp_string);
        answers[encoding].push_back(temp_string);
        initials.push_back(encoding);
    }
    ansfs.close();
    sort(initials.begin(),initials.end());
    initials.erase(unique(initials.begin(), initials.end()), initials.end());

    fstream wordfs("wordle-words.txt", fstream::in);
    map<unsigned int, vector<string>> words;
    vector<unsigned int> candidates;
    while(getline(wordfs, temp_string)){
        unsigned int encoding = encode_string(temp_string);
        words[encoding].push_back(temp_string);
        candidates.push_back(encoding);
    }
    wordfs.close();
    sort(candidates.begin(),candidates.end());
    candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());

    vector<thread> threads;
    fstream output("solution.txt", fstream::out | fstream::trunc);
    for(size_t i = 0; i < num_threads; i++){
        threads.emplace_back(threadfunc, ref(initials), ref(candidates), ref(words), ref(answers), ref(output));
    }

    for(size_t i = 0; i < num_threads; i++){
        threads[i].join();
    }
}