#include #include #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]; void initialize_st(int i1, int i2, int i3, int 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 StateList; 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), under(0), nr_valid_under(0) { 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; StateList* under; int nr_valid_under; State *next; }; struct StateList { StateList(State* _state) : state(_state), valid(true), next(0) {} ~StateList() { delete next; } State* state; bool valid; StateList* 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); } 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; } int nr_states = 0; for (State* state = all_states; state != 0; state = state->next) if (state->nr_before > 0) state->nr = ++nr_states; // 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); } // Calculate possible states under each state for (State *state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0) { StateList **ref_under = &state->under; for (State *state_under = all_states; state_under != 0; state_under = state_under->next) if (state_under->nr_before > 0 && state_under->same_as == 0) { bool fits = true; for (Variant *variant_under = state_under->variants; variant_under != 0; variant_under = variant_under->next) { char pattern[DEPTH+1]; pattern[0] = state_under->first; for (int i = 0; i < DEPTH-1; i++) pattern[i+1] = variant_under->pattern[i]; pattern[DEPTH] = '\0'; bool found = false; for (Variant *variant = state->variants; variant != 0; variant = variant->next) { int cmp = strcmp(variant->pattern, pattern); if (cmp < 0) continue; found = cmp == 0; break; } if (!found) { fits = false; break; } } if (fits) { *ref_under = new StateList(state_under); ref_under = &(*ref_under)->next; state->nr_valid_under++; } } } // Check for all under states there is a possible continuation for all next states for (bool go = true; go;) { go = false; for (State *state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0) for (StateList* under = state->under; under != 0; under = under->next) if (under->valid) { State* under_state = under->state; bool found = false; for (int i = 0; i < 9 && !found; i++) { State* next_state = state->next_state[i]->uniqueState(); if (next_state != 0) { for (int i2 = 0; i2 < 9 && !found; i2++) { State* under_next_state = under_state->next_state[i2]->uniqueState(); if (under_next_state != 0) for (StateList* next_under = next_state->under; next_under != 0; next_under = next_under->next) if (next_under->valid && next_under->state == under_next_state) { found = true; break; } } } } if (!found) { under->valid = false; go = true; state->nr_valid_under--; } } } for (State *state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0 && state->nr_valid_under == 0) printf("State %d%c has not valid under\n", state->nr, state->first); } #define WIDTH 40 #define HEIGHT 40 bool validUDTile(State* s1, State* s2, State* s3, State* s4) { return st[s3->first-'A'][s4->first-'A'][s1->first-'A'][s2->first-'A']; } void generateRandomRTL() { srand (time(NULL)); int nr_opt, s; State* line[WIDTH]; // Generate first sequence nr_opt = 0; for (State *state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0) nr_opt++; s = rand() % nr_opt; for (State *state = all_states; state != 0; state = state->next) if (state->nr_before > 0 && state->same_as == 0) { if (s == 0) { line[0] = state; break; } s--; } printf("\""); printf("%c", line[0]->first); for (int i = 1; i < WIDTH; i++) { nr_opt = 0; for (int n = 0; n < 9; n++) if (line[i-1]->next_state[n] != 0) nr_opt++; s = rand() % nr_opt; for (int n = 0; n < 9; n++) if (line[i-1]->next_state[n] != 0) { if (s == 0) { line[i] = line[i-1]->next_state[n]->uniqueState(); break; } s--; } printf("%c", line[i]->first); } printf("\",\n"); // Generate next sequences for (int j = 1; j < HEIGHT; j++) { // Fill unders StateList* unders[WIDTH]; for (int i = 0; i < WIDTH; i++) { unders[i] = 0; int count = 0; StateList** ref_under = &(unders[i]); for (StateList* under = line[i]->under; under != 0; under = under->next) if (under->valid) { bool valid = i == 0; if (!valid) for (StateList* prev_under = unders[i-1]; prev_under != 0 && !valid; prev_under = prev_under->next) for (int i4 = 0; i4 < 9 && !valid; i4++) if ( prev_under->state->next_state[i4]->uniqueState() == under->state && validUDTile(line[i-1], line[i], prev_under->state, under->state)) valid = true; if (valid) { *ref_under = new StateList(under->state); ref_under = &(*ref_under)->next; count++; } } } char outputline[WIDTH+1]; outputline[WIDTH] = '\0'; State* corner = 0; nr_opt = 0; for (StateList* under = unders[WIDTH-1]; under != 0; under = under->next) nr_opt++; if (nr_opt == 0) { printf("\nError: no option\n"); return; } s = rand() % nr_opt; for (StateList* under = unders[WIDTH-1]; under != 0; under = under->next) { if (s == 0) { corner = line[WIDTH-1]; line[WIDTH-1] = under->state; break; } s--; } outputline[WIDTH-1] = line[WIDTH-1]->first; for (int i = WIDTH-2; i >= 0; i--) { nr_opt = 0; for (StateList* under = unders[i]; under != 0; under = under->next) { bool valid = false; for (int i4 = 0; i4 < 9; i4++) if ( under->state->next_state[i4]->uniqueState() == line[i+1] && validUDTile(line[i], corner, under->state, line[i+1])) { valid = true; break; } if (valid) nr_opt++; } if (nr_opt == 0) { printf("\nError: no option for %d\n", i); return; } s = rand() % nr_opt; for (StateList* under = unders[i]; under != 0 && s >= 0; under = under->next) if (under->valid) { bool valid = false; for (int i4 = 0; i4 < 9; i4++) if ( under->state->next_state[i4]->uniqueState() == line[i+1] && validUDTile(line[i], corner, under->state, line[i+1])) { valid = true; break; } if (valid) { if (s == 0) { corner = line[i]; line[i] = under->state; break; } s--; } } outputline[i] = line[i]->first; } for (int i = 0; i < WIDTH; i++) delete unders[i]; printf("\"%s\",\n", outputline); } } 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; } // empty 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)); // horizontal 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)); // vertical 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)); // T 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)); // T rotated to the left 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)); // T rotated to the right 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)); // T upside-down 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)); for (bool go = true; go; ) { // 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) { 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) 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); } } } 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(); generateRandomRTL(); return 0; }