#!/usr/local/bin/perl -w

$|=1;
# strip packing 2D with rotation
$HORIZ =  2;        # altura inicial
$VERT  =  60;       # ancho
$GRID = 1;          # escalado (nulo)

for $i (1..$HORIZ*$GRID*10_000){   # máxima altura
    for $j (1..$VERT*$GRID){
	$s[$i][$j]=0;
    }
}

$N = shift || 90;   # número de objetos
for $i (1 .. $N){   # generación aleatoria de dimensiones 
    $l = 2+int (rand(10)*$GRID);
    $w = 2+int (rand(6)*$GRID);
    if ($w > $l) { ($w, $l) = ($l, $w); }   # swap
    $o[$i][1]=$l;
    $o[$i][2]=$w;
    $o[$i][3]=0;
    $o[$i][4]=$l*$w;
}

$MAXpercent=0;
for (;;){
    for $i (1 .. $HORIZ*$GRID){
	for $j (1 .. $VERT*$GRID){
	    $s[$i][$j]=0;
	}
    }
    $HORIZ=2;
    for $i (1 .. $N){
	$o[$i][3]=0;
    }
    for (;;){       # bucle principal 
	do{    
	    $k = 1+int(rand($N));
	}until($o[$k][3]==0);  # hasta encontrar un objeto libre
	$h = int (.5+rand());
	if ($h==0) {         # rotación de 90 grados
	    ($o[$k][1],$o[$k][2])=($o[$k][2],$o[$k][1]); }
	$ok=0;
	$HORIZ++;            # se sube la altura en una unidad
	$cc=0;
	$kontador=0;
	for $i (1..$HORIZ*$GRID){
	    $a = $i+$o[$k][1];
	    for $j (1..$VERT*$GRID){
		$b = $j+$o[$k][2];
		if (defined($s[$a][$b]) || $ok==1){
		    if ($ok==0){
			if (($s[$i][$j]==0 && $s[$a][$b]==0 
			    && $s[$a][$j]==0
			    && $s[$i][$b]==0)){
				$ok=1;
				$o[$k][3]=1;         # el objeto está asignado
				$origi=$i;
				$origj=$j;
				$limith=$a-1;
				$limitv=$b-1;
			    }
		    }
		    if ($ok==1 && $i>=$origi && $j>=$origj 
			&& $i<=$limith && $j<=$limitv) {
			    if ($s[$i][$j]!=0){
				destroy($s[$i][$j]); 
			    }
			    $s[$i][$j]=$k;            # se asigna el objeto al elemento
			    $kontador++;
#			    last if ($kontador==$o[$k][4]);
			}
		}
		if ($i==$HORIZ*$GRID && $s[$i][$j]==0) { $cc++; }
	    }
	}
	if ($cc==$VERT*$GRID){ $HORIZ--; }
	if ($kontador != $o[$k][4]){ 
#	warn "Error de objeto - altura baja";
#	print "contador $kontador - tamaño $o[$k][4]\n";
	    destroy($k);
	}
	if ($limitv-$origj+1 != $o[$k][2] &&
	    $limitv-$origj+1 != $o[$k][1]){ warn "Error de w o l"; }
	if ($limith-$origi+1 != $o[$k][1] &&
	    $limith-$origi+1 != $o[$k][2]){ warn "Error de l o w"; }
	$ok=0;
	for $i (1..$N){
	    if ($o[$i][3]==0) { $ok=1; }
	}
	last if ($ok==0);  # si todos los objetos están asignados, acabar
    }

    $count=0;  
    for $i (1 .. $HORIZ*$GRID){
	for $j (1 .. $VERT*$GRID){
	    if ($s[$i][$j]!=0) { $count++; }
	}
    }
    $percent = 100*$count/($HORIZ*$GRID*$VERT*$GRID);
    if ($percent >= $MAXpercent){
	$MAXpercent = $percent;
	for $i (1..$HORIZ*$GRID){ # dibujar el resultado
	    for $j (1..$VERT*$GRID){
		print chr(33+$s[$i][$j] % 90);  # ! = espacio libre
	    }
	    print "\n";
	}
	print "$HORIZ\n";    # decir la altura
	print "La ocupación es del $percent%\n";
    }
}

sub destroy {
    my $kk = @_;
    $o[$kk][3]=0;   # libera al objeto de debajo
    for my $ii (1..$HORIZ*$GRID){
	for my $jj (1..$VERT*$GRID){
	    if ($s[$ii][$jj]==$kk) { 
		$s[$ii][$jj]=0;  # desocupa el espacio
	    }
	}
    }
}



__END__

Referecias:
www.math.tu-dresden.de/~belov/publ/text030908_SUBMIT.ps