Assume you are given an n by n array of letters and a list of words (a sequence of letters). Your program should determine if any word from the list can be found in the array, and if so, what is the position of its first and last letters. A word can appear in the array horizontally, vertically, and diagonally, each in both directions (there is no wrap-around). A word can appear in the array more than once or not appear in it at all. The format of the input will contain:
5abcedgratoitboyeargotrace 3bra3cab3eat3ate3boy3rae5trace4race3rat6simple5great2go0This file represents the array:
a b c d e
g r a t o
i t b o y
e a r g o
t r a c e
and the words to find are: "bra", "cab", ..., "go". The output of your
program should contain a line for each occurrence of each word in the array.
Each line should contain the word followed by the position of its first letter
and the position of its last letter. For example, with the above file, your
output should be: bra 3 3 5 3
bra 3 3 1 1
cab 1 3 3 3
eat 1 4 3 2
ate 2 3 4 1
boy 3 3 3 5
rae 4 3 4 1
trace 5 1 5 5
race 5 2 5 5
rat 2 2 2 4
rat 5 2 3 2
go 4 4 3 4
go 4 4 4 5
First:
5abcedgratoitboyeargotrace 3bra3cab3eat3ate3boy3rae5trace4race3rat6simple5great2go0
Expected output:
bra 3 3 5 3 bra 3 3 1 1 cab 1 3 3 3 eat 1 4 3 2 ate 2 3 4 1 boy 3 3 3 5 rae 4 3 4 1 trace 5 1 5 5 race 5 2 5 5 rat 2 2 2 4 rat 5 2 3 2 go 4 4 3 4 go 4 4 4 5
Second:
21trihsyffupjsizanpuoscjracyllemsoxcdtkqkhprsulhecrlnvnhoomtnveeadinjakqtkhvacesriabnzyarixtvxvnozktltqprfykglbojvcwuiznjveacrfjnonaerbeetgiarsclnkmokmnishmcvthpyefdaczyeyscahgtirctsangromnadoomjmtignnsedndndvxuakchttrobhtciaeeckllbvpuddyyenwdapyrbweqxrozorbukwttprpabazmkkolkjccmcgpeuqodnnbrafragvbqgimltpopaiisrnntnehwjbvfitdjbyeacrtwsiooizdvwxcdtuatrnnxsekrsbbzfhvukxmdsbsnneaxgqigafcbffenaqvperzmbegaknirhswmyekardehteelainebenesrsxkramerm 7maestro12yadayadayada8soupnazi5cosmo11elainebenes8costanza6kramer12aboutnothing5frank6george6newman14crazyjoedavola8uncleleo9smellycar10juniormint8thedrake10puffyshirt7thebris12poppiespizza6mickey9shrinkage8bigsalad5bania13jonvoightscar6mrpitt5puddy12steinbrenner9jpeterman0
Expected output:
maestro 19 20 13 20 yadayadayada 8 13 19 13 soupnazi 1 20 1 13 cosmo 11 2 7 2 elainebenes 21 1 21 11 costanza 2 13 9 20 kramer 21 15 21 20 aboutnothing 17 13 6 2 frank 6 20 2 16 george 15 1 20 1 newman 10 14 15 19 crazyjoedavola 1 21 14 21 uncleleo 10 20 3 13 smellycar 2 10 2 2 juniormint 2 1 11 10 thedrake 20 20 20 13 puffyshirt 1 10 1 1 thebris 9 7 3 1 poppiespizza 15 12 4 12 mickey 15 7 20 12 shrinkage 20 9 20 1 bigsalad 11 8 4 1 bania 12 15 16 15 jonvoightscar 1 11 13 11 mrpitt 7 20 2 15 puddy 12 1 12 5 steinbrenner 18 14 7 14 jpeterman 16 11 8 3
The first snag with this problem was the typo: the example input file begins
5abced but the first row of the array is a b c d e. I
don't remember whether this was Leila's mistake or I introduced it myself while
preparing the questions. Anyway, someone noticed the mistake and the judges said
that it was a simple typo.
Then we noticed that solutions included eat 1 4 3 2 although
"eat" does not appear in the array and we wondered whether programs were just
writing the expected output for the given sample, because "eat" does not occur
in the array as given in the problem statement, but it does occur in the
expected output. Fortunately, we realized quite quickly that "eat" does appear
in the actual array derived from the input data.
The second snag was the realization that my intepretation of "strings of reasonable length" and the teams' intepretation might be different. Also, I told the invigilators to make the announcement that the words to be found had fewer than ten letters -- which is not true for the second data set! Consequently, we could not fairly use the second test data set and we were stuck with the first data set -- which is exactly the same as that given in the problem! We therefore took the risk that the programs we were testing did not consist simply of a print statement to output the given results.
The problem is straightforward but tedious. The essential difficulty seemed
to me to be minimizing the code required to search in eight different
directions. I solved this by writing a function look() that matches
a word without actually knowing which direction it is searching in -- this
information is supplied by dr and dc.
look() is called eight times from each position in the letter
array.
A smaller difficulty is reading the embedded numbers in the strings. I wrote
another function, getnum(), to handle this.
#include <iostream.h>
#include <fstream.h>
#include <strstrea.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
const char EOS = '\0';
ifstream in;
ofstream out;
int getnum()
{
int n = 0;
char c;
while (1)
{
in >> c;
if (!in || !isdigit(c))
{
in.putback(c);
return n;
}
n = 10 * n + c - '0';
}
}
char a[100][100];
int size;
void look(char *w, int r, int c, int dr, int dc)
{
int nr = r;
int nc = c;
char *nw = w;
while (true)
{
nw++;
if (*nw == EOS)
break;
nr += dr;
nc += dc;
if (nr < 0 || nr == size || nc < 0 || nc == size || *nw != a[nr][nc])
return;
}
out << w << ' ' << r << ' ' << c << ' ' << nr << ' ' << nc << endl;
}
void main(int argc, char *argv[])
{
in.open(argv[1]);
out.open(argv[2]);
size = getnum();
int r, c;
for (r = 0; r < size; r++)
for (c = 0; c < size; c++)
in >> a[r][c];
char wds[100][50];
int nw = 0;
while(true)
{
int len = getnum();
if (len == 0)
break;
for (int i = 0; i < len; i++)
{
char c;
in >> c;
wds[nw][i] = c;
}
wds[nw][len] = EOS;
nw++;
}
in.close();
for (int w = 0; w < nw; w++)
{
for (r = 0; r < size; r++)
for (c = 0; c < size; c++)
if (wds[w][0] == a[r][c])
{
look(wds[w], r, c, -1, -1);
look(wds[w], r, c, -1, 0);
look(wds[w], r, c, -1, 1);
look(wds[w], r, c, 0, -1);
look(wds[w], r, c, 0, 1);
look(wds[w], r, c, 1, -1);
look(wds[w], r, c, 1, 0);
look(wds[w], r, c, 1, 1);
}
}
out.close();
}