#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

char *strcopy(const char *s)
{
    char *r = (char*)malloc(strlen(s) + 1);
    strcpy(r, s);
    return r;
}
        
FILE *log_file = stdout;

#define N 20

int C[N][N];
bool Cr[N][N];
const char *Cname[N][N];
bool modified = true;

void set(int i, int j, int v, const char *name, bool by_rule)
{
    if (v > C[i][j] || (v == C[i][j] && by_rule && !Cr[i][j])) 
    {
        C[i][j] = C[j][i] = v;
        Cr[i][j] = Cr[j][i] = by_rule;
        Cname[i][j] = Cname[j][i] = strcopy(name);
        modified = true;
    }
}

void bprintC(char *s, int i, int j)
{
    s += strlen(s);
    if (i < j)
        sprintf(s, "C(%d,%d) [%s]", i, j, Cname[i][j]);
    else
        sprintf(s, "C(%d,%d) [%s]", j, i, Cname[j][i]);
}

void bprintF(char *s, char name, int n)
{
    if (n == 0)
        return;
    if (s[0] != '\0')
        strcat(s, ",");
    s += strlen(s);
    if (n == 1)
        sprintf(s, "%c", name);
    else
        sprintf(s, "%d%c", n, name);
}

typedef struct
{
    int x, y;
} coord_t;

coord_t foldings[11][6] = {
    { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 1, 1 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 1, 0 }, { 2, 1 }, { 1, 1 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 1, 0 }, { 2, 2 }, { 1, 1 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 1, 0 }, { 2, 3 }, { 1, 1 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 1 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 2 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 3 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 3 }, { 1, 2 }, { 2, 2 } },
    { { 0, 1 }, { 1, 0 }, { 2, 1 }, { 1, 1 }, { 1, 2 }, { 1, 3 } },
    { { 0, 1 }, { 1, 0 }, { 2, 2 }, { 1, 1 }, { 1, 2 }, { 1, 3 } },
    { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 3 }, { 1, 4 } },
};

typedef struct placement_s placement_t, *placement_p;
struct placement_s
{
    int nr;
    coord_t pos[5];
    placement_p next;
};

placement_p placements = 0;

void add_placement(coord_t *pos, int nr)
{
    for (placement_p placement = placements; placement != 0; placement = placement->next)
        if (memcmp(pos, placement->pos, 5 * sizeof(coord_t)) == 0)
            return;
    placement_p new_placement = new placement_t;
    new_placement->next = placements;
    new_placement->nr = nr;
    memcpy(new_placement->pos, pos, 5 * sizeof(coord_t));
    placements = new_placement;
}

int compare_max(const void* vl, const void* vr)
{
    coord_t *l = (coord_t*)vl;
    coord_t *r = (coord_t*)vr;
    int d = l->y - r->y;
    return d != 0 ? d : l->x - r->x;
}

const char *placement_names = "TABZCDEWKXS";

void build_placements()
{
    for (int i = 0; i < 11; i++)
    {
        coord_t points[6];
        for (int j = 0; j < 6; j++)
            points[j] = foldings[i][j];
        
        for (int r = 0; r < 8; r++)
        {
            qsort(points, 6, sizeof(coord_t), compare_max);
            
            coord_t pos[5];
            for (int j = 0; j < 6; j++)
            {
                pos[j].x = points[j+1].x - points[0].x;
                pos[j].y = points[j+1].y - points[0].y;
            }
            add_placement(pos, i);
            
            if (r % 2 == 0)
            {
                for (int j = 0; j < 6; j++)
                {
                    int h = points[j].x;
                    points[j].x = points[j].y;
                    points[j].y = h;
                }
            }
            else
            {
                for (int j = 0; j < 6; j++)
                    points[j].x = -points[j].x;
            }
        }
    }
}

#define FIELD_BORDER_SIZE 4

int min_x, max_x, min_y, max_y;
int field[100][100];
char fname[100][100];
int max_folds;
int init_max_folds;
int nr_folds[11];
int expand_pos[N];

struct Solution
{
    int n, m;
    int rep_width;
    int my_field[N][N];
    int my_expand_pos[N];
    int my_nr_folds[11];
    int nr_rep_folds[11];
    int tot_nr_folds;
    
