USACO NOV06 Problem 'scrbl' Analysis

by Rob Kolstad

Matching a scrabble 'rack' requires a technique for determining whether a word uses up the appropriate letters and determining how to deal with blanks.

This simple solution keeps track of the count of each of the letters in the rack. Each dictionary word is read in sequence (thus removing any sorting requirements). An array of 128 integers keeps track of the rack's letter count (while only 26 are needed, 128 is plenty and enables subscripting with the character's ASCII value). So, a rack of ("COWFOOD") would have rack['O'] == 3, while the 'C', 'W', 'F', and 'D' subscripts would each ave the value 1.

Each letter in the dictionary's input word is used to subscript and decrement that letter's count in 'dictword'. If the letter count goes negative, then a new variable 'nbad' is increment. If the number of wildcards ('#') is at least as big as 'nbad', then the rack 'matches' the dictionary word.

#include <stdio.h>
#include <strings.h>

char rack[128];
char dictword[128];

main () {
    FILE *fin = fopen ("scrbl.in", "r");
    FILE *fout = fopen ("scrbl.out", "w");
    FILE *fdict = fopen ("scrbl.txt", "r");
    char *p, line[80];
    int nbad, i;
    int nwords = 0;
    fgets (line, 80, fin);      /* ignore number of words; use EOF */
    fgets (line, 80, fin);
    for (p = line; *p; p++)
        rack[*p]++;
    fclose (fin);
    while (fgets (line, 80, fdict) ) {
        nwords++;
        bcopy (rack, dictword, 128);
        nbad = 0;
        for (p = line; *p; p++)
            if (--dictword[*p] < 0) { nbad++; }
        if (nbad <= rack['#'])
            fprintf (fout, "%s", line);
    }
    fclose (fout);
    exit (0);
}