#include #include int value(int w, int h) { return w + 3*h - 4; } int inverse(int x) { return 3*(x%3) + x/3; } bool st[9][9][9][9]; int st3[9][9][9]; struct { int top; int left; int right; int bottom; } stc[9][9]; bool debug_init = true; class DoubleLinesOutput { public: DoubleLinesOutput() : col(0), enable(false) {} void setEnable(bool v) { enable = v; } void add(int i1, int i2, int i3, int i4) { if (!enable) return; line1[col] = ' '; line2[col] = ' '; col++; line1[col] = i1+'A'; line1[col+1] = i2+'A'; line2[col] = i3+'A'; line2[col+1] = i4+'A'; col += 2; if (col > 64) { line1[col] = '\0'; line2[col] = '\0'; printf("%s\n%s\n\n", line1, line2); col = 0; } } void flush() { if (!enable) return; if (col > 0) { line1[col] = '\0'; line2[col] = '\0'; printf("%s\n%s\n", line1, line2); col = 0; } printf("\n"); } private: bool enable; int col; char line1[100]; char line2[100]; }; void initialize_st(int i1, int i2, int i3, int i4, DoubleLinesOutput &doubleLinesOutput) { doubleLinesOutput.add(i1, i2, i3, i4); st[i1][i2][i3][i4] = true; stc[i1][i2].top++; stc[i1][i3].left++; stc[i2][i4].right++; stc[i3][i4].bottom++; } void remove_st(int i1, int i2, int i3, int i4) { if (st[i1][i2][i3][i4]) { st[i1][i2][i3][i4] = false; stc[i1][i2].top--; stc[i1][i3].left--; stc[i2][i4].right--; stc[i3][i4].bottom--; } } #define DEPTH 5 struct VariantTransition; struct Variant { Variant(char *_pattern, Variant *_next) : next(_next), from_trans(0), to_trans(0) { strcpy(pattern, _pattern); } ~Variant(); char pattern[DEPTH+1]; VariantTransition *from_trans; VariantTransition *to_trans; Variant *next; }; struct VariantTransition { VariantTransition(Variant *_from, Variant *_to) { from = _from; if (from->to_trans != 0) from->to_trans->ref_prev_to = &next_to; next_to = from->to_trans; from->to_trans = this; ref_prev_to = &from->to_trans; to = _to; if (to->from_trans != 0) to->from_trans->ref_prev_from = &next_from; next_from = to->from_trans; to->from_trans = this; ref_prev_from = &to->from_trans; } ~VariantTransition() { if (next_from != 0) next_from->ref_prev_from = ref_prev_from; *ref_prev_from = next_from; if (next_to != 0) next_to->ref_prev_to = ref_prev_to; *ref_prev_to = next_to; } Variant *from; VariantTransition **ref_prev_from; VariantTransition *next_from; Variant *to; VariantTransition **ref_prev_to; VariantTransition *next_to; }; Variant::~Variant() { while (from_trans != 0) delete from_trans; while (to_trans != 0) delete to_trans; delete next; } Variant* insert(Variant **ref_var, char *pattern) { for (; *ref_var != 0; ref_var = &(*ref_var)->next) { int cmp = strcmp((*ref_var)->pattern, pattern); if (cmp == 0) return (*ref_var); if (cmp > 0) break; } *ref_var = new Variant(pattern, *ref_var); return (*ref_var); } int compare(Variant *left, Variant *right) { for (; left != 0 && right != 0; left = left->next, right = right->next) { int c = strcmp(left->pattern, right->pattern); if (c != 0) return c; } return left == 0 && right == 0 ? 0 : left == 0 ? -1 : 1; } struct State { State(char _first, Variant *_variants, State *_next) : first(_first), variants(_variants), next(_next), nr_before(0), processed(false), same_as(0), non_circular(false), reach_all(false) { for (int i = 0; i < 9; i++) next_state[i] = 0; } int nr; int nr_before; char first; Variant *variants; bool processed; State *next_state[9]; State *same_as; State *uniqueState() { if (this == 0) return 0; if (same_as == 0) return this; same_as = same_as->uniqueState(); return same_as; } bool non_circular; bool reach_all; bool s1, s2; State *next; }; int compare(State *left, char first, Variant *variants) { if (left->first < first) return -1; if (left->first > first) return 1; return compare(left->variants, variants); } State *all_states = 0; State* insertState(char first, Variant *variants, bool before) { State **state_ref = &all_states; for (; *state_ref != 0; state_ref = &(*state_ref)->next) { int cmp = compare((*state_ref), first, variants); if (cmp == 0) { if (before) (*state_ref)->nr_before++; // copy VariantTransition Variant* target = (*state_ref)->variants; for (Variant* source = variants; source != 0; source = source->next, target = target->next) for (VariantTransition* trans = source->from_trans; trans != 0; trans = trans->next_from) new VariantTransition(trans->from, target); delete variants; return (*state_ref); } if (cmp > 0) break; } *state_ref = new State(first, variants, *state_ref); if (before) (*state_ref)->nr_before++; return (*state_ref); } bool nonEmpty(State* state, int i) { return (state->first != 'G' && i%3 == 0 && !(state->first >= 'H' && i == 6)) || state->first-'A'+1 == i; } void printStates() { int nr_states = 0; for (State* state = all_states; state != 0; state = state->next) if (state->nr_before > 0) state->nr = ++nr_states; int unique_states = 0; printf(" A B C D E F G H I\n"); for (State* state = all_states; state != 0; state = state->next) if (state->nr_before > 0) { printf("%3d", state->nr); if (state->same_as != 0) printf("=%3d", state->same_as->nr); else { unique_states++; printf(" "); } printf(" %c :", state->first); for (int i = 0; i < 9; i++) if (state->next_state[i] == 0) printf(" %s", nonEmpty(state, i) ? "***" : " "); else printf(" %3d", state->next_state[i]->nr); printf(" | "); for (Variant *variant = state->variants; variant != 0; variant = variant->next) if (variant->from_trans != 0) printf(" %s%s", variant->pattern, variant->from_trans != 0 ? "" : "#"); printf(" (%d)\n", state->nr_before); } printf("\nunique states = %d\n\n", unique_states); nr_states = 0; for (State* state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0) state->nr = ++nr_states; printf(" A B C D E F G H I\n"); for (State* state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0) { printf("%2d", state->nr); printf(" %c :", state->first); for (int i = 0; i < 9; i++) if (state->next_state[i] == 0) printf(" %s", nonEmpty(state, i) ? "**" : " "); else printf(" %2d", state->next_state[i]->uniqueState()->nr); printf("%s%s\n", state->non_circular ? " non-circular" : "", state->reach_all ? "" : " does not reach all"); } printf("\n\n"); } void buildInit(int i1, int i2, int depth, char *pattern, Variant **ref_variants) { if (depth == DEPTH) { insert(ref_variants, pattern); return; } for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) if (st[i3][i4][i1][i2]) { pattern[depth] = i4 + 'A'; buildInit(i3, i4, depth+1, pattern, ref_variants); } } void buildNext(int i1, int i2, int depth, char *prev_pattern, char *pattern, Variant **ref_variants, Variant *from) { if (depth == DEPTH) { Variant* to = insert(ref_variants, pattern); new VariantTransition(from, to); return; } int i3 = prev_pattern[depth] - 'A'; for (int i4 = 0; i4 < 9; i4++) if (st[i3][i4][i1][i2]) { pattern[depth] = i4 + 'A'; buildNext(i3, i4, depth+1, prev_pattern, pattern, ref_variants, from); } } void findStates() { char pattern[DEPTH+1]; pattern[DEPTH] = '\0'; // initialize states for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) { Variant *variants = 0; buildInit(i1, i2, 0, pattern, &variants); if (variants != 0) insertState(i2+'A', variants, false); } // Expand all states for (;;) { State *state = all_states; while (state != 0 && state->processed) state = state->next; if (state == 0) break; for (int i2 = 0; i2 < 9; i2++) { Variant *variants = 0; for (Variant *variant = state->variants; variant != 0; variant = variant->next) buildNext(state->first - 'A', i2, 0, variant->pattern, pattern, &variants, variant); if (variants != 0) state->next_state[i2] = insertState(i2+'A', variants, true); } state->processed = true; } // Incremental removal of unreachable variants in both directions for (int removed = -1; removed != 0;) { removed = 0; for (State* state = all_states; state != 0; state = state->next) for (Variant* variant = state->variants; variant != 0; variant = variant->next) { if (variant->to_trans == 0) while (variant->from_trans != 0) { delete variant->from_trans; removed++; } if (variant->from_trans == 0) while (variant->to_trans != 0) { delete variant->to_trans; removed++; } } printf("Loop %d\n", removed); } // Compact for (bool go = true; go;) { go = false; for (State *first = all_states; first != 0; first = first->next) if (first->nr_before > 0) for (State *second = first->next; second != 0; second = second->next) if (second->nr_before > 0 && second->same_as == 0) { bool same_next_states = true; for (int i = 0; i < 9; i++) if (first->next_state[i]->uniqueState() != second->next_state[i]->uniqueState()) { same_next_states = false; break; } if (same_next_states) { second->same_as = first; go = true; } } } // Find non-circular states for (State *state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0) { for (State *state1 = all_states; state1 != 0; state1 = state1->next) { state1->s1 = false; state1->s2 = state1 == state; } for (bool go = true; go;) { go = false; for (State *state1 = all_states; state1 != 0; state1 = state1->next) if (state1->s2) { go = true; for (int i = 0; i < 9; i++) if (state1->next_state[i] != 0) { State *next = state1->next_state[i]->uniqueState(); if (!next->s1) { next->s1 = true; next->s2 = true; } } state1->s2 = false; } } state->non_circular = !state->s1; state->reach_all = true; for (State *state1 = all_states; state1 != 0; state1 = state1->next) if (state1->nr_before > 0 && state1->same_as == 0) if (!state1->s1) { state->reach_all = false; break; } } printStates(); } void analyseSequence(const char* seq) { for (State* state = all_states; state != 0; state = state->next) { state->s1 = state->nr_before > 0 && state->same_as == 0; state->s2 = false; } for (const char *s = seq; *s != '\0'; s++) { int i = *s - 'A'; for (State* state = all_states; state != 0; state = state->next) if (state->s1 && state->next_state[i] != 0) state->next_state[i]->uniqueState()->s2 = true; printf(" %c", *s); bool first = true; for (State* state = all_states; state != 0; state = state->next) { if (state->s2 && first) { printf(" %d", state->nr); first = false; } state->s1 = state->s2; state->s2 = false; } } printf("\n"); } int main(int argc, char* argv[]) { for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) { for (int i3 = 0; i3 < 9; i3++) { for (int i4 = 0; i4 < 9; i4++) st[i1][i2][i3][i4] = false; st3[i1][i2][i3] = 0; } stc[i1][i2].top = 0; stc[i1][i2].left = 0; stc[i1][i2].right = 0; stc[i1][i2].bottom = 0; } DoubleLinesOutput doubleLinesOutput; doubleLinesOutput.setEnable(debug_init); // empty if (debug_init) printf("empty\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b+1 <= 3; b++) initialize_st(value(a, b), value(a+1, b), value(a, b+1), value(a+1, b+1), doubleLinesOutput); doubleLinesOutput.flush(); // horizontal if (debug_init) printf("\nhorizontal\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c+1 <= 3; c++) if (a != 2 || c != 2) initialize_st(value(a, b), value(a+1, b), value(c, 1), value(c+1, 1), doubleLinesOutput); doubleLinesOutput.flush(); // vertical if (debug_init) printf("\nvertical\n"); for (int a = 1; a < 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c+1 <= 3; c++) if (a != 2 || c != 2) initialize_st(value(b, a), value(1, c), value(b, a+1), value(1, c+1), doubleLinesOutput); doubleLinesOutput.flush(); // T if (debug_init) printf("\nT\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c <= 3; c++) initialize_st(value(a, b), value(a+1, b), value(c, 1), value(1, 1), doubleLinesOutput); doubleLinesOutput.flush(); // T rotated to the left if (debug_init) printf("\nT rotated to the left\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c <= 3; c++) initialize_st(value(b, a), value(1, c), value(b, a+1), value(1, 1), doubleLinesOutput); doubleLinesOutput.flush(); // T rotated to the right if (debug_init) printf("\nT rotated to the right\n"); for (int a = 1; a <= 3; a++) for (int b = 1; b <= 3; b++) if (!(a == 3 && b == 1) && !(a == 1 && b == 3)) for (int c = 1; c <= 3; c++) if (c != a) for (int d = 1; d+1 <= 3; d++) initialize_st(value(a, b), value(1, d), value(c, 1), value(1, d+1), doubleLinesOutput); doubleLinesOutput.flush(); // T upside-down if (debug_init) printf("\nT upside-down\n"); for (int a = 1; a <= 3; a++) for (int b = 1; b <= 3; b++) if (!(a == 3 && b == 1) && !(a == 1 && b == 3)) for (int c = 1; c <= 3; c++) if (c != a) for (int d = 1; d+1 <= 3; d++) initialize_st(value(b, a), value(1, c), value(d, 1), value(d+1, 1), doubleLinesOutput); doubleLinesOutput.flush(); if (debug_init) printf("\n-----\n\n"); doubleLinesOutput.setEnable(true); for (bool go = true; go; ) { for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4]) doubleLinesOutput.add(i1, i2, i3, i4); doubleLinesOutput.flush(); // Check top versus bottom go = false; for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) { bool top = stc[i1][i2].top > 0; bool bottom = stc[i1][i2].bottom > 0; if (top != bottom) { printf("%c%c top = %d bottom = %d\n", i1+'A', i2+'A', stc[i1][i2].top, stc[i1][i2].bottom); go = true; } if (top && !bottom) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i1, i2, i3, i4); } if (bottom && !top) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i3, i4, i1, i2); } } // Check left versus right for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) { bool left = stc[i1][i2].left > 0; bool right = stc[i1][i2].right > 0; if (left != right) { printf("%c%c left = %d right = %d\n", i1+'A', i2+'A', stc[i1][i2].left, stc[i1][i2].right); go = true; } if (left && !right) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i1, i3, i2, i4); } if (right && !left) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i3, i1, i4, i2); } } printf("\n"); } for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4]) st3[i1][i2][i3]++; // check if symmetric for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) for (int i3 = 0; i3 < 9; i3++) { if (st3[i1][i2][i3] != st3[inverse(i1)][inverse(i3)][inverse(i2)]) { printf("Not symmetric for %c%c %c\n", i1+'A', i2+'A', i3+'A'); return 1; } for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4] != st[inverse(i1)][inverse(i3)][inverse(i2)][inverse(i4)]) { printf("Not symmetric for %c%c %c%c\n", i1+'A', i2+'A', i3+'A', i4+'A'); return 1; } } findStates(); printf("\n[ABC]A(ABC)*AA\n"); analyseSequence("AAAA"); analyseSequence("BAAA"); analyseSequence("CAAA"); analyseSequence("AAABCAA"); analyseSequence("AAABCABCAA"); printf("\n([ABC]AAD|[HI]D)(A?ABA?D)*(AAA|G)\n"); analyseSequence("AAAD"); analyseSequence("BAAD"); analyseSequence("CAAD"); analyseSequence("HD"); analyseSequence("ID"); analyseSequence("AAADABADG"); analyseSequence("AAADAABADG"); analyseSequence("AAADABAADG"); analyseSequence("AAADAABAADG"); printf("\n(([ABC]AAD|[HI]D)(ABD)?AA|[GHI]AB)DDEFD(ABG|AA(DAB)?(DAAA|DG))\n"); analyseSequence("AAADAA"); analyseSequence("AAADABDAA"); analyseSequence("HDAA"); analyseSequence("IDAA"); analyseSequence("IDABDAA"); analyseSequence("HAB"); analyseSequence("IAB"); analyseSequence("HDAADDEFDABG"); analyseSequence("HABDDEFDABG"); analyseSequence("HABDDEFDAADAAA"); analyseSequence("HABDDEFDAADG"); analyseSequence("HABDDEFDAADABDAAA"); analyseSequence("HABDDEFDAADABDG"); printf("\n(([ABC]AAD|[HI]D)AABC|[HI]AB)(AADEAA|AABA)(ABG|ABCA(DAAA|DG))\n"); analyseSequence("AAADAABC"); analyseSequence("HDAABC"); analyseSequence("HAB"); analyseSequence("HABAADEAA"); analyseSequence("HABAABA"); analyseSequence("HABAABAABG"); analyseSequence("HABAABAABCADAAA"); analyseSequence("HABAABAABCADG"); printf("\n[HI]ABG\n"); analyseSequence("HABG"); printf("\n[DEFHI]A[DG]\n"); analyseSequence("DAD"); analyseSequence("DAG"); analyseSequence("HAG"); return 0; }