/*  fracwalk.c :  ANSI C program to print a string of numbers
                  that do a 1/f "fractal" walk.

			  Taken from Martin Gardner's article
			  "White, Brown, and Fractal Music", 
			  algorithm attributed to Richard Voss.

    2/2/98, Ben Sussman.  N is a very imporant #define;
                          In the future, put it in argv[] and malloc.

    please e-mail to:  sussman@red-bean.com

*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>  /* used for a seed to pseudo-random generator */


/*

  User assigns "N" on the command line:

   N    = number of dice used;
   2^N  = number of numbers produced;
   5N+1 = size of output range;
*/

int N;


/* Global array pointers for simplicity */

int *dice;     /* to hold die-roll results */
char *array1;  /* to hold old binary digits */
char *array2;  /* to hold new binary digits */
char *diff;    /* to hold difference between array1 and array2 */


/* return sum of dice rolls */

int dice_sum()
{
  int count, sum=0;
  for (count = 0; count < N; count++) {
    sum += dice[count];
  }
  return sum;
}


/* roll a specific die */

void dice_roll(int die)
{
  if (die >= N) {
    printf("error: dice array out of bounds");
    exit(1);
  }
  dice[die] = (rand() % 6) + 1;  /* random number from 1 to 6 */
}


/* initialize arrays, random numbers, and return initial sum */

int choose_seed()
{
  int count;
  unsigned int myseed;

  if ((dice = (int *) malloc((sizeof(int))*N)) == NULL) {
    printf("Error: can't malloc enough memory.\n");
    exit(1);
  }

  if ((array1 = (char *) malloc((sizeof(char))*N)) == NULL) {
    printf("Error: can't malloc enough memory.\n");
    exit(1);
  }

  if ((array2 = (char *) malloc((sizeof(char))*N)) == NULL) {
    printf("Error: can't malloc enough memory.\n");
    exit(1);
  }

  if ((diff = (char *) malloc((sizeof(char))*N)) == NULL) {
    printf("Error: can't malloc enough memory.\n");
    exit(1);
  }

  for (count = 0; count < N; count++) {
    dice_roll(count);
    array1[count] = 0;
    array2[count] = 0;
    diff[count] = 0;
  }

  myseed = (unsigned int) (time(NULL));
  srand(myseed);

  return dice_sum();
}


/* Useful function from C programming 101 */

void swap_arrays(char **a, char **b)
{
  char *temp;
  temp = *a;
  *a = *b;
  *b = temp;
}


/* Place "changes" between array1[] and array2[] into diff[] */

void compare_arrays(char *a, char *b)
{
  int count;
  for (count = 0; count < N; count++) {
    if (a[count] != b[count])
      diff[count] = 1;
    else
      diff[count] = 0;
  }
}


/* Given an integer, convert to binary and fill in char array 
   with '1' and '0'.  The binary number in the array is backwards,
   but that's irrelevant here.  (We're only interested in changes
   between binary numbers)
*/


void int2bin(int i, char *binary)
{
  int div, mod, count = 0;
  long l;
  l = (long) i;
  while (l > 0) {
    div = (int) floor(l/2);        /* divide 2 into our total, round down */
    mod = ((int) l) % 2;           /* calculate the remainder */
    binary[count] = mod ? '1':'0';
    l = (long) div;
    count++;
  }
  binary[count]='\0';
}



/* Our main computational horse, does a fractal walk
     by outputting a string of numbers  */


void do_fracwalk()
{
  int count, count2;
  int maxx = pow(2, N) - 1;
  char *old, *new;          /* point to array1[] or array2[] */
  
  old = array1;
  new = array2;

  /* Each loop generates one new number */

  for (count = 0; count < maxx; count++) {

    /* convert count to binary, place in new array */

    int2bin(count, new);

    compare_arrays(old, new);  /* fill in diff[] */
    
    /* and roll a die only if binary digit has changed: */

    for (count2 = 0; count2 < N; count2++) {
      if (diff[count2])
	dice_roll(count2);
    }
    
    /* output the newest dice sum */

    printf("%d ",dice_sum());

    /* and swap the arrays, so new becomes old */

    swap_arrays(&old, &new);
  }
  
  /* Give a final newline when finished */

  printf("\n");

}


int main(int argc, char *argv[])
{
  if (argc !=2) {
    printf("fracwalk: generate a random 1/f fractal sequence of numbers\n\n");
    printf("Usage: fracwalk <N>, where 2^N is the length of the sequence\n\n");
    exit(1);
  }
  
  N = atoi(argv[1]);

  /* create arrays and generate initial value */

  printf("%d ", choose_seed(N));

  /* do the walk */

  do_fracwalk();
  exit(0);
}