package evolution;

import java.awt.*;
import java.lang.Math;
import java.util.Random;

/** solve NxN magic squares using genetic algorithms with a 
 ** special repair operator
 ** @version 0.1
 ** @author  hthadler
 **/
public class MagicSquare_bit extends GAgui 
{
  static protected Random randgen = new Random();
  static protected Font   nfont   = new Font("Courier",Font.PLAIN,8);
  static protected Double optimal = new Double(0);

  int big_n=4; 
  int num_bits=5; //[1..16] = 5 bits;


  /**
   **/
  public GAchromosome repair( GAchromosome c )
  {
 
    int [] is = new int [big_n*big_n+1];
    for(int i=1; i=big_n*big_n; i++)
      is[i]=c.decode_to_int(i-1);

    // detect 'out of range' values
    int min=1;
    int max=big_n*big_n;
    for(int i=1; i=big_n*big_n; i++)
    {
      if( is[i]  min )
        is[i]=min;
      if( is[i]  max )
        is[i]=max;
    }

    // get value count
    int [] num_count = new int [big_n*big_n+1];
    for( int i=1; i=big_n*big_n; i++)
    {
      int cnt = 0;
      for( int j=1; j=big_n*big_n; j++)
        if( is[j] == i )
          cnt++;
      num_count[i]=cnt;
    }

    // is[i] = number in cell i
    // num_count[i] = # of i in is[i]
    // replace values with count  1 with values with count = 0
    for( int i=1; i=big_n*big_n; i++ )
    {

      while(num_count[i]  1) 
      {
        int j=1+(int)(randgen.nextDouble()*((double)big_n*big_n));
        while( num_count[1+j%(big_n*big_n)]  0) 
          j++;
        j=1+j%(big_n*big_n);

        num_count[j]++;
        num_count[i]--;   
      
        //search for i and replace it by j
        boolean replaced = false;
        int k = (int)(((double)(big_n*big_n))*randgen.nextDouble());
        while(!replaced)
        {
          if( is[(1+k)%(big_n*big_n+1)] == i )
          {
            is[(1+k)%(big_n*big_n+1)]=j;
            replaced = true;
          }
          k++;
        }
      }
    }

    for( int i=0; ibig_n*big_n; i++)
       c.set_param_int(i,is[i+1]);
  
    return c;
  }


  /**
   **/
  public GAchromosome [] startpopulation(int num)
  {   
 
    //create num new chromosomes
    GAchromosome [] s = new GAchromosome[num];

    for(int i=0; inum; i++)
    {
      s[i]=new GAchromosome( big_n*big_n, num_bits);
      s[i]= this.repair(s[i]);
    }
    return s;
  }


  /**
   **/
  public Dimension dimension_of_drawing_area()
  {
    int num_digits=0;
    int magic_sum=(big_n*(big_n*big_n+1))/2;    
    double how_many_digits = (double)(magic_sum);
    for(int i=0; how_many_digits = 1; i++)
    {
       how_many_digits/=10;
       num_digits++;
    }
    if( num_digits  3 )
      num_digits = 3;
    int box_dim = (num_digits+1)*nfont.getSize();
    return new Dimension((big_n+2)*box_dim,(big_n+2)*box_dim); 
  }




  /** 
   **/
  public double calc_quality(GAchromosome c)
  {
    double quality,S,s;
    int i,j,len;

    len = big_n;
  
    S = 0.5*len*(len*len+1);
 
    quality=0.0;

    //rows
    for(i=0; ilen; i++)
    {
      s=0.0;
      for(j=0; jlen; j++)
      {
        s+=c.decode_to_int(i*len+j);
      }
      quality += (S-s)*(S-s);
    }

    //columns
    for(i=0; ilen; i++)
    {
      s=0.0;
      for(j=0; jlen; j++)
      {
        s+=c.decode_to_int(j*len+i);
      }
      quality += (S-s)*(S-s);
    }
    

    //diagonal top,left - bottom,right
    s=0.0;
    for(i=0; ilen; i++)
      s+=c.decode_to_int(i*len+i);
    quality += (S-s)*(S-s);

    //diagonal bottom,left - top,right
    s=0.0;
    for(i=0; ilen; i++)
      s+=c.decode_to_int((len-i-1)*len+i);
    quality += (S-s)*(S-s);

    return(quality);
  }


