commodius_vicus
BAN USER@tjcbs2: right you are: let me see if I can salvage it!
That oughtta do it.
Same for me.
- commodius_vicus March 12, 2015I *think* this answers the question. This code will return an int value between 0 and n with the probability of a[n]. I have seen this question elsewhere specified a bit differently. (I think.)
/*
Distribute probabilities with weights read from an array.
Usage:
./a.out ntests array_size array[1] ... array[array_size]
./a.out 100000 6 0 2 3 4 5 6
That will run 100000 tests for a list of 6 numbers with relative probabilities
2 3 4 5 6. (The initial 0 is required.)
What is stored in the array is the sequence of accumulated total probabilities
to that point in the array. The algorithm does a binary search for the input
until
a[mid-1] <= number < a[mid]
OR
a[mid] <= number < [mid+1]. So the
"array" could be considered a very primitive form of hash.
another example:
./a.out 100000 9 0 2 2 4 10 3 3 10 10
int array[9] = { 0, 2, 4, 8, 18, 21, 24, 34, 44 };
input: 0 2 2 4 10 3 3 10 10
lookup values: 0-1, 2-3 4-7 8-17 18-20 21-23 24-33 34-43 NA
probability : 2/44 2/44 4/44 10/44 3/44 10/44 10/44 10/44 NA
The total is 44 and each number after the inital zero is the weight
assigned to the *preceding* index.
First entry MUST be lowest number you expect to get from random
generator, 0 is not assumed, but if you are going to use '%'
to get your randome values, you'll get 0s.
Running the first example:
./a.out 100000 6 0 2 3 4 5 6
probabilities for usage example are are:
1/10 3/20 1/5 1/4 3/10
./a.out 1000000 6 0 2 3 4 5 6
array_size=6 { 0, 2, 5, 9, 14, 20, }
running 1000000 tests with max_number=20
value=0 count=100022
value=1 count=150392
value=2 count=199435
value=3 count=250420
value=4 count=299731
value=5 count=0
for even distribution:
./a.out 1000000 6 0 1 1 1 1 1
Notes:
Doesn't now deal with probability 0, but that can be handled by
checking for contiguous equivalent sums in the array.
The max_num check is unnecessary here, but left in because that
may not always be the case. Also, the recursion runaway hasn't happened,
but I haven't tested with all possibly weird inputs.
All '0's will give a float exception at the '%'.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int max_recursion_level;
int find_index( int array[], int number, int start, int end );
int *create_array(int array_size, int argc, char **argv, int *ptr);
int find_index( int array[], int number, int start, int end ) {
int mid;
mid = (end - start)/2;
mid += start;
if (!--max_recursion_level) {
printf("Exceeded max recursion level!\n");
return(-1);
}
if (number < array[mid] ) {
int lbound = mid-1;
if (number >= array[lbound]) { return lbound; }
end = lbound;
} else if ( number == array[mid] ) {
return mid;
} else if ( number > array[mid] ) {
int ubound = mid+1;
if (number < array[ubound]) { return mid; }
if (number == array[ubound] ) { return ubound; }
start = ubound;
}
return find_index( array, number, start, end );
}
int *create_array(int array_size, int argc, char **argv, int *ptr) {
int i, sum;
int *curr;
if (argv != NULL && array_size != argc ) {
printf("Argument count %d is inconsistent with array size %d.\n",argc,array_size);
exit(1);
}
ptr = calloc(sizeof(int),array_size);
if (!ptr) {
printf("calloc() failed.\n");
exit(1);
}
if (argv == NULL) {
return ptr;
}
curr = ptr;
printf("array[%d] = { ",array_size);
sum = 0;
for(i=0; i<array_size; i++) {
sum += atoi(*argv++);
printf("%d%c",sum,i==array_size-1 ? ' ' : ',' );
*curr++ = sum;
}
printf("};\n");
return ptr;
}
main(int argc, char **argv) {
int ntests;
int value,number;
int *array, *result_array;
int max_number, min_number, array_size;
*argv++;
ntests = atoi(*argv++);
array_size = atoi(*argv++);
argc -= 3;
result_array = create_array(array_size, 0, NULL, result_array);
array = create_array(array_size, argc, argv, array );
min_number = array[0];
max_number = array[array_size-1];
printf("running %d tests with max_number=%d\n",ntests,max_number);
while (ntests--) {
max_recursion_level = 8;
number = rand() % max_number;
if (number >= max_number) {
printf("Number %d out_of_range 0-%d.\n", number,array[array_size-1]);
continue;
}
value = find_index(array, number, 0, array_size );
result_array[value]++;
}
for (value=0; value<array_size; value++) {
printf("value=%d count=%d\n",value,result_array[value]);
}
free(array);
free(result_array);
exit(0);
}
/*
Find a word in matrix of letters. Use each instance of a letter only once.
usage:
./a.out row1 row2 row3 row4 word
where a1 a2 a3 a4 are four letter sequences to put in the rows of the matrix and
"word" is th eword to search for.
The matrix for the examples below would be:
abcd
efgh
ijkl
mnop
e.g.
% ./a.out abcd efgh ijkl mnop pkfa
% search: pkfa
% found : pkfa
% ./a.out abcd efgh ijkl mnop pkfd
% search: pkfd
% not found
Pretty straightforward. Spread out from each letter to the surrounding letters, if you
find something mark it as visited in a bit string and continue for as long as there are
letters left in "word" or you can't find the next letter. Uses only counters and a 16-bit
short on the stack.
Compile with _trace set to follow all the action.
It CAN be done with one routine, you just have to initially call it four times
for all possible starting letters to work.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int _trace = 0;
main(int argc, char **argv) {
char *word, *start;
unsigned short visited = 0;
int i,j,msize;
int col, row;
int found = 0;
char matrix[4][4];
if (argc < 6) {
printf("Not enough arguments.\n");
exit(1);
}
memset(&matrix[0][0],0x00,16);
for (i=0; i<4; i++) {
strncpy(&matrix[i][0], argv[i+1],4);
}
word = argv[5];
msize = 4;
start = word;
printf("search: %s\n",word);
for (col=1; col<msize; col+=2) {
for (row=1; row<msize; row+=2) {
if (_trace) {
printf("starting at %d %d\n",row,col);
}
found = find_word(start,matrix,row,col,msize,&visited);
if (found) break;
start = word;
visited = 0;
}
if (found) break;
}
if (found) {
printf("found : %s\n",word);
} else {
printf("not found\n");
}
exit(!found);
}
int find_word(char *word, char matrix[4][4], int arg_col, int arg_row, int msize, unsigned short *visited) {
int row,col;
unsigned short bits = 0;
char *start;
if (*word == 0x00) {
return 1;
}
for (col=arg_col-1; col<=arg_col+1; col++) {
if ((col < 0) || (col >= msize)) continue;
for (row=arg_row-1; row<=arg_row+1; row++) {
if ((row < 0) || (row >= msize)) continue;
bits = (0x01<<((col<<2)+row));
if (_trace) {
printf("%d %d %c %c %u\n",col,row,matrix[col][row],*word,!(bits & *visited));
}
if ((matrix[col][row] == *word) && !(bits & *visited) ) {
start = ++word; *visited |= bits;
return find_word(start, matrix, col, row, msize, visited);
}
}
}
*visited = 0;
return 0;
}
/*
Balance pairs of brackets/parens uses an array of m chars where the
start of the pair is at n and the match is at n+(m/2).
This implementation will ignore anything not in the pairs array, except
that if the first character of the passed in string is '^', "trace" will be set
and the consumptoin of the string.
If the max recursion level is exceeded, the process will bail. It is
currently set to 16.
Note that this can very easily be upgraded to do proper quote
processing (about eight more lines of code). Left as an exercise for the
reader.
usage:
./a.out string
Examples:
$ ./a.out "[[<<>>]()]"
string: [[<<>>]()]
balanced = true
$ ./a.out "^[[<<>>]()]"
string: ^[[<<>>]()]
level=0 start=^[[<<>>]()] s=^[[<<>>]()]
level=0 start=^[[<<>>]()] s=[[<<>>]()]
level=1 start=[[<<>>]()] s=[<<>>]()]
level=2 start=[<<>>]()] s=<<>>]()]
level=3 start=<<>>]()] s=<>>]()]
level=4 start=<>>]()] s=>>]()]
level=3 start=<<>>]()] s=>]()]
level=2 start=[<<>>]()] s=]()]
level=1 start=[[<<>>]()] s=()]
level=2 start=()] s=)]
level=1 start=[[<<>>]()] s=]
balanced = true
$ ./a.out "^[[<<>>]()"
string: ^[[<<>>]()
level=0 start=^[[<<>>]() s=^[[<<>>]()
level=0 start=^[[<<>>]() s=[[<<>>]()
level=1 start=[[<<>>]() s=[<<>>]()
level=2 start=[<<>>]() s=<<>>]()
level=3 start=<<>>]() s=<>>]()
level=4 start=<>>]() s=>>]()
level=3 start=<<>>]() s=>]()
level=2 start=[<<>>]() s=]()
level=1 start=[[<<>>]() s=()
level=2 start=() s=)
level=1 start=[[<<>>]() s=[[<<>>]()
level=2 start=() s=)
level=1 start=[[<<>>]() s=[[<<>>]()
balanced = false: Unbalanced start token: [ at position 1
$ ./a.out "[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]"
string: [[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]
Reached max recursion level: aborting.
balanced = false: Reached max recursion level 16: { at position 16
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int balance(char **ptr, const char *pairs, int npairs, int *level );
int max_level = 16;
int _trace = 0;
main(int argc, char **argv) {
int level = 0;
char *pairs="({[<)}]>";
char **s = &argv[1];
char *save = *s;;
int balanced = 0;
printf("string: %s\n",*s);
if (*save == '^') {
_trace = 1;
}
while (**s && balanced == 0) {
balanced = balance(s,pairs,strlen(pairs),&level);
}
printf("balanced = %s ",balanced == 0 ? "true\n" : "false: ");
if (balanced == -1) {
printf("Unbalanced end token: \"%c\" at position %ld\n",**s,*s-save);
} else if (balanced == 1) {
printf("Unbalanced start token: \"%c\" at position %ld\n",**s,*s-save);
} else if (balanced == 2) {
printf("Reached max recursion level %d: \"%c\" at position %ld\n",max_level,**s,*s-save);
}
}
int balance(char **s, const char *pairs, int npairs, int *level ) {
int i,k,balanced;
char *start = (*s);
balanced == 0;
if (*level > max_level) {
printf("Reached max recursion level: aborting.\n");
return 2;
}
if (*level) (*s)++;
k = (npairs)>>1;
while (**s) {
char *curr = *s;
if (_trace) printf("level=%d start=%s s=%s\n", *level, start, *s);
for (i=0; i<k; i++) {
int j = i+k;
if ( *curr == pairs[j] ) {
if ( *start != pairs[i] ) return -1;
(*level)--;
return 0;
} else if ( *curr == pairs[i] ) {
(*level)++;
balanced = balance(s, pairs, npairs, level);
if (balanced != 0) {
(*level)--;
return balanced;
}
break;
}
}
(*s)++;
}
if (!**s && *level !=0) {
*s = start;
if (_trace) printf("level=%d start=%s s=%s\n", *level, start, *s);
if (*level == -1) {
return -1;
}
return 1;
}
return 0;
}
/*
Reverse the words (space delimited tokens, anyway) in a sentence.
Usage: ./a.out 'Put the sentence between two single quotes.'
Reverse string with converging pointers, "unreverse" words when you have
finished the token. When pointers converge, start at least word pointer
and unreverse the words in the second half. All that unreversing seems
kind of silly: I'd like to see another way.
Note: I'm not a big believer in XOR swaps. It's a macro. Feel free.
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SWAP(s,i,j,temp) temp=s[i]; s[i] = s[j]; s[j]=temp;
main(int argc, char **argv) {
int i,j,k,w,len;
register char *s;
register char temp = 0x00;
if (argc > 0) {
s=calloc(strlen(argv[1]+4 % 4),1);
if (!s) {
printf("calloc() failed.\n");
exit(1);
}
strncpy(s,argv[1],strlen(argv[1]));
} else {
printf("Nothing to do.\n");
exit(0);
}
w = 0;
i = 0;
len = strlen(s);
j = len-1;
printf("sentence: %s\n",s);
do {
SWAP(s,i,j,temp);
if (s[i] == ' ') {
k = i-1;
do {
SWAP(s,w,k,temp);
} while (--k > w++);
w = i+1;
}
} while(--j > i++);
for (i=w; i<len+1; i++) {
if (s[i] == ' ' || i == len) {
k = i-1;
do {
SWAP(s,w,k,temp);
} while (--k > w++);
w = i+1;
}
}
printf("reversed: %s\n",s);
exit(0);
}
/*
Find longest unique substring.
usage:
% ./a.out string
This prints *first* instance of longest unique string. Iterates once
through the string, setting a bit in an array of masks if it sees
a letter that it hasn't seen before. If it HAS seen it before,
it first sets the position of the repeated letter as the beginning of a new
"candidate" lus and clears the mask, which if it becomes longer than
the previous lus, becomes the new lus.
change '>' to '>='
if (++lus_candidate_len >= lus_len) {
to get last.
Notes:
Adds a total of 61 bytes to the stack with printfs commented out.
./a.out "abcdabcde"
./a.out "abcdeabcd"
*/
#include <stdio.h>
#include <stdlib.h>
main(int argc, char **argv) {
char *s;
unsigned long bits[4] = {0,0,0,0};
unsigned long set = 0;
unsigned char i,c;
register int curr;
int lus_candidate, lus;
int lus_candidate_len, lus_len;
if (argc == 2) {
s = argv[1];
} else {
printf("Nothing to do.\n");
exit(0);
}
lus_candidate = lus = curr = 0;
lus_candidate_len = lus_len = 0;
printf("string: %s\n",s);
for(curr=0; curr<strlen(s); curr++) {
c = (unsigned char)s[curr];
i = c >> 5;
set = 0x01<<(c & 0x1F);
if (bits[i] & set) {
do {
c = (unsigned char)s[lus_candidate];
bits[c >> 5] ^= 0x01<<(c & 0x1F);
lus_candidate_len--;
} while(s[lus_candidate++] != s[curr]);
}
bits[i] |= set;
if (++lus_candidate_len >= lus_len) {
lus = lus_candidate;
lus_len = lus_candidate_len;
}
}
if (lus_len) {
printf("lus %s%*s%.*s\n\"%.*s\" at offset %d with length=%d.\n",
lus==0 ? ":":": ",lus," ",lus_len,&s[lus],
lus_len,&s[lus],lus,(int)lus_len);
} else {
printf("Nothing found.\n");
}
}
#include <stdio.h>
#include <stdlib.h>
main(int argc, char **argv) {
char *s;
unsigned long bits[4] = {0,0,0,0};
unsigned long set = 0;
unsigned char i,c;
register int curr;
int lus_candidate, lus;
int lus_candidate_len, lus_len;
if (argc == 2) {
s = argv[1];
} else {
printf("Nothing to do.\n");
exit(0);
}
lus_candidate = lus = curr = 0;
lus_candidate_len = lus_len = 0;
printf("string: %s\n",s);
for(curr=0; curr<strlen(s); curr++) {
c = (unsigned char)s[curr];
i = c >> 5;
set = 0x01<<(c & 0x1F);
if (bits[i] & set) {
do {
c = (unsigned char)s[lus_candidate];
bits[c >> 5] ^= 0x01<<(c & 0x1F);
lus_candidate_len--;
} while(s[lus_candidate++] != s[curr]);
}
bits[i] |= set;
if (++lus_candidate_len >= lus_len) {
lus = lus_candidate;
lus_len = lus_candidate_len;
}
}
if (lus_len) {
printf("lus %s%*s%.*s\n\"%.*s\" at offset %d with length=%d.\n",
lus==0 ? ":":": ",lus," ",lus_len,&s[lus],
lus_len,&s[lus],lus,(int)lus_len);
} else {
printf("Nothing found.\n");
}
}
Code formatter does't like '>>' operator. >>;5 should obviously be >>5
- commodius_vicus March 16, 2015