/* Generating Street Tilings Copyright (C) 2016 Frans Faase This program is used to generate HTML pages for the Chinese Wooden Puzzles on my website. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. GNU General Public License: http://www.iwriteiam.nl/GNU.txt Details: http://www.iwriteiam.nl/D1605.html#1 */ #include #include #include #include class bitvec; class counter { friend class bitvec; int i; int b; public: counter() : i(0), b(1) {} counter(const counter& rhs) { i = rhs.i; b = rhs.b; } counter(int v) { i = v >> 3; b = 1 << (v & 7); } inline void zero() { i = 0; b = 1; } inline bool iszero() { return i == 0 && b == 1; } inline void inc() { if (b == 128) { i++; b = 1; } else b *= 2; } inline void dec() { if (b == 1) { i--; b = 128; } else b /= 2; } inline const counter& operator=(const int v) { i = v >> 3; b = 1 << (v & 7); return *this; } inline const counter& operator=(const counter& rhs) { i = rhs.i; b = rhs.b; return *this; } inline bool operator<(const counter& rhs) { return i < rhs.i || (i == rhs.i && b < rhs.b); } inline bool operator==(const counter& rhs) { return i == rhs.i && b == rhs.b; } void print() { printf("(%d:%d)",i,b); } }; class counter; class bitvec { public: int v[25]; static int len; static counter lencounter; static counter highbit; static int len8; static int len8m1; static int highnrbits; static int highmask; static int memlen; static void setlen(int newlen) { len = newlen; lencounter = len; highbit = len - 1; len8 = (len + 7)/8; len8m1 = len8-1; highnrbits = len % 8; highmask = (1 << highnrbits) - 1; memlen = len8 * sizeof(int); init_nrones(); } inline void zero() { memset(v, 0, memlen); } bool isZero() { for (int i = 0; i < len8; i++) if (v[i] != 0) return false; return true; } inline bitvec& operator=(const bitvec rhs) { memcpy(v, rhs.v, memlen); return *this; } inline bool operator==(const bitvec rhs) const { return memcmp(v, rhs.v, memlen) == 0; } bool operator<=(const bitvec rhs) const { if (*this == rhs) return true; for (int i = len8m1; i >= 0; i--) { if (v[i] < rhs.v[i]) return true; if (v[i] > rhs.v[i]) return false; } return true; // equal, should not occur } bool operator<(const bitvec rhs) const { for (int i = len8m1; i >= 0; i--) { if (v[i] < rhs.v[i]) return true; if (v[i] > rhs.v[i]) return false; } return false; } inline bool getbit(const counter& c) const { return (v[c.i] & c.b) != 0; } inline void setbit(const counter& c) { v[c.i] |= c.b; } inline void resetbit(const counter& c) { v[c.i] &= ~c.b; } inline void assignbit(const counter& c, int val) { if (val) v[c.i] |= c.b; else v[c.i] &= ~c.b; } void inc() { int i = 0; counter c; for (; i < len && getbit(c); i++) { resetbit(c); c.inc(); } if (i < len) setbit(c); } void print(FILE* f = stdout) { counter i = lencounter; for (; !i.iszero();) { i.dec(); fprintf(f, "%c", getbit(i) ? '1' : '0'); } //for (int j = len8m1; j >= 0; j--) // fprintf(f, ",%d", v[j]); } int nrones() const { int ones = 0; for (int i = 0; i < len8; i++) ones += _nrones[v[i]]; return ones; } void rotate() { int lowest = v[0] & 1; for (int i = 0; i < len8m1; i++) { v[i] /= 2; if (v[i+1] & 1) v[i] |= (1 << 7); } v[len8m1] /= 2; if (lowest) v[len8m1] |= (1 << (highnrbits-1)); } private: static int _nrones[256]; static void init_nrones() { for (int i = 0; i < 256; i++) { int ones = 0; for (int j = 0; j < 8; j++) if (i & (1 << j)) ones++; _nrones[i] = ones; } } }; int bitvec::len; counter bitvec::lencounter; counter bitvec::highbit; int bitvec::len8; int bitvec::len8m1; int bitvec::highnrbits; int bitvec::highmask; int bitvec::memlen; int bitvec::_nrones[256]; struct transl_t { bool swap; int s_w; int s_h; bool mirror; bool rot_shift; bool rot_inv_shift; } transls[8] = { { false, 1, 1, false, false, false }, { false, -1, 1, true, false, false }, { false, 1, -1, true, false, false }, { false, -1, -1, false, false, false }, { true, 1, 1, false, true, false }, { true, -1, 1, false, false, true }, { true, 1, -1, false, false, true }, { true, -1, -1, false, true, false } }; int area; int width; int height; int shift; int rot_shift; bool mirror; bool rotate; int horz_pos(int w, int h) { while (h < 0) { h += height; w += shift; } while (h >= height) { h -= height; w -= shift; } while (w < 0) w += width; while (w >= width) w -= width; return w + width * h; } int horz_pos(int w, int h, int width, int height, int shift) { while (h < 0) { h += height; w += shift; } while (h >= height) { h -= height; w -= shift; } while (w < 0) w += width; while (w >= width) w -= width; return w + width * h; } #define IMPLIES(X,Y) (!(X) || (Y)) bool vertical_infinite_tile(bitvec& a) { for (int w = 0; w < width; w++) { bool all_zero = true; for (int h = 0; h < area; h++) if (a.getbit(horz_pos(w, h))) { all_zero = false; break; } if (all_zero) return true; } return false; } bool vertical_size_limit(bitvec& a) { //return true; for (int w = 0; w < width; w++) for (int h = 0; h < height; h++) if ( a.getbit(horz_pos(w, h)) && !a.getbit(horz_pos(w, h+1)) && !a.getbit(horz_pos(w, h+2)) && !a.getbit(horz_pos(w, h+3))) return false; return true; } FILE *fout = 0; bool restrict_on_repeat = true; bool restrict_on_size = true; bool restrict_on_H_shape = true; bool restrict_on_cross = true; int count; void process_sol(bitvec &horzvec, char* vert) { char *error = 0; // Check for horizontal infinite tile for (int i = 0; i < height && error == 0; i++) { bool all_zero = true; for (int j = 0; j < width; j++) if (vert[width*i + j] == '1') { all_zero = false; break; } if (all_zero) error = "horizontal infinite tile"; } bitvec vertvec; vertvec.zero(); for (int j = 0; j < area; j++) vertvec.assignbit(counter(j), vert[j] == '1'); char *error2 = 0; char buffer[200]; if (error == 0 && restrict_on_size) { //printf("<"); // Filter on pieces other than 1x1, 1x2, 2x2, 2x3, and 3x3 for (int w = 0; w < width && error2 == 0; w++) for (int h = 0; h < height && error2 == 0; h++) if (vertvec.getbit(horz_pos(w, h)) && horzvec.getbit(horz_pos(w, h))) { int x = 1; while (!vertvec.getbit(horz_pos(w+x, h)))// && x < width*2) { //printf("x"); x++; } int y = 1; while (!horzvec.getbit(horz_pos(w, h+y))) // && y < width*2) { //printf("y"); y++; } //if (horz.getbit((j+x+shift*y)%width)) //{ if (x > 3 || y > 3) error2 = "too large piece"; else if (x < y-1) error2 = "too narrow piece"; else if (y < x-1) error2 = "too narrow piece"; //} } error = error2; error2 = 0; } if (error == 0 && restrict_on_H_shape) { //printf("<"); // Filter on H shapes for (int w = 0; w < width && error2 == 0; w++) for (int h = 0; h < height && error2 == 0; h++) { if (horzvec.getbit(horz_pos(w, h)) && vertvec.getbit(horz_pos(w, h)) && vertvec.getbit(horz_pos(w, h-1))) { int x = 1; while (horzvec.getbit(horz_pos(w+x, h)) && !vertvec.getbit(horz_pos(w+x, h)) && !vertvec.getbit(horz_pos(w+x, h-1))) x++; if (!horzvec.getbit(horz_pos(w+x, h)) && vertvec.getbit(horz_pos(w+x, h)) && vertvec.getbit(horz_pos(w+x, h-1))) error2 = "H figure"; } if (vertvec.getbit(horz_pos(w, h)) && horzvec.getbit(horz_pos(w, h)) && horzvec.getbit(horz_pos(w-1, h))) { int y = 1; while (vertvec.getbit(horz_pos(w, h+y)) && !horzvec.getbit(horz_pos(w, h+y)) && !horzvec.getbit(horz_pos(w-1, h+y))) y++; if (!vertvec.getbit(horz_pos(w, h+y)) && horzvec.getbit(horz_pos(w, h+y)) && horzvec.getbit(horz_pos(w-1, h+y))) error2 = "turned H figure"; } } error = error2; error2 = 0; } if (error == 0) { for (int d = 0; d < 8 && error2 == 0; d++) if ( IMPLIES(transls[d].mirror, mirror) && IMPLIES(transls[d].rot_shift, rotate && shift == rot_shift) && IMPLIES(transls[d].rot_inv_shift, rotate && shift == width - rot_shift)) { bool swap = transls[d].swap; int s_w = transls[d].s_w; int a_w = s_w < 0 ? -1 : 0; int s_h = transls[d].s_h; int a_h = s_h < 0 ? -1 : 0; for (int w_o = 0; w_o < width && error2 == 0; w_o++) for (int h_o = 0; h_o < height && error2 == 0; h_o++) if (d != 0 || w_o != 0 || h_o != 0) { int h_sign = 0; int v_sign = 0; for (int w = 0; w < width && h_sign == 0; w++) for (int h = 0; h < height && h_sign == 0; h++) { bool v_h = horzvec.getbit(horz_pos(w, h)); bool v_h_o = swap ? vertvec.getbit(horz_pos(w_o + s_w * h, h_o + a_h + s_h * w)) : horzvec.getbit(horz_pos(w_o + a_w + s_w * w, h_o + s_h * h)); bool v_v = vertvec.getbit(horz_pos(w, h)); bool v_v_o = swap ? horzvec.getbit(horz_pos(w_o + a_w + s_w * h, h_o + s_h * w)) : vertvec.getbit(horz_pos(w_o + s_w * w, h_o + a_h + s_h * h)); if (v_h != v_h_o) h_sign = v_h && !v_h_o ? -1 : 1; if (v_sign == 0 && v_v != v_v_o) v_sign = v_v && !v_v_o ? -1 : 1; } if (h_sign == 0 && v_sign == 0) { if (d == 0 && restrict_on_repeat) error2 = "repeat"; } else if (h_sign < 0) { sprintf(buffer, "%d h smaller", d); error2 = buffer; } else if (h_sign == 0 && v_sign < 0) { sprintf(buffer, "%d v smaller", d); error2 = buffer; } } } error = error2; error2 = 0; } if (error == 0) { count++; if (fout != 0) { fprintf(fout, "\t{w:%d,h:%d,s:%d,v:[", width, height, shift); for (int j = 0; j < area; j++) { int w = j % width; int h = j / width; int value = (horzvec.getbit(horz_pos(w-1,h)) ? 1 : 0) | (horzvec.getbit(horz_pos(w,h)) ? 4 : 0) | (vertvec.getbit(horz_pos(w,h-1)) ? 2 : 0) | (vertvec.getbit(horz_pos(w,h)) ? 8 : 0); fprintf(fout, "%s%d", j == 0 ? "" : ",", value); } fprintf(fout, "]},\n"); fflush(fout); } } } void solverec(bitvec &horz, char* vert, int i) { if (i == area) { process_sol(horz, vert); } else { int w = i % width; int h = i / width; bool right = horz.getbit(horz_pos(w, h)); bool left = horz.getbit(horz_pos(w-1, h)); char* top = &vert[horz_pos(w, h-1)]; char* bottom = &vert[horz_pos(w, h)]; char old_top = *top; char old_bottom = *bottom; if (right != left) { if (*top != '0' && *bottom != '0') { *top = '1'; *bottom = '1'; bool okay = true; if (restrict_on_H_shape && (old_top == '?' || old_bottom == '?')) { int inc = right ? 1 : -1; for (int w2 = w + inc; ; w2 += inc) { char top_2 = vert[horz_pos(w2, h-1)]; char bottom_2 = vert[horz_pos(w2, h)]; if (top_2 == '1' && bottom_2 == '1') { okay = false; break; } if (top_2 != '0' || bottom_2 != '0') break; } } if (okay) solverec(horz, vert, i+1); *top = old_top; *bottom = old_bottom; } } else if (right) // && left { if (*top != '1') { *top = '0'; bool okay = true; if (restrict_on_size && old_top == '?') { if ( horz.getbit(horz_pos(w, h-1)) && ( vert[horz_pos(w+1, h-1)] == '0' || vert[horz_pos(w-1, h-1)] == '0')) okay = false; } if (okay) { if (*bottom != '1') { *bottom = '0'; bool okay = true; if (okay) solverec(horz, vert, i+1); *bottom = old_bottom; } *top = '0'; if (*bottom != '0') { *bottom = '1'; bool okay = true; if (restrict_on_H_shape && old_bottom == '?') { for (int h2 = h + 1; ; h2++) { bool right_2 = horz.getbit(horz_pos(w, h2)); bool left_2 = horz.getbit(horz_pos(w-1, h2)); if (right_2 && left_2) { okay = false; break; } if (right_2 || left_2) break; } } if (okay) solverec(horz, vert, i+1); *bottom = old_bottom; } } *top = old_top; } if (*top != '0') { *top = '1'; bool okay = true; if (restrict_on_H_shape && old_top == '?') { for (int h2 = h - 1; ; h2--) { bool right_2 = horz.getbit(horz_pos(w, h2)); bool left_2 = horz.getbit(horz_pos(w-1, h2)); if (right_2 && left_2) { okay = false; break; } if (right_2 || left_2) break; } } if (okay) { if (*bottom != '1') { *bottom = '0'; bool okay = true; if (restrict_on_size && old_bottom == '?') { if ( horz.getbit(horz_pos(w, h+1)) && ( vert[horz_pos(w+1, h)] == '0' || vert[horz_pos(w-1, h)] == '0')) okay = false; } if (okay) solverec(horz, vert, i+1); *bottom = old_bottom; } if (!restrict_on_cross) { *top = '1'; if (*bottom != '0') { *bottom = '1'; solverec(horz, vert, i+1); *bottom = old_bottom; } } } *top = old_top; } } else // !right && !left { if (*top != '0' && *bottom != '0') { *top = '1'; *bottom = '1'; solverec(horz, vert, i+1); *top = old_top; *bottom = old_bottom; } if (*top != '1' && *bottom != '1') { *top = '0'; *bottom = '0'; solverec(horz, vert, i+1); *top = old_top; *bottom = old_bottom; } } } } void rotate_90(int w, int h, int s, int &r_w, int &r_h, int &r_s) { r_w = 0; r_h = w; r_s = 0; int y = w; while (y != 0) { if (y > 0) { if (y < r_h) { r_h = y; r_s = r_w; } r_w += h; y -= (w - s); } else y += w; } } bool fill_implied_values(bitvec &horz, char* vert) { bool set_zero = false; for (int w = 0; w < width; w++) for (int h = 0; h < height; h++) { bool left = horz.getbit(horz_pos(w-1, h)); bool right = horz.getbit(horz_pos(w, h)); if (left != right) { if ( restrict_on_H_shape && right && !horz.getbit(horz_pos(w+1, h))) return false; if ( restrict_on_size && !right && horz.getbit(horz_pos(w+1,h)) && (!horz.getbit(horz_pos(w,h-1)) || !horz.getbit(horz_pos(w,h+1)))) return false; // top and bottom need to be set to '1' char* top = &vert[horz_pos(w, h-1)]; char* bottom = &vert[horz_pos(w, h)]; if (*top == '0' || *bottom == '0') return false; for (int htop = h-1; *top == '?'; htop--) { *top = '1'; left = horz.getbit(horz_pos(w-1, htop)); right = horz.getbit(horz_pos(w, htop)); if (left != right) break; top = &vert[horz_pos(w, htop-1)]; if (left) { if (restrict_on_cross) { if (*top == '1') return false; if (*top == '?') { *top = '0'; set_zero = true; } } break; } else { if (*top == '0') return false; } } for (int hbottom = h+1; *bottom == '?'; hbottom++) { *bottom = '1'; left = horz.getbit(horz_pos(w-1, hbottom)); right = horz.getbit(horz_pos(w, hbottom)); if (left != right) break; bottom = &vert[horz_pos(w, hbottom)]; if (left) { if (restrict_on_cross) { if (*bottom == '1') return false; if (*bottom == '?') { *bottom = '0'; set_zero = true; } } break; } else { if (*bottom == '0') return false; } } } } return true; } int main(int argc, char *argv[]) { fout = fopen("StreetTilings_test.txt", "wt"); clock_t start_clock = clock(); clock_t last_clock = start_clock; for (area = 1; area <= 30; area++) { count = 0; bitvec::setlen(area); for (width = area; width >= 1; width--) if (area % width == 0) { height = area / width; for (shift = 0; shift <= width/2; shift++) { int rot_width, rot_height; rotate_90(width, height, shift, rot_width, rot_height, rot_shift); //printf("// %d %d %d => %d %d %d\n", width, height, shift, rot_width, rot_height, rot_shift); if (rot_height < height || (rot_height == height && (rot_shift < shift || width - rot_shift < shift))) ; // rotated equal to combination we already tried else { rotate = width == rot_width && height == rot_height; mirror = 2*shift == width; bitvec horz; horz.zero(); for (horz.inc(); !horz.isZero(); horz.inc()) if (!vertical_infinite_tile(horz)) { char vert[100]; for (int i = 0; i < area; i++) vert[i] = '?'; if ( fill_implied_values(horz, vert) && IMPLIES(restrict_on_size, vertical_size_limit(horz))) solverec(horz, vert, 0); } } } } } fclose(fout); }