  /** draw a given chromosome using Graphics object g
   ** @param g Graphics object @see java.awt.Graphics
   ** @param c chromosome to be drawn
   **/
  public void draw_single(Graphics g, GAchromosome c)
  {
    int [] colors = new int [big_n*big_n];
    int [] rows   = new int [big_n];
    int [] cols   = new int [big_n];
    int [] diag   = new int [2];
    
    int len = big_n;
    int magic_sum=(len*(len*len+1))/2;

    // get row sums
    int s=0;
    for(int i=0; ilen; i++)
    {
      s=0;
      for(int j=0; jlen; j++)
        s+=c.decode_to_int(i*len+j);
      rows[i]=s;
    }

    // get column sums
    for(int i=0; ilen; i++)
    {
      s=0;
      for(int j=0; jlen;j++)
        s+=c.decode_to_int(j*len+i);
      cols[i]=s; 
    }

    // get diagonal sums
    s=0;
    for(int i=0; ilen; i++)
      s+=c.decode_to_int(i*len+i);
    diag[0]=s;
    s=0;
    for(int i=0; ilen; i++)
      s+=c.decode_to_int((len-i-1)*len+i);
    diag[1]=s;


    // get colors
    // cols: 1 (blue), rows: 2(green), diag: 4(red)
    for(int i=0; ilen; i++)
    {
      if( rows[i] == magic_sum ) 
      {
        for(int j=0; jlen; j++)
          colors[i*len+j]+=2;
      }  
      if( cols[i] == magic_sum )
      {
        for(int j=0; jlen; j++)
          colors[j*len+i]+=1;
      }
    }
    if(diag[0]==magic_sum)
      for(int i=0; ilen; i++)
        colors[i*len+i]+=4;
 
    if(diag[1]==magic_sum)
      for(int i=0; ilen; i++)
        colors[i*len+(len-i-1)]+=4;


    // get dimension for a single number-box
    int num_digits=0;
    double how_many_digits = (double)(magic_sum);
    for(int i=0; how_many_digits = 1; i++)
    {
       how_many_digits/=10;
       num_digits++;
    }
    if( num_digits  3 )
      num_digits = 3;
    int box_dim = (num_digits+1)*nfont.getSize();
    int y_off   = 4;
    int x_off   = 4;
 
    g.drawRect(0,0,
                dimension_of_drawing_area().width-1,
                dimension_of_drawing_area().height-1);

    // draw colored boxes
    for(int i=0; ilen; i++)
    {
      for(int j=0; jlen; j++)
      {
        switch(colors[i*len+j])
	{
	  case 0: g.setColor(this.getBackground());
            break;
	  case 1: g.setColor(Color.blue);
            break;
	  case 2: g.setColor(Color.blue);
            break;
	  case 3: g.setColor(Color.green);
            break;
	  case 4:
	  case 5: 
	  case 6:
	  case 7: g.setColor(Color.red);
            break;
	  default: g.setColor(Color.red);
            break;
	}
        g.fillRect(box_dim+i*box_dim, box_dim+j*box_dim,
                   box_dim, box_dim);
        g.setColor(Color.white);
        g.fillRect(box_dim+i*box_dim+4, box_dim+j*box_dim+4,
                    box_dim-7,box_dim-7);
        g.setColor(Color.black);
        g.drawRect(box_dim+i*box_dim, box_dim+j*box_dim,
                   box_dim, box_dim);
        g.drawString(""+c.decode_to_int(i*len+j), 
                      box_dim+i*box_dim + x_off, 
                      box_dim+(j+1)*box_dim-y_off);
      }
    }

    // draw column sums
    for(int i=0; ilen; i++)
      g.drawString(""+cols[i], (len+1)*box_dim+x_off, (i+2)*box_dim-y_off);

    // draw row sums
    for(int i=0; ilen; i++)
      g.drawString(""+rows[i], (i+1)*box_dim+x_off,   (len+2)*box_dim-y_off);

    //draw diagonal sums
    g.drawString(""+diag[0], (len+1)*box_dim+x_off, (len+2)*box_dim-y_off);
    g.drawString(""+diag[1], x_off            , (len+2)*box_dim-y_off);
 
  }

  /**
   **/
  public void init()
  {
    //read appletparameter and get number of bits needed
    //to encode a single parameter
    try 
    { 
      big_n = (int)Integer.parseInt(getParameter("n")); 
      int n = 1;
      int nb = 1;
      while( big_n*big_n  n )
      {
        n = n  1;
        nb++;
      }
      num_bits = nb;
    }
    catch ( NumberFormatException e) 
    { 
      big_n = 4; num_bits=5; 
    } 
    super.init();
    //setup problem-specific gui here
    super.set_parameters(GA.elite,true,
                         1,1,100,
                         100,1,1000,
                         1,1,big_n*big_n-1,
                         0.1,
                         1.0);
  }

  /**
   **/
  public Double optimum()
  {
    return optimal;
  }

  /** 
   **/
  public String[][] getParameterInfo()
  {
    String[][]info=
    { // name, type, description
      {"n",  "integer", "n × n magic square"}
    };
    return info; 
  }

}