#include <stdio.h>

#define BIT(V,N) (((V) & (N)) != 0)

bool possible_unfold(int a) { return a == 0 || (a >= 16 && a != 24 && a != 29); }

bool straight_unfold(int a) { return a == 0 || a == 16 || a == 18 || a == 26; }

int rotate_unfold(int a)
{
    return ((a & 1) << 4) | (a & 2) | ((a & 4) << 1) | ((a & 8) >> 3) | ((a & 16) >> 2);
}

int bits_set(int a) { return (a & 1) + ((a >> 1) & 1) + ((a >> 2) & 1) + ((a >> 3) & 1) + ((a >> 4) & 1); }

void print_unfold(int a)
{
    printf(" %d%d%d%d%d", (a >> 4) & 1, a & 1, (a >> 1) & 1, (a >> 2) & 1, (a >> 3) & 1);
}

struct Tile
{
    int i;
    int j;
    int k;
    int k_mode;
    int l;
    int l_mode;
    bool is_empty;
    Tile *next;
    Tile(int n_i, int n_j, int n_k, int n_k_mode, int n_l, int n_l_mode, Tile *n_next)
     : i(n_i), j(n_j), k(n_k), k_mode(n_k_mode), l(n_l), l_mode(n_l_mode), is_empty(i == 0 && j == 0 && k == 0 && l == 0), next(n_next) {}
};

Tile *tiles[32][4][32][4];

    int unfold_invert[32];

