I encountered a problem at work that cost me an entire day’s worth of productivity to solve. I thought of different ways to go about it and finished coding many ideas only to realize fatal flaws during testing that rendered my “solution” useless. I found a solution at around 2:30 in the morning, while I laid wide awake in bed unable to sleep because my brain refuses to shut down while the problem was left unsolved. It was fairly simple, as with all things when we look back after the struggle has passed.

I have a rectangular area whose upper-left corner is at the origin (0,0) and whose bottom-right corner is at (w,h) where w is the width and h is the height of the area. I also have small rectangular pieces, each having a width and height that is less than or equal to w and h, respectively.

A piece is placed on the rectangular area by giving it a home. The home of a piece is any rectangular space on the area that is equal or greater in size to the piece. The piece is always at the upper-left corner of its home, even when there is space enough to its right or below.

Each piece needs to be positioned in the rectangular area such that its upper-left corner is at (x, y) where x is different but constant for every piece, and y is 20 units below the bottom of the previous piece. The first piece, therefore, is always placed at (x,20).

There are two ways to assign a home to a piece.

(A,p,q,i,k) means that the home of the piece is defined by absolute position. It is the rectangle formed from positions (p,q) and (i,k) in the rectangle. p,i <= w and q,k <= h

(R,r/l,p,u/d,q,i,k) means that the home of the piece is defined by relative position. The upper-left corner of the home rectangle is at (r/l+p,u/d+q) where r is the rightmost, l is the leftmost, u is the upper, and d is the bottom unit of the previous piece. It has a width of i and a height of k.

If the first piece is defined by relative position, the top line of the rectangular area will serve as its “previous piece”. This means that l=0, r=w, u=d=0.

I am given a certain order in which the pieces must appear and the x where the left side of each piece must be. I need to assign them homes such that even if I remove or add pieces in between, they will appear as intended.

At the start, I thought the pieces were constant so I coded them all using absolute positioning. Of course, the moment I was told they would be added or removed at any time, absolute positioning no longer became an option.

The next thing I tried was to set their positions based on where the the upper-left corner of the previous piece was. This worked for a while, mainly because the pieces that were usually removed or added were in positions that did not affect the remaining pieces. Soon enough, I realized that if I removed a piece whose home’s x is different from the piece before it, the succeeding piece will move incorrectly. Likewise, if a piece was added with similar conditions.

In the end, I set the homes to all end at the rightmost position of the rectangular area. The idea was to have a common point that was consistent throughout all pieces. Taking advantage of the fact that the home could be larger than the piece and that it would still appear at the upper-left corner of the home meant that I could extend the home all the way to the end of the area and the piece would still be in the same position.

Every home I create, then, was always relative to the previous home. But this time, the computation was from its end. A home is at the whole area’s width minus its x position subtracted again from its width. (Confusing, I know, but hopefully the image is clearer.) A home is also always set with the same height as the piece so that a trivial addition of 20 would place the next home (and its corresponding piece) at exactly 20 units below it.

With that, the positions of the home of any piece that must be placed at (x,y) is as follows:

**(R,w,-(w-x),d,20,piece_width,piece_height) **

## Leave a Reply