/* 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 <stdio.h>

#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 <stdio.h>\n");
    printf("#include <time.h>\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");
}