int nr_tiles = 0;
void gen_tiles()
{
    for (int i = 0; i < 16; i++)
        unfold_invert[i] = 0;
    for (int i = 16; i < 32; i++)
        unfold_invert[i] =   (i & 16)
                           | ((i & 1) ? 0 : 4) 
                           | ((i & 2) ? 0 : 8) 
                           | ((i & 4) ? 0 : 1) 
                           | ((i & 8) ? 0 : 2);

    for (int i = 0; i < 32; i++)
        for (int i_mode = 0; i_mode < 4; i_mode++)
            for (int j = 0; j < 32; j++)
                for (int j_mode = 0; j_mode < 4; j_mode++)
                    tiles[i][i_mode][j][j_mode] = 0;
    tiles[0][0][0][0] = new Tile(0, 0, 0, 0, 0, 0, 0);
    
    for (int i = 0; i < 32; i++)
        if (possible_unfold(i))
        {
            int i_rot = rotate_unfold(i);
            
            for (int j = 0; j < 32; j++) 
                if (possible_unfold(j) && (i_rot & j) == 0)
                {
                    int ij_rot = rotate_unfold(i_rot | j);
                    
                    for (int k = 0; k < 32; k++)
                        if (possible_unfold(k) && (ij_rot & k) == 0)
                        {
                            int ijk_rot = rotate_unfold(ij_rot | k);
                            
                            int l = 31 & ~ijk_rot;
                            if (possible_unfold(l))
                            {
                                for (int i_mode = 0; i_mode < 4; i_mode++)
                                {
                                    int k_mode = k == 0 ? 0 : i_mode | (j != 0 ? 1 : 0) | (l != 0 ? 2 : 0); 
                                    if (   (i_mode != 0 || straight_unfold(i))
                                        && (k_mode != 3 || straight_unfold(k))
                                        && ((i_mode & 1) == 0 || j == 0)
                                        && ((i_mode & 2) == 0 || l == 0)) 
                                    {
                                        for (int j_mode = 0; j_mode < 4; j_mode++)
                                        {
                                            int l_mode = l == 0 ? 0 : j_mode | (i != 0 ? 1 : 0) | (k != 0 ? 2 : 0); 
                                            if (   (j_mode != 0 || straight_unfold(j))
                                                && (l_mode != 3 || straight_unfold(l))
                                                && ((j_mode & 1) == 0 || i == 0)
                                                && ((j_mode & 2) == 0 || k == 0)) 
                                            {
                                                /*
                                                print_unfold(i); printf(" (%d)", i_mode);
                                                print_unfold(j); printf(" (%d)", j_mode);
                                                print_unfold(k); printf(" (%d)", k_mode);
                                                print_unfold(l); printf(" (%d)", l_mode);
                                                printf(" |");
                                                print_unfold(unfold_invert[k]);
                                                print_unfold(unfold_invert[l]);
                                                printf("\n");
                                                //*/
                                                tiles[i][i_mode][j][j_mode] = new Tile(i, j, unfold_invert[k], k_mode, unfold_invert[l], l_mode, tiles[i][i_mode][j][j_mode]);
                                                nr_tiles++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                }
        } 
}

#define N 20
#define MAX_NR 1000

struct ColumnList;

struct Column
{
    int values[N];
    int modes[N];
    int min_nr_empty;
    bool empties[12];
    bool reachable;
    ColumnList *next_columns;
    ColumnList *prev_columns;
    Column *next;
    Column() : min_nr_empty(MAX_NR), next_columns(0), prev_columns(0), reachable(false), next(0)
    {
        for (int i = 0; i < N; i++)
            values[i] = modes[i] = 0;
        for (int i = 0; i < 12; i++)
            empties[i] = 0;
    }
};

struct ColumnList
{
    Column* prev_column;
    Column* next_column;
    int nr_empty;
    ColumnList *next_columns;
    ColumnList *prev_columns;
    int values[N-1];
    ColumnList(Column* n_prev_column, Column* n_next_column, int n_nr_empty) 
     : prev_column(n_prev_column), next_column(n_next_column), nr_empty(n_nr_empty)
    {
        next_columns = prev_column->next_columns;
        prev_column->next_columns = this;
        prev_columns = next_column->prev_columns;
        next_column->prev_columns = this;
    }
};


Column *columns = 0;
int nr_columns = 1;
int nr_transitions = 0;

void expand_column(Column* column, int p, int n, int j, int j_mode, int nr_empty, Tile *sel_tiles[])
{
    if (p == n)
    {
        //printf("%d with ", p);
        //print_unfold(j);
        //printf("\n");
        if (j == 0)
        {
            /*
            printf("--\n");
            for (int q = 0; q < n; q++)
            {
                printf("             "); 
                print_unfold(sel_tiles[q]->j);
                printf("\n");
                print_unfold(column->values[p]);
                printf(" ");
                print_unfold(sel_tiles[q]->i);
                printf("   %d   ", sel_tiles[q]->is_empty ? 0 : 1);
                print_unfold(unfold_invert[sel_tiles[q]->k]);
                printf(" ");
                print_unfold(sel_tiles[q]->k);
                printf("\n");
                printf("             "); 
                print_unfold(unfold_invert[sel_tiles[q]->l]);
                printf("\n");
            }
            //*/
            /*
            printf("--\n");
            for (int q = 0; q < n; q++)
            {
                if (q > 0)
                    printf("\n");
                #define BITV(L,V) BIT(sel_tiles[q]->L,V)
                #define BITU(L,V) BIT(unfold_invert[sel_tiles[q]->L],V)
                printf("      %d\n", BITV(j, 8));
                printf("      %d\n", BITV(j, 2));
                printf("     %d%d%d\n", BITV(j, 4), BITV(j, 16), BITV(j, 1));
                printf("    %d   %d     %d\n", BITV(i,1), BITU(k, 4), BITV(k, 1));
                printf("%d %d%d%d %d %d%d%d %d%d%d %d\n", column->modes[q], BITV(i, 8), BITV(i, 2), BITV(i, 16), sel_tiles[q]->is_empty ? 0 : 1,
                        BITU(k,16), BITU(k,2), BITU(k,8), BITV(k,8), BITV(k,2), BITV(k,16), sel_tiles[q]->k_mode); 
                printf("    %d   %d     %d\n", BITV(i,4), BITU(k, 1), BITV(k, 4));
                printf("     %d%d%d\n", BITU(l, 1), BITU(l, 16), BITU(l, 4));
                printf("      %d\n", BITU(l, 2));
                printf("      %d\n", BITU(l, 8));
            }
            //*/
            /*
            printf(" --> ");
            for (int q = 0; q < n; q++)
                print_unfold(sel_tiles[q]->k);
            printf("\n");
            */
            nr_transitions++;
            Column** ref_column = &columns;
            for (; *ref_column != 0; ref_column = &(*ref_column)->next)
            {
                bool equal = true;
                for (int q = 0; q < n; q++)
                    if (   (*ref_column)->values[q] != sel_tiles[q]->k
                        || (*ref_column)->modes[q] != sel_tiles[q]->k_mode)
                    {
                        equal = false;
                        break;
                    }
                if (equal)
                {
                    //printf("equal\n");
                    break;
                }
            }
            if (*ref_column == 0)
            {
                //printf("New\n");
                nr_columns++;
                (*ref_column) = new Column();
                for (int q = 0; q < n; q++)
                {
                    (*ref_column)->values[q] = sel_tiles[q]->k;
                    (*ref_column)->modes[q] = sel_tiles[q]->k_mode;
                }
            }
            if ((*ref_column)->min_nr_empty > column->min_nr_empty + nr_empty)
                (*ref_column)->min_nr_empty = column->min_nr_empty + nr_empty;
            ColumnList *trans = new ColumnList(column, *ref_column, nr_empty);
            for (int q = 0; q < n - 1; q++)
                trans->values[q] = sel_tiles[q]->l;
        }        
        return;
    }
    
    int i = column->values[p];
    int i_mode = column->modes[p];
    //printf("%*.*s", p * 2, p * 2, "");
    //print_unfold(i);
    //print_unfold(j);
    //printf("\n");
    for (Tile *tile = tiles[i][i_mode][j][j_mode]; tile != 0; tile = tile->next)
    {
        //printf("%*.*s", p * 2, p * 2, "");
        //printf(" use ");
        //print_unfold(i);
        //print_unfold(j);
        //print_unfold(unfold_invert[tile->k]);
        //print_unfold(unfold_invert[tile->l]);
        //printf("\n");

        sel_tiles[p] = tile;
        expand_column(column, p + 1, n, tile->l, tile->l_mode, nr_empty + (tile->is_empty ? 1 : 0), sel_tiles);
    }
} 

void build_graph(int n)
{
    columns = new Column();
    columns->min_nr_empty = 0;
    columns->empties[0] = true;
    int nr = 0;
    for (Column *column = columns; column != 0; column = column->next)
    {
        /*
        printf("Processing ");
        for (int i = 0; i < n; i++)
            print_unfold(column->values[i]);
        printf("\n");
        */
        fprintf(stderr, "%c", column->min_nr_empty + 'a');
        if (nr % 100 == 0)
            printf("%d %d %d\n", nr, nr_columns, nr_transitions);
        nr++;
        Tile *sel_tiles[N];
        expand_column(column, 0, n, 0, 0, 0, sel_tiles);
    }
}

int height = 6;

Column *sel_columns[30];
ColumnList *sel_trans[30];

int length = 10;

void print_sols(Column *column, int depth, int nr_empty)
{
    sel_columns[depth] = column;
    if (depth == length || (depth > 0 && column == columns))
    {
        for (int d = 1; d <= depth; d++)
            printf("+--");
        printf("+\n");
        for (int h = 0; h < height; h++)
        {
            printf("|");
            for (int d = 1; d <= depth; d++)
                printf("  %c", sel_columns[d]->values[h] == 0 ? '|' : ' ');
            printf("\n");
            if (h < height - 1)
            {
                printf("+");
                for (int d = 0; d < depth; d++)
                    printf("%s+", sel_trans[d]->values[h] == 0 ? "--" : "  ");
                printf("\n");
            }
        }
        for (int d = 1; d <= depth; d++)
            printf("+--");
        printf("+\n\n");
        
        return;
    }
    
    if (nr_empty > 10)
        return;
    
    for (ColumnList *next_column = column->next_columns; next_column != 0; next_column = next_column->next_columns)
        if (next_column->next_column->reachable)
        {
            sel_trans[depth] = next_column;
            print_sols(next_column->next_column, depth + 1, nr_empty + next_column->nr_empty);
        }
}      

int main(int argc, char *argv[])
{    
    gen_tiles();
    printf("%d\n", nr_tiles);
    
    build_graph(height);
    printf("%d %d\n", nr_columns, nr_transitions);
    
    int nr_reachable = 1;
    columns->reachable = true;
    for (bool more = true; more;)
    {
        more = false;
        for (Column *column = columns; column != 0; column = column->next)
            if (column->reachable)
                for (ColumnList *trans = column->prev_columns; trans != 0; trans = trans->prev_columns)
                    if (!trans->prev_column->reachable)
                    {
                        trans->prev_column->reachable = true;
                        nr_reachable++;
                        more = true;
                    }
    }
    printf("%d\n", nr_reachable);
    
    
    //for (Column *column = columns; column != 0; column = column->next)
    //    printf("%4d %d\n", column->min_nr_empty, column->reachable);
    
    
    //print_sols(columns, 0, 0);
    
    return 0;
}