    void print(FILE *f)
    {
        fprintf(f, "%d,%d: %d", n, m, tot_nr_folds);
        if (rep_width > 0)
            fprintf(f, "(%d +%d)", rep_width, nr_rep_folds[6] + nr_rep_folds[7] + nr_rep_folds[10]);
        fprintf(f, "\n");
            
        for (int x = 0; x < n; x++)
            fprintf(f, "+--");
        fprintf(f, "+\n");
        for (int y = 0; y < m; y++)
        {
            int prev = -1;
            for (int x = 0; x < n; x++)
            {
                int v = my_field[x][y];
                fprintf(f, "%c%s", x == my_expand_pos[y] ? '$' : v != prev ? '|' : ' ', v == 0 ? "##" : "  ");
                prev = v;
            }
            fprintf(f, "%c\n+", n == my_expand_pos[y] ? '$' : '|');
            for (int x = 0; x < n; x++)
            {
                if (y + 1 == m || my_field[x][y] != my_field[x][y + 1])
                    fprintf(f, "--+");
                else
                    fprintf(f, "  +");
            }
            fprintf(f, "\n");
        }
    }
    
    void store()
    {
        bool by_rule = tot_nr_folds == max_folds;
        int n_rep = n;
        for (int rep = 0; n_rep < N; rep++, n_rep += rep_width)
        {
            int nr = 0;
            char name[50];
            name[0] = '\0';
            for (int i = 0; i < 11; i++)
            {
                int v = my_nr_folds[i] + rep * nr_rep_folds[i];
                bprintF(name, placement_names[i], v);
                nr += v;
            }
            printf("set %d %d %d %s (%d)\n", n_rep, m, nr, name, n_rep * m - 6 * nr);
            set(n_rep, m, nr, name, by_rule);
            if (rep_width == 0)
                break;
        }
    }
    
    void load(int width, int nr_S, int nr_W, int nr_E)
    {
        rep_width = width;
        n = max_x - min_x;
        m = max_y - min_y;
        tot_nr_folds = 0;
        for (int i = 0; i < 11; i++)
        {
            my_nr_folds[i] = nr_folds[i];
            nr_rep_folds[i] = 0;
            tot_nr_folds += my_nr_folds[i];
        }
        nr_rep_folds[ 6] = nr_E * (width == 0 ? 0 : width == 3 ? 2 : 4);
        nr_rep_folds[ 7] = nr_W * (width == 0 ? 0 : width == 2 ? 1 : 3);
        nr_rep_folds[10] = nr_S * (width == 0 ? 0 : width == 3 ? 1 : 2);
    
        for (int x = min_x; x < max_x; x++)
            for (int y = min_y; y < max_y; y++)
                this->my_field[x - FIELD_BORDER_SIZE][y - FIELD_BORDER_SIZE] = field[x][y] < 0 ? 0 : field[x][y];
    
        for (int i = 0; i < max_y - min_y; i++)
            my_expand_pos[i] = width == 0 ? -1 : expand_pos[i];
    }
};

Solution sols[4];

int field_val(int x, int y) { return field[x][y] <= 0 ? 0 : field[x][y]; }

#define WALL(X1,Y1,X2,Y2) (field_val(X1,Y1) != field_val(X2,Y2))


bool down_wall(int x, int &y)
{
    if (WALL(x - 1, y, x, y))
    {
        expand_pos[y - FIELD_BORDER_SIZE] = x - FIELD_BORDER_SIZE;
        y++;
        return true;
    }
    return false;
}

bool left_wall(int &x, int y)
{
    if (WALL(x - 1, y - 1, x - 1, y))
    {
        x--;
        return true;
    }
    return false;
}

bool right_wall(int &x, int y)
{
    if (WALL(x, y - 1, x, y))
    {
        x++;
        return true;
    }
    return false;
}

