import java.awt.*;
import java.applet.*;
import java.util.*;

public class MagicSquare extends Applet implements Runnable {
/************************************************************************/
/*									*/
/*		Class MagicSquare: Magic Square Finder			*/
/*									*/
/*		Copyright (C) 1996 by Yasusi Kanada			*/
/*									*/
/*	This program can be freely distributed under the GNU General	*/
/*	Public License.							*/
/*									*/
/* Initial Version = "ver 1.00, 1996-8-13";				*/
   String Version = "ver 1.05, 1996-11-23";
/*									*/
/************************************************************************/

/*======================================================================*/
/*	Class global objects and methods				*/
/*======================================================================*/
   protected int n = 4;			/* default: 4 x 4 square	*/

   private Thread solver;

   private int min(int x, int y) {
      return x <= y ? x : y;
   }


/*======================================================================*/
/*	Widget handler							*/
/*======================================================================*/
   private TextField message_box;	/* public inside the class	*/
   private TextField n_box;		/* to specify n (#queens)	*/
   private TextField initial_frustration_box;
   private TextField frustration_factor_box;

   private void init_widgets() {
      setLayout(new FlowLayout());
      add(new Label("Magic square solver using CCM (Chemical Casting Model) -- " +
              Version + " --"));
      add(new Button("Stop"));
      add(new Button("Restart"));

      Panel major_option_panel = new Panel();
      major_option_panel.add(new Label("Major options:  N ="));
      n_box = new TextField("3    ");
      major_option_panel.add(n_box);
      init_speed_choice(major_option_panel);
      init_rule_choice(major_option_panel);
      add(major_option_panel);

      Panel minor_option_panel = new Panel();
      minor_option_panel.add
         (new Label("Minor options:  Initial frustration ="));
      initial_frustration_box = new TextField("1e-15 ");
      minor_option_panel.add(initial_frustration_box);
      minor_option_panel.add(new Label("Frustration factor ="));
      frustration_factor_box = new TextField("2.0   ");
      minor_option_panel.add(frustration_factor_box);
      add(minor_option_panel);

      message_box = new TextField(80);
      add(message_box);
   }

   public boolean action(Event e, Object arg) {
      message_box.setText("");
      if (speed_action(arg) || rule_action(arg)) {
         return true;
      } else if ("Restart".equals(arg)) {
         stop();
         start();
         return true;
      } else if ("Stop".equals(arg)) {
         stop();
         return true;
      } else {
         return false;
      };
   }


/* Choice extension: */

   private Choice new_choice(String[] labels, int default_index,
                             Panel p) {
      Choice c = new Choice();
      for (int i = 0; i < labels.length; i++) {
         c.addItem(labels[i]);
      };
      c.select(default_index);
      p.add(c);
      return c;
   }

   private int find_index(Object arg, String[] labels) {
      for (int i = 0; i < labels.length; i++) {
         if (labels[i].equals(arg)) {
            return i;
         };
      };
      return -1;	/* not found */
   }


/* Speed control: */

   final int[] Sleep_time = {333, 50, 0};	/* in mili seconds	*/
   final int Medium_speed_index = 1;
   final int Fast_speed_index = 2;
   final int Full_speed_index = 3;
   final int Speed_default_index = Medium_speed_index;
   final String[] Speed_choice_labels =
      {"Slow speed (3 rps)", "Medium speed (20 rps)",
       "Fast speed", "Full speed"};

   private int speed_selected_index;
   private Choice speed_choice;

   private void init_speed_choice(Panel p) {
   /* Speed choice is created and initialized.	*/
      speed_choice =
         new_choice(Speed_choice_labels, Speed_default_index, p);
      speed_selected_index = Speed_default_index;
   }

   private boolean speed_action(Object arg) {
   /* Event handler for speed control choice.				*/
   /* Warning: This function is called not only when the event is	*/
   /*	caused by the speed control choice.				*/
      int index = find_index(arg, Speed_choice_labels);
      if (index >= 0) {		/* found	*/
         speed_selected_index = index;
	 display_switch =
            index == Fast_speed_index || index == Full_speed_index
			? false	/* no display while executing	*/
			: true;
         return true;
      } else {			/* not found	*/
         return false;
      };
   }


/* Rule choice: */

