Name: Anonymous 2012-02-13 18:30
as complicated as possible and in a functional language of your choosing
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <time.h>
#define START_OF_STRING_SYMBOL 256
#define NUMBER_OF_STATES 257
struct byte_set {
unsigned char array[256>>3];
};
void init_byte_set(struct byte_set* self) {
memset(self->array, 0, (256>>3)*sizeof(char));
}
int get_byte(struct byte_set* self, unsigned char ascii) {
return self->array[ascii>>3]&(1<<(ascii&((1<<3)-1)));
}
void set_byte_on(struct byte_set* self, unsigned char ascii) {
self->array[ascii>>3] |= (1<<(ascii&((1<<3)-1)));
}
void set_byte_off(struct byte_set* self, unsigned char ascii) {
self->array[ascii>>3] &= ~(1<<(ascii&((1<<3)-1)));
}
/* debugging
void print_byte_set(struct byte_set* self) {
int ascii;
int index;
printf("(");
for(index = 0; index < (256>>3); ++index) {
printf("%x ", self->array[index]);
}
printf(")");
printf("[");
for(ascii = 0; ascii < 256; ++ascii) {
if(get_byte(self, ascii)) {
printf("%x ", ascii);
}
}
printf("]");
}
*/
struct transition_sets {
struct byte_set start_transitions;
struct byte_set char_transitions[256];
};
void init_transition_sets(struct transition_sets* self) {
int index;
init_byte_set(&self->start_transitions);
for(index = 0; index < 256; ++index) {
init_byte_set(&self->char_transitions[index]);
}
}
void insert_start_char(struct transition_sets* self, unsigned char value) {
set_byte_on(&self->start_transitions, value);
}
void insert_char(struct transition_sets* self, unsigned char key, unsigned char value) {
set_byte_on(&self->char_transitions[key], value);
}
/* debugging
void print_transition_sets(struct transition_sets* self) {
int index;
printf("starts: "); print_byte_set(&self->start_transitions); printf("\n");
for(index = 0; index < 256; ++index) {
printf("[%x] = ", index); print_byte_set(&self->char_transitions[index]); printf("\n");
}
}
*/
void read_string_to_transition_sets(char* string, struct transition_sets* self) {
insert_start_char(self, *string);
char* prev = string;
char* next = string+1;
for(;;) {
insert_char(self, *prev, *next);
if(*next == '\0') break;
prev++;
next++;
}
}
struct sparse_byte_set {
int length;
char buffer[256]; // wasted space
};
void init_sparse_byte_set(struct sparse_byte_set* self) {
self->length = 0;
}
void push_char_on_sparse_byte_set(struct sparse_byte_set* self, char value) {
self->buffer[self->length++] = value;
}
void byte_set_to_sparse_byte_set(struct byte_set* input, struct sparse_byte_set* output) {
int ascii;
for(ascii = 0; ascii < 256; ++ascii) {
if(get_byte(input, ascii)) push_char_on_sparse_byte_set(output, ascii);
}
}
char sample_sparse_byte_set(struct sparse_byte_set* self) {
assert(self->length > 0);
int mod = random() % self->length;
int index = mod >= 0 ? mod : -mod;
return self->buffer[index];
}
struct sparse_transition_sets {
struct sparse_byte_set start_transitions;
struct sparse_byte_set char_transitions[256];
};
void init_sparse_transition_sets(struct sparse_transition_sets* self) {
int index;
init_sparse_byte_set(&self->start_transitions);
for(index = 0; index < 256; ++index) {
init_sparse_byte_set(&self->char_transitions[index]);
}
}
void transition_sets_to_sparse_transition_sets(struct transition_sets* input, struct sparse_transition_sets* output) {
int index;
byte_set_to_sparse_byte_set(&input->start_transitions, &output->start_transitions);
for(index = 0; index < 256; ++index) {
byte_set_to_sparse_byte_set(&input->char_transitions[index], &output->char_transitions[index]);
}
}
void run_sparse_transition_sets(struct sparse_transition_sets* self, FILE* output) {
char current;
for(current = sample_sparse_byte_set(&self->start_transitions);
current != '\0';
current = sample_sparse_byte_set(&self->char_transitions[current])) {
fputc(current, output);
}
}
int main(int argc, char** argv) {
char* string = "hello world!\n";
struct transition_sets reading_table;
struct sparse_transition_sets writing_table;
srand(time(NULL));
init_transition_sets(&reading_table);
read_string_to_transition_sets(string, &reading_table);
init_sparse_transition_sets(&writing_table);
transition_sets_to_sparse_transition_sets(&reading_table, &writing_table);
run_sparse_transition_sets(&writing_table, stdout);
return 0;
}
$ gcc hel.c
$ a.out
held!
$ a.out
helo worlorlllo wo wo world!
$ a.out
helo worlld!
$ a.out
helorlld!
$ a.out
hellorlorlo wo world!
$ a.out
helllllo wo worlorlo worlld!
$ a.out
helorlld!
$ a.out
helo wo worlo wo wo world!
$ a.out
helo wo wo worlld!
$ a.out
hellld!
$ a.out
held!
$ a.out
helorld!
$ a.out
helorld!
$