// bubble sort  28 June 97

global bub[100];  // 100 integers

initbub(n) {
  while (n>0) {
    bub[n] = 100-n;
    n = n -1 ;
  }
}

bubble(n) {
  i = n;
  j = 0;
  while( i > 0 ) {
    while( j < n ) {
     if( bub[j] > bub[j+1] ) {
       t = bub[j];
       bub[j] = bub[j+1];
       bub[j+1] = t;
     }
     j = j+1;
    }
    i = i-1;
  }
}

showbub(n) {
  i=0;
  while(i<n) {
    print(bub[i]," ");
    i = i+1;
  }
}

// tower of hanoi   29 June 97

global num[4];

mov(n, from, to) {
  if ( n == 1 ) {
    num[from] = num[from] - 1 ;
    num[to] = num[to] + 1;
    print(from," -> ", to, "\n");
  } else {
    other = 6 - from - to;
    mov(n-1, from, other);
    mov(1, from, to);
    mov(n-1, other, to);
  }
}

// matrix multiplication   27 June 97
// matrix size 10 x 10 : A = B * C
global DIM, a[100], b[100], c[100];

initmat() {
  i = 0;
  k = DIM * DIM;
  while ( i<k ) {
    a[i] = 2;
    b[i] = 3;
    i = i+1;
  }
}

matmul() {
  i = 0;
  while( i<DIM ) {
    j = 0;
    while( j<DIM ) {
      m = i*DIM + j;
      c[m] = 0;
      k = 0;
      while( k<DIM ) {
	c[m] = c[m] + (a[i*DIM + k] * b[k*DIM + j]);
	k = k+1;
      }
      j = j+1;
    }
    i = i+1;
  }
}

showmat() {
  i = 0;
  while( i<DIM ) {
    j = 0;
    while( j<DIM ) {
      print( c[i*DIM + j], " ");
      j = j+1;
    }
    print("\n");
    i = i+1;
  }
}

// permutation  27 June 97

global val[4], id, LEN;

writeperm() {
  i = 0;
  while( i<LEN ) {
    print(val[i]," ");
    i = i+1;
  }
  print("\n");
}

visit(k) {
  id = id + 1;
  val[k] = id;
  if( id == (LEN-1) ) writeperm();
  t = 0;
  while ( t<LEN ) {
    if( val[t] == 0 ) visit(t);
    t = t+1;
  }
  id = id-1;
  val[k]= 0;
}

// quick sort  27 June 97

// sort 100 integers
global ss[100];

initss() {
 i = 0;
 while( i<100 ) {
   ss[i] = 100 - i;
   i = i + 1;
 }
}

showss(n) {
  i = 0;
  while( i<n ) {
    print( ss[i]," " );
    i = i + 1;
  }
  print("\n");
}

qsort(l,r) {
  if( r>l ) {
    v = ss[r];
    i = l-1;
    j = r;
    s1 = 1;
    while( s1 ) {
      s2 = 1;
      while( s2 ) {
	i = i + 1;
	if( ss[i] >= v ) s2 = 0;
      }
      s2 = 1;
      while( s2 ) {
	j = j -1;
	if( ss[j] <= v ) s2 = 0;
      }
      t = ss[i];
      ss[i] = ss[j];
      ss[j] = t;
      if( j <= i ) s1 = 0;
    }
    ss[j] = ss[i];
    ss[i] = ss[r];
    ss[r] = t;
    qsort(l,i-1);
    qsort(i+1,r);
  }
}

// 8-queens  27 June 97

global Q, Z, D;
global col[8], d45[15], d135[15], queen[8], soln;

printboard() {
  i = 0;
  while( i<Q ) {
    print(queen[i], " ");
    i = i + 1;
  }
  soln = soln + 1;
  print("\n");
}

find(level) {
  if( level == Q ) {
    printboard();
  } else {
    i = 0;
    while( i<Q ) {
      if( (col[i] >= level) && (d45[level+i] >= level) &&
	  (d135[level+Q-1-i] >= level ) ) {
	queen[level] = i;
	col[i] = level;
	d45[level+i] = level;
	d135[level+Q-1-i] = level;
	find(level+1);
	col[i] = Z;
	d45[level+i] = Z;
	d135[level+Q-1-i] = Z;
      }
      i = i + 1;
    }
  }
}

// prime number Sieve of Erasthones  27 June 97

global p[10000], NUM;

sieve() {
  i = 0;
  while( i<NUM ) {
    if( p[i] ) {
      prime = i + i + 3;
      k = i + prime;
      while( k<NUM ) {
	p[k] = 0;
	k = k + prime;
      }
    }
    i = i + 1;
  }
}

showprime() {
  cnt = 0;
  last = 0;
  i = 0;
  while( i<NUM ) {
    if( p[i] ) {
      last = i;
      cnt = cnt + 1;
    }
    i = i+ 1;
  }
  print( "prime found ", cnt, " last ",last);
}

main() {

  initbub(100); // bubble sort
  bubble(100);
  showbub(10);

  num[0] = 0; // hanoi, move 5 disks from pole 1 to pole 3
  num[1] = 5; 
  num[2] = 0;
  num[3] = 0;
  mov(5,1,3);

  DIM = 10;   // matrix mul 10x10
  initmat();
  matmul();
  showmat();

  LEN = 4;    //  permute a sequence of 4 numbers
  i = 0;
  while( i<LEN ) {
    val[i] = 0;
    i = i+1;
  }
  id = 0-1;
  visit(0);

  initss();	// quick sort 100 integers
  qsort(0,100);
  showss(10);

  Q  = 8; Z = Q + 1; D = Q + Q - 1;  // solve 8-queen
  soln = 0;
  i = 0;
  while( i<Q ) {
    col[i] = Z;
    i = i + 1;
  }
  i = 0;
  while( i < D ) {
    d45[i] = Z;
    d135[i] = Z;
    i = i + 1;
  }
  find(0);
  print("no of soln ", soln);

  NUM = 10000;	// find all primes less than 100000
  i = 0;
  while( i<NUM ) {
    p[i] = 1;
    i = i + 1;
  }
  sieve();
  showprime();
}

