/* takuzu.cpp -- Counting number of Takuzu Copyright (C) 2015 Frans Faase 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/D1512.html#14 */ #include #define SIZE 10 void gen_solve(int i, int j, double speed) { speed /= 2; printf(" for (int i = 0; i < 2; ++i) {\n"); if (i == 0) printf(" Tree* row_tree_%d_%d = trees->trees[i];\n", i+1, j); else printf(" Tree* row_tree_%d_%d = row_tree_%d_%d->trees[i];\n", i+1, j, i, j); if (j == 0) printf(" Tree* col_tree_%d_%d = trees->trees[i];\n", i, j+1); else printf(" Tree* col_tree_%d_%d = col_tree_%d_%d->trees[i];\n", i, j+1, i, j); printf(" if (row_tree_%d_%d != 0 && col_tree_%d_%d != 0) {\n", i+1, j, i, j+1); if (i == SIZE-2 || j == SIZE-2) printf(" bool unique = true;\n"); if (i == SIZE-2) printf(" if (++row_tree_%d_%d->row_count > 1) unique = false;\n", i+1, j); if (j == SIZE-2) printf(" if (++col_tree_%d_%d->col_count > 1) unique = false;\n", i, j+1); if (i == SIZE-2 || j == SIZE-2) printf(" if (unique)\n"); if (i == SIZE-1 && j == SIZE-1) { printf(" count += 2;\n"); printf(" static clock_t s = clock();\n"); printf(" static clock_t ct = clock();\n"); printf(" if (ct < clock())\n"); printf(" {\n"); printf(" ct = clock() + 6000;\n"); printf(" double secs = (clock() - s)/1000.0;\n"); printf(" double secleft = 0.0;\n"); printf(" if (perc > 0) secleft = secs * (1 - perc) / perc;\n"); printf(" printf(\"%%10.1lf %%20.0lf (%%10.3lf) %%12.10lf %%lf\\n\", secs, count, count/secs, perc, secleft);\n"); printf(" }\n"); } else { int n_i = i + 1; int n_j = j - 1; if (n_j < 0 || n_i >= SIZE) { n_i = 0; n_j = j + i + 1; while (n_j >= SIZE) { n_j--; n_i++; } } gen_solve(n_i, n_j, speed); } if (i == SIZE-2 || j == SIZE-2) printf(" else perc += %lg;\n", speed); if (i == SIZE-2) printf(" --row_tree_%d_%d->row_count;\n", i+1, j); if (j == SIZE-2) printf(" --col_tree_%d_%d->col_count;\n", i, j+1); printf(" } else perc += %lg; }\n", speed); } int main(int argc, char *argv[]) { printf("#include \n"); printf("#include \n"); printf("\n"); printf("long nr_rows;\n"); printf("int row[%d];\n", SIZE); printf("\n"); printf("class Tree\n"); printf("{\n"); printf("public:\n"); printf(" Tree() : row_count(0), col_count(0) { trees[0] = trees[1] = 0; }\n"); printf(" Tree* trees[2];\n"); printf(" int row_count;\n"); printf(" int col_count;\n"); printf("};\n"); printf("\n"); printf("Tree *trees = 0;\n"); printf("\n"); printf("void findrow(int p, int zeros, int ones)\n"); printf("{\n"); printf(" if (zeros == 0 && ones == 0)\n"); printf(" {\n"); printf(" Tree **rtree = &trees;\n"); printf(" for (int i = 0; i < %d; i++)\n", SIZE); printf(" {\n"); printf(" if (*rtree == 0)\n"); printf(" *rtree = new Tree();\n"); printf(" rtree = &(*rtree)->trees[row[i]];\n"); printf(" \n"); printf(" printf(\"%%d\",row[i]);\n"); printf(" }\n"); printf(" *rtree = new Tree();\n"); printf(" printf(\"\\n\");\n"); printf(" nr_rows++;\n"); printf(" return;\n"); printf(" }\n"); printf(" if (zeros > 0 && (p < 2 || row[p-1] != 0 || row[p-2] != 0))\n"); printf(" {\n"); printf(" row[p] = 0;\n"); printf(" findrow(p+1, zeros-1, ones);\n"); printf(" }\n"); printf(" if (ones > 0 && (p < 2 || row[p-1] != 1 || row[p-2] != 1))\n"); printf(" {\n"); printf(" row[p] = 1;\n"); printf(" findrow(p+1, zeros, ones-1);\n"); printf(" }\n"); printf("}\n"); printf("\n"); printf("int main(int argc, char *argv[])\n"); printf("{\n"); printf(" findrow(0, %d, %d);\n", SIZE/2, SIZE/2); printf(" printf(\"Rows = %%d\\n\", nr_rows);\n"); printf(" double count = 0;\n"); printf(" double perc = 0;\n"); printf(" Tree* row_tree_1_0 = trees->trees[0];\n"); printf(" Tree* col_tree_0_1 = trees->trees[0];\n"); gen_solve(0, 1, 1.0); printf(" printf(\"count = %%20.0lf\\n\", count);\n"); printf(" return 0;\n"); printf("}\n"); }