2
\$\begingroup\$

I am looking for help in code proofreading. The program is trying to solve this question: Fit non-congruent rectangles into an array_size x array_size square grid. What is the smallest difference possible between the areas of the largest and the smallest rectangles?

I have a class of Rectangles, which I try to fit in a class called Boards. The function AutoInsert is basically the algorithm, where I have a linked list consisting of both Boards & Rectangles that adds and removes potential Rectangles from the Boards. This program works for small numbers of global variable array_size.

I appreciate any help at all: even if you don't understand the question or my programming, if you recognize any bad practices in my programming, please do tell.

#include<iostream>
#include<math.h>
#include<vector>
#include<time.h>
#include<stdlib.h>
#include <cstdio>
#include <ctime>

using namespace std;

const int array_size = 15; //array_size x array_size square
const int upperbound = ceil(3+array_size/log(array_size)); //given in reddit link
const int SQ = pow(array_size,2);

char getRandom(){
    int n=rand()%78;
    char c=(char)(n+49);
    return c;
}

class Rect{
private:
    int l,w,use; //int use: 0=haven't used, 1=using, 2=congruent use, 3=never use again ... should I add a possible use number w. respect to wnBounds?
    int coords[4]; //top left x,tly,brx,bry
    char random;
public:
    Rect(){
        l=0;
        w=0;
        use=0;
        for(int i=0;i<4;i++){
            coords[i]=-1;
        }
    }
    void setL(int l){this->l=l;}
    void setW(int w){this->w=w;}
    void setUse(int use){this->use=use;}
    void setCoords(int coords[]){
        for(int i=0;i<4;i++){
            this->coords[i]=coords[i];
        }
    }
    int getL(){return l;}
    int getW(){return w;}
    int getArea(){return l*w;}
    int getUse(){return use;}
    int *getCoords(){return coords;}
    int tlx(){return coords[0];}
    int tly(){return coords[1];}
    int brx(){return coords[2];}
    int bry(){return coords[3];}
    char setPiece(char c){random=c;}
    char getPiece(){return random;}
};

class Rboard{
private:
    bool inRange(int c[4]); //defensive functions
    bool rectAtLoc(int c[4]); //defense
    bool canUse(Rect n); //defense
    Rect p[SQ]; //all possible rectangles, p[pow(array_size,2)-1] is the square so be careful
    Rect first; //initial Rect
    int difference;
public:
    Rboard();
    Rboard(Rect n); //initialize Rboard with first Rectangle, it will be up to Rsort to input good rectangles
    bool coords[array_size][array_size]; //main coords, all begin as false, true is if occupied
    void setFirst(Rect n){first=n;}
    void editPoss(int c[4],int n);
    Rect returnP(int n){return p[n];}
    int getIndex(int l, int w);
    int getDiff();
    int spaceLeft();
    vector<int> wnBound(); //returns rectangles within upperbound of initial rectangle
    vector<int> pp(); //returns the Index of possible rectangles which can be placed
    vector<int> pc(int i); //even index = top left x, odd index=y, can figure out rest of coords of rectangle from this information.
    void display();
};

Rboard::Rboard(){
    difference=upperbound;
    int i=0;
    for(int i=0;i<array_size;i++){
        for(int j=0;j<array_size;j++){
            coords[i][j]=false;
        }
    }
    for(int j=0;j<array_size;j++){
        for(int k=0;k<array_size;k++){
            p[i].setL(j+1);
            p[i].setW(k+1);
            i++;
        }
    }
}

Rboard::Rboard(Rect n){
    Rboard();
    first=n;
}

int Rboard::getIndex(int l, int w){
    for(int i=0;i<SQ;i++){
        if((p[i].getL()==l)&&(p[i].getW()==w)){
            return i;
        }
    }
}

void Rboard::editPoss(int c[4],int n){
    Rect g=p[n];
    g.setCoords(c);
    g.setL(p[n].getL());
    g.setW(p[n].getW());
    if(canUse(g)){
        p[n].setPiece(getRandom());
        p[n].setCoords(c);
        p[n].setUse(1);
        if(g.getL()!=g.getW()){
            p[getIndex(g.getW(),g.getL())].setUse(2);
        }
        for(int i=p[n].tly();i<=p[n].bry();i++){
            for(int j=p[n].tlx();j<=p[n].brx();j++){
                coords[j][i]=true;
            }
        }
    }
}

