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

# Burro: fase1 zonifi (finita) y fase2 tsp simple rotatorio
# duda: repartir en n puntos iguales o zonificación libre



$|=1;

open (IN, "<","coordenadas") || die "Cannot open coordenadas:$!";
while (<IN>){
    next if (/^#/);
    next if (/^teco/);
    next if (/^costa/);
    chomp;
    $n++;
    @linea = split /\s+/,$_;
    $nombre[$n]=$linea[0];
    $x[$n]=$linea[1];
    $y[$n]=$linea[2];
    $h[$n]=1;
}
close IN;

for $i (1..$n){
    for $j (1..$i){
	$d[$i][$j]=sqrt( ($x[$i]-$x[$j])**2 + ($y[$i]-$y[$j])**2 );
	$d[$j][$i]=$d[$i][$j];
    }
}

$NN = 8;            # NUMBER OF SALESMEN!
$PUNTOS = $n;

$mindist=9e99;
while (1){
    $iteracion++;
    $w = 1+ int rand ($PUNTOS);
    $grupold = $h[$w];
    $grupnew = 1+int rand ($NN);
    $h[$w] = $grupnew;
    $totdist=0;
    for $g (1..$NN){
	for $i (1..$PUNTOS){
	    if ($h[$i] == $g){
		for $j (1..$PUNTOS){
		    if ($h[$j] == $g){
			$totdist += $d[$i][$j];
		    }
		}
	    }
	}
    }
    if ($totdist<$mindist){
	$mindist=$totdist;
	print "\nDistancia total $totdist\n";
	for $g (1..$NN){
	    print "ZONA $g: ";
	    for $i (1..$PUNTOS){
		if ($h[$i]==$g){
		    print "$i ";
		}
	    }
	    print "\n";
	}
	$iteracion = 0;
    }else{
	$h[$w]=$grupold;
	last if ($iteracion > 2*$PUNTOS*$PUNTOS);
    }
}

for $j (1..$NN){
    for $i (1..$PUNTOS){
	if ($h[$i]==$j){
	    $size[$j]++;
	    $p[$j][$size[$j]]=$i;
	}
    }
}

$MINI = 9e99;
$iteracion=0;
while (1){
    $j++;
    if ($j > $NN) { $j = 1; }
    $iteracion++;
    $k = 1+ int rand ($size[$j]);
loop0:     
    $l = 1+ int rand ($size[$j]);
    if ($k == $l) { goto loop0; }
    
    if ($k == 1) { $antesk = $p[$j][$size[$j]]; }
    else { $antesk = $p[$j][$k-1]; }
    if ($k == $size[$j]) { $despuesk = $p[$j][1]; }
    else { $despuesk = $p[$j][$k+1]; }
    $temp0 = $d[$antesk][ $p[$j][$k] ] + $d[$p[$j][$k]][ $despuesk ];

    if ($l == 1) { $antesl = $p[$j][$size[$j]]; }
    else { $antesl = $p[$j][$l-1]; }
    if ($l == $size[$j]) { $despuesl = $p[$j][1]; }
    else { $despuesl = $p[$j][$l+1]; }
    $temp0 += $d[$antesl][ $p[$j][$l] ] + $d[$p[$j][$l]][ $despuesl ];

    $temp1 = $d[$p[$j][$l]][ $antesk ] + $d[$p[$j][$l]][ $despuesk ];
    $temp1 += $d[$p[$j][$k]][ $antesl ] + $d[$p[$j][$k]][ $despuesl ];

    if ($temp0 > $temp1 ){
	$temp=$p[$j][$k];
	$p[$j][$k]=$p[$j][$l];
	$p[$j][$l]=$temp;
	@dist=undef;
	$sumadist=0;
	for $z (1..$NN){
	    for $i (1..$size[$z]){
		if ($i+1 == 1+$size[$z]){
		    $dist[$z]+=$d[ $p[$z][$size[$z]] ][$p[$z][1]];
		}else{
		    $dist[$z]+=$d[$p[$z][$i]][$p[$z][$i+1]];
		}
	    }
	    $sumadist +=$dist[$z];
	}
	if ($sumadist < $MINI ) {
	    $MINI = $sumadist;
	    $sol++;
	    print "\n$0: Iteración $iteracion, Ahorro ", $temp0-$temp1, "\n";
	    print "Solución $sol: Distancia total = $sumadist\n";
	    for $z (1..$NN){
		print "Viajante $z ";
		print "-> distancia $dist[$z]: ";
		for $i (1..$size[$z]){
		    print "$p[$z][$i] ";
		}
		print "\n";
	    }
	}else{
	    $temp=$p[$j][$k];
	    $p[$j][$k]=$p[$j][$l];
	    $p[$j][$l]=$temp;
	}
    }
}

exit;



$size= 1+int($PUNTOS/$NN);
$holgura = $size*$NN-$PUNTOS;

$j=1;
$k=0;
for $i (1..$PUNTOS){
    $k++;
    if ($k < $size){
	$p[$j][$k]=$i;
	$h[$i]=$j;
	$l[$i]=$k;
    }elsif ($j <= $holgura){
	$p[$j][$k]=-2;
	$k=1;
	$j++;
	$p[$j][$k]=$i;
	$h[$i]=$j;
	$l[$i]=$k;
    }else{
	$p[$j][$k]=$i;
	$h[$i]=$j;
	$l[$i]=$k;
	$k=0;
	$j++;
    }
}

$MIN=9e99;
$sqmin=9e99;
$iteracion=0;
for (;;){
    @r=();
    $suma=0;
    for $j (1..$NN){
	for $i (1..$size-1){
	    if ($p[$j][$i+1]>0){
		$r[$j] += $d[ $p[$j][$i] ][ $p[$j][$i+1] ];
		if ($i+1==$size){
		    $r[$j] += $d[ $p[$j][$size] ][ $p[$j][1] ];
		    last;
		}
	    }else{
		$r[$j] += $d[ $p[$j][$i] ][ $p[$j][1] ];
		last;
	    }
	}
	$suma += $r[$j];
    }
    $media = $suma / $NN;
    $sqerr=0;
    for $j (1..$NN){
	$sqerr += ($r[$j]-$media)**2;
    }
    if ($suma<$MIN){
#    if ($sqerr<=$sqmin){
	$kk++;
	$MIN=$suma;
	$sqmin=$sqerr;
	print "\n$0: Problema de $PUNTOS puntos, con $NN vendedores\n";
	print "Iteracion $iteracion, solucion $kk, ";
	printf "distancia %.3f, ",$suma;
	printf "error %.3f\n", $sqerr;
	for $j (1..$NN){
	    print "Viajante $j distancia ";
	    printf "%.3f: ",$r[$j];
	    for $i (1..$size){
		if ($p[$j][$i]>0) { print "$p[$j][$i] "; }
	    }
	    print "\n";
	}
    }
##############################    
# $z=1+int rand($PUNTOS);
loop: 
    
    $iteracion++;
    $z = 1+ int rand($PUNTOS);
#    $z++;
#    if ($z>$PUNTOS) {
#	$z=1;
	$m++;
	if ($m>$PUNTOS){
	    $m =1;
#	    $z = 1+int rand($PUNTOS);
	}
#    }
#    $m = 1+ int rand($PUNTOS);
    if ($z==$m) { goto loop; }
    
    $ii= $h[$z];
    $jj= $h[$m];
    $i = $l[$z];
    $j = $l[$m];
    
#    if ($ii == $jj){
#	$min=($i>$j) ? $j : $i;
#	$max= ($i>$j) ? $i : $j;
#	if ($min > 1 && $max<$size-1){
#	    if ($i == $j+1 || $i == $j-1){
#		$temp0 = $d[$p[$ii][$min-1]][$p[$ii][$min]]
#		  +$d[$p[$ii][$max]][$p[$ii][$max+1]];
#		$temp1 = $d[$p[$ii][$min-1]][$p[$ii][$max]]
#		  +$d[$p[$ii][$min]][$p[$ii][$max+1]];
#		goto vecinos;
#	    }
#	}
#    }
    
    if ($p[$ii][$size]>0){ $ultimo = $p[$ii][$size] ; }
    else { $ultimo = $p[$ii][$size-1]; }
    if ($i-1==0) { $antesz=$ultimo; }
    else { $antesz=$p[$ii][$i-1]; }
    if ($i+1==$size+1 || $p[$ii][$i+1]==-2){ $despuesz=$p[$ii][1]; }
    else { $despuesz=$p[$ii][$i+1]; }
             
    $d1 = $d[$z][ $antesz ] + $d[$z][ $despuesz ];

    if ($p[$jj][$size]>0){ $ultimo = $p[$jj][$size] ; }
    else { $ultimo = $p[$jj][$size-1]; }
    if ($j-1==0) { $antesm=$ultimo; }
    else { $antesm=$p[$jj][$j-1]; }
    if ($j+1==$size+1 || $p[$jj][$j+1]==-2){ $despuesm=$p[$jj][1]; }
    else { $despuesm=$p[$jj][$j+1]; }

    $d2 = $d[$m][ $antesm ] + $d[$m][ $despuesm ];
    $temp0 = $d1+$d2;
    
    $temp1 = $d[$m][ $antesz ] + $d[$m][ $despuesz ];
    $temp1 += $d[$z][ $antesm ] + $d[$z][ $despuesm ];

vecinos:	
    if ($temp0>$temp1){
	$p[$ii][$i]=$m;
	$h[$m]=$ii;
	$l[$m]=$i;
	$p[$jj][$j]=$z;
	$h[$z]=$jj;
	$l[$z]=$j;
    }else { 
	goto loop;
    }
}

__END__
mtsp6: Iteración 48060, Ahorro 7.54400374531753117
  Solución 445: Distancia total = 10685.4348473080253
  Viajante 1 -> distancia 1266.69876063025278: 43 55 72 132 27 82 181 138 100 222
  139 92 121 145 110 135 155 210 146 214 168
  Viajante 2 -> distancia 2057.99975977288913: 119 208 109 120 28 47 60 57 16 90 67 160 14 2 106 203 205 195 53 151 103 83 129
  Viajante 3 -> distancia 1557.81467944122265: 3 52 44 200 35 220 143 154 199 66 136 131 6 125 65 13 177 10 15 12 206 124 39 164 96 193 46 216 40 64 59 77 219 134 217 221
  Viajante 4 -> distancia 1244.22121406064337: 54 102 29 117 114 140 41 211 171 174 173 172 49 31 163 191 115 209 133 73 79 37 84 126 158 127 183 170 32 68 78 45
  213 212 190 157 201 101 88 162 70
  Viajante 5 -> distancia 1139.75263357635987: 198 34 74 104 11 50 51 166 86 42 180 112 97 107 61 4 204 62 150 17 118 159 128 20 91 149 161 48 153 175 71 116 122
  Viajante 6 -> distancia 943.513536387628409: 22 1 25 93 184 137 108 152 95 24 192 185 186
  Viajante 7 -> distancia 1144.5536193364733: 69 179 99 81 169 147 30 36 33 76 176 89 156 23 218 105 123 167 197 38 182 202 223 87 141 63
  Viajante 8 -> distancia 1330.88064410255578: 56 111 9 98 80 75 142 19 7 58 85 5
  196 21 148 94 113 130 194 189 144 165 26 215 178 207 18 188 8 187