use strict;
use warnings;
use Data::Dumper;

my $area = [ [ 10, 20 ] ];
my $rect = [ [ 5, 12 ], [ 4, 8 ], [ 12, 2 ] ];

foreach my $r (@$rect) {
    my $leftover = [];
    foreach (@$area) {
        my ($n1, $n2) = fit_rect_in_area($r, $_);
        next if !defined $n1;
        $leftover = [ @$leftover, @$n1, @$n2 ];
    }
    $area = $leftover;
}

#
#  +------------------------+
#  |                        |
#  |                        |
#  +---------------+        |
#  |               |        |
#  |               |        |
#  +---------------+--------+
#
#  two left over area options =>
#
#  +------------------------+     +--------+
#  |                        |  +  |        |
#  |                        |     |        |
#  +------------------------+     +--------+
#
#  or
#
#  +---------------+     +--------+
#  |               |  +  |        |
#  |               |     |        |
#  +---------------+     |        |
#                        |        |
#                        |        |
#                        +--------+
#

sub fit_rect_in_area
{
    my ($rect, $area) = @_;
    if (canfit($rect, $area)) {
        print rectstr($rect) . " can fit inside " . rectstr($area) . "
+\n";
        my ($n1, $n2) = fitrect($rect, $area);
        print "leftover option 1: " . join(" and ", map { rectstr($_) 
+} @{$n1}) . "\n";
        print "leftover option 2: " . join(" and ", map { rectstr($_) 
+} @{$n2}) . "\n";
        return ($n1, $n2);
    } elsif (canfit(rotate($rect), $area)) {
        print rectstr($rect) . " can fit inside " . rectstr($area) . "
+ after rotation\n";
        my ($n1, $n2) = fitrect(rotate($rect), $area);
        print "leftover option 1: " . join(" and ", map { rectstr($_) 
+} @{$n1}) . "\n";
        print "leftover option 2: " . join(" and ", map { rectstr($_) 
+} @{$n2}) . "\n";
        return ($n1, $n2);
    } else {
        print rectstr($rect) . " can not fit inside " . rectstr($area)
+ . "\n";
        return ();
    }
}

# place rect on area
sub fitrect
{
    my ($rect, $area) = @_;

    my $a1 = [ $area->[0] - $rect->[0], $area->[1] ];
    my $a2 = [ $rect->[0], $area->[1] - $rect->[1] ];

    my $b1 = [ $area->[0] - $rect->[0], $rect->[1] ];
    my $b2 = [ $area->[0], $area->[1] - $rect->[1] ];

    return ([ $a1, $a2 ], [ $b1, $b2 ]);
}

# check if a rect can fit
sub canfit
{
    my ($rect, $area) = @_;
    return $rect->[0] <= $area->[0] && $rect->[1] <= $area->[1];
}

# rotate a rectangle
sub rotate
{
    my $rect = shift;
    return [ $rect->[1], $rect->[0] ];
}

# return textual representation of rectangle
sub rectstr
{
    my $rect = shift;
    return sprintf "R(W=%d, H=%d)", $rect->[0], $rect->[1];
}
[download]

R(W=5, H=12) can fit inside R(W=10, H=20)
leftover option 1: R(W=5, H=20) and R(W=5, H=8)
leftover option 2: R(W=5, H=12) and R(W=10, H=8)
R(W=4, H=8) can fit inside R(W=5, H=20)
leftover option 1: R(W=1, H=20) and R(W=4, H=12)
leftover option 2: R(W=1, H=8) and R(W=5, H=12)
R(W=4, H=8) can fit inside R(W=5, H=8)
leftover option 1: R(W=1, H=8) and R(W=4, H=0)
leftover option 2: R(W=1, H=8) and R(W=5, H=0)
R(W=4, H=8) can fit inside R(W=5, H=12)
leftover option 1: R(W=1, H=12) and R(W=4, H=4)
leftover option 2: R(W=1, H=8) and R(W=5, H=4)
R(W=4, H=8) can fit inside R(W=10, H=8)
leftover option 1: R(W=6, H=8) and R(W=4, H=0)
leftover option 2: R(W=6, H=8) and R(W=10, H=0)
R(W=12, H=2) can not fit inside R(W=1, H=20)
R(W=12, H=2) can fit inside R(W=4, H=12) after rotation
leftover option 1: R(W=2, H=12) and R(W=2, H=0)
leftover option 2: R(W=2, H=12) and R(W=4, H=0)
R(W=12, H=2) can not fit inside R(W=1, H=8)
R(W=12, H=2) can fit inside R(W=5, H=12) after rotation
leftover option 1: R(W=3, H=12) and R(W=2, H=0)
leftover option 2: R(W=3, H=12) and R(W=5, H=0)
R(W=12, H=2) can not fit inside R(W=1, H=8)
R(W=12, H=2) can not fit inside R(W=4, H=0)
R(W=12, H=2) can not fit inside R(W=1, H=8)
R(W=12, H=2) can not fit inside R(W=5, H=0)
R(W=12, H=2) can not fit inside R(W=1, H=12)
R(W=12, H=2) can not fit inside R(W=4, H=4)
R(W=12, H=2) can not fit inside R(W=1, H=8)
R(W=12, H=2) can not fit inside R(W=5, H=4)
R(W=12, H=2) can not fit inside R(W=6, H=8)
R(W=12, H=2) can not fit inside R(W=4, H=0)
R(W=12, H=2) can not fit inside R(W=6, H=8)
R(W=12, H=2) can not fit inside R(W=10, H=0)
[download]

This is the knapsack problem. It is NP-hard. Were you to find a polynomial-time solution to it, you'd have basically solved all the hardest problems in computer science.

There are heuristic approaches that shoot for decent solutions that don't attempt or claim to be optimal solutions. If you follow the Google link above, you'll probably find some.

I apologize, but I thought that I was trying to simplify my problem, but all I was really doing was asking it again. I am looking to have either a vertical or horizontal line from one edge to the other, but I do not know how to create the loop(s) and how to determine which is the "best" to create the vertical or horizontal line. Could someone help me by maybe pointing me to some code that will help me set up these loops. I would like to start with the largest x or y, and then on the next iteration, use the second largest x or y. I do not know how to accomplish this.

What's this business of a horizontal or vertical line dividing the area, by the way? That's just confusing the issue. Can I solve the problem for you by saying "put that line one millimetre from the edge and then solve the knapsack thing with your MaxX x MaxY area one millimetre smaller than before?"

The practical side of this knapsack business, by the way, is that you can spend enormous amounts of time finding better and better solutions, but they'll only be slightly better. If you find a solution that's about 80% better than random, then stop looking and go with it. People who really understand math, please correct me if I'm wrong, but there's no point continuing trying to find a slightly-more-perfect solution, unless you're chopping up solid gold, I guess.

---




($_='kkvvttuubbooppuuiiffssqqffssmmiibbddllffss')
 =~y~b-v~a-z~s;                             print
[download]

This may not be a question all about Perl

Not only is it not "all about Perl" it is not at all about Perl.

Do you care to share with us the code you've written so far? Maybe we can help you find your mistakes...

-sauoq
"My two cents aren't worth a dime.";