#06

// area.c -- calcurate area of 2-D object
#include <stdio.h>
#define DELTA 0.001

int inside_circle(double x, double y) {
  return x*x+y*y <= 4.0;
}
double area(double x1, double x2, double y1, double y2,
            int (*f)(double,double)) {
 int b1 = (*f)(x1,y1), b2 = (*f)(x1,y2);
 int b3 = (*f)(x2,y1), b4 = (*f)(x2,y2), bn = b1+b2+b3+b4;
 if(x2-x1 < DELTA || bn == 0 || bn == 4) {
   return bn*0.25*(x2-x1)*(y2-y1);
 } else {
   double x3 = 0.5*(x1+x2), y3 = 0.5*(y1+y2);
   return area(x1, x3, y1, y3, f) + area(x1, x3, y3, y2, f) +
          area(x3, x2, y1, y3, f) + area(x3, x2, y3, y2, f);
  }
}
int main(void) {
  printf("%8.6f\n", area(0, 2, 0, 2, inside_circle));
  return 0;
}

int gcd(int x, int y) {
  if(x == y) {
    return x;
  } else if(x > y) {
    return gcd(x-y, y);
  } else {
    return gcd(x, y-x);
  }
}

int gcd2(int x, int y) {
  while(true) {
    if(x == y) {
      return x;
    } else if(x > y) {
      x = x - y;
    } else {
      y = y - x;
    }
  }
}

bool iseven(int n) {
  if(n == 0) {
    return true;
  } else if(n == 1) {
    return false;
  } else {
    return iseven(n - 2);
  }
}

int sum(int a, int b) {
  if(a == 0) {
    return b;
  } else {
    return sum(a-1, b+1);
  }
}

void strtriangle(char *s) {
  printf("%s\n", s);
  if(*s == '\0') {
    // do nothing
  } else {
    strtriangle(s+1); 
  }
}

int fact(int n) {
  if(n < 1) {
    return 1;
  } else {
    return n * fact(n-1);
  }
}

int fact1(int n, int r) {
  if(n < 1) {
    return r;
  } else {
    return fact1(n-1, r*n);
  }
}
int fact(int n) { return fact1(n, 1); }

int mul(int a, int b) {
  if(a == 0) {
    return 0;
  } else {
    return a + mul(a, b-1);
  }
}

int powx(double x, int n) {
  if(n < 1) {
    return 1.0;
  } else {
    return x * powx(x, n-1);
  }
}

