/* Counting the Paths on a Grid 
 *
 * このプログラムは海野秀之 (unno.hideyuki@nifty.com) が書きました。
 * 使用条件：無保証でよければ、ご自由に。
 *
 * 2008-05-13: とりあえず書いてみたけど間違っているような気がする。
 * 2008-05-25 (1): バックトラック実装してみた。
 * 2008-05-20: count_paths.c に改名しつつ、過去のバリエーションを統合。
 */


#include <stdlib.h>
#include <stdio.h>

void init_genrand(unsigned long s);
unsigned long genrand_int31(void);


static double sum_length = 0;
static double sum_paths = 0;
static double sum_hitc = 0;
static long   sum_num = 0;
static long   sum_faild = 0;

static int loop_size = 1;
static int opt_enb_backtrack = 0;     /* バックトラックする or あきらめる */
static int opt_rand_use_residual = 0; /* ある値以下の乱数を生成する際に、
                                       *  0: 望みの範囲の値が出るまでリトライ
                                       *  1: (max + 1) で割った余りを用いる
				       */
static int opt_count_faild_path = 0;     /* 袋小路に陥ったパスも失敗数として
					  * 母数に含める */
static int opt_use_mersenne_twister = 0; /* メルセンヌ・ツイスタを使う */
static int opt_print_generated_path = 0; /* 生成されたパスを print する */

typedef struct {
  char grids[11][11];
  int length;
  int ncands[200];
  int hitc;
} WORK;

void initrand()
{
  if (opt_use_mersenne_twister) { init_genrand(0); }
  else                          { srand(0); }
}

inline static int getr()
{
  if (opt_use_mersenne_twister) { return genrand_int31(); }
  else                          { return rand(); }
}

int getrand(int max) /* 0 < max <= 3 */
{
  int r;

  if (max > 0){
    if (opt_rand_use_residual){
      r = getr() % (max + 1);
    } else {
      do { r = getr() & 3; } while (r > max);
    }
  } else {
    r = 0;
  }

  return r;
}

void init_work(WORK *pw)
{
  int x, y;
  for (y = 0; y <= 10; y++){
    for (x = 0; x <= 10; x++){
      pw->grids[x][y] = 0;
    }
  }

  pw->length = 0;

  for (x = 0; x < 200; x++)
    pw->ncands[x] = 0;

  pw->hitc = 0;
}

void calc_candidates(int x, int y, WORK *pw,
		     int *right, int *up, int *left, int *down)
{
  *right = 1;
  *up    = 1;
  *left  = 1;
  *down  = 1;

  if (x == 0 || y == 0){
    *left  = 0;
    *down  = 0;
  } 

  if (x == 10){
    *down  = 0;
    *right = 0;
  }

  if (y == 10){
    *up    = 0;
    *left  = 0;
  }

  if (*up    && pw->grids[x][y+1]){ *up    = 0; }
  if (*down  && pw->grids[x][y-1]){ *down  = 0; }
  if (*right && pw->grids[x+1][y]){ *right = 0; }
  if (*left  && pw->grids[x-1][y]){ *left  = 0; }
}

int rand_direction(int right, int up, int left, int down)
{
  int r, m, d;

  m = right + up + left + down;
  r = getrand(m-1);

  if      ((r -= right) < 0) d = 0;
  else if ((r -= up)    < 0) d = 1;
  else if ((r -= left)  < 0) d = 2;
  else                       d = 3;
  
  return d;
}

void next_pos(int d, int x, int y, int *next_x, int *next_y)
{
  switch (d){
  case 0: 
    *next_x = x + 1;
    *next_y = y;
    break;
  case 1: 
    *next_x = x;
    *next_y = y + 1;
    break;
  case 2: 
    *next_x = x - 1;
    *next_y = y;
    break;
  default:
    *next_x = x;
    *next_y = y - 1;
  }
}

void delete_cand(int d, int *right, int *up, int *left, int *down)
{
  switch(d){
  case 0:  *right = 0; break;
  case 1:  *up    = 0; break;
  case 2:  *left  = 0; break;
  default: *down  = 0;
  }
}

int lp_next_pos(int x, int y, WORK *pw)
{
  int right, up, left, down;
  int next_x, next_y;
  int d;

  if (x == 10 && y == 10){
    if (opt_print_generated_path){
      printf("(10, 10)");
    }
    return 1;
  }

  pw->grids[x][y] = 1;

  calc_candidates(x, y, pw, &right, &up, &left, &down);

  pw->ncands[pw->length] = right + up + left + down;
  pw->length++;

  while (right + up + left + down > 0){
    d = rand_direction(right, up, left, down);
    next_pos(d, x, y, &next_x, &next_y);

    if (lp_next_pos(next_x, next_y, pw)){
      if (x == 5 && y == 5){
	pw->hitc = 1;
      }

      if (opt_print_generated_path){
	printf(" <- (%d, %d), %d", x, y, right + up + left + down);
      }
      return 1;
    } else if (!opt_enb_backtrack){
      break;
    }

    delete_cand(d, &right, &up, &left, &down);
    pw->ncands[pw->length - 1] = right + up + left + down;
  }

  if (opt_print_generated_path && !opt_enb_backtrack){
    printf(" <- (%d, %d), %d", x, y, right + up + left + down);
  }
  pw->grids[x][y] = 0;
  pw->length--;
  return 0;
}

int generate_a_path()
{
  int i, ret;
  double npaths;

  WORK work;
  init_work(&work);
  ret = lp_next_pos(0, 0, &work);

  if (ret){
    npaths = 1;
    for(i = 0; i < work.length; i++){
      npaths *= work.ncands[i];
    }

    if (opt_print_generated_path){
      printf(": l = %d, n = %e\n", work.length, npaths);
    }
    sum_num++;
    sum_length += work.length * npaths;
    sum_paths += npaths;
    if (work.hitc){
      sum_hitc += npaths;
    }
  } else {
    sum_faild++;
    if (opt_print_generated_path){
      puts(": faild.");
    }
  }

  return ret;
}

/* 自前で引数解析。ださくてごめん。 */
void
parse_opts(char* str)
{
  char* c;
  for (c = str; *c; c++){
    switch (*c){
    case 'b': opt_enb_backtrack        = 1; break;
    case 'r': opt_rand_use_residual    = 1; break;
    case 'f': opt_count_faild_path     = 1; break;
    case 'm': opt_use_mersenne_twister = 1; break;
    case 'p': opt_print_generated_path = 1; break;
    default:
      fprintf(stderr, "Unknown opt: %c\n", (int) *c);
      exit(1);
    }
  }
}

void
parse_num(char* str)
{
  loop_size = atol(str);
  if (loop_size < 0){ loop_size = 1; }
}

void
parse_args(int argc, char** argv)
{
  switch (argc){
  case 1: break;
  case 2: parse_num(argv[1]); break;
  case 3: parse_opts(argv[1]); parse_num(argv[2]); break;
  default:
    fputs("Too many args!", stderr);
    exit(1);
  }
}

void
print_result()
{
  puts("---- Result ----");
  printf("# of paths = %e, l = %.3f, hitc = %.3f\n", 
	 (double) sum_paths / 
	 (sum_num + (opt_count_faild_path ?  sum_faild : 0)),
	 (double) sum_length / sum_paths,
	 (double) sum_hitc * 100 / sum_paths
	 );
}

int
main(int argc, char** argv)
{
  int i;
  
  parse_args(argc, argv);

  initrand();

  i = 0;
  while (i < loop_size){
    i += generate_a_path();
  }

  print_result();

  return 0;
}