#include #include struct Piece { char name; char left; char top[3]; char bottom[3]; char right; char bottoml() { return bottom[0]; } char bottomr() { return bottom[1] != '\0' ? bottom[1] : bottom[0]; } }; Piece pieces[8] = { { 'a', '|', "2", "4", '.' }, { 'b', '.', "3", "15", '.' }, { 'c', '.', "4", "2", '|' }, { 'd', '.', "", "3", '.' }, { 'e', '|', "3", "3", '|' }, { 'f', '.', "41", "14", '.' }, { 'g', '.', "52", "25", '.' }, { '-', '.', "3", "3", '.' }, }; struct Connection { bool possible; char top[4]; char bottom[4]; }; Connection connections[8][8]; void buildConnections() { for (int li = 0; li < 8; li++) { Piece &l = pieces[li]; for (int ri = 0; ri < 8; ri++) { Piece &r = pieces[ri]; Connection &c = connections[li][ri]; c.possible = false; if (l.right != r.left) continue; if (l.name == 'd') { if (r.bottoml() != '1') continue; } else if (r.name == 'd') { if (l.bottomr() != '5') continue; } else { if (l.bottomr() == '5' && r.bottoml() == '1') continue; if (l.bottomr() == '5' && r.bottoml() == '3') continue; if (l.bottomr() == '3' && r.bottoml() == '1') continue; } c.possible = true; strcpy(c.top, r.top); char *t = c.bottom; if (l.bottomr() == '5' && r.name != 'd') *t++ = '5'; for (char *f = r.bottom + (l.name == 'd' ? 1 : 0); *f != '\0'; f++) if (*f != '5') *t++ = *f; *t = '\0'; } } printf(" "); for (int ri = 0; ri < 8; ri++) printf(" %c", pieces[ri].name); printf("\n"); for (int li = 0; li < 8; li++) { printf(" %c ", pieces[li].name); for (int ri = 0; ri < 8; ri++) { Connection &c = connections[li][ri]; if (c.possible) printf(" %2s/%-2s", c.top, c.bottom); else printf(" - "); } printf("\n"); } } #define MAX_LEN 50 void reverse(const char *in, char *out) { int l = strlen(in); for (int i = 0; i < l; i++) { char ch = in[i]; switch(ch) { case 'a' : ch = 'c'; break; case 'c' : ch = 'a'; break; case 'f' : ch = 'g'; break; case 'g' : ch = 'f'; break; case '1' : ch = '5'; break; case '2' : ch = '4'; break; case '4' : ch = '2'; break; case '5' : ch = '1'; break; } out[l-1-i] = ch; } out[l] = '\0'; } bool normalize(char *in, char *out) { char temp[MAX_LEN+1]; char rev_temp[MAX_LEN+1]; bool opt = true; strcpy(out, in); int l = strlen(in); for (int i = 0; i < l; i++) { for (int j = 0; j < l; j++) temp[j] = in[(i+j)%l]; temp[l] = '\0'; if (strcmp(temp, out) < 0) { strcpy(out, temp); opt = false; } reverse(temp, rev_temp); if (strcmp(rev_temp, out) < 0) { strcpy(out, rev_temp); opt = false; } } return opt; } struct BelowLines; struct Line { int len; char line[MAX_LEN+1]; int nr_top; int nr_bottom; bool ok; BelowLines *below_lines; int group; Line *next; }; struct BelowLines { Line *line; char pieces[MAX_LEN+1]; BelowLines *next; }; Line *lines = 0; Line *find_line(const char *s) { int len = strlen(s); Line **ref_line = &lines; while (*ref_line != 0 && ((*ref_line)->len < len || ((*ref_line)->len == len && strcmp((*ref_line)->line, s) < 0))) ref_line = &(*ref_line)->next; if (*ref_line != 0 && strcmp((*ref_line)->line, s) == 0) return (*ref_line); Line *new_line = new Line; new_line->len = len; strcpy(new_line->line, s); new_line->nr_top = 0; new_line->nr_bottom = 0; new_line->below_lines = 0; new_line->group = 0; new_line->next = *ref_line; *ref_line = new_line; return new_line; } char g_top[MAX_LEN+5]; char g_bottom[MAX_LEN+5]; char g_pieces[MAX_LEN+2]; void find_length(int n, int start, int cur, int depth) { //printf("%*.*sFind %c |%s|%s| %d\n", 2*depth, 2*depth, "", pieces[cur].name, g_top, g_bottom, n); if (depth == n) { if (start == cur) { //printf("%*.*sFind %s/%s |%s|%s| %d\n", 2*depth, 2*depth, "", cur->top, cur->bottom, g_top, g_bottom, n); char out_p[MAX_LEN+1]; if (normalize(g_pieces, out_p)) { char out_t[MAX_LEN+1]; normalize(g_top, out_t); Line *top_line = find_line(out_t); char out_b[MAX_LEN+1]; normalize(g_bottom, out_b); Line *bottom_line = find_line(out_b); top_line->nr_top++; bottom_line->nr_bottom++; BelowLines *new_below_line = new BelowLines; new_below_line->line = bottom_line; g_pieces[depth] = '\0'; // printf("%s / %s %s / %s : %s\n", g_top, g_bottom, out_t, out_b, g_pieces); strcpy(new_below_line->pieces, g_pieces); new_below_line->next = top_line->below_lines; top_line->below_lines = new_below_line; char out[MAX_LEN+1]; } } return; } int g_top_len = strlen(g_top); int g_bottom_len = strlen(g_bottom); for (int next = 0; next < 8; next++) { Connection &conn = connections[cur][next]; if (conn.possible) { g_pieces[depth] = pieces[next].name; strcpy(g_top + g_top_len, conn.top); strcpy(g_bottom + g_bottom_len, conn.bottom); find_length(n, start, next, depth+1); g_top[g_top_len] = '\0'; g_bottom[g_bottom_len] = '\0'; } } } void find_group(Line *line, int group) { if (line->group == 0 && line->ok) { printf(" %s %d %d", line->line, line->nr_top, line->nr_bottom); for (BelowLines *below_line = line->below_lines; below_line != 0; below_line = below_line->next) printf(" = %s (%s%s)", below_line->pieces, below_line->line->line, below_line->line->ok ? "" : " FAIL"); printf("\n"); line->group = group; for (BelowLines *line_below = line->below_lines; line_below != 0; line_below = line_below->next) find_group(line_below->line, group); } } int main(int argc, char **argv) { buildConnections(); for (int n = 1; n < 12; n++) { //printf("\n\nn = %d\n", n); for (int i = 0; i < 8; i++) { g_top[0] = '\0'; g_bottom[0] = '\0'; find_length(n, i, i, 0); } } for (Line *line = lines; line != 0; line = line->next) line->ok = line->nr_bottom > 0 && line->nr_top > 0; //printf("\n"); for (bool go = true; go;) { //printf("Pass: "); go = false; for (Line *line = lines; line != 0; line = line->next) if (line->ok) { bool any_below_ok = false; for (BelowLines *below_line = line->below_lines; below_line != 0; below_line = below_line->next) if (below_line->line->ok) { any_below_ok = true; break; } if (!any_below_ok) { line->ok = false; go = true; //printf("*"); } } //printf("\n"); } // Mark groups int nr_groups = 1; for (Line *line = lines; line != 0; line = line->next) if (line->group == 0 && line->ok) { printf("\ngroup %d:\n", nr_groups); find_group(line, nr_groups); nr_groups++; } return 0; }