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

int PickRand (int min, int max) {
	int range;
	int rval;
	int val;
	range = max - min;
	rval = rand() % (range + 1);
	val = rval + min;
	return val;
}

int ChooseProb( int chances, int total) {
	int rval;
	rval = rand() % total;
	if (rval < chances) {
		return 1;
	}
	else {
		return 0;
	}
	return 0;
}

int APossCard (int possNum, int numDigit){
     int toStrip = 1;
      int firstDig;
      int rest;
      int rem;
	  int cnt;
	for (cnt = 0; cnt < (numDigit - 1); cnt++) {
		toStrip = toStrip * 10;
	}
      firstDig = possNum / toStrip;
      rest = possNum - (firstDig * toStrip);
      rem = (rest % 9) + 1;
      if (rem == firstDig) {
         return 1;
       }
      else {
         return 0;
       }
      return 0;
    }




void GenListCredCards (int array[], int numToGen, int numDigit) {
	int cnt;
	int numGend = 0;
	int rem;
	int firstDig;
	int numLeft = numToGen;
	int maxGen = 1;
	int numChancesLeft;
	int numNeeded;
	int cardNum;
	int keep;
	for (cnt = 0; cnt < (numDigit - 1); cnt++) {
		maxGen = maxGen * 10;
	}
	/* gen all possible */
	for (cnt = 0; cnt < maxGen; cnt++ ) {
		rem = (cnt % 9) + 1;
		firstDig = rem * maxGen; 
		cardNum = cnt + firstDig;
		/* cut some off */
		numChancesLeft = maxGen - cnt;
		numNeeded = numToGen - numGend;
		keep = ChooseProb(numNeeded,numChancesLeft);
		if (keep) {
			array[numGend] = cardNum;
			numGend++;
		}
	}
	/* are we sure to have the right number? */
	return;
}

void GenSearchList(int array[], int numToGen, int numDigit) {
	int cnt;
	int numGend = 0;
	int maxPoss = 1;
	int numImpossible = 0;
	int numPoss = 0;
	int couldBeOk ;
      int useIt;
	int rval;
	for (cnt = 0; cnt < numDigit; cnt++) {
		maxPoss = maxPoss * 10;
	}
      while (numGend < numToGen) {
         rval = rand() % maxPoss;
         couldBeOk = APossCard(rval,numDigit);
         if (couldBeOk) {
             useIt = ChooseProb(98,100);
           }
         else {
             useIt = ChooseProb(2,100);
           }
         if (useIt) {
            array[numGend] = rval;
            numGend++;
			/* for debugging */
			if (couldBeOk) {
				numPoss++;
			}
			else {
				numImpossible++;
			}
           }
        }
	  printf("Generated %d possible cards and %d impossible cards \n",
		  numPoss,numImpossible);
	return;

     }

/* returns first value above (e.g. log2 of 12 returns 4) */
int ApproxLog2N (int value) {
    int calc = 1;
    int power = 0;
    while (value > calc) {
       power++;
       calc = calc * 2;
     }
    return power;
  }