Name: Anonymous 2013-08-07 20:47
Write the fastest program that counts the number of words and lines in a string.
Here's my solution
#include "stdlib.h"
#include "stdbool.h"
#include "stdio.h"
// macro that increments index, sets variables for the next stage, and
// gotos the label indexed by the current character
#define next(c, lc, iw) cnt = (c); lcnt = (lc); in_word = (iw); idx++; goto *(jmp_arr[(int)str[idx-1]]);
int main(int argc, char** argv)
{
/* test string */
char* str = argv[1];
/* normally this would be done as a sort of partial evaluation, but i can't for example generate an optimized function at runtime in C */
void** jmp_arr;
jmp_arr = malloc(sizeof(char)*256);
int i;
for (i = 0; i < 256; i++)
{
switch ((char)i)
{
case '\n':
jmp_arr[i] = &&newline;
break;
case ' ':
jmp_arr[i] = &&whitespace;
break;
default:
jmp_arr[i] = &&character;
break;
}
}
// null character points to exit label
jmp_arr[0] = &&terminate;
int cnt = 0;
int lcnt = 1;
bool in_word = false;
int idx = 0;
// jump to label for first char
goto *(jmp_arr[(int)str[0]]);
terminate:
printf("words: %i, lines: %i\n", cnt, lcnt);
return 0;
whitespace:
next(cnt, lcnt, false);
newline:
next(cnt, lcnt+1, false);
character:
if (in_word)
{
next(cnt, lcnt, true);
}
else
{
next(cnt+1, lcnt, true);
}
}
Here's my solution
#include "stdlib.h"
#include "stdbool.h"
#include "stdio.h"
// macro that increments index, sets variables for the next stage, and
// gotos the label indexed by the current character
#define next(c, lc, iw) cnt = (c); lcnt = (lc); in_word = (iw); idx++; goto *(jmp_arr[(int)str[idx-1]]);
int main(int argc, char** argv)
{
/* test string */
char* str = argv[1];
/* normally this would be done as a sort of partial evaluation, but i can't for example generate an optimized function at runtime in C */
void** jmp_arr;
jmp_arr = malloc(sizeof(char)*256);
int i;
for (i = 0; i < 256; i++)
{
switch ((char)i)
{
case '\n':
jmp_arr[i] = &&newline;
break;
case ' ':
jmp_arr[i] = &&whitespace;
break;
default:
jmp_arr[i] = &&character;
break;
}
}
// null character points to exit label
jmp_arr[0] = &&terminate;
int cnt = 0;
int lcnt = 1;
bool in_word = false;
int idx = 0;
// jump to label for first char
goto *(jmp_arr[(int)str[0]]);
terminate:
printf("words: %i, lines: %i\n", cnt, lcnt);
return 0;
whitespace:
next(cnt, lcnt, false);
newline:
next(cnt, lcnt+1, false);
character:
if (in_word)
{
next(cnt, lcnt, true);
}
else
{
next(cnt+1, lcnt, true);
}
}