bool found2, found3, found6;
void find_expansion_line(int x, int y, int nr_S, int nr_W, int nr_E)
{
    if (y == max_y)
    {
        bool w2 = nr_W > 0;
        bool w3 = nr_S > 0 || nr_E > 0;
        int i = -1;
        if (w2 && w3)
        {
            if (!found6)
            {
                found6 = true;
                sols[3].load(6, nr_S, nr_W, nr_E);
            }
        }
        else if (w2)
        {
            if (!found2)
            {
                found2 = true;
                sols[1].load(2, nr_S, nr_W, nr_E);
            }
        }
        else if (w3)
        {
            if (!found3)
            {
                found3 = true;
                sols[2].load(3, nr_S, nr_W, nr_E);
            }
        }
        return;
    }
    
    if (found6 && nr_W > 0 && (nr_S > 0 || nr_E > 0))
        return;
    
    for (int d = 0; d < 2; d++)
    {
        int x1 = x;
        do
        {
            int y1 = y;
            if ((d == 0 || x1 != x) && down_wall(x1, y1))
            {
                int x2, y2;
                
                #define LEFT_W left_wall(x2, y2)
                #define RIGHT_W right_wall(x2, y2)
                #define DOWN_W down_wall(x2, y2)
                x2 = x1; y2 = y1;
                if (!found3 && LEFT_W  && LEFT_W  && DOWN_W) find_expansion_line(x2, y2, nr_S + 1, nr_W, nr_E);
                    
                x2 = x1; y2 = y1;
                if (!found3 && RIGHT_W && RIGHT_W && DOWN_W) find_expansion_line(x2, y2, nr_S + 1, nr_W, nr_E);

                x2 = x1; y2 = y1;
                if (!found2 && LEFT_W  && DOWN_W && LEFT_W  && DOWN_W) find_expansion_line(x2, y2, nr_S, nr_W + 1, nr_E);

                x2 = x1; y2 = y1;
                if (!found2 && RIGHT_W && DOWN_W && RIGHT_W && DOWN_W) find_expansion_line(x2, y2, nr_S, nr_W + 1, nr_E);
                
                x2 = x1; y2 = y1;
                if (!found3 && DOWN_W && LEFT_W  && DOWN_W && DOWN_W) find_expansion_line(x2, y2, nr_S, nr_W, nr_E + 1);

                x2 = x1; y2 = y1;
                if (!found3 && DOWN_W && RIGHT_W && DOWN_W && DOWN_W) find_expansion_line(x2, y2, nr_S, nr_W, nr_E + 1);

                x2 = x1; y2 = y1;
                if (!found3 && LEFT_W  && DOWN_W && DOWN_W && LEFT_W  && DOWN_W) find_expansion_line(x2, y2, nr_S, nr_W, nr_E + 1);

                x2 = x1; y2 = y1;
                if (!found3 && RIGHT_W && DOWN_W && DOWN_W && RIGHT_W && DOWN_W) find_expansion_line(x2, y2, nr_S, nr_W, nr_E + 1);
            }
        }
        while (d == 0 ? left_wall(x1, y) : right_wall(x1, y));
    }
}

int nr_call_find_expansion_line = 0;