   final int Swap_index = 0;
   final int Rotate_index     = 1;
   final int[] Rules = {Swap_index, Rotate_index};
   final int Rule_default_index = Swap_index;
   final String[] Rule_choice_labels = {"Swapping rule", "Rotation rule"};

   private int rule_selected_index;
   private Choice rule_choice;

   private void init_rule_choice(Panel p) {
   /* Rule choice is created and initialized.		*/
      rule_choice =
         new_choice(Rule_choice_labels, Rule_default_index, p);
      rule_selected_index = Rule_default_index;
   }

   private boolean rule_action(Object arg) {
      int index = find_index(arg, Rule_choice_labels);
      if (index >= 0) {		/* found	*/
         rule_selected_index = index;
         return true;
      } else {
         return false;
      };
   }


/*======================================================================*/
/*	Magic square viewer						*/
/*======================================================================*/
   protected boolean display_switch = true;
				/* To display the map or not	*/

   final int Common_offset = 8;

   protected int x_offset = 0;
   protected int y_offset = 170;
   protected int drawn_n;
   protected int queen_x_offset, queen_y_offset;
   int drawing_size, drawing_step, queen_size;
   int font_size;

   private void init_view() {
   }

   private void start_view() {
      drawing_step =
         (min(size().width - x_offset, size().height - y_offset) -
          2 * Common_offset) / n;
      if (drawing_step <= 0) {
         message_box.setText("Applet size too small! ");
         drawing_step = 0;
      };
      drawing_size = drawing_step * n;
      font_size = drawing_step * 3 / 5;
   }

   public void paint(Graphics g) {
      int x0 = x_offset + Common_offset;
      int y0 = y_offset + Common_offset;
      for (int i = 0; i <= n; i++) {
         int grid_coord = i * drawing_step;
         g.drawLine(x0, y0 + grid_coord,
                    x0 + drawing_size - 1, y0 + grid_coord);
         g.drawLine(x0 + grid_coord, y0,
                    x0 + grid_coord, y0 + drawing_size - 1);
      };
      x0 = x0 + drawing_step / 10;
      y0 = y0 + drawing_step / 10;
      Font old_font = g.getFont();
      g.setFont(new Font("TimesRoman", Font.PLAIN, font_size));
      for (int i = 0; i < wm_size; i++) {
         g.drawString
            ("" + value_wm[i],
             x0 + x_coord_wm[i] * drawing_step,
             y0 + y_coord_wm[i] * drawing_step + drawing_step * 2 / 3);
      };
      g.setFont(old_font);
   }


/*======================================================================*/
/*	Solver								*/
/*======================================================================*/
   double initial_frustration = 1.0e-15;
   double frustration_factor = 2.0;

   protected int expected_summation;

   /* Working memory: */
   private int[] value_wm, x_coord_wm, y_coord_wm;
   private double[] frustration_wm;
   private int[][][] summation_wm;
   private int[] n_summations;
   private int wm_size;

   private int n_tests;
   private int n_reactions;
   private int n_failed_tests;

   /* Order degree: */
   private int order(int index, int value_difference) {
      int sum = 0;
      for (int i = 0; i < n_summations[index]; i++) {
         int diff = expected_summation -
                    (summation_wm[index][i][0] + value_difference);
         sum -= diff * diff;
      }
      return sum;
   }

   private double mean_order() {
   /* Returns the mean order degree of the current WM.	*/
      int total_order = 0;
      for (int i = 0; i < wm_size; i++) {
         total_order += order(i, 0);
      };
      return total_order / (double)wm_size;
   }

   private void init_solver() {
   }

