DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Roger has posted 34 posts at DZone. View Full User Profile

USACO Name That Number Puzzle

12.05.2008
| 745 views |
  • submit to reddit
        // A brute-force approach to USACO's "Name that Number" problem. I'm just using the site to give 
// myself interesting problems to solve, so this solution is more verbose than a good code 
// competition solution would be. It would be rather easy to speed up this algorithm by pruning
// the search down, but it passed USACO's judge as is, so I'm leaving it alone.

/*
ID: rturnau1
PROG: namenum
LANG: C
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define SIZE_OF_DICTIONARY  4618
#define MAX_STRING          13

char two[] =   { 'A', 'B', 'C' }; 
char three[] = { 'D', 'E', 'F' };
char four[] =  { 'G', 'H', 'I' };
char five[] =  { 'J', 'K', 'L' };
char six[] =   { 'M', 'N', 'O' };
char seven[] = { 'P', 'R', 'S' };
char eight[] = { 'T', 'U', 'V' };
char nine[] =  { 'W', 'X', 'Y' };

bool hasOneName = false;

char *dict[SIZE_OF_DICTIONARY];

bool searchName(char *name, int compChars) {
    int low, high, mid, result;
    low = 0;
    high = SIZE_OF_DICTIONARY - 1;
    
    while (low <= high) {
        mid = (low + high) / 2;
        result = strncmp(dict[mid], name, compChars);
        if (result > 0) {
            high = mid - 1;
        } else if (result < 0) {
            low = mid + 1;
        } else {
            return true;
        }   
    }
    return false;
}

int readDictionary() {
    int i = 0, result = 0;
    FILE *dictionary;
    dictionary = fopen("dict.txt", "r");
    memset(dict, 0, sizeof dict);
    char name[MAX_STRING];
    char * entry;
    memset(name, 0, sizeof name);
    while ((result = fscanf(dictionary, "%s", name)) != EOF) {
        entry = malloc(sizeof name);
        strcpy(entry, name);
        dict[i++] = entry;
        memset(name, 0, sizeof name);
    }
    
    return EXIT_SUCCESS;
}

char getNextChar(char number, int index) {
    char next;
    
    switch (number) {
    case '2':
        next = two[index];
        break;
    case '3':
        next = three[index];
        break;
    case '4':
        next = four[index];
        break;
    case '5':
        next = five[index];
        break;
    case '6':
        next = six[index];
        break;
    case '7':
        next = seven[index];
        break;
    case '8':
        next = eight[index];
        break;
    case '9':
        next = nine[index];
        break;
    }
    return next;
}

int showWord(FILE *fout, int numdigits, char name[numdigits+1], int index[numdigits]) {
    char result[numdigits+1];
    memset(result, 0, sizeof result);
    int x;
    bool found = false;
    
    for (x = 0; x < numdigits; ++x) {
        result[x] = getNextChar(name[x], index[x]);
    }
    
    if ((found = searchName(result, numdigits+1)) == true) {
        hasOneName = true;
        fprintf(fout, "%s\n", result);
    }
    
    
    return EXIT_SUCCESS;
}



int permute(FILE *fout, int numdigits, char numstring[numdigits+1]) {
    /* count ternary */
    int num[numdigits];
    memset(num, 0, sizeof num);
    num[numdigits] = 0;
    int *curIndex = &num[numdigits-1];
    int *end = &num[numdigits-1];
    int *start = &num[0];
    bool done = false;
    
    while (!done) {
        showWord(fout, numdigits, numstring, num);
        if (*curIndex < 2) {
            (*curIndex)++;
        } else {
            /* move left until you find a number < 2 */
            while (curIndex >= start && *curIndex == 2) {
                --curIndex;
            }
            if (curIndex < start) {
                done = true;
            } else {
                (*curIndex)++;
                while (curIndex < end) {
                    curIndex++;
                    *curIndex = 0;
                }                
            }
        }
    }  
    return EXIT_SUCCESS;
}

int main(void) {
    FILE *fin, *fout;
    int result = 0;
    
    char numstring[MAX_STRING];
    char name[MAX_STRING];
    memset(numstring, 0, sizeof numstring);
    memset(name, 0, sizeof name);
    fin = fopen("namenum.in", "r");
    fout = fopen("namenum.out", "w");
    fscanf(fin, "%s", numstring);
    int numdigits = strlen(numstring);
    
    readDictionary();
    
    result = permute(fout, numdigits, numstring);
    if (hasOneName == false) {
        fprintf(fout, "%s\n", "NONE");
    }
	
	return EXIT_SUCCESS;
}

    
    Tags:
  • C