void find_sol(int folds, int mark_for_this_depth)
{
    if (folds >= max_folds)
    {
        if (folds > max_folds)
        {
            found2 = false;
            found3 = false;
            found6 = false;
            max_folds = folds;
            sols[0].load(0, 0, 0, 0);
        }
        if (folds > 0)
        {
            nr_call_find_expansion_line++;
            if (nr_call_find_expansion_line % 100 == 0)
                printf("find expansion lines for %d,%d  %d  %d %d %d (%d)\n", max_x - min_x, max_y - min_y, folds, found2, found3, found6, nr_call_find_expansion_line);
            find_expansion_line(min_x, min_y, 0, 0, 0);
        }
    }

    // Find the position with the lowest number of placements
    for (int x2 = min_x; x2 < max_x; x2++)
        for (int y2 = min_y; y2 < max_y; y2++)
            if (field[x2][y2] == 0)
                field[x2][y2] = mark_for_this_depth;
    int x = -1, y = -1;
    int open_left = 0;
    for (int x2 = min_x; x2 < max_x; x2++)
        for (int y2 = min_y; y2 < max_y; y2++)
            if (field[x2][y2] == 0 || field[x2][y2] == mark_for_this_depth)
            {
                int nr_pos = 0;
                for (placement_p placement2 = placements; placement2 != 0; placement2 = placement2->next)
                {
                    bool possible = true;
                    for (int i = 0; i < 5; i++)
                        if (field[x2 + placement2->pos[i].x][y2 + placement2->pos[i].y] > 0)
                        {
                            possible = false;
                            break;
                        }
                    if (possible)
                    {
                        nr_pos++;
                        for (int i = 0; i < 5; i++)
                            if (field[x2 + placement2->pos[i].x][y2 + placement2->pos[i].y] == mark_for_this_depth)
                            {
                                open_left++;
                                field[x2 + placement2->pos[i].x][y2 + placement2->pos[i].y] = 0;
                            }
                    }
                }
                if (nr_pos > 0)
                {
                    if (field[x2][y2] == mark_for_this_depth)
                    {
                        open_left++;
                        field[x2][y2] = 0;
                    }
                
                    if (x == -1)
                    {
                        x = x2;
                        y = y2;
                    }
                }
            }            

    if (x != -1)
    {
        if (folds + open_left / 6 > max_folds || (max_folds > init_max_folds && folds + open_left / 6 == max_folds))
        {
            for (placement_p placement = placements; placement != 0; placement = placement->next)
            {
                bool possible = true;
                for (int i = 0; i < 5; i++)
                    if (field[x + placement->pos[i].x][y + placement->pos[i].y] != 0)
                    {
                        possible = false;
                        break;
                    }
                if (possible)
                {
                    nr_folds[placement->nr]++;
                    int v = 10 + folds;
                    char name = placement_names[placement->nr];
                    field[x][y] = v;
                    fname[x][y] = name;
                    for (int i = 0; i < 5; i++)
                    {
                        field[x + placement->pos[i].x][y + placement->pos[i].y] = v;
                        fname[x + placement->pos[i].x][y + placement->pos[i].y] = name;
                    }
    
                    find_sol(folds + 1, mark_for_this_depth - 1);
    
                    field[x][y] = 0;
                    for (int i = 0; i < 5; i++)     
                        field[x + placement->pos[i].x][y + placement->pos[i].y] = 0;
                    nr_folds[placement->nr]--;
                }
            }
        }
        if (folds + (open_left - 1) / 6 > max_folds || (max_folds > init_max_folds && folds + (open_left - 1) / 6 == max_folds))
        {
            field[x][y] = mark_for_this_depth;
            find_sol(folds, mark_for_this_depth - 1);
            field[x][y] = 0;
        }
    }
    
    for (int x2 = min_x; x2 < max_x; x2++)
        for (int y2 = min_y; y2 < max_y; y2++)
            if (field[x2][y2] == mark_for_this_depth)
                field[x2][y2] = 0;
}

void find_max_depth(int n, int m)
{
    min_x = FIELD_BORDER_SIZE;
    max_x = min_x + m;
    min_y = FIELD_BORDER_SIZE;
    max_y = min_y + n;
    
    for (int x = 0; x < m + 10; x++)
        for (int y = 0; y < n + 10; y++)
            field[x][y] = (min_x <= x && x < max_x && min_y <= y && y < max_y) ? 0 : 1;
    
    init_max_folds = max_folds;
    for (int i = 0; i < 4; i++)
        sols[i].tot_nr_folds = 0;
        
    for (int i = 0; i < 11; i++)
        nr_folds[i] = 0;
    
    found2 = false;
    found3 = false;
    found6 = false;
    nr_call_find_expansion_line = 0;

    find_sol(0, -1);

    if (sols[0].tot_nr_folds > sols[1].tot_nr_folds && sols[0].tot_nr_folds > sols[2].tot_nr_folds && sols[0].tot_nr_folds > sols[3].tot_nr_folds)
    {
        sols[0].print(stdout);
        sols[0].print(log_file); fflush(log_file);
        sols[0].store();
    }
    if (sols[1].tot_nr_folds > 0)
    {
        sols[1].print(stdout);
        sols[1].print(log_file); fflush(log_file);
        sols[1].store();
    }
    if (sols[2].tot_nr_folds > 0)
    {
        sols[2].print(stdout);
        sols[2].print(log_file); fflush(log_file);
        sols[2].store();
    }
    if (sols[3].tot_nr_folds > 0 && sols[1].tot_nr_folds == 0 && sols[2].tot_nr_folds == 0)
    {
        sols[3].print(stdout);
        sols[3].print(log_file); fflush(log_file);
        sols[3].store();
    }
}