double powx(double x, int n) {
  if(n < 1) {
    return 1.0;
  } else if(n % 2 == 1) {
    return x * powx(x, n-1);
  } else {
    double y = powx(x, n / 2); return y*y;
  }

int calc(double x, int n) {
  if(n < 0) {
    return 0.0;
  } else {
    return 1/(x+i) + calc(x, n-1);
  }
}

void hanoi(int k, int x, int y, int z) { // (1)
  if(k == 1) {
    printf("move disc %d from %c to %c.\n", k, x, y);
  } else {
    hanoi(k-1, x, z, y); // (2)
    printf("move disc %d from %c to %c.\n", k, x, y); 
    hanoi(k-1, z, y, x); 
  }
}

// istack.h --- int type stack interface
#include <stdbool.h>
struct istack;
typedef struct istack *istackp;
istackp istack_new(int size); // allocate new stack
bool istack_isempty(istackp p); // test if the stack is empty
void istack_push(istackp p, int v); // push a value
int istack_pop(istackp p);      // pop a value and return it
int istack_top(istackp p);      // peek the topmost value

// istack.c --- int type stack impl. with array
#include <stdlib.h>
#include "istack.h"
struct istack { int ptr; int *arr; };
istackp istack_new(int size) {
  istackp p = (istackp)malloc(sizeof(struct istack));
  p->ptr = 0; p->arr = (int*)malloc(size * sizeof(int));
  return p;
}
bool istack_isempty(istackp p) { return p->ptr <= 0; }
void istack_push(istackp p, int v) { p->arr[p->ptr++] = v; }
int istack_pop(istackp p) { return p->arr[--(p->ptr)]; }
int istack_top(istackp p) { return p->arr[p->ptr - 1]; }

// hanoistack.c --- hanoi with stack
#include <stdio.h>
#include <stdlib.h>
#include "istack.h"

void p5(istackp s, int a, int b, int c, int d, int e) {
  istack_push(s,e); istack_push(s,d);
  istack_push(s,c); istack_push(s,b); istack_push(s,a);
}  
void hanoiloop(int k, int x, int y, int z) {
  istackp s = istack_new(100); p5(s, 1, k, x, y, z);
  while(!istack_isempty(s)) {
    int cont = istack_pop(s); k = istack_pop(s);
    x = istack_pop(s); y = istack_pop(s); z = istack_pop(s);
//  printf("%d %d %c %c %c\n", cont, k, x, y, z);
    if(cont == 1) {
      if(k == 1) {
        printf("move disk %d from %c to %c.\n", k, x, y);
      } else {
        p5(s, 2, k, x, y, z); p5(s, 1, k-1, x, z, y);
      }
    } else { // cont == 2
      printf("move disk %d from %c to %c.\n", k, x, y);
      p5(s, 1, k-1, z, y, x);
    }
  }
}
int main(int argc, char *argv[]) {
  hanoiloop(atoi(argv[1]), 'A', 'B', 'C'); return 0;
}

int combr(int n, int r) { // (1)
  if(r == 0 || r == n) {
    return 1;
  } else {
    return combr(n-1, r) + combr(n-1, r-1); // (2)
  }
}

// combstack.c --- combination with stack
#include <stdio.h>
#include <stdlib.h>
#include "istack.h"

void p3(istackp s, int a, int b, int c) {
  istack_push(s,c); istack_push(s,b); istack_push(s,a);
}  
int combloop(int n, int r) {
  int x, ret;
  istackp v = istack_new(100);
  istackp s = istack_new(100); p3(s, 1, n, r);
  while(!istack_isempty(s)) {
    int cont = istack_pop(s);
    n = istack_pop(s); r = istack_pop(s);
//  printf("%d %d %d\n", cont, n, r);
    if(cont == 1) {
      if(r == n || r == 0) {
        istack_push(v, 1);
      } else {
        p3(s, 2, 0, 0); p3(s, 1, n-1, r-1); p3(s, 1, n-1, r);
      }
    } else { // cont == 2
      istack_push(v, istack_pop(v)+istack_pop(v));
    }
  }
  return istack_pop(v);
}
int main(int argc, char *argv[]) {
  printf("%d\n", combloop(atoi(argv[1]), atoi(argv[2]))); return 0;
}

// decr12.c --- usage: ./a.out INTEGER
#include <stdio.h>
#include <stdlib.h>

void decr12(int n, int k, int *a) {
  if(n < 1) {
    // do nothing
  } else if(n == 1) {
    a[k] = 1;
    int i;
    for(i = 0; i <= k; ++i) { printf(" %d", a[i]); }
    printf("\n");
  } else {
    a[k] = n; decr12(n-1, k+1, a); decr12(n-2, k+1, a);
  }
}
int main(int argc, char *argv[]) {
  int buf[100]; decr12(atoi(argv[1]), 0, buf); return 0;
}

// allstr.c --- usage: ./a.out STRING LENGTH
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void allstr(int n, char *s, int len, int k, char *a) {
  if(len == 0) {
    a[k] = '\0'; printf("%s\n", a);
  } else {
    int i;
    for(i = 0; i < n; ++i) {
      a[k] = s[i]; allstr(n, s, len-1, k+1, a);
    }
  }
}
int main(int argc, char *argv[]) {
  char str[100];
  allstr(strlen(argv[1]), argv[1], atoi(argv[2]), 0, str);
  return 0;
}

// perm.c --- usage: ./a.out STRING
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void cswap(char *a, int i, int j) {
  char c = a[i]; a[i] = a[j]; a[j] = c;
}
void perm(int len, int k, char *a) {
  if(k == len) {
    printf("%s\n", a);
  } else {
    int i;
    for(i = k; i < len; ++i) {
      cswap(a, k, i); perm(len, k+1, a); cswap(a, k, i);
    }
  }
}
int main(int argc, char *argv[]) {
  char str[100];
  strcpy(str, argv[1]); perm(strlen(str), 0, str); return 0;
}