bool Rboard::inRange(int c[4]){
    for(int i=0;i<4;i++){
        if((c[i]>=array_size)||(c[i]<0)){
            return false;
        }
    }
    return true;
}

bool Rboard::rectAtLoc(int c[4]){
    for(int i=c[0];i<=c[2];i++){
        for(int j=c[1];j<=c[3];j++){
            if(coords[i][j]){
                return true;
            }
        }
    }
    return false;
}

bool Rboard::canUse(Rect n){
    if((n.getUse()==0)&&(inRange(n.getCoords()))&&(rectAtLoc(n.getCoords())==false)){
        return true;
    }
    return false;
}

int Rboard::getDiff(){
    int oriDiff=difference, counter=0, minN=SQ+1, maxN=-1; //biggest number, smallest number
    for(int i=0;i<SQ;i++){
        if(p[i].getUse()==1){
            if(p[i].getArea()>maxN){
                maxN=p[i].getArea();
            }
            if(p[i].getArea()<minN){
                minN=p[i].getArea();
            }
            counter++;
        }
    }
    if((counter<=1)&&(spaceLeft()==0)){
        return oriDiff;
    }else{
        return maxN-minN;
    }
}

int Rboard::spaceLeft(){
    int sum=0;
    for(int i=0;i<array_size;i++){
        for(int j=0;j<array_size;j++){
            if(coords[i][j]){
                sum+=1;
            }
        }
    }
    return (SQ-sum);
}

vector<int> Rboard::wnBound(){
    vector<int> output;
    for(int i=0;i<SQ;i++){
        if(abs(p[i].getArea()-first.getArea())<=upperbound){
            output.push_back(i);
        }
    }
    return output;
}

vector<int> Rboard::pc(int i){
    vector<int> output;
    int l=p[i].getL(),w=p[i].getW(),area=p[i].getArea(),counter=0;
    for(int a=0;a<(array_size-l+1);a++){
        for(int b=0;b<(array_size-w+1);b++){
            for(int c=0;c<w;c++){
                for(int d=0;d<l;d++){
                    if(!coords[b+c][a+d]){
                        counter++;
                    }
                }
            }
            if(counter==area){
                output.push_back(b);
                output.push_back(a);
            }
            counter=0;
        }
    }
    return output;
}

vector<int> Rboard::pp(){
    vector<int> indexes;
    for(int i=0;i<wnBound().size();i++){
        int j=wnBound()[i];
        if(p[j].getUse()==0){
            if(spaceLeft()>=p[j].getArea()){
                if(pc(j).size()!=0){
                    indexes.push_back(j);
                }
            }
        }
    }
    return indexes;
}

void Rboard::display(){
    for(int i=0;i<array_size;i++){
        for(int j=0;j<array_size;j++){
            if(coords[j][i]){
                for(int a=0;a<SQ;a++){
                    if((p[a].tlx()<=j)&&(p[a].brx()>=j)&&(p[a].tly()<=i)&&(p[a].bry()>=i)){
                        cout<<p[a].getPiece()<<" ";
                    }
                }
            }else{
                cout<<0<<" ";
            }
        }
        cout<<endl;
    }
}

class Rnode{
private:
    Rect piece;
    Rboard state;
    Rnode *next;
public:
    Rnode(Rect p, Rboard s, Rnode *n){piece=p; state=s; next=n;}
    Rect getPiece(){return piece;}
    Rboard getState(){return state;}
    Rnode* getNext(){return next;}
    void setPiece(Rect p){piece=p;}
    void setState(Rboard s){state=s;}
    void setNext(Rnode *next1){next=next1;}
};

class Rsort{
private:
    Rnode *root;
    vector<Rect> best;
    int diff;
public:
    Rsort(){
        root=NULL;
        diff=upperbound+1;
    };
    void setFirst(int i);
    bool isLoser(Rboard b);
    bool isDonut(Rboard b);
    //to do: keep track of duplicates. e.j., 1x1+1x2+3x1 has been calculated... make sure don't branch to other 6!-1 combinations.
    void autoInsert(Rnode *c,double duration,int maxDepth);
    void autoFirst();
    void display();
};

void Rsort::setFirst(int i){
    Rboard board;
    Rect f=board.returnP(i);
    int coords[4]={0,0,f.getW()-1,f.getL()-1};

    f.setCoords(coords);
    board.editPoss(coords,i);
    board.setFirst(f);

    if(root!=NULL){
        root=NULL;
    }
    root=new Rnode(f,board,NULL);
}

