/* the hanoi tower
   
   play hanoi(<number of disk between 1 and 9>) */


int win_hanoi = -1;			/* hanoi window */
int ndisk_hanoi;			/* total number of disk */
int tower_size_hanoi[3];		/* number of disk per tower */
int width_disk_hanoi[3][10];		/* disks'width per tower */


/* rub out the specified disk */

void remove_disk_hanoi(int tower, int altitude)
{
  int n;

  /* upper line */
  
  goto_line((ndisk_hanoi - altitude) * 2 + 2);
  goto_beginning_of_line();
  goto_char(current_position() + tower * (2 * ndisk_hanoi + 3) + 1);
  
  for (n = ndisk_hanoi; n; n -= 1) {
    replace_char(' ');
    goto_next_char();
  }
  if (altitude > ndisk_hanoi) replace_char(' ');
  goto_next_char();
  for (n = ndisk_hanoi; n; n -= 1) {
    replace_char(' ');
    goto_next_char();
  }
  
  /* lower line */
  
  goto_next_line();
  goto_beginning_of_line();
  goto_char(current_position() + tower * (2 * ndisk_hanoi + 3) + 1);
  
  for (n = ndisk_hanoi; n; n -= 1) {
    replace_char(' ');
    goto_next_char();
  }
  if (altitude > ndisk_hanoi) replace_char(' ');
  goto_next_char();
  for (n = ndisk_hanoi; n; n -= 1) {
    replace_char(' ');
    goto_next_char();
  }
}

/* draw the specified disk */

void draw_disk_hanoi(int tower, int altitude, int width)
{
  int n;

  /* upper line */
  
  goto_line((ndisk_hanoi - altitude) * 2 + 2);
  goto_beginning_of_line();
  goto_char(current_position() + tower * (2 * ndisk_hanoi + 3) +
	    ndisk_hanoi - width + 2);
  
  for (n = width - 1; n; n -= 1) {
    replace_char('_');
    goto_next_char();
  }
  if (altitude > ndisk_hanoi) replace_char('_');
  goto_next_char();
  for (n = width - 1; n; n -= 1) {
    replace_char('_');
    goto_next_char();
  }
  
  /* lower line */
  
  goto_next_line();
  goto_beginning_of_line();
  goto_char(current_position() + tower * (2 * ndisk_hanoi + 3) +
	    ndisk_hanoi - width + 1);
  
  replace_char('(');
  goto_next_char();
  for (n = width - 1; n; n -= 1) {
    replace_char('_');
    goto_next_char();
  }
  if (altitude > ndisk_hanoi) replace_char('_');
  goto_next_char();
  for (n = width - 1; n; n -= 1) {
    replace_char('_');
    goto_next_char();
  }
  replace_char(')');
}

/* initial drawing of the hanoi towers */

void draw_hanoi()
{
  int n;

  /* reuse or create the hanoi window */
  
  if (((win_hanoi == -1) || (select_window(win_hanoi) == -1)) &&
      ((win_hanoi = new_window()) == -1))
    error("To many open window");

  select_window(win_hanoi);
  kill_current_buffer();
  raise_window();
  
  /* draw all towers empty */
  
  for (n = 6 * ndisk_hanoi + 9; n; n -= 1) insert_char(' ');
  insert_char('\n');
  for (n = 6 * ndisk_hanoi + 9; n; n -= 1) insert_char(' ');
  insert_char('\n');
  
  for (n = ndisk_hanoi * 2 + 1; n; n -= 1) {
    int tower;
    
    for (tower = 0; tower != 3; tower += 1) {
      int nsp;
      
      for (nsp = ndisk_hanoi + 1; nsp; nsp -= 1) insert_char(' ');
      insert_char('|');
      for (nsp = ndisk_hanoi + 1; nsp; nsp -= 1) insert_char(' ');
    }
    insert_char('\n');
  }
  
  for (n = ndisk_hanoi * 6 + 9; n ; n -= 1) insert_char('=');
  insert_char('\n');

  /* add disks to the first tower */
  
  for (n = 1; n <= ndisk_hanoi; n += 1)
    draw_disk_hanoi(0, n, ndisk_hanoi - n + 1);

  /* to see the beautiful result */
  
  goto_char(0);
  redisplay();
  sleep(2);
}

/* initialize data */

void init_hanoi(int n)
{
  if (((ndisk_hanoi = n) < 0) || (n > 9))
    error("number of disk may be between 1 and 9");

  tower_size_hanoi[0] = n;
  tower_size_hanoi[1] = tower_size_hanoi[2] = 0;
  
  while (n) {
    width_disk_hanoi[0][n] = ndisk_hanoi - n + 1;
    width_disk_hanoi[1][n] = width_disk_hanoi[2][n] = 0;
    n -= 1;
  }
}

/* move a disk from src to dest */

void move_hanoi(int src, int dest)
{
  int src_size = tower_size_hanoi[src]--;
  int dest_size = ++(tower_size_hanoi[dest]);
  int width =
    width_disk_hanoi[dest][dest_size] = width_disk_hanoi[src][src_size];
  int speed = (ndisk_hanoi < 6) ? 1 : ndisk_hanoi/2;
  int alt;

  /* move up disk on src tower */
  
  alt = src_size;
  do {
    remove_disk_hanoi(src, alt);
    if ((alt += speed) > ndisk_hanoi) alt = ndisk_hanoi + 1;
    draw_disk_hanoi(src, alt, width);
    goto_char(0);
    redisplay();
  } while (alt <= ndisk_hanoi);
  
  /* move disk from src to dest */
  
  remove_disk_hanoi(src, alt);
  goto_char(0);
  redisplay();
  draw_disk_hanoi(dest, alt, width);
  goto_char(0);
  redisplay();
  
  /* move down disk on dest tower */
  
  do {
    remove_disk_hanoi(dest, alt);
    if ((alt -= speed) < dest_size) alt = dest_size;
    draw_disk_hanoi(dest, alt, width);
    goto_char(0);
    redisplay();
  } while (alt != dest_size);
}

/* the engine */

void internal_hanoi(int src, int inter, int dest, int ndisk)
{
  if (ndisk > 1)
    internal_hanoi(src, dest, inter, ndisk - 1);

  move_hanoi(src, dest);

  if (ndisk > 1)
    internal_hanoi(inter, src, dest, ndisk - 1);
}

/* the top level function */

void hanoi(int n)
{
  init_hanoi(n);
  draw_hanoi();
  internal_hanoi(0, 1, 2, n);
}