Skip to analysis
This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!
Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don’t appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, “C’mon, #4734, get along.”
Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for “Q” and “Z”):
2: A,B,C 5: J,K,L 8: T,U,V
3: D,E,F 6: M,N,O 9: W,X,Y
4: G,H,I 7: P,R,S
Acceptable names for cattle are provided to you in a file named “dict.txt”, which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow’s brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).
For instance, the brand number 4734 produces all the following names:
GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG
GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH
HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI
IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG
ISEH ISEI ISFG ISFH ISFI
As it happens, the only one of these 81 names that is in the list of valid names is “GREG”.
Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ‘NONE’ if there are no valid names. Serial numbers can be as many as a dozen digits long.
PROGRAM NAME: namenum
INPUT FORMAT
A single line with a number from 1 through 12 digits in length.
SAMPLE INPUT (file namenum.in)
4734
OUTPUT FORMAT
A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.
SAMPLE OUTPUT (file namenum.out)
GREG
CODE
Java
C++
Pascal
ANALYSIS
Russ Cox & Rob Kolstad
There are two ways to do this problem. One is, given the number, to generate all possible strings that encode to that number and look them up in the dictionary. Since there are 3 letters for each number and 12 digits in the string, that’s 312 = 531441 lookups into a dictionary of size 5000, which although manageable would be a little on the long side (binary search can help this).
Or, we can examine each word in the dictionary to see if it maps to the digits of the number in question. This has the advantage of a shorter program that probably will work right first time.
The solution below might be considered to be a bit more straightforward: no tricky offsets, no +1 or -1, no knowledge about character values. The lines of actual code in this solution are minimal.
This is the sort of program that might work reliably the first time and every time. The only tricky part is knowing that scanf will yield a string without a newline on the end:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
FILE *in = fopen ("namenum.in", "r");
FILE *in2 = fopen ("dict.txt", "r");
FILE *out = fopen ("namenum.out","w");
int nsolutions = 0;
int numlen;
char word[80], num[80], *p, *q, map[256];
int i, j;
map['A'] = map['B'] = map['C'] = '2';
map['D'] = map['E'] = map['F'] = '3';
map['G'] = map['H'] = map['I'] = '4';
map['J'] = map['K'] = map['L'] = '5';
map['M'] = map['N'] = map['O'] = '6';
map['P'] = map['R'] = map['S'] = '7';
map['T'] = map['U'] = map['V'] = '8';
map['W'] = map['X'] = map['Y'] = '9';
fscanf (in, "%s",num);
numlen = strlen(num);
while (fscanf (in2, "%s", word) != EOF) {
for (p=word, q=num; *p && *q; p++, q++) {
if (map[*p] != *q)
break;
}
if (*p == '\0' && *q == '\0') {
fprintf (out, "%s\n", word);
nsolutions++;
}
}
if (nsolutions == 0) fprintf(out,"NONE\n");
return 0;
}
Michel Mizrah
Here is Argentina competitor’s Michel Mizrah’s solution using the first method with a binary search. While it is blazingly fast, it does have the disadvantage of some fairly tricky coding in the binary search routine. A single off-by-one error would doom a program in a contest.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char num[12],sol[12];
char dict[5000][13];
int nsolutions = 0;
int nwords;
int maxlen;
FILE *out;
void calc (int charloc, int low, int high) {
if (charloc == maxlen) {
sol[charloc] = '\0';
for (int x = low; x < high; x++) {
if (strcmp (sol, dict[x]) == 0) {
fprintf (out, "%s\n", sol);
nsolutions++;
}
}
return;
}
if (charloc > 0) {
for (int j=low; j <= high; j++){
if (sol[charloc-1] == dict[j][charloc-1]) {
low=j;
while (sol[charloc-1] == dict[j][charloc-1])
j++;
high=j;
break;
}
if (j == high) return;
}
}
if (low > high) return;
switch(num[charloc]){
case '2':sol[charloc] = 'A'; calc(charloc+1,low,high);
sol[charloc] = 'B'; calc(charloc+1,low,high);
sol[charloc] = 'C'; calc(charloc+1,low,high);
break;
case '3':sol[charloc] = 'D'; calc(charloc+1,low,high);
sol[charloc] = 'E'; calc(charloc+1,low,high);
sol[charloc] = 'F'; calc(charloc+1,low,high);
break;
case '4':sol[charloc] = 'G'; calc(charloc+1,low,high);
sol[charloc] = 'H'; calc(charloc+1,low,high);
sol[charloc] = 'I'; calc(charloc+1,low,high);
break;
case '5':sol[charloc] = 'J'; calc(charloc+1,low,high);
sol[charloc] = 'K'; calc(charloc+1,low,high);
sol[charloc] = 'L'; calc(charloc+1,low,high);
break;
case '6':sol[charloc] = 'M'; calc(charloc+1,low,high);
sol[charloc] = 'N'; calc(charloc+1,low,high);
sol[charloc] = 'O'; calc(charloc+1,low,high);
break;
case '7':sol[charloc] = 'P'; calc(charloc+1,low,high);
sol[charloc] = 'R'; calc(charloc+1,low,high);
sol[charloc] = 'S'; calc(charloc+1,low,high);
break;
case '8':sol[charloc] = 'T'; calc(charloc+1,low,high);
sol[charloc] = 'U'; calc(charloc+1,low,high);
sol[charloc] = 'V'; calc(charloc+1,low,high);
break;
case '9':sol[charloc] = 'W'; calc(charloc+1,low,high);
sol[charloc] = 'X'; calc(charloc+1,low,high);
sol[charloc] = 'Y'; calc(charloc+1,low,high);
break;
}
}
int main(){
FILE *in=fopen ("namenum.in", "r");
FILE *in2=fopen ("dict.txt", "r");
int j;
out=fopen ("namenum.out","w");
for (nwords = 0; fscanf (in2, "%s", &dict[nwords++]) != EOF; )
;
fscanf (in, "%s",&num);
maxlen = strlen(num);
calc (0, 0, nwords);
if (nsolutions == 0) fprintf(out,"NONE\n");
return 0;
}
Back to top