aboutsummaryrefslogtreecommitdiff
path: root/semestr-6/jfizo/rozwy
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2022-03-08 12:18:08 +0100
committerFranciszek Malinka <franciszek.malinka@gmail.com>2022-03-08 12:18:08 +0100
commitacc4c160401cc7bb1fc3a7db407bdfd3be3d3a49 (patch)
treef9641ab9a62a0e58655f395d8ec541f62db8f59f /semestr-6/jfizo/rozwy
parent143547a8e219c10541c70c779c10411a345e01f1 (diff)
update
Diffstat (limited to 'semestr-6/jfizo/rozwy')
-rw-r--r--semestr-6/jfizo/rozwy/gen.cpp244
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);
+}