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

$|=1;
$HORIZ =  int (2995/100);        # altura inicial
$VERT  =  int (1250/100);       # ancho
$GRID = 1;          # escalado (nulo)
$MAXBIN = 8;
$REPORT = 0;
if ($REPORT==0){
    use integer;
}

for $i (1..$HORIZ*$GRID){
    for $j (1..$VERT*$GRID){
	for $z (1..$MAXBIN){
	    $s[$i][$j][$z]=0;
	}
    }
}

# H   W
# 2995 1250
# N  H  W
# 1 420 240
# 1 400 240
# 2 2035 95
# 6 1138 731
# 4 1464 611
# 2 2057 416

$o[1][1]=420; $o[1][2]=240;
$o[2][1]=400; $o[2][2]=240;
$o[3][1]=2035; $o[3][2]=95;
$o[4][1]=2035; $o[4][2]=95;
$o[5][1]=1138; $o[5][2]=731;
$o[6][1]=1138; $o[6][2]=731;
$o[7][1]=1138; $o[7][2]=731;
$o[8][1]=1138; $o[8][2]=731;
$o[9][1]=1138; $o[9][2]=731;
$o[10][1]=1138; $o[10][2]=731;
$o[11][1]=1464; $o[11][2]=611;
$o[12][1]=1464; $o[12][2]=611;
$o[13][1]=1464; $o[13][2]=611;
$o[14][1]=1464; $o[14][2]=611;
$o[15][1]=2057; $o[15][2]=416;
$o[16][1]=2057; $o[16][2]=416;

$N = 16;   # número de objetos
for $i (1 .. $N){   # generación aleatoria de dimensiones 
    $o[$i][1]=int $o[$i][1]/100;
    $o[$i][2]=int $o[$i][2]/100;
    $o[$i][3]=0;
    $o[$i][4]=$o[$i][1]*$o[$i][2];
}

$BIN=1;
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;
    $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][$BIN]) || $ok==1){
		if ($ok==0){
		    if (($s[$i][$j][$BIN]==0 && $s[$a][$b][$BIN]==0 
			&& $s[$a][$j][$BIN]==0
			&& $s[$i][$b][$BIN]==0)){
			    $ok=1;
			    $o[$k][3]=$BIN;  # 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][$BIN]!=0){
			    destroy($s[$i][$j][$BIN]); 
			}
			$s[$i][$j][$BIN]=$k;            # se asigna el objeto al elemento
			$kontador++;
#			    last if ($kontador==$o[$k][4]);
		    }
	    }
	}
    }
    if ($kontador != $o[$k][4]){ 
#	warn "Error de objeto - altura baja";
#	print "contador $kontador - tamaño $o[$k][4]\n";
	destroy($k);
	$fallo++; 
	if ($fallo>=$N/2) {
	    $fallo=0;
#	    report();
	    $BIN++;
	}
    }
    $counter=0;
    for (1..$N){
	if ($o[$_][3]>0){ $counter++; }
    }
    if ($counter==$N){
	report();
	exit;
    }
}

sub report {
    for $z (1..$BIN){
	    $count=0;  
	    for $i (1 .. $HORIZ*$GRID){
		for $j (1 .. $VERT*$GRID){
		    if ($s[$i][$j][$z]!=0) { $count++; }
		}
	    }
	    $percent = 100*$count/($HORIZ*$GRID*$VERT*$GRID);
	if ($REPORT) {
	    for $i (1..$HORIZ*$GRID){ # dibujar el resultado
		for $j (1..$VERT*$GRID){
		    print chr(33+$s[$i][$j][$z] % 90);  # ! = espacio libre
		}
		print "\n";
	    }
	}else{
            print "Bin $z: lista de objetos\n";
            for $k (1..$N){
		if ($o[$k][3]==$z){
		    print "$k: $o[$k][1] x $o[$k][2]\n"; 
		}
            }       
	}
        print "BIN $z. La ocupación es del $percent%\n";
    }
}

sub destroy {
    my $kk = $_[0];
    $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][$BIN]==$kk) { 
		$s[$ii][$jj][$BIN]=0;  # desocupa el espacio
	    }
	}
    }
}

__END__