int main(int argc, char *argv[])
{
    build_placements();

    log_file = fopen("CubesFromSheet.txt", "w");
        
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            C[i][j] = 0;
            Cr[i][j] = false;
            Cname[i][j] = "";
        }
            
    char name[3000];
    
    int n = 2;
    int m = 2;
    int area = 16;
    bool do_print = true;
    for (;;)
    {
        if (modified)
        {
            modified = false;
    
            for (int i = 1; i < N; i++)
                for (int j = 1; j < N; j++)
                    if (C[i][j] < C[i-1][j])
                    {
                        name[0] = '\0';
                        bprintC(name, i-1, j);
                        set(i, j, C[i-1][j], name, false);
                    }
    
            for (int i = 3; i < N; i++)
            {
                for (int i1 = i / 2; i1 > 1; i1--)
                {
                    for (int j = 2; j < N; j++)
                    {
                        sprintf(name, "%d.", i1);
                        bprintC(name, 2, j);
                        if (i - i1 * 2 > 0)
                        {
                            strcat(name, " + ");
                            bprintC(name, i - i1 * 2, j);
                        }
                        set(i, j, i1*C[2][j] + C[i - i1 * 2][j], name, false);
                    }
                }
            }
        
            for (int i = 2; i < N; i++)
                for (int i1 = 1; i1 + i1 <= i; i1++)    
                    for (int j = 2; j < N; j++)
                    {
                        name[0] = '\0';
                        bprintC(name, i1, j);
                        strcat(name, " + ");
                        bprintC(name, i - i1, j);
                        set(i, j, C[i1][j] + C[i - i1][j], name, false);
                    }
                    
            for (int i = 5; i < N; i += 2)
                for (int j = 6; j < N; j += 2)
                {
                    int v = (i + j - 5) / 2;
                    sprintf(name, "X: %d.W + ", v);
                    bprintC(name, i-3, j-3);
                    v += C[i-3][j-3];
                    set(i, j, v, name, false);
                }
            do_print = true;
        }
        else
        {
            if (do_print)
            {
                FILE *table_file = fopen("CubesFromSheetResults.txt", "w");
                fprintf(table_file, "   |");
                for (int i = 2; i < N; i++)
                    fprintf(table_file, "%4d", i);
                fprintf(table_file, "\n---+");
                for (int i = 2; i < N; i++)
                    fprintf(table_file, "----");
                fprintf(table_file, "\n");
                for (int i = 2; i < N; i++)
                {
                    fprintf(table_file, "%2d |", i);
                    for (int j = 2; j < N; j++)
                        if (C[i][j] == 0)
                            fprintf(table_file, "    ");
                        else
                            fprintf(table_file, "%4d", C[i][j]);
                    fprintf(table_file, "\n");
                }
            
                for (int j = 2; j < N; j++)
                    for (int i = j; i < N; i++)
                        if (C[i][j] > 0)
                        {
                            fprintf(table_file, "C(%d,%d) = %d {%d} = %s\n", j, i, C[i][j], i * j - 6 * C[i][j], Cname[i][j]);
                        }
                fclose(table_file);
                
                do_print = false;
            }
            
#ifdef BY_INCREASING_AREA                
            for (;;)
            {
                n++;
                if (n * n > area)
                {
                    area++;
                    if (area > N * N)
                        return 0;
                    n = 2;
                }
                else if (area % n == 0)
                {
                    int m = area / n;
                    
                    if (m < N)
                    {
                        printf("Search all folds for %d, %d\n", n, m);
                        fprintf(log_file, "Search all folds for %d, %d\n", n, m);
                        fflush(log_file);
                        max_folds = C[n][m];
                        find_max_depth(n, m);
                        sprintf(name, "seached %d", max_folds);
                        set(n, m, max_folds, name, false);
                        break;
                    }
                }
            }
#else
            for (;;)
            {
                m++;
                if (m >= N)
                {
                    n++;
                    if (n >= N)
                        return 0;
                    m = n;;
                }
                if (n * m > 6 && !Cr[n][m])
                {
                    printf("Search all folds for %d, %d\n", n, m);
                    fprintf(log_file, "Search all folds for %d, %d\n", n, m);
                    fflush(log_file);
                    max_folds = C[n][m];
                    find_max_depth(n, m);
                    sprintf(name, "seached %d", max_folds);
                    set(n, m, max_folds, name, false);
                    break;
                }
            }
#endif
        }
    }
    
}