bool Rsort::isLoser(Rboard b){ //optimizes by 2 seconds
    vector<int> pp=b.pp(),dup;
    int sum=0,dupS=0;
    for(int i=0;i<pp.size();i++){
        if((b.returnP(pp[i]).getL())!=(b.returnP(pp[i]).getW())){
            dup.push_back(b.returnP(pp[i]).getArea());
        }
        sum+=b.returnP(pp[i]).getArea();
    }
    for(int i=0;i<dup.size();i++){
        dupS+=dup[i];
    }
    return ((sum-dupS/2)<b.spaceLeft()); //if sum of areas of possible rectangles < spaceLeft, this board will be a loser
}

bool Rsort::isDonut(Rboard b){ //check if there is an non-patchable "hole"
    bool invBoard[array_size+2][array_size+2];
    vector<int> p=b.wnBound();

    for(int x=0;x<(array_size+2);x++){
        invBoard[x][0]=true;
        invBoard[x][array_size+1]=true;
    }
    for(int y=1;y<(array_size+1);y++){
        invBoard[0][y]=true;
        for(int x=1;x<(array_size+1);x++){
            invBoard[x][y]=!b.coords[x-1][y-1]; //made coords public for this reason
        }
        invBoard[array_size+1][y]=true;
    }

    for(int i=0;i<p.size();i++){
        int l=b.returnP(i).getL(),w=b.returnP(i).getW(),area=b.returnP(i).getArea(),counter=0;
        for(int a=0;a<(array_size-l+3);a++){
            for(int b=0;b<(array_size-w+3);b++){
                for(int c=0;c<w;c++){
                    for(int d=0;d<l;d++){
                        if(invBoard[b+c][a+d]){
                            counter++;
                        }
                    }
                }
                if(counter==area){
                    return 0;
                }
                counter=0;
            }
        }
    }
    return 1;
}

void Rsort::autoInsert(Rnode *c,double duration,int maxDepth){ //add terminating counter for recursion?
    if(isDonut(c->getState())||(maxDepth>=7)){ //max number of rectangles you want: change #. Need to define a function
                                                //to calculate this based on array_size and upperbound. This variable
                                                //alone has stopped my program from crashing at high values of array_size.
                                                //I suspect this due to the stack overflow error.
        return;
    }
    if(duration>=15.0){ //timer x.0 seconds => gives better solutions the longer the timer
        root=NULL;
        return;
    }
    clock_t start;
    double d;
    start = clock();

    vector<int> pp=c->getState().pp(), pc;
    c->setNext(NULL);

    if(pp.size()==0){
        if(c->getState().spaceLeft()==0){
            if(c->getState().getDiff()<diff){
                diff=c->getState().getDiff();
                best.clear();
                for(int a=0;a<SQ;a++){
                    if(c->getState().returnP(a).getUse()==1){
                        best.push_back(c->getState().returnP(a));
                    }
                }
                display();
                c->getState().display();
            }
        }
    }else if((root!=NULL)&&(!isLoser(c->getState()))){
        for(int i=0;i<pp.size();i++){ //better restrictions here please
            pc=c->getState().pc(pp[i]);
            for(int j=0;j<pc.size();j+=2){
                if(j==2){ //to cut down runtime
                    break;
                }
                Rect n;
                Rboard n1=c->getState();

                int coords[4]={pc[j],pc[j+1],pc[j]+c->getState().returnP(pp[i]).getW()-1,pc[j+1]+c->getState().returnP(pp[i]).getL()-1};
                n.setL(c->getState().returnP(pp[i]).getL());
                n.setW(c->getState().returnP(pp[i]).getW());
                n.setCoords(coords);
                n1.editPoss(coords,pp[i]);
                Rnode *newnode=new Rnode(n,n1,NULL);
                c->setNext(newnode);

                d=(clock()-start)/(double)CLOCKS_PER_SEC;
                autoInsert(c->getNext(),(duration+d),(maxDepth+1)); //remove +d if you have all the time in the world to wait for output
            }
        }
    }
}

void Rsort::autoFirst(){
    //to do: only iterate through non congruent rectangles, and interquartile range of that.
    for(int i=SQ/4;i<3*SQ/4;i++){ //interquartile range
        cout<<i<<endl;
        setFirst(i);
        autoInsert(root,0,0);
    }
}

void Rsort::display(){
    cout<<diff<<endl;
    for(int i=0;i<best.size();i++){
        cout<<best[i].getL()<<" x "<<best[i].getW()<<endl;
    }
}

