Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# USACO Name That Number Puzzle

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```// 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
LANG: C
*/

#include

#include

#include

#include

#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 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 = #[numdigits-1];
int *end = #[numdigits-1];
int *start = #[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);
fscanf(fin, "%s", numstring);
int numdigits = strlen(numstring);

result = permute(fout, numdigits, numstring);
if (hasOneName == false) {
fprintf(fout, "%s\n", "NONE");
}

return EXIT_SUCCESS;
}

``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.