Piet (Mondrian)'s Puzzle

Question

For more information, watch this video, and go to A276523 for a related sequence.

The Mondrian Puzzle (for an integer n) is the following:

Fit non-congruent rectangles into a n*n square grid. What is the smallest difference possible between the largest and the smallest rectangle?

For 6, the optimal difference for M(6) is 5, and can be demonstrated like so:

 ___________
| |S|_______|
| | |   L   |
| |_|_______|
| |     |   |
| |_____|___|
|_|_________| (fig. I)

The largest rectangle (L) has an area of 2 * 4 = 8, and the smallest rectangle (S) has an area of 1 * 3 = 3. Therefore, the difference is 8 - 3 = 5.

Keep in mind that currently, no optimal solutions for n > 44 have been found.

Your task is to create a program that generates a Mondrian grid that contains a (non-optimal) solution, given an integer n.

You will be tested on the numbers from 100 to 150. Your score for each test will be the difference between the largest and smallest rectangle. Your total score is the sum of your scores for all the tests from 100 to 150.

You must present your output like so:

{number}
{grid}

Where number is the score (the difference between largest and smallest), and grid is either:

• A multi-lined string, or
• A two-dimensional list.

The grid MUST clearly show where a rectangle starts and ends.

Rules:

• Your program must fit within your answer.
• Your program must output a value for any number between 100 and 150 within 1 hour on a modern laptop.
• Your program must generate the same solution for an integer n every time the program is run.
• You must provide a link to the outputs of all 51 solutions (using Pastebin, Github Gist... anything, really).
• You must have at least two rectangles on the square grid for your solution.

Answer 1

Piet, 9625

(It finally works!)

The people demanded it, so here it is. This is an extremely naive solution (essentially the same as the loose upper bounds on the OEIS page): it divides each square into just two rectangles.

This gist contains the details in two files:

• The program's output (using npiet v1.3) for all required inputs. Note that I only captured stdout, so the ? is the input prompt, followed immediately by the output score, then the grid.
• The "pseudo-assembly" source I used to plan out the program.

Explanation

This program takes a single number N as input. If the number is odd, the score is the number; if even, the score is twice the number.

After outputting the score, the rest of the left-hand side of the program is spent filling the stack with five lots of the following information:

• The grid width (which is N)
• A number of lines to print
• A character to print across the grid (either _ or space)
• A character to print at each edge of the grid (either space or |)

The right-hand side of the program takes each set of four values and prints out that part of the grid.

Answer 2

C 6108

This uses a recursive (really iterative) version of the minimal solution. Instead of dividing the square into two rectangles where one is a little bit bigger than half the area, it divides it into N rectangles. So the first rectangle is a bit larger than 1/N the total area. Then taking the remainder, the program splits off a rectangle a bit larger than 1/(N-1) of the remainder and so on until it just takes the remainder as the last rectangle. The rectangles are cut off of the remainder in a clockwise spiral, so first at the top, then on the right, etc.

Since this a very direct method instead of a search of a broad space, it runs quickly - taking about 25 seconds (on a Raspberry Pi) to look at 74 solutions each for the given problem set.

My intent is to use these results to better inform a search algorithm for a more sophisticated approach.

The output gives the score and both an (ascii) drawing and coordinates for the vertices of the rectangles. The vertices are in clockwise order, starting from the upper left hand corner of the rectangle in question.

Developed using gcc 4.9.2-10.

Results at https://github.com/JaySpencerAnderson/mondrian

Code:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
    int y, x, height, width;
} rectangle;
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#ifndef TRUE
#define TRUE -1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#define MAXCOUNT 75

