update

1 files changed, 244 insertions, 0 deletions

diff --git a/semestr-6/jfizo/rozwy/gen.cpp b/semestr-6/jfizo/rozwy/gen.cpp
new file mode 100644
index 0000000..a6a2988
--- /dev/null
+++ b/semestr-6/jfizo/rozwy/gen.cpp
@@ -0,0 +1,244 @@
+#include <iostream>
+#include <vector>
+#include <assert.h>
+#include <unordered_map>
+#include <string>
+#include <algorithm>
+
+using namespace std;
+
+typedef vector<int> transitions;
+typedef vector<int> word;
+
+struct Automaton {
+    int states;
+    vector<int> accept;
+    vector<transitions> delta;
+    int initial;
+
+    Automaton(int in, int n, const vector<transitions> &d, const vector<int> &acc) {
+        assert(in < n);
+        assert(d.size() == n);
+        
+        accept = acc;
+        delta.resize(n);
+        for (int i = 0; i < d.size(); i++) {
+            delta[i] = transitions(d[i]);
+        }
+        in = initial;
+        states = n;
+    }
+
+    int apply(const word &w, int beg) {
+        int crawl = beg;
+        for (auto c: w) {
+            crawl = delta[crawl][c];
+        }
+        return crawl;
+    }
+
+    bool check(const word &s) {
+        int q = apply(s, initial);
+        for (auto i: accept) {
+            if (q == i)
+                return true;
+        }
+        return false;
+    }
+
+    void dump() {
+        cout << "States: " << states << "; accepting: ";
+        for (auto i: accept) cout << i << " ";
+        cout << "\n";
+        cout << "Transition table:\n";
+        for (int i = 0; i < states; i++) {
+            cout << i << ":";
+            for (int j = 0; j < delta[i].size(); j++) {
+                cout << "\t--" << (char)(j + 'a') << "--> " << delta[i][j] << "\n";
+            }
+        }
+    }
+};
+
+void fill_accepts(int mask, int states, vector<int> &acc) {
+    acc.clear();
+    for (int i = 0; i < states; i++) {
+        if (mask & (1<<i))
+            acc.push_back(1);
+        else  
+            acc.push_back(0);
+    }
+}
+
+bool nextperm(int states, transitions &t, int alph_sz) {
+    for (int s = 0; s < alph_sz; s++) {
+        t[s]++;
+        if (t[s] == states) {
+            t[s] = 0;
+        }
+        else {
+            return true;
+        }
+    }
+    return false;
+}
+
+void reset_transition(transitions &t, int alph_sz) {
+    for (int s = 0; s < alph_sz; s++) {
+        t[s] = 0;
+    }
+}
+
+bool next_word(word &w, int alph_sz) {
+    for (int i = 0; i < w.size(); i++) {
+        w[i]++;
+        if (w[i] == alph_sz) {
+            w[i] = 0;
+        } else return true;
+    }
+    return false;
+}
+
+vector<word> generate_words(int max_len, int alph_sz) {
+    vector<word> result;
+    for (int len = 0; len <= max_len; len++) {
+        word w;
+        for (int i = 0; i < len; i++) w.push_back(0);
+        do {
+            result.push_back(w);
+        } while (next_word(w, alph_sz));
+    }
+    return result;
+}
+
+void get_transitions(Automaton &aut, word &w, vector<int> &res) {
+    res.clear();
+    for (int i = 0; i < aut.states; i++) {
+        res.push_back(aut.apply(w, i));
+    }
+}
+
+int my_power(int a, int b) {
+    if (b == 0) return 1;
+    return a * my_power(a, b-1);
+}
+
+bool check_automaton(vector<word> &words, Automaton &aut) {
+    vector<vector<int>> funcs;
+    for (auto w: words) {
+        vector<int> trans;
+        get_transitions(aut, w, trans);
+        funcs.push_back(trans);            
+    }
+    sort(funcs.begin(), funcs.end());
+    auto it = unique(funcs.begin(), funcs.end());
+    funcs.erase(it, funcs.end());
+
+    cout << funcs.size() << "\n";
+    if (funcs.size() == my_power(aut.states, aut.states)) {
+        cout << "mamy to!!\n";
+        aut.dump();
+        return true;
+    }
+    return false;
+}
+
+vector<Automaton> generate_automatons(int states, int alph_sz, vector<word> &words) {   
+    vector<Automaton> result;
+    vector<transitions> delta;
+    vector<int> accepts;
+
+    for (int i = 0; i < states; i++) {
+        delta.push_back(transitions());
+        for (int s = 0; s < alph_sz; s++) {
+            delta[i].push_back(0);
+        }
+    }
+
+    /* loop over accepting states */
+    // for (int i = 0; i < (1<<states); i++) {
+    //     if (i == 0) continue;
+    fill_accepts(1, states, accepts);
+    
+    /* loop over possible transitions */
+    bool last = false;
+    while (!last) {
+        Automaton a(0, states, delta, accepts);
+        if (check_automaton(words, a)) {
+            return result;
+        }
+        // result.push_back(a);
+        last = true;
+        for (int i = 0; i < states; i++) {
+            if (nextperm(states, delta[i], alph_sz)) {
+                last = false;
+                break;
+            }
+            else {
+                reset_transition(delta[i], alph_sz);
+            }
+        }   
+    }
+    // }
+
+    return result;
+}
+
+Automaton automaton_from_input() {
+    int states, alph_sz;
+    cin >> states >> alph_sz;
+    
+    vector<int> accept;
+    vector<transitions> delta;
+    int initial;
+
+    fill_accepts(1, states, accept);
+
+    initial = 0;
+    for (int i = 0; i < states; i++) {
+        cout << i << ":";
+        delta.push_back(transitions());
+        for (int j = 0; j < alph_sz; j++) {
+            int x;
+            cout << "\t--" << (char)(j + 'a') << "--> ? ";
+            cin >> x;
+            delta[i].push_back(x);
+        }
+    }
+
+    return Automaton(0, states, delta, accept);
+}
+
+int main(int argc, char *argv[]) {
+    if (argc != 4) {
+        fprintf(stderr, "Usage: %s states alph_sz word_sz\n", argv[0]);
+        return -1;
+    }
+
+    int states = atoi(argv[1]);
+    int alph_sz = atoi(argv[2]);
+    int word_sz = atoi(argv[3]);
+
+
+    // vector<Automaton> automatons = generate_automatons(states, alph_sz);
+
+    // for (auto a: automatons) {
+    //     a.dump();
+    //     cout << "\n";
+    // }
+
+    fprintf(stderr, "Generating words...\n");
+    vector<word> words = generate_words(word_sz, alph_sz);
+
+    // for (auto w: words) {
+    //     for (auto c: w) {
+    //         cout << (char)(c + 'a');
+    //     }
+    //     cout << "\n";
+    // }
+    // fprintf(stderr, "Generating %d automatons...\n", my_power(alph_sz, alph_sz * states));
+    // generate_automatons(states, alph_sz, words);
+
+    Automaton aut = automaton_from_input();
+    check_automaton(words, aut);
+}