int main(){
    srand(time(NULL));
    Rsort r;
    Rboard t;
    r.isDonut(t);
    r.autoFirst();
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ "The program is trying to solve this question" Yes, and it isn't entirely clear whether it succeeded to your satisfaction or not. Could you clarify this? And take a look at the help center while you're at it :-) \$\endgroup\$ – Mast Oct 30 '18 at 18:17
  • \$\begingroup\$ Yes, my program works for array_size up til 15 x 15. Help center says "Questions about improving scalability are allowable, as long as your code works for small inputs." My program just takes too long after 15 x 15 (ie 20 x 20) for me to really say whether it works or not. I ran it for 10 minutes and gave up. Thanks for the link to the help center \$\endgroup\$ – Bo Work Oct 30 '18 at 18:53
3
\$\begingroup\$

Look at your compiler's warnings

When I try to compile your code, the compiler gives two warnings: Rect::setPiece() doesn't have a return statement, and Rboard::getIndex() is missing a return statement after the loop.

The first warning can be fixed by simply changing the return type of Rect::setPiece() to void. The second warning might be harmless; the assumption is that Rboard::getIndex() will always be called with values for l and w that match one of the rectangles. But what if it doesn't? Then the for loop will end, and a bogus value will be returned. If this is never supposed to happen, just throw an exception there: the compiler warning will go away, and if your code ever does the wrong things, you will hopefully get a helpful error message.

Try to write more C++

In general, your code looks very much like C with classes, and doesn't make good use of the features that the C++ language and its standard library provides. Try to find more C++-like ways to write your code. That doesn't mean "write templates, use inheritance, and overload every operator you possibly can", rather try to make better use of the STL, use features like range for, auto, and so on, to help you write more concise code.

Use a proper random number generator

If you can use C++11 or later, use the functions from <random> to generate random numbers, instead of using the rather bad rand() function from C.

While it is not so important for this particular code, srand(time(NULL)) will only generate a new seed every second, which might be bad if your code is run multiple times per second, or multiple instances of the code are started in parallel. Also, rand() % N will, for most values of N, not give you a uniformly distributed random number. There are ways around both issues, but the C++11 RNG functions take care of this for you.

Code style

Every programmer has his/her own favourite way of formatting their source code. While there is no right or wrong, you are using a very dense style, omitting spaces almost wherever possible. I would suggest you use spaces after punctuation (such as ;), and spaces around operators (such as =, <, and so on). For example this line:

