Stafettlek för programmerare

/*
 * Stafettlek för programmerare.
 *
 * Tävligen är väldigt enkel och består av två moment:
 *
 *   A) Bidra med kod för att bygga upp ett framework.
 *   B) Använd framework:et för skriva originella program.
 *
 * Reglerna är väldigt enkla
 *   - man skall enbart använda funktioner/datastrukturer från denna modul.
 *   - inga funktionsanrop till standardbiblioktet.
 *   - inga "headers" får inkluderas.
 *   - inga externa bibliotek.
 *
 * Tanken är alltså att vi skall sluta upp med en jättestor fil som utgör vårt
 * "standardbibliotek" när vi går över till moment (B).
 *
 * Finns inga krav på att man måste bidra till (A) för att få delta i (B) eller
 * att man måste använda en viss stil. Keep it simple, reuse and code(tm).
 *
 * Språk: C
 *
 * Senaste versionen av denna fil hittar ni hittar ni på:
 *
 * http://www.superdupa.com/public/code/swec/
 *
 * Tips/ideér:
 *  - implementera memcpy/memset/memmove
 *  - vi behöver helt klart de vanligaste strängfunktionerna
 *  - få till lite buffrad output istället för en write_char åt gången
 *  - matematik funktioner (sin/tan/exp/log)
 *  - använd stdin/stdout för att komma åt filer under moment (B).
 *  - implementera lite enkla filformat (t.ex TGA)
 * 
 * Lycka till!
 *
 * PS. Ni som hänger på #c++.se kan väl försöka få hit lite folk.
 *
 */

#define NULL ((void*)0)

/*
 *=======================================
 *  Boilerplate and primitive I/O functions (from support.c)
 *=======================================
 */

#define assert(expr) \
  do{if(!(expr)){assertion_failed(#expr,__FILE__,__LINE__);}}while(0)

/* Print error message and terminate program execution. */
extern void err_quit(char *fmt, ...);

/* Print developer output. */
extern void trace(char *fmt, ...);

/* Report runtime assertion failure. */
extern void assertion_failed(char *expr, char *file, int line);

/* Returns 0 if char could not be written to stdout. */
extern int write_char(int ch);

/* Returns 1 if the input stream (stdin) has reached end of file. */
extern int is_eof();

/* Returns char value (0-255) or (-1) if read operation from stdin failed. */
extern int read_char();

/* Returns pointer to freshly allocated memoryblock of n bytes. */
extern void *mem_alloc(int num_bytes);

/* Deallocate memory block. */
extern void mem_free(void *p);

/*
 *=======================================
 *  Your contribution here [nick]
 *=======================================
 */

/* This comment tell us what myfunc returns. */
void myfunc()
{
}

/*
 *=======================================
 *  Program entrypoint.
 *=======================================
 */

#define UNUSED_ARGUMENT(x) ((void)(x))

int main(int argc, char *argv[])
{
  UNUSED_ARGUMENT(argc);
  UNUSED_ARGUMENT(argv);

  return 0;
}

/*
 *=======================================
 *  String search [Rampkorv]
 *=======================================
 */

/* Returns location of first match or NULL if char was not found. */
char *SearchForChar(char *str, char ch)
{
  char *p = str;

  while (p) {
    if (*p == ch)
      return p;
    if (*p == '\0')                     /* End of string, null terminator. */
      break;
    p++;
  }

  return NULL;
}

/*
 *=======================================
 *  String length [Sirjeppe]
 *=======================================
 */

/* Return length of string (>= 0). */
int strlen(char *str)
{
  char *nullPos = SearchForChar(str, '\0');
  return (nullPos ? (nullPos - str) : 0);
}

C exempel: boolean scrabble_match(char *word, char *letters);

/*
 *=======================================
 *  Generate primes [bobby]
 *=======================================
 */

/* Returns 1 if n can be factored using supplied table of primes. */
int can_factor(int n, int *primes, int num_primes)
{
  int i;

  for (i = 0; i < num_primes; i++) {
    if ((n % primes[i]) == 0)
      return 1;
  }
  
  return 0;
}

/* Computes the first 'n' primes and stores them into 'sieve'.
   Note: caller must ensure array size of 'sieves' >= 'n'. */
void gen_primes(int n, int *sieves)
{
  int i, j;

  if (n > 0) {
    sieves[0] = 2;
    for (i = 1; i < n; i++) {
      /* Search forward from last prime. */
      j = sieves[i-1] + 1;
      while (can_factor(j, sieves, i))
	j++;
      sieves[i] = j;
    }
  }
}

/*
 *=======================================
 *  Scrabble matcher [bobby]
 *=======================================
 */

/* Assign each character a prime factor based on a simplistic character
   frequency distribution order (higher freq gives low prime). */
void setup_char_prime_table(int *chartab)
{
    int i;
    int primes[26];
    int order[26] = {'e','t','a','h','o','s','n','r','i','l','d','u','w',
		     'm','c','g','y','f','b','p','k','v','j','x','q','z'};
    
    gen_primes(26, primes);
    for (i = 0; i < 26; i++)
      chartab[order[i] - 'a'] = primes[i];
}

/* Returns prime factor representation for a given letter [a-z]. */
int char_as_prime(char ch)
{
  static int primes[26];
  static int table_init = 0;

  assert(ch >= 'a' && ch <= 'z');

  if (!table_init) {
    setup_char_prime_table(primes);
    table_init = 1;
  }

  return primes[ch - 'a'];
}

#define MAX_WORD_VALUE 2147483647
#define MUL_WILL_OVERFLOW(prod, fact) ((MAX_WORD_VALUE / (prod)) < (fact))

/* Compute a numerical representation of word [a-z] using prime factors. */
int make_word_num(char *word)
{
  int i, r, k;

  /* Abuse the fundamental theorem of arithmetic to create number where each
     letter maps to a specific prime factor. */
  r = 1;
  for (i = 0; i < strlen(word); i++) {
    k = char_as_prime(word[i]);
    /* @Portability: Word probably contained lots of characters with low
       frequency which would have resulted in an overflow. This is not an
       algorithmic limitation but rather the lack of a builtin 'bignum'. */
    if (MUL_WILL_OVERFLOW(r, k))
      err_quit("Overflow during calculation of 'make_word_num'.");
    r *= k;
  }
  
  return r;
}

/* Returns 1 if 'word' can be made up by using some or all letters in 'rack'.
   Note: caller must filter arguments through 'make_word_num'. */
int scrabble_match(int word, int rack)
{
  /* The idea is very simple. If we represent our rack "abab" as 2*3*2*3=36
     and the word "abb" as 2*3*3=18 we can easily see that 18 shares factors with
     36 and thus the it can be composed using the "factors" from the rack. */
  return (rack % word) == 0;
}

/*
 * trace("match: %d\n",
 *	scrabble_match(
 *	  make_word_num("rabbit"),
 *	  make_word_num("abbirt")));
 *	  
 * trace("match: %d\n",
 *	scrabble_match(
 *	  make_word_num("rabbit"),
 *	  make_word_num("xbbirt")));
 *
 */