void initstack(rectangle *s, int n){
    int i;
    for(i=0;i<n;i++){
        s[i].y=s[i].x=s[i].height=s[i].width=0;
    }
}
int valid(rectangle *s,int n){
    int i,j;
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            if(min(s[i].height,s[i].width) == min(s[j].height,s[j].width) && max(s[i].height,s[i].width) == max(s[j].height,s[j].width)){

                initstack(s, n);
                return FALSE;
            }
        }
    }
    return TRUE;
}
int horizontal(rectangle s, int y, int x){
    if(s.y == y && x >= s.x && x < s.x+s.width){
        return TRUE;
    }
    else if(s.y+s.height == y && x >= s.x && x < s.x+s.width){
        return TRUE;
    }
    return FALSE;
}
int vertical(rectangle s, int y, int x){
    if(s.x == x && y > s.y && y <= s.y+s.height){
        return TRUE;
    }
    else if(s.x+s.width == x && y > s.y && y <= s.y+s.height){
        return TRUE;
    }
    return FALSE;
}
void graph(rectangle *s, int n, int side){
    unsigned int row,col,i;
    unsigned int line;
    printf("{\n");
/* vertical lines take precedence since "1" cell is 1 char high and 2 char wide */
    for(row=0;row<=side;row++){
        for(col=0;col<=side;col++){
            line=0;
/* Possible values are "  " (0), "__" (1), "| " (2) or "|_" (3). */
            for(i=0;i<n;i++){
                if(horizontal(s[i],row,col)){
                    line|=1;
                }
                if(vertical(s[i],row,col)){
                    line|=2;
                }
            }
            
            switch(line){
            case 0: printf("  ");   break;
            case 1: printf("__");   break;
            case 2: printf("| ");   break;
            case 3: printf("|_");   break;
            default: printf("##");  break;
            }
        }
        printf("\n");
    }
    printf("}\n");
}
unsigned int score(rectangle *s, int n){
    int i;
    unsigned int smallest,biggest;

    smallest=biggest=s[0].width*s[0].height;

    for(i=0;i<n;i++){
        smallest=min(smallest,s[i].width*s[i].height);
        biggest=max(biggest,s[i].width*s[i].height);
    }
    return biggest-smallest;
}
void report(rectangle *s, int n, int side){
    int i;

    printf("{%d}\n",score(s,n));
    graph(s, n, side);
    printf("{\n");
    for(i=0;i<n;i++){
        printf("[%d,%d] ",s[i].x,s[i].y);
        printf("[%d,%d] ",s[i].x+s[i].width,s[i].y);
        printf("[%d,%d] ",s[i].x+s[i].width,s[i].y+s[i].height);
        printf("[%d,%d]\n",s[i].x,s[i].y+s[i].height);
    }
    printf("\n}\n");
}
void locateandrotate(rectangle *stack, int n){
    unsigned int scratch,i;
    for(i=1;i<n;i++){
        /* Odd rectangles are on their side */
        if(i&1){
            scratch=stack[i].width;
            stack[i].width=stack[i].height;
            stack[i].height=scratch;
        }
        switch(i%4){
        case 0:
            stack[i].x=stack[i-1].x+stack[i-1].width;
            stack[i].y=stack[i-1].y;
            break;
        case 1:
            stack[i].x=stack[i-1].x+stack[i-1].width-stack[i].width;
            stack[i].y=stack[i-1].y+stack[i-1].height;
            break;
        case 2:
            stack[i].x=stack[i-1].x-stack[i].width;
            stack[i].y=stack[i-1].y+stack[i-1].height-stack[i].height;
            break;
        case 3:
            stack[i].x=stack[i-1].x;
            stack[i].y=stack[i-1].y-stack[i].height;
            break;
        default:
            printf("Woops!\n");
        }
    }
}
/* These are the height and width of the remaining area to be filled. */
void door(rectangle *stack, unsigned int height, unsigned int width, unsigned int n, unsigned int totaln){
    unsigned int thisheight, thiswidth;
    int i;

    for(i=0;i<totaln;i++){
/* Not yet used */
        if(stack[i].width == 0){
            stack[i].width=width;
            if(i+1 == totaln){
                stack[i].height=height;
            }
            else {
/* Sometimes yields congruent rectangles, as with 16x16, 8 rectangles */
                if(totaln&1 || height%n){
                    int j;
                    stack[i].height=height-(((n-1)*height)/n);
                }
                else {
                    stack[i].height=height-((((n-1)*height)-1)/n);
                }
                /* Exchange height and width to rotate */
                door(stack,width,height-stack[i].height,n-1,totaln);
            }
            return;
        }
    }
}
void usage(char *argv[],int side){
    printf("Usage: %s -s <side-length>\n",argv[0]);
    printf("Purpose: Calculate N non-congruent rectangles arranged to exactly fill a square with the specified side length.\n");
    printf("Defaults: %s -s %d\n",argv[0],side);
    exit(0);
    
}
int main(int argc, char *argv[]){
    int side=16;
    int n,bestscore,bestn=2;
    int status;

    while((status=getopt(argc,argv,"s:h")) >= 0){
        switch(status){
        case 's':
            sscanf(optarg,"%d",&side);
            break;
        case 'h':
        default:
            usage(argv,side);
        }
    }

    bestscore=side+side;
    
    rectangle stack[MAXCOUNT],best[MAXCOUNT];
    for(n=2;n<=MAXCOUNT;n++){
        initstack(stack,MAXCOUNT);
        door(stack, side, side, n, n);
        locateandrotate(stack, n);
        if(valid(stack,n)){
            if(score(stack,n) < bestscore){
                bestn=n;
                initstack(best,MAXCOUNT);
                door(best, side, side, n, n);
                locateandrotate(best, n);
                
                bestscore=score(best,n);
            }
        }
    }
    report(best,bestn,side);
}