if((b.returnP(pp[i]).getL())!=(b.returnP(pp[i]).getW())){

It's hard to see that this is comparing the result of two function called. Just adding some spaces (and removing some superfluous parentheses) results in:

if (b.returnP(pp[i]).getL() != b.returnP(pp[i]).getW()) {

And when you are initializing arrays, you can also put each element on its own line. So this line for example:

int coords[4]={pc[j],pc[j+1],pc[j]+c->getState().returnP(pp[i]).getW()-1,pc[j+1]+c->getState().returnP(pp[i]).getL()-1};

Will become:

int coords[4] = {
    pc[j],
    pc[j+1],
    pc[j]   + c->getState().returnP(pp[i]).getW() - 1,
    pc[j+1] + c->getState().returnP(pp[i]).getL() - 1,
};

Also, declare one variable per line, so:

int l=p[i].getL(),w=p[i].getW(),area=p[i].getArea(),counter=0;

Becomes:

int l = p[i].getL();
int w = p[i].getW();
int area = p[i].getArea();
int counter = 0;

Use descriptive variable and function names

It should be possible to determine what a variable or function does by looking at its name. There are some commonly used abbreviations, such as i for a loop index, x, y and z for coordinates, but otherwise you should not use abbreviations.

Instead of l and w, write length and width. Instead of SQ, write array_elements. Or better yet, array_size, and split the original array_size into array_length and array_width. This way, you'll be able to handle non-square boards.

Instead of Rboard, name your class either RectangleBoard or just Board. And what do Rboard::pc() and Rboard::pp() do? Even looking at the code I have no idea what those abbreviations mean.

Move member variable initialization to the declaration

It's generally best to move initialization of variables as close as possible to their declaration. For example, in class Rect, instead of initializing the private member variables inside the constructor, just write:

class Rect {
private:
    int l = 0;
    int w = 0;
    ...

Here it is not too important, but if you have multiple constructors, or have a lot of member variables, it will become clear that this is better. Here, you might get rid of the constructor altogether this way.

Don't store redundant information

Your class Rect stores the top-left and bottom-right coordinates of the rectangle, and its length and width. There is also nothing in that class that prevents these pieces of information from being in conflict with each other. Either store both coordinates, or one coordinate and the length and width. Your getters and setters should take care of calculating the required information if necessary.

Avoid using an array to store coordinates

Unless you are going to store manydimensional coordinates, it's usually better to just name the coordinates x and y, or in this case if you don't want to store width and height, x1, y1, x2 and y2. The reason is that it's easy to make mistakes when you store the coordinates in an int[4]: did you store the coordinates in the aforementioned order or, was is x1, x2, y1, y2? Being explicit here avoids issues.

Even better is to define a struct coordinate {int x; int y;}, or use a library like GLM that provides you with various vector and matrix types, including all kinds of useful functions that operate on them.

Use a single function to get/set multiple variables, if that is the typical use case

Instead of having separate functions setL(int l) and setW(int w), which you will always call in pairs, create a single function set_size(int l, int w). Of course, if you use a struct for coordinates, then you will automatically write code like that.

Use std::vector instead of arrays where appropriate

In class Rboard, you declare an array Rect p[SQ]. You are not always using all elements. It makes much more sense to make this a std::vector<Rect> p. This way, you can add elements to the vector as needed, you don't have to have a member variable in class Rect to tell you whether the rectangle is in use or not.

Avoid if (foo) return true; else return false;

Just directly return foo. For example Rboard::canUse() can be simplified to:

bool Rboard::canUse(Rect n) {
    return n.getUse() == 0 && inRange(n.getCoords()) && !rectAtLoc(n.getCoords());
}

Use const references where appropriate

Passing large classes by value might result in expensive copies, and might even trigger some undesired behaviour, depending on how these classes are implemented. Use const references to avoid that. For example, Rboard::canUse() can be rewritten as:

bool Rboard::canUse(const Rect &n) {
    ... // no need to change anything in the implementation
}

Use std::list<> instead of writing your own linked lists

Your class Rnode implements a linked list. Let the STL do that for you! Remove the member variable Rnode *next, the function setNext(), and in class Rsort use std::list<Rnode> nodes instead of Rnode *root. Then instead of having to do thinks like Rnode *newnode = new Rnode(...) and setNext(newnode), you can just write nodes.push_back(...). As a bonus, this will take care of deleting the memory for you, which you forgot to do.

Use nullptr instead of NULL

NULL is C, nullptr is C++.

Use '\n' instead of std::endl

When you want to end a line, output a '\n' instead of using std::endl. The latter is the same but also flushes the output, which might slow down your program.

Optimize your Rboard::display() function

Your function to display a board is quite inefficient: it has complexity O(array_size⁴). The reason is that for every position, you check every possible square if it is covering that position. It is better to create a 2D array that represents the board, and then for each square, draw it onto that representation, and at the end write out the whole array. This reduces the complexity to O(array_size²). For example:

void Rboard::display() {
    char output[array_size][array_size];

    for (auto &rect: p) {
         char piece = getRandom();

         for (int y = rect.tly(); y < rect.bry(); y++) {
             for (int x = rect.tlx(); x < rect.brx(); x++) {
                  output[y][x] = piece;
             }
         }
    }

    for (int y = 0; y < array_size; y++) {
        cout.write(output[y], array_size);
        cout.put('\n');
    }
}

Note that the above function also no longer needs the member variable char random in class Rect.

Use an enum for Rect::use

Instead of using an int to represent different states, make them explicit by using an enum, preferrably even an enum class if you can use C++11 or later. For example:

class Rect {
    public:
    enum class UseType {
        UNUSED,
        USED,
        CONGRUENT_USE
    };

    private:
    UseType use = UseType::UNUSED;
    ...

    public:
    void setUse(UseType use) {
        this->use = use;
    }

    UseType getUse() {
        return use;
    }

Then later in the code, you can for example write setUse(Rect::UseType::CONGRUENT_USE). That's very verbose, but it's clear from just that line of code what the intention is, whereas setUse(2) leaves the reader searching through the code to find out what 2 means. Also, you can now no longer accidentily set an invalid value, like setUse(9).

\$\endgroup\$
  • \$\begingroup\$ Thank you for your insight. It must have taken you quite a while to write this, which I appreciate. \$\endgroup\$ – Bo Work Oct 31 '18 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.