   private double get_option(TextField option, String format_error_message,
                             double minimum_value, String value_error_message,
                             double default_value) {
      double value;
      try {
         value = (new Double(option.getText())).doubleValue();
         /* value = Integer.parseInt(option.getText()); */
      } catch (NumberFormatException e) {
         message_box.setText(format_error_message);
         value = default_value;
      };
      option.setText("" + value);
      if (value < minimum_value) {
         message_box.setText(value_error_message);
         value = default_value;
      };
      return value;
   }


/* Random color/index generators */

   private Random selector = new Random();

   private int random(int max) {
      return (selector.nextInt() & 0x7FFFFFFF) % max;
   }

   private void update_summations(int index, int difference) {
      for (int i = 0; i < n_summations[index]; i++) {
         summation_wm[index][i][0] += difference;
      };
   }


/* Rules */

   private void swap_rule() {
   /* A rule to swap two columns of the magic square	*/
      int index1, index2;
      n_tests++;

   /* Select columns to apply the rule:	*/
      index1 = random(wm_size);
      do {
         index2 = random(wm_size);
      } while (index2 == index1);

   /* Compute LODs: */
      int old_order = order(index1, 0) + order(index2, 0);
      int new_order = order(index1, value_wm[index2] - value_wm[index1]) +
                      order(index2, value_wm[index1] - value_wm[index2]);

      if (old_order >= 0) {	/* A local termination condition holds	*/
         n_failed_tests++;
      } else if (((double)old_order - frustration_wm[index1]
                  - frustration_wm[index2]) >
                 new_order) {
					/* not to be reacted	*/
         n_failed_tests++;
         frustration_wm[index1] *= frustration_factor;
         frustration_wm[index2] *= frustration_factor;
      } else {
         n_reactions++;
         n_failed_tests = 0;
         int v1 = value_wm[index1];
         int v2 = value_wm[index2];
         update_summations(index1, v2 - v1);
         update_summations(index2, v1 - v2);
         value_wm[index1] = v2;
         value_wm[index2] = v1;
         if (display_switch) {
            repaint();
            try {solver.sleep(Sleep_time[speed_selected_index]);}
            catch (InterruptedException e) {};
         };
         frustration_wm[index1] = initial_frustration;
         frustration_wm[index2] = initial_frustration;
      };
   }

   private void rotate_rule() {
   /* A rule to rotate three columns of the magic square	*/
      int index1, index2, index3;
      n_tests++;

   /* Select columns to apply the rule:	*/
      index1 = random(wm_size);
      do {
         index2 = random(wm_size);
      } while (index2 == index1);
      do {
         index3 = random(wm_size);
      } while (index3 == index1 || index3 == index2);

   /* Compute LODs: */
      int old_order =
             order(index1, 0) + order(index2, 0) + order(index3, 0);
      int new_order = order(index1, value_wm[index2] - value_wm[index1]) +
                      order(index2, value_wm[index3] - value_wm[index2]) +
                      order(index3, value_wm[index1] - value_wm[index3]);

      if (old_order >= 0) {	/* A local termination condition holds	*/
         n_failed_tests++;
      } else if (((double)old_order - frustration_wm[index1]
                  - frustration_wm[index2] - frustration_wm[index3]) >
                 new_order) {
					/* not to be reacted	*/
         n_failed_tests++;
         frustration_wm[index1] *= frustration_factor;
         frustration_wm[index2] *= frustration_factor;
         frustration_wm[index3] *= frustration_factor;
      } else {
         n_reactions++;
         n_failed_tests = 0;
         int v1 = value_wm[index1];
         int v2 = value_wm[index2];
         int v3 = value_wm[index3];
         update_summations(index1, v2 - v1);
         update_summations(index2, v3 - v2);
         update_summations(index3, v1 - v3);
         value_wm[index1] = v2;
         value_wm[index2] = v3;
         value_wm[index3] = v1;
         if (display_switch) {
            repaint();
            try {solver.sleep(Sleep_time[speed_selected_index]);}
            catch (InterruptedException e) {};
         };
         frustration_wm[index1] = initial_frustration;
         frustration_wm[index2] = initial_frustration;
         frustration_wm[index3] = initial_frustration;
      };
   }


/* Solver main part: */