Answer 3

C - 2982

This program implements a search through a broad results set. The important part of making this search practical was to fail early and/or not go down bad paths.

This generates a set of rectangles to be considered for the solution. The set of rectangles generated avoids those with dimensions that would not be useful. For instance, if the program is trying to find the solution to a 128x128 square, divided into 8 rectangles, it will generate a rectangle that is 128x16. It will not generate that one is 120x17 because there is no prospect of a generating rectangle that is 8 wide to fill in the gap at the end of 120.

The initial strategy for placing rectangles is to place them on the inside of the perimeter of the square (buildedge function). In that way, the algorithm gets pretty quick feedback at each corner as to whether there is a problem with the sequence chosen. While placing rectangles, the logic keeps watching to see if any gaps of space develop which are too narrow for any rectangle. After the perimeter has been populated successfully, the strategy changes to trying to match the space remaining with the remaining rectangles (match function).

One other thing that might be of interest is that this implements transactions with rollback for the stacks of rectangles.

This program doesn't try to find the best possible fit. It is given a budget (64) and quits when it finds the first solution. If it never finds a solution, we bump up the budget (by 16) and try again. The time required (on a Dell laptop with an I7 processor) ranged from well under a minute to 48 minutes for 150 on a side (149 on a side took less than 2 minutes). All 51 solutions used 11 rectangles. The scores of the 51 solutions ranged from 41 to 78. The reasons I used 11 rectangles were that the score was lower than with fewer rectangles and it looked like 12 rectangles would take much more than the hour allotted.

The solutions and code may be found at https://github.com/JaySpencerAnderson/mondrian . They are the two my4* files.

BTW, if you compile this to "my4" and execute it as follows: "./my4 -h", it will give you usage. If you want to see it in action working away, try something like "./my4 -l 50 -n 8". If you change the one "#if 0" to "#if 1" it will render the remaining space on the screen. If you want to change this to render the rectangles, look for the one spot where the code executes "graph(space,side)" and change that to "graph(callstack,side)" instead. I'd also suggest changing the initial budget from 64 to 32 if you want to play around with solutions for squares that are about 50 wide. The solution for smaller squares will have a better score with a smaller budget.

The program below is functional. Check github for the complete code (with usage, comments, etc).

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
    int y, x, height, width, created, deleted;
} rectangle;
#define NOTYET -1
#define TOPEDGE 1
#define RIGHTEDGE 2
#define BOTTOMEDGE 4
#define LEFTEDGE 8
#define CENTER 16
#define nextEdge(e) (e<<=1)
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#define MAXFACTORS 1000
#define EOL printf("\n")
#define isCurrent(r) (r.created != NOTYET && r.deleted == NOTYET)
#define deleteTxn(r,t) (r.deleted=t)
int area(rectangle r){
    return r.width*r.height;
}
void pop(rectangle *s){
    unsigned int k=0;
    while(s[k].width){
        k++;
    }
    s[k-1].width=s[k-1].height=0;
}
void rpush(rectangle *s, rectangle x){
    unsigned int k=0;
    while(s[k].width){
        k++;
    }
    x.deleted=NOTYET;
    s[k++]=x;
    s[k].width=s[k].height=0;

    return;
}
void dumprectangle(rectangle r){
    printf("%dX%d@[%d,%d] (%d,%d)\t",r.width, r.height, r.x, r.y, r.created, r.deleted);
}
void dumpstack(rectangle *s){
    unsigned int k=0;
    while(s[k].width){
        dumprectangle(s[k]);
        k++;
    }
}
rectangle initrectangle(int width, int height){
    rectangle r;
    r.x=r.y=0;
    r.width=width;
    r.height=height;
    r.created=0;
    r.deleted=NOTYET;
    return r;
}
void initstack(rectangle *s, int n){
    int i;
    for(i=0;i<n;i++){
        s[i].y=s[i].x=s[i].height=s[i].width=0;
    }
}
int bitcount(int x){
    int count=0;
    while(x){
        if(x&1){
            count++;
        }
        x>>=1;
    }
    return count;
}
int congruent(rectangle a, rectangle b){
    return min(a.height,a.width) == min(b.height,b.width) && max(a.height,a.width) == max(b.height,b.width);
}
void report(rectangle *s, int side){
    int i;
    unsigned int smallest,biggest,area=0;

    smallest=side*side;
    biggest=0;

    for(i=0;s[i].width;i++){
        if(isCurrent(s[i])){
            smallest=min(smallest,s[i].width*s[i].height);
            biggest=max(biggest,s[i].width*s[i].height);
        }
    }
    printf("{%d}\n",biggest-smallest);
    printf("{\nDimensions\tLocation\n");
    for(i=0;s[i].width;i++){
        printf("%dx%d\t\t[%d,%d]\n",
            s[i].width,         s[i].height,
            s[i].x,             s[i].y);
    }
    printf("}\n");
}
unsigned int sumstack(rectangle *s){
    unsigned int sum=0;
    int i;
    for(i=0;s[i].width;i++){
        if(isCurrent(s[i])){
            sum+=s[i].width*s[i].height;
            s++;
        }
    }
    return sum;
}
unsigned int minstack(rectangle *s){
    unsigned int area=400000;
    int i;

    for(i=0;s[i].width;i++){
        if(isCurrent(s[i])){
            area=min(area,s[i].width*s[i].height);
        }
    }
    return area;
}
void rollback(rectangle *r, int txn){
    int i;

    if(txn != NOTYET){
        for(i=0;r[i].width;i++){
            if(r[i].created == txn){
                r[i].created=r[i].deleted=NOTYET;
                r[i].x=r[i].width=r[i].y=r[i].height=0;
            }
            else if(r[i].deleted == txn){
                r[i].deleted=NOTYET;
            }
        }
    }
}
int overlap(rectangle a, rectangle b){
    if((a.x < b.x+b.width && a.x+a.width > b.x) && (b.y < a.y+a.height && b.y+b.height > a.y)){
        return TRUE;
    }
    return FALSE;
}
int stackoverlap(rectangle *callstack, rectangle next){
    int i,j;
    for(i=0;callstack[i].width;i++){
        if(overlap(callstack[i], next)){
            return TRUE;
        }
    }
    return FALSE;
}
rectangle rotate(rectangle a){
    int x=a.width;
    a.width=a.height;
    a.height=x;
    return a;
}
int buildedge(rectangle *stack, rectangle *callstack,int side, rectangle *space){
    int i,j,edge,goal,nextgoal,x,y,d,mindim,minarea,result=FALSE,spacetxn,stacktxn;
    mindim=side;
    minarea=side*side;
    for(i=0;stack[i].width;i++){
        mindim=min(mindim,min(stack[i].width,stack[i].height));
        minarea=min(minarea,area(stack[i]));
    }
    x=y=0;
    edge=TOPEDGE;
    i=0;
    while(edge == TOPEDGE && callstack[i].width != 0){
        if(callstack[i].x == x && callstack[i].y == y){
            x+=callstack[i].width;
            if(x == side){
                nextEdge(edge);
                y=0;
            }
            i=0;
        }
        else {
            i++;
        }
    }
    while(edge == RIGHTEDGE && callstack[i].width != 0){
        if(callstack[i].x+callstack[i].width == x && callstack[i].y == y){
            y+=callstack[i].height;
            if(y == side){
                nextEdge(edge);
                x=side;
            }
            i=0;
        }
        else {
            i++;
        }
    }
    while(edge == BOTTOMEDGE && callstack[i].width != 0){
        if(callstack[i].x+callstack[i].width == x && callstack[i].y+callstack[i].height == y){
            x-=callstack[i].width;
            if(x == 0){
                nextEdge(edge);
                y=side;
            }
            i=0;
        }
        else {
            i++;
        }
    }
    while(edge == LEFTEDGE && callstack[i].width != 0){
        if(callstack[i].x == x && callstack[i].y+callstack[i].height == y){
            y-=callstack[i].height;
            if(y == 0){
                nextEdge(edge);
            }
            i=0;
        }
        else {
            i++;
        }
    }
    if(edge == CENTER){
        /* rectangles are placed all along the perimeter of the square.
         * Now match will use a different strategy to match the remaining space
         * with what remains in stack */
        if(match(stack,callstack,space)){
            report(callstack,side);
            return TRUE;
        }
        return FALSE;
    }
    switch(edge){
    case TOPEDGE:
        goal=side-x;
        break;
    case RIGHTEDGE:
        goal=side-y;
        break;
    case BOTTOMEDGE:
        goal=x;
        break;
    case LEFTEDGE:
        /* Still a good assumption that callstack[0] is at 0,0 */
        goal=y-callstack[0].height;
        break;
    default:
        fprintf(stderr,"Error: buildedge has unexpected edge (b): %d\n",edge);
        exit(0);
    }
    nextgoal=goal-mindim;
    for(i=0;stack[i].width;i++){
        if(isCurrent(stack[i])){
            for(d=0;d<2;d++){
                switch(edge){
                case TOPEDGE:
                    if(stack[i].width == goal || stack[i].width <= nextgoal){
                        stack[i].x=x;
                        stack[i].y=y;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                case RIGHTEDGE:
                    if(stack[i].height == goal || stack[i].height <= nextgoal){
                        stack[i].x=x-stack[i].width;
                        stack[i].y=y;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                case BOTTOMEDGE:
                    if(stack[i].width == goal || stack[i].width <= nextgoal){
                        stack[i].x=x-stack[i].width;
                        stack[i].y=y-stack[i].height;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                case LEFTEDGE:
                    if(stack[i].height == goal || stack[i].height <= nextgoal){
                        stack[i].x=x;
                        stack[i].y=y-stack[i].height;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                default:
                    fprintf(stderr,"Error: buildedge has unexpected edge (c): %d\n",edge);
                    exit(0);
                }
                if(callstack[0].width != 0 && stack[i].width != stack[i].height){
                    stack[i]=rotate(stack[i]);
                }
                else {
                    break;
                }
            }
        }
    }
    return FALSE;
}
int populatestack(rectangle *stack, int score, int side, int rectangles){
    int offset,negative,area,mindim;
    rectangle local;

    int avg_area=(side*side)/rectangles;

    if(avg_area < 4){
        /* It's getting too small - really */
        return FALSE;
    }
    local.x=0;
    local.y=0;
    local.created=0;
    local.deleted=NOTYET;

    initstack(stack,MAXFACTORS);
    for(offset=1;offset<=score;offset++){
        negative=offset&1;
        area=avg_area + (negative?(0-(offset>>1)):(offset>>1));
        mindim=area/side;

        if(side*(area/side) == area){
            local.width=side;
            local.height=area/side;
            rpush(stack,local);
        }

        if(area > 0){
            for(local.width=side-mindim;local.width>=area/local.width;local.width--){
                if(local.width*(area/local.width) == area){
                    local.height=area/local.width;
                    rpush(stack,local);
                }
            }
        }
    }
    return TRUE;
}
int solve(int side,int rectangles,int score){
    rectangle stack[MAXFACTORS],callstack[MAXFACTORS];
    rectangle space[MAXFACTORS];
    rectangle universe;

    if(!populatestack(stack, score, side, rectangles)){
        return FALSE;
    }
    if(sumstack(stack) >= side*side){
        initstack(callstack,MAXFACTORS);
        initstack(space,MAXFACTORS);

        /* Initialize space (not occupied by a rectangle) to be side by side
         * where side is the height/width of the square into which the rectangles fit. */
        universe.width=universe.height=side;
        universe.x=universe.y=0;
        universe.created=0;
        universe.deleted=NOTYET;
        rpush(space, universe);

        if(buildedge(stack,callstack,side,space)){
            return TRUE;
        }
    }
    return FALSE;
}
int containsPoint(rectangle a, int x, int y){
    return a.x <= x && a.y <= y && a.x+a.width > x && a.y+a.height > y;
}
int containsRectangle(rectangle a, rectangle b){
    return containsPoint(a, b.x, b.y) && containsPoint(a, b.x+b.width-1, b.y) && containsPoint(a, b.x, b.y+b.height-1) && containsPoint(a, b.x+b.width-1, b.y+b.height-1);
}
int areEqual(rectangle a, rectangle b){
    return a.x == b.x && a.y == b.y && a.width == b.width && a.height == b.height;
}
int nexttransaction(rectangle *r){
    int i,n=NOTYET;

    for(i=0;r[i].width;i++){
        n=max(n,max(r[i].created,r[i].deleted));
    }
    return n+1;
}
void splitrectanglevertically(rectangle *space, int i, int x, int txn){
    rectangle left, right;
    left=right=space[i];
    right.x=x;
    left.width=right.x-left.x;
    right.width-=left.width;
    left.created=right.created=space[i].deleted=txn;
    rpush(space,left);
    rpush(space,right);
}
void splitrectanglehorizontally(rectangle *space, int i, int y, int txn){
    rectangle top, bottom;
    top=bottom=space[i];
    bottom.y=y;
    top.height=bottom.y-top.y;
    bottom.height-=top.height;
    top.created=bottom.created=space[i].deleted=txn;
    rpush(space,top);
    rpush(space,bottom);
}
int smallest(rectangle *space){
    int i,j,smallest;
    rectangle current;
    smallest=0;
    for(i=0;space[i].width;i++){
        if(isCurrent(space[i])){
            current=space[i];
            for(j=0;space[j].width;j++){
                if(isCurrent(space[j]) && i != j){
                    if(current.x+current.width == space[j].x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.width+=space[j].width;
                    }
                    else if(space[j].x+space[j].width == current.x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.x=space[j].x;
                        current.width+=space[j].width;
                    }
                    else if(current.y+current.height == space[j].y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.height+=space[j].height;
                    }
                    else if(space[j].y+space[j].height == current.y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.y=space[j].y;
                        current.height+=space[j].height;
                    }
                }
            }
            if(smallest == 0){
                smallest=current.width * current.height;
            }
            else if(smallest > current.width * current.height){
                smallest=current.width * current.height;
            }
        }
    }
    return smallest;
}
int narrow(rectangle *space){
    int i,j;
    rectangle smallest,current;

    smallest.width=0;
    for(i=0;space[i].width;i++){
        current=space[i];
        if(isCurrent(current)){
            for(j=0;space[j].width;j++){
                if(isCurrent(space[j]) && i != j){
                    if(current.width <= current.height
                    && current.x+current.width == space[j].x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.width+=space[j].width;
                    }
                    else if(current.width <= current.height
                    && space[j].x+space[j].width == current.x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.x=space[j].x;
                        current.width+=space[j].width;
                    }

                    if(current.width >= current.height
                    && current.y+current.height == space[j].y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.height+=space[j].height;
                    }
                    else if(current.width >= current.height
                    && space[j].y+space[j].height == current.y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.y=space[j].y;
                        current.height+=space[j].height;
                    }
                }
            }
            if(smallest.width == 0){
                smallest=current;
            }
            else if(min(smallest.width,smallest.height) > min(current.width,current.height)){
                smallest=current;
            }
        }
    }
    return min(smallest.width,smallest.height);
}
int notEmpty(rectangle *space){
    int i,count;

    for(i=0,count=0;space[i].width;i++){
        if(isCurrent(space[i])){
            count++;
        }
    }
    return count;
}
int isAdjacent(rectangle r, rectangle s){
    if(r.y == s.y+s.height && r.x < s.x+s.width && s.x < r.x+r.width){
        return TOPEDGE;
    }
    if(s.x == r.x+r.width && r.y < s.y+s.height && s.y < r.y+r.height){
        return RIGHTEDGE;
    }
    if(s.y == r.y+r.height && r.x < s.x+s.width && s.x < r.x+r.width){
        return BOTTOMEDGE;
    }
    if(r.x == s.x+s.width && r.y < s.y+s.height && s.y < r.y+r.height){
        return LEFTEDGE;
    }
    return NOTYET;
}

int adjacentrectangle(rectangle *space, int k, int k0){
    int i,edge;
    for(i=k0+1;space[i].width;i++){
        if(i != k && isCurrent(space[i])){
            if(isAdjacent(space[k],space[i]) != NOTYET){
                return i;
            }
        }
    }
    return NOTYET;
}
int expanse(rectangle *space, int j, int d){ /* Returns how far space[j] can expand in the d direction */
    int extent,k,giveUp,distance;
    rectangle result=space[j];

    extent=0;
    giveUp=FALSE;
    distance=0;
    if(d == TOPEDGE || d == BOTTOMEDGE){
        while(extent < space[j].width && !giveUp){
            giveUp=TRUE;
            for(k=0;space[k].width;k++){
                if(k != j && isCurrent(space[k]) && isAdjacent(space[j],space[k]) == d){
                    if(space[j].x+extent == space[k].x){
                        extent+=space[k].width;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                    else if(space[j].x+extent > space[k].x && space[j].x+extent < space[k].x+space[k].width){
                        extent=space[k].x+space[k].width-space[j].x;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                }
            }
        }
        if(extent < space[j].width){
            return 0;
        }
        return space[j].height+distance;
    }
    else if(d == LEFTEDGE || d == RIGHTEDGE){
        while(extent < space[j].height && !giveUp){
            giveUp=TRUE;
            for(k=0;space[k].width;k++){
                if(k != j && isCurrent(space[k]) && isAdjacent(space[j],space[k]) == d){
                    if(space[j].y+extent == space[k].y){
                        extent+=space[k].height;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                    else if(space[j].y+extent > space[k].y && space[j].y+extent < space[k].y+space[k].height){
                        extent=space[k].y+space[k].height-space[j].y;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                }
            }
        }
        if(extent < space[j].height){
            return 0;
        }
        return space[j].width+distance;
    }
    return 0;
}
int match(rectangle *stack, rectangle *callstack, rectangle *space){
    int i,j,k,d,goal,mn;
    int height;
    int spacetxn, stacktxn, calltxn;
    int map;
    rectangle r;

    for(i=0,goal=0;space[i].width;i++){
        if(isCurrent(space[i])){
            goal+=space[i].width*space[i].height;
        }
    }
    if(goal == 0){
        return TRUE;
    }
    mn=minstack(stack);
    if(goal < mn){
        /* The goal (space available) is smaller than any rectangle left in the stack */
        return FALSE;
    }
    spacetxn=nexttransaction(space);
    stacktxn=nexttransaction(stack);
    calltxn=nexttransaction(callstack);
    for(j=0;space[j].width;j++){
        for(i=0;stack[i].width;i++){
            if(isCurrent(stack[i]) && isCurrent(space[j])){
                if(congruent(space[j], stack[i]) && adjacentrectangle(space,j,NOTYET) == NOTYET){
                    r=space[j];
                    r.created=calltxn;
                    rpush(callstack, r);
                    deleteTxn(stack[i],stacktxn);
                    deleteTxn(space[j],spacetxn);
                }
            }
        }
    }
    if(!notEmpty(space)){
        return TRUE;
    }
    rectangle e;
    for(j=0;space[j].width;j++){
        if(isCurrent(space[j])){
            e=space[j];
            for(k=0,map=0;space[k].width;k++){
                if(k != j && isCurrent(space[k])){
                    d=isAdjacent(space[j], space[k]);
                    if(d != NOTYET){
                        map|=d;
                    }
                }
            }
            if(bitcount(map) == 1){ /* space[j] has adjacent space on only one side */
                if(map == TOPEDGE || map == BOTTOMEDGE){
                    e.height=expanse(space,j,map);
                }
                else if(map == LEFTEDGE || map == RIGHTEDGE){
                    e.width=expanse(space,j,map);
                }
                for(i=0;stack[i].width;i++){
                    if(isCurrent(stack[i])){
                        if(congruent(e, stack[i])){
                            e.created=calltxn;
                            rpush(callstack, e);
                            deleteTxn(stack[i],stacktxn);
                            if(!removerectangle(space, e, spacetxn)){
                                printf("Logic error in match/expanse.  Terminating\n");
                                exit(0);
                            }
                            if(match(stack,callstack,space)){
                                return TRUE;
                            }
                            else {
                                rollback(stack,stacktxn);
                                rollback(callstack,calltxn);
                                rollback(space,spacetxn);
                                return FALSE;
                            }
                        }
                        else if(congruent(space[j], stack[i])){
                            r=space[j];
                            r.created=calltxn;
                            rpush(callstack, r);
                            deleteTxn(stack[i],stacktxn);
                            if(!removerectangle(space, r, spacetxn)){
                                printf("Logic error in match/expanse.  Terminating\n");
                                exit(0);
                            }
                            if(match(stack,callstack,space)){
                                return TRUE;
                            }
                            else {
                                rollback(stack,stacktxn);
                                rollback(callstack,calltxn);
                                rollback(space,spacetxn);
                                return FALSE;
                            }
                        }
                    }
                }
            }
        }
    }
    if(notEmpty(space)){
        rollback(stack,stacktxn);
        rollback(callstack,calltxn);
        rollback(space,spacetxn);
        return FALSE;
    }
    return TRUE;
}
int removerectangle(rectangle *space, rectangle r, int ntxn){
    int i,status=TRUE;
    for(i=0;space[i].width;i++){
        if(space[i].deleted == NOTYET){
            if(areEqual(space[i], r)){
                space[i].deleted=ntxn;
                return TRUE;
            }
            else if(containsRectangle(space[i], r)){
                if(r.x > space[i].x){
                    splitrectanglevertically(space, i, r.x, ntxn);
                }
                else if(r.y > space[i].y){
                    splitrectanglehorizontally(space, i, r.y, ntxn);
                }
                else if(r.x+r.width < space[i].x+space[i].width){
                    splitrectanglevertically(space, i, r.x+r.width, ntxn);
                }
                else if(r.y+r.height < space[i].y+space[i].height){
                    splitrectanglehorizontally(space, i, r.y+r.height, ntxn);
                }
            }
            else if(overlap(space[i], r)){  /* we have to split both */
                rectangle aux;
                if(r.x < space[i].x){
                    aux=r;
                    aux.width=space[i].x-r.x;
                    r.x+=aux.width;
                    r.width-=aux.width;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(r.x+r.width > space[i].x+space[i].width){
                    aux=r;
                    aux.x=space[i].x+space[i].width;
                    aux.width=r.x+r.width-aux.x;
                    r.width-=aux.width;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(r.y < space[i].y){
                    aux=r;
                    aux.height=space[i].y-aux.y;
                    r.y+=aux.height;
                    r.height-=aux.height;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(r.y+r.height > space[i].y+space[i].height){
                    aux=r;
                    aux.y=space[i].y+space[i].height;
                    aux.height=r.y+r.height-aux.y;
                    r.height-=aux.height;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(areEqual(space[i], r)){
                    space[i].deleted=ntxn;
                    return TRUE;
                }
                else {
                    if(!removerectangle(space,r,ntxn)){
                        return FALSE;
                    }
                    return TRUE;
                }
            }
        }
    }
    return TRUE;
}
int main(int argc, char *argv[]){
    int side=15;
    int n=5;
    int budget=0;
    int status;
    while((status=getopt(argc,argv,"l:n:")) >= 0){
        switch(status){
        case 'l':
            sscanf(optarg,"%d",&side);
            break;
        case 'n':
            sscanf(optarg,"%d",&n);
            break;
        }
    }
    budget=64;
    while(solve(side,n,budget) == FALSE){
        budget+=16;
    }
}