/* 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/D1604.html#16

*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

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');
        }
    }
    
    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;
}

FILE *fout = 0;

bool restrict_on_repeat = true;
bool restrict_on_size = false;
bool restrict_on_H_shape = false;
bool restrict_on_cross = false;
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)
    {
        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 && restrict_on_size)
    {
        // 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++;
                    int y = 1;
                    while (!horzvec.getbit(horz_pos(w, h+y)))
                        y++;
                    if (x > 3 || y > 3)
                        error2 = "too large piece";
                    else if ((x < y-1) || (y < x-1))
                        error2 = "too narrow piece";
                }
        error = error2;
        error2 = 0;
    }
    if (error == 0 && restrict_on_H_shape)
    {
        // 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)
    {
        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)) != 0;
        bool left = horz.getbit(horz_pos(w-1, h)) != 0;
        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';
                solverec(horz, vert, i+1);
                *top = old_top;
                *bottom = old_bottom;
            }
        }
        else if (right)
        {
            if (*top != '1')
            {
                *top = '0';
                if (*bottom != '1')
                {
                    *bottom = '0';
                    solverec(horz, vert, i+1);
                    *bottom = old_bottom;
                }
                *top = '0';
                if (*bottom != '0')
                {
                    *bottom = '1';
                    solverec(horz, vert, i+1);
                    *bottom = old_bottom;
                }
                *top = old_top;
            }
            if (*top != '0')
            {
                *top = '1';
                if (*bottom != '1')
                {
                    *bottom = '0';
                    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
        {
            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;
    }
}

int main(int argc, char *argv[])
{
    fout = 0; //fopen("StreetTilings.txt", "wt");
    
    for (area = 1; area <= 15; 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);
                    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] = '?';
                                solverec(horz, vert, 0);    
                            }
                    }
                }
            }
        printf("%d,", count);
    }
    if (restrict_on_repeat) printf(" repeat");
    if (restrict_on_size) printf(" size");
    if (restrict_on_H_shape) printf(" H");
    if (restrict_on_cross) printf(" cross");
    printf("\n");
}