   public void run() {
      long initial_time;
      int max_tests = 1000;
      int max_tests_20 = 20 * max_tests;

      n = (int)get_option(n_box, "Format error -- n ",
                          3, "The value of N must be 3 or larger! ", 3);
      initial_frustration =
         get_option(initial_frustration_box,
                    "Format error -- initial_frustration ",
                    0, "The value of initial frustration must be positive! ",
                    1e-15);
      frustration_factor =
         get_option(frustration_factor_box,
                    "Format error -- frustration_factor ",
                    0, "The value of initial frustration must be positive! ",
                    2.0);
      init_wm(n);

      start_view();
      repaint();
      try {solver.sleep(50);}
      catch (InterruptedException e) {};

      message_box.setText("Running...");
      initial_time = System.currentTimeMillis();
      n_tests = 0;
      n_reactions = 0;
      n_failed_tests = 0;
      while (true) {
         switch (rule_selected_index) {
         case Swap_index:
            swap_rule();
            break;
         case Rotate_index:
            rotate_rule();
            break;
         };

         if (n_failed_tests >= max_tests) {	/* termination condition */
            if (n_tests < max_tests_20) {
               break;
            };
            max_tests_20 = 2 * max_tests_20;
            max_tests = max_tests_20 / 20;
         };
         if (speed_selected_index != Full_speed_index &&
	     n_tests % 10000 == 0) {
            message_box.setText
               ("Running... #tests = " + n_tests +
                "  #reactions = " + n_reactions + "  MOD = " + mean_order() +
                "  Time = " +
                (System.currentTimeMillis() - initial_time) / 1000.0);
            repaint();
            try {solver.sleep(50);}
            catch (InterruptedException e) {};
         };
      };
      double order = mean_order();
      message_box.setText
         ("Stoppped.  #tests = " + n_tests +
          "  #reactions = " + n_reactions +
          "  MOD = " + order + (order < 0 ? "  *** Failed! ***" : "") +
          "  Time = " + (System.currentTimeMillis() - initial_time) / 1000.0);
      repaint();
   };


/*======================================================================*/
/*	Working memory (Initial queen layout) generation		*/
/*======================================================================*/
   /* protected int summations[]; */

   private void add2summation(int[] summation, int index) {
      summation[0] += value_wm[index];
      summation_wm[index][n_summations[index]++] = summation;
   }

   private void init_wm(int n) {
      wm_size = n * n;
      value_wm = new int[wm_size];
      x_coord_wm = new int[wm_size];
      y_coord_wm = new int[wm_size];
      frustration_wm = new double[wm_size];
      summation_wm = new int[wm_size][][];
      n_summations = new int[wm_size];

      expected_summation = (n * (n * n + 1)) / 2;

      for (int i = 0; i < wm_size; i++) {
         x_coord_wm[i] = i % n;
         y_coord_wm[i] = i / n;
         value_wm[i] = i + 1;
         frustration_wm[i] = initial_frustration;
      };
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            n_summations[n * i + j]++;
            n_summations[n * j + i]++;
         };
         n_summations[n * i + i]++;
         n_summations[n * i + n - i - 1]++;
      };
      for (int i = 0; i < wm_size; i++) {
         summation_wm[i] = new int[n_summations[i]][];
         n_summations[i] = 0;
      };
      int[] up_diagonal_summation = new int[1];
      int[] down_diagonal_summation = new int[1];
      for (int i = 0; i < n; i++) {
         int[] row_summation = new int[1];
         int[] column_summation = new int[1];
         for (int j = 0; j < n; j++) {
            add2summation(row_summation, n * i + j);
            add2summation(column_summation, n * j + i);
         };
         add2summation(up_diagonal_summation, n * i + i);
         add2summation(down_diagonal_summation, n * i + n - i - 1);
      };
   }


/*======================================================================*/
/*	Dispatchers							*/
/*======================================================================*/
   public void init() {
      init_widgets();
      init_solver();
      init_view();
   }

   public void start() {
      solver = new Thread(this);
      solver.start();
   }

   public void stop() {
      solver.stop();
   }

}