Make delicious recipes!

Fit maximum no of cuboids into each other


Problem: Given a lot of cuboid boxes with different length, breadth and heights, find the
maximum subset of cubes which can fit into each other.

Solution: This problem is just another form of the Longest Increasing Subsequence (LIS) problem.

Imagine what would happen if the boxes were perfect cubes (i.e. l=b=h for each box)
If boxes were perfect cubes, then one box will fit inside other only if its side is smaller than other.
So, in that case, the problem will become exactly the same as LIS.

For cuboid case, only difference is that the comparison function here will compare all three dimensions: l, b and h.
A comparator like the following should work:

class Box implements Comparable<Box>
{
    public int l;
    public int b;
    public int h;

    public Box(int l, int b, int h)
    {
        this.l = l;
        this.b = b;
        this.h = h;
    }

    @Override
    public int compareTo(Box other)
    {
        if (this.l < other.l && this.b < other.b && this.h < other.h)
            return -1;
        if (this.l == other.l && this.b == other.b && this.h == other.h)
            return 0;
        if (this.l > other.l && this.b > other.b && this.h > other.h)
            return 1;
        throw new IllegalArgumentException("Cannot compare " + this + " to " + other);
    }
}

Note that the comparator only gives valid results when box is equal or completely fits another.
For other cases like comparing Box(5,6,7) with Box(6,6,6), the compareTo function throws an exception.
The application logic should handle this exception and use it accordingly when writing the LIS for boxes.

Note that LIS does not sort the input but in this case, there is no requirement to preserve the order of the boxes.
So to maximize the number of fitting boxes, we should sort the array of boxes before finding LIS.

Example: If boxes were: [{9,8,7}, {5,4,3}, {4,3,2}, {3,9,9}], then without sorting, LIS would return zero.
But with sorting, order of boxes becomes [{3,9,9}, {4,3,2}, {5,4,3}, {9,8,7}] and LIS would return 3.
The comparator used for sorting this can return either of -1,0,1 because during sorting, it does not matter if
two unfitting boxes come before or after each other. Only requirement is that fitting boxes should be in order.



Above solution does not consider box-rotations.
Example rotation could be where a box like {2,4,6} can be rotated to {4,2,6} for fitting inside {5,3,6}
Or where a box {2,4,6} can be rotated to {6,4,2} and then rotated to {4,6,2} for fitting inside {5,7,3}.
One possible solution could be to sort the boxes' dimensions individually (such that l <= b <= h for each box)
before doing anything else. This would make sure that the lowest of each box is compared with the lowest of target box.

Example: If boxes were: [{9,8,7}, {5,4,3}, {4,3,2}, {3,9,1}],

then dimension sort would give: [{7,8,9}, {3,4,5}, {2,3,4}, {1,3,9}]

array sort would give: [{1,3,9}, {2,3,4}, {3,4,5}, {7,8,9}]

And the LIS for the above would be: [{2,3,4}, {3,4,5}, {3,9,9}]






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal