Aby uzyskać więcej informacji, obejrzyj ten film i przejdź do A276523, aby uzyskać powiązaną sekwencję.

Układanka Mondrian (dla liczby całkowitej n) jest następująca:

Dopasuj nie przystające prostokąty do n*nkwadratowej siatki. Jaka jest najmniejsza możliwa różnica między największym a najmniejszym prostokątem?

Dla 6optymalnej różnicy M(6)jest 5i można to wykazać w następujący sposób:

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

Największy prostokąt (L) ma powierzchnię 2 * 4 = 8, a najmniejszy prostokąt (S) ma powierzchnię 1 * 3 = 3. Dlatego różnica jest taka 8 - 3 = 5.

Należy pamiętać, że obecnie nie n > 44znaleziono optymalnych rozwiązań .

Twoim zadaniem jest stworzenie programu, który generuje siatkę Mondrian, która zawiera (nieoptymalne) rozwiązanie, biorąc pod uwagę liczbę całkowitą n.

Zostaniesz przetestowany na liczbach od 100 do 150. Twój wynik za każdy test będzie różnicą między największym i najmniejszym prostokątem. Twój łączny wynik to suma wyników wszystkich testów od 100 do 150.

Musisz przedstawić swoje wyniki w następujący sposób:

{number}
{grid}

Gdzie numberjest wynik (różnica między największym a najmniejszym) i gridwynosi albo:

• Sznurek z wieloma liniami lub
• Dwuwymiarowa lista.

Siatka MUSI wyraźnie pokazywać, gdzie prostokąt zaczyna się i kończy.

Zasady:

• Twój program musi mieścić się w twojej odpowiedzi.
• Twój program musi wypisać wartość dla dowolnej liczby od 100 do 150 w ciągu 1 godziny na nowoczesnym laptopie.
• Twój program musi generować to samo rozwiązanie dla liczby całkowitej przy nkażdym uruchomieniu programu.
• Musisz podać link do wyników wszystkich 51 rozwiązań (używając Pastebin, Github Gist ... cokolwiek, naprawdę).
• Musisz mieć co najmniej dwa prostokąty na kwadratowej siatce dla swojego rozwiązania.

Piet, 9625

(W końcu to działa!)

Ludzie tego zażądali, więc oto jest. Jest to niezwykle naiwne rozwiązanie (zasadniczo takie samo jak luźne górne granice na stronie OEIS): dzieli każdy kwadrat na tylko dwa prostokąty.

Ta lista zawiera szczegóły w dwóch plikach:

• Wyjście programu (przy użyciu npiet v1.3) dla wszystkich wymaganych danych wejściowych. Zauważ, że przechwyciłem tylko standardowe wyjście, więc ?jest monit o wprowadzenie, a następnie natychmiast wynik wyjściowy, a następnie siatka.
• Źródło „pseudo-zestawu”, którego użyłem do zaplanowania programu.

Wyjaśnienie

Ten program ma jeden numer N jako dane wejściowe. Jeśli liczba jest nieparzysta, wynikiem jest liczba; jeśli parzysty, wynik jest dwa razy większy niż liczba.

Po wypisaniu wyniku, reszta lewej strony programu jest wydawana na wypełnienie stosu pięcioma partiami następujących informacji:

• Szerokość siatki (która wynosi N )
• Liczba linii do wydrukowania
• Znak do wydrukowania w poprzek siatki (albo _ spacji)
• Znak do wydrukowania na każdej krawędzi siatki (spacja lub |)

Prawa strona programu pobiera każdy zestaw czterech wartości i drukuje tę część siatki.

C 6108

Wykorzystuje rekurencyjną (naprawdę iteracyjną) wersję minimalnego rozwiązania. Zamiast dzielić kwadrat na dwa prostokąty, z których jeden jest nieco większy niż połowa powierzchni, dzieli go na N prostokątów. Pierwszy prostokąt jest więc nieco większy niż 1/Ncałkowity obszar. Następnie biorąc resztę, program dzieli prostokąt nieco większy niż 1/(N-1)reszta i tak dalej, aż resztę zajmie tylko jako ostatni prostokąt. Prostokąty są odcinane od reszty spiralnie zgodnie z ruchem wskazówek zegara, więc najpierw u góry, potem po prawej itd.

Ponieważ jest to bardzo bezpośrednia metoda zamiast przeszukiwania szerokiej przestrzeni, działa szybko - zajmuje około 25 sekund (na Raspberry Pi) po 74 rozwiązań dla każdego zestawu problemów.

Moim zamiarem jest wykorzystanie tych wyników, aby lepiej poinformować algorytm wyszukiwania o bardziej wyrafinowanym podejściu.

Dane wyjściowe dają wynik i rysunek (ascii) oraz współrzędne wierzchołków prostokątów. Wierzchołki są w kolejności zgodnej z ruchem wskazówek zegara, zaczynając od lewego górnego rogu danego prostokąta.

Opracowany przy użyciu gcc 4.9.2-10.

Wyniki na https://github.com/JaySpencerAnderson/mondrian

Kod:

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

C - 2982

Ten program realizuje wyszukiwanie za pomocą szerokiego zestawu wyników. Ważną częścią praktycznego poszukiwania było wczesne niepowodzenie i / lub zejście złymi ścieżkami.

Generuje to zestaw prostokątów do rozważenia dla rozwiązania. Zestaw wygenerowanych prostokątów pozwala uniknąć tych o wymiarach, które nie byłyby przydatne. Na przykład, jeśli program próbuje znaleźć rozwiązanie kwadratu 128 x 128, podzielonego na 8 prostokątów, wygeneruje prostokąt o wymiarach 128 x 16. Nie wygeneruje tego, że ma wymiary 120 x 17, ponieważ nie ma szansy na wygenerowanie prostokąta o szerokości 8 do wypełnienia luki na końcu 120.

Początkowa strategia umieszczania prostokątów polega na umieszczeniu ich po wewnętrznej stronie obwodu kwadratu (funkcja budowania). W ten sposób algorytm otrzymuje dość szybką informację zwrotną na każdym rogu, czy istnieje problem z wybraną sekwencją. Umieszczając prostokąty, logika stale obserwuje, aby zobaczyć, czy pojawią się luki w przestrzeni, które są zbyt wąskie dla jakiegokolwiek prostokąta. Po pomyślnym wypełnieniu obwodu strategia zmienia się na próbę dopasowania pozostałego miejsca do pozostałych prostokątów (funkcja dopasowania).

Inną rzeczą, która może być interesująca jest to, że implementuje transakcje z wycofywaniem stosów prostokątów.

Ten program nie próbuje znaleźć najlepszego możliwego dopasowania. Otrzymuje budżet (64) i kończy pracę, gdy znajdzie pierwsze rozwiązanie. Jeśli to nigdy nie znajdzie rozwiązania, zwiększamy budżet (o 16) i próbujemy ponownie. Wymagany czas (na laptopie Dell z procesorem I7) wahał się od znacznie poniżej minuty do 48 minut dla 150 na boku (149 na stronie zajęło mniej niż 2 minuty). We wszystkich 51 rozwiązaniach zastosowano 11 prostokątów. Wyniki 51 rozwiązań wahały się od 41 do 78. Powodem, dla którego użyłem 11 prostokątów było to, że wynik był niższy niż przy mniejszej liczbie prostokątów i wyglądało na to, że 12 prostokątów zajmie znacznie więcej niż wyznaczona godzina.

Rozwiązania i kod można znaleźć na stronie https://github.com/JaySpencerAnderson/mondrian . Są to dwa pliki my4 *.

BTW, jeśli skompilujesz to do „my4” i wykonasz to w następujący sposób: „./my4 -h”, da ci to użytkowanie. Jeśli chcesz zobaczyć, jak działa, spróbuj czegoś takiego jak „./my4 -l 50 -n 8”. Jeśli zmienisz „#if 0” na „#if 1”, wyświetli pozostałe miejsce na ekranie. Jeśli chcesz to zmienić, aby renderować prostokąty, poszukaj jednego miejsca, w którym kod wykonuje „graf (spacja, bok)” i zamiast tego zmień to na „graf (stos wywołań, bok)”. Proponuję również zmienić początkowy budżet z 64 na 32, jeśli chcesz bawić się rozwiązaniami dla kwadratów o szerokości około 50. Rozwiązanie dla mniejszych kwadratów będzie miało lepszy wynik przy mniejszym budżecie.

Poniższy program działa. Sprawdź github pod kątem pełnego kodu (z użyciem, komentarzami itp.).

#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;
    }
}