Match Editorial

It is safe to say that few TopCoder members suffer from fear of math, but the results of the latest Single Round Match suggest that fear of text is epidemic. Both divisions were caught off guard by a set of problems in which parsing did not act as an obstacle to performing a task, as it usually does, but constituted the task itself. Jan_Kuipers, gawry, and lars topped the leader board in Division One. Special mention goes to skanthak and bmerry, who made a game effort to solve the hard problem and fell just short on a day when no one in either division got the hard. Division Two saw a victory by ggoprea, followed by the harmoniously named runners-up wizy and quazee.

The Problems

Value	250
Submission Rate	214 / 232 (92.24%)
Success Rate	195 / 214 (91.12%)
High Score	anomaly for 246.66 points (3 mins 19 secs)
Average Score	210.38 (for 195 correct submissions)

We are asked to replace the special characters '_' and '*' in a piece of text with the HTML tags for italics and boldface, respectively. The principal difficulty is in deciding whether to use the opening tag, "<i>" or "<b>", or rather the closing tag, "</i>" or "</b>", whenever we come across a special character. In my C implementation, I have a variable called open whose value I set to 1 when I print an opening tag, and to 0 when I print a closing tag. Its value therefore tells me what I need to do at the next occurrence of a special character. I initialize it to 0, since I certainly haven't printed any opening tags at the outset.

void expand(char *s) {
  int i, open = 0;
  for (i = 0; s[i] != '\0'; i++)
    if (s[i] == '_' || s[i] == '*') {
      if (open)
        printf("</%c>", s[i] == '_' ? 'i' : 'b');
      else
        printf("<%c>", s[i] == '_' ? 'i' : 'b');
      open = (open+1)%2;
    }
    else
      printf("%c", s[i]);
  printf("\n");
}

The % symbol I use above is the modulo operator in C and many other languages. For integers N and D, the operation N%D returns the remainder of the division N/D. Thus, N%2 can only return 0 or 1.

Value	500
Submission Rate	90 / 232 (38.79%)
Success Rate	63 / 90 (70.00%)
High Score	quazee for 391.97 points (15 mins 51 secs)
Average Score	234.04 (for 63 correct submissions)

Value	250
Submission Rate	156 / 181 (86.19%)
Success Rate	134 / 156 (85.90%)
High Score	m00tz for 231.36 points (8 mins 11 secs)
Average Score	150.78 (for 134 correct submissions)

Given a dictionary of syllabized words such as "squir rel" and "el e phant", we are to verify and if necessary correct a hyphenated word such as "eleph-ant". Among the five problems of the match, I would say that this one requires the most effort for the least reward. Rather than algorithmic prowess, it is swift fingers and attention to detail that lead to success here.

In my C implementation, I first make a copy cand of the candidate string, omitting the hyphen. At the same time, I identify the hyphen's position hx.

void hyphenate(char **dictionary, int dnum, char **candidates, int cnum) {
  char cand[100], good[100], *dict;
  int ci, di, cx, hx, hh, bx;
  for (ci = 0; ci < cnum; ci++) {
    for (cx = 0, hx = -1; candidates[ci][cx] != '\0'; cx++)
      if (candidates[ci][cx] == '-')
        hx = cx;
      else
        cand[cx - (hx == -1 ? 0 : 1)] = candidates[ci][cx];
    cand[cx - (hx == -1 ? 0 : 1)] = '\0'; 

For each item dict in the dictionary, I first consider whether it is the same as cand. If so, the word must be monosyllabic.

    for (di = 0; di < dnum; di++) {
      dict = dictionary[di];
      if (!strcmp(cand, dict)) {
        printf("%s\n", cand);
        break;
      }

Otherwise, I step through cand and dict using the index variable cx. By initializing a hyphen counter hh to 0 and incrementing it on each hyphen, I know that the character at position cx of cand aligns with the character at position cx+hh of dict. At the same time, I keep track of the closest position bx of a dictionary hyphen to that of the candidate's hyphen. In the event of a mismatch between an aligned pair of characters, I reject the current dictionary item.

      bx = -100;
      for (cx = hh = 0; cand[cx] != '\0' && dict[cx+hh] != '\0'; cx++) {
        if (dict[cx+hh] == ' ') {
          if (abs(cx-hx) < abs(bx-hx))
            bx = cx;
          hh++;
        }
        if (cand[cx] != dict[cx+hh])
          break;
      }
      if (bx == -100 || cand[cx] != '\0' || dict[cx+hh] != '\0')
        continue;

If all non-space, non-hyphen characters match, I have the right dictionary item. Now, unless the best dict hyphen coincides with the cand hyphen, I print the candidate string in two parts with a hyphen in between.

      if (bx == hx) {
        printf("correct\n");
        break;
      }
      strncpy(good, cand, bx);
      good[bx] = '-';
      strcpy(&good[bx+1], &cand[bx]);
      printf("%s\n", good);
      break;
    }
  }
}

It is not difficult to verify hyphens, but mathematically inclined coders must recoil from this problem because it cannot be generalized or solved systematically. I think it resembles the tasks that professional software developers undertake regularly rather than the puzzles that attract academic researchers.

Value	1000
Submission Rate	5 / 232 (2.16%)
Success Rate	0 / 5 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Given a query consisting of words separated by ellipses, such as "fourscore...years...ago", we are to find text passages that contain every query word order. If we wanted to perform this task at high speed, we would build a data structure that maps words to their positions in a document—in other words, an index—and look for sequences of word-position numbers. But we can get by with a solution that searches directly on the text, since each document is only 50 characters long. At worst, we would begin searching at each of the 50 characters and continue to the end of the document, for a total of about 50*50/2 = 1250 character comparisons. My solution starts matching only at the beginning of each word in the document, so I need no more than half that many comparisons.

The most important part of my C implementation is a function that takes a query pat, the pi-th character of which I am currently comparing to the si-th character of a string str. If I simultaneously reach the end of both the code and the pattern, I have found a match which I mark in the array ends. It is possible that several recursive calls to match() will mark the same location in the array, since I make branching calls and I make no effort to remember whether I have compared particular pairs of characters before.

The branching occurs when I come across a period character in the pattern, denoting the start of an ellipsis. I can now skip the next word in the string and make a recursive call to the matching function.

void match(char *pat, int pi, char *str, int si, int *ends) {
  int skip;
  if (pat[pi] == '.') {
    while (!isalpha(str[++si]) && str[si] != '\0');
    if (str[si] == '\0')
      return;
    skip = si;
    while (isalpha(str[++skip]));
    match(pat, pi, str, skip, ends);
    pi += 3;
  }

On the other hand, I also try to match the current word in the string. The matching attempt has three possible outcomes: it fails in the event of different alphabetic characters in the string and pattern; succeeds if I reach the end of each; or continues with a recursive call if I reach a period in the pattern and a non-alphabetic character in the string.

  while (tolower(pat[pi]) == tolower(str[si]) && isalpha(str[si])) {
    pi++;
    si++;
  }
  if (pat[pi] == '\0' && !isalpha(str[si])) {
    ends[si] = 1;
  }
  else if (pat[pi] == '.' && !isalpha(str[si]) && str[si] != '\0') {
    match(pat, pi, str, si, ends);
  }
}

After match() has found all matching passages that begin from some point in a document, I shall record their endpoints in a two-dimensional array which I eventually sort to find the best passages over all documents. Each element of this array contains three integers denoting the starting position of the match, its ending position, and the number of the document in which it is found. Below is a comparison function written in the style demanded by the C standard library's qsort(). It returns a negative value if passage a comes earlier than b, or a positive value if the opposite is true. A zero value would result if the passages were identical in every respect, but this will never happen in my program.

int cmp(const void *a, const void *b) {
  int *sa = *((int **) a), *sb = *((int **) b);
  int da = sa[1] - sa[0], db = sb[1] - sb[0];
  if (da != db)
    return da - db;
  if (sa[2] != sb[2])
    return sa[2] - sb[2];
  return sa[0] - sb[0];
}

A quick calculation on the back of an envelope tells me that I won't find more than 20000 passages among all documents. There are roughly 25 possible points at which a passage may begin or end in any document, making a total of about 50*25*25/2=15625 passages over all documents.

void sequence_search(char **docs, int doc_num, char *query) {
  int *ends = calloc(100, sizeof(int)), i, ix, beg, p, q;
  int dlen, flag = 0, **passages = calloc(20000, sizeof(int *)), pnum = 0;
  char *doc, buf[100];
  for (i = 0; i < 20000; i++)
    passages[i] = calloc(3, sizeof(int)); 

I traverse each document, updating the flag variable to tell me whether I am in the middle of a word. At the start of each word, I initialize the ends array, launch a match() operation, and augment the passages array based on the marks left in ends.

  for (i = 0; i < doc_num; i++) {
    dlen = strlen(doc = docs[i]);
    for (beg = 0; doc[beg] != '\0'; beg++)
      if (isalpha(doc[beg]) && !flag) {
        memset(&ends[beg+1], 0, (dlen-beg)*sizeof(int));
        match(query, 0, doc, beg, ends);
        for (ix = beg+1; ix <= dlen; ix++)
          if (ends[ix]) {
            passages[pnum][0] = beg;
            passages[pnum][1] = ix;
            passages[pnum++][2] = i;
          }
        flag = 1;
      }
      else if (!isalpha(doc[beg]))
        flag = 0;
  }

Finally, I can sort the passages using my comparison function.

  qsort(passages, pnum, sizeof(int *), cmp);
  for (i = 0; i < (pnum < 5 ? pnum : 5); i++) {
    p = passages[i][0];
    q = passages[i][1];
    strncpy(buf, &docs[passages[i][2]][p], q-p);
    buf[q-p] = '\0';
    printf("%d %d [%s]\n", passages[i][2], p, buf);
  }
}

If you are interested in the notion of building an index for each document, see my solution to the proximity-search problem below.

Value	600
Submission Rate	33 / 181 (18.23%)
Success Rate	21 / 33 (63.64%)
High Score	gawry for 384.63 points (24 mins 20 secs)
Average Score	295.10 (for 21 correct submissions)

Given a pair of syntactically correct HTML documents, we are to compare their tag trees and determine whether one is an intree of the other, meaning that the latter contains every path of the former descending in order from the root. HTML documents can be parsed painlessly if we think of them as parenthesized expressions. Each opening tag is comparable to a left parenthesis, and each closing tag is like a right parenthesis. When building a tag tree, we use the name of each tag as a node label, discarding all other text.

Because I know from the input constraints that a node will not have more than 1000 children, my C implementation has a fixed-size child array in each node.

struct Tree {
  char label[100];
  struct Tree *children[1000];
  int child_num;
};

Some people like to push left parentheses or opening tags onto a stack, then pop them at a right parenthesis or closing tag. My preferred approach is to write a function that makes a recursive call at an opening tag and returns at a closing tag. The following function takes a string position ix and advances it to the end of the next closing tag, then returns the updated position.

int parse(struct Tree *tree, char *str, int ix) {
  int jx;
  struct Tree *child;
  while (1) {
    while (str[ix++] != '<');
    if (str[ix] == '/') {
      while (str[ix++] != '>');
      return ix;
    }
    child = calloc(1, sizeof(struct Tree));
    jx = 0;
    while (str[ix++] != '>')
      child->label[jx++] = str[ix-1];
    child->label[jx] = '\0';
    ix = parse(tree->children[tree->child_num++] = child, str, ix);
  }
}

To find out whether one tree is an intree of another, I use a recursive function to compare the children of each. In the function below, aix is the number of the child I am currently considering in atree, while bix is the same for btree. The final if statement originally read

  if (intree(atree->children[aix], 0, btree->children[bix], 0)
      && intree(atree, aix+1, btree, bix+1))
    return 1;

int intree(struct Tree *atree, int aix, struct Tree *btree, int bix) {
  if (aix == 0 && bix == 0 && strcmp(atree->label, btree->label))
    return 0;
  if (aix == atree->child_num)
    return 1;
  if (bix == btree->child_num)
    return 0;
  if (intree(atree->children[aix], 0, btree->children[bix], 0))
    return intree(atree, aix+1, btree, bix+1);
  return intree(atree, aix, btree, bix+1); 
} 

A fancy intree() function would count the number of identical nodes at the same time that it verified the intree relationship, but I like to keep my code simple by delegating the node count to a separate recursion.

int count(struct Tree *tree) {
  int ct = 1, i;
  for (i = 0; i < tree->child_num; i++)
    ct += count(tree->children[i]);
  return ct;
}

To start the whole process off, I make a preliminary "html" node and advance a pointer in each document to the end of the first opening tag, which is guaranteed to be of "html" type.

void compare(char *docA, char *docB) {
  struct Tree *treeA = calloc(1, sizeof(struct Tree));
  struct Tree *treeB = calloc(1, sizeof(struct Tree));
  int ix = 0, AinB, BinA;
  sprintf(treeA->label, "html");
  while (docA[ix++] != '>');
  parse(treeA, docA, ix);
  sprintf(treeB->label, "html");
  while (docB[ix++] != '>');
  parse(treeB, docB, ix);
  AinB = intree(treeA, 0, treeB, 0);
  BinA = intree(treeB, 0, treeA, 0);
  if (AinB && BinA)
    printf("equivalent\n");
  else if (!AinB && BinA)
    printf("incompatible\n");
  else if (AinB)
    printf("intree %d\n", count(treeB)-count(treeA));
  else
    printf("outtree %d\n", count(treeA)-count(treeB)); 
} 

If the trees are neither equivalent nor incompatible, I subtract their node counts in the appropriate order to find out how many nodes they have in common.

Value	1000
Submission Rate	2 / 181 (1.10%)
Success Rate	0 / 2 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Given a query expressing proximity relationships between pairs of passages, we are to find the shortest and earliest matches in a collection of documents. Although we have only 50 documents, each of which accommodates fewer than 400 passages, the structure of the search query may entail several pairwise comparisons between sets of matching passages in each document. A textual index is in order if we want to perform the comparisons at high speed.

Most languages offer a hashing facility that works as a ready-made data structure for mapping words to word positions, but I wrote my solution in C without resorting to any high-level functions. I implemented my index using a trie, which is just another name for a maximal DFA. Words are easily inserted into or retrieved from a trie by recursive descent. Each node stores the starting indices of the word that terminates at that node.

struct Index {
  struct Index *next[128];
  int count, pos[100];
};

void put(struct Index *index, char *s, int pos, int ix, int end) {
  int ci = (int) tolower(s[ix]);
  if (ix == end) {
    index->pos[index->count++] = pos;
    return;
  }
  if (index->next[ci] == NULL)
    index->next[ci] = calloc(1, sizeof(struct Index));
  put(index->next[ci], s, pos, ix+1, end); }

struct Index *get(struct Index *index, char *s, int ix, int end) {
  int ci = (int) tolower(s[ix]);
  if (ix < end && index->next[ci] == NULL)
    return NULL;
  return ((ix == end) ? index : get(index->next[ci], s, ix+1, end)); 
} 

To build an index for a certain document, I scan its text and put each maximal sequence of alphabetic characters into the trie along with its word number. At the same time, I store the character indices of each word in the array spans, letting me subsequently extract document substrings based on word numbers.

struct Index *make_index(char *text, int **spans) {
  int ix = 0, begin = -1, pos = 0;
  struct Index *index = calloc(1, sizeof(struct Index));
  do {
    if (isalpha(text[ix]) && begin == -1)
      begin = ix;
    else if (!isalpha(text[ix]) && begin != -1) {
      spans[pos][0] = begin;
      spans[pos][1] = ix;
      put(index, text, pos++, begin, ix);
      begin = -1;
    }
  } while (text[ix++] != '\0');
  return index;
}

To parse a query, I take advantage of the fact that the outermost '+' operator must be surrounded by balanced parenthetical expressions. Once I have found the position of this '+', I can split the query in two and continue parsing recursively.

struct Parse {
  char word[100];
  struct Parse *left, *right;
  int distance;
};

struct Parse *make_parse(char *s, int begin, int end) {
  int ix = begin, bix = 0, depth = 0;
  char buf[1000];
  struct Parse *parse = calloc(1, sizeof(struct Parse));
  if (s[begin] == '(') {
    while (s[++ix] != '+' || depth > 0) {
      depth += s[ix] == '(' ? 1 : 0;
      depth -= s[ix] == ')' ? 1 : 0;
    }
    parse->left = make_parse(s, begin+1, ix-1);
    while (s[++ix] != ' ')
      buf[bix++] = s[ix];
    buf[bix] = '\0';
    parse->right = make_parse(s, ix+1, end-1);
    parse->distance = atoi(buf);
    return parse;
  }
  strncpy(parse->word, &s[begin], end-begin);
  parse->word[end-begin] = '\0';
  return parse;
}

When I'm looking for passages matching a query, the base case is that the query consists of a single word. I can then reach into the index to retrieve a list of word positions, if any.

int add_passages(int **passages, int pnum, int docid,
    struct Index *index, struct Parse *parse) {
  int i, j, *used = calloc(700, sizeof(int)), pnum1, pnum2;
  int a, b, c, d, distance, x, y;
  if (parse->word[0] != '\0') {
    index = get(index, parse->word, 0, strlen(parse->word));
    if (index == NULL)
      return pnum;
    for (i = index->count-1; i >= 0; i--) {
      passages[pnum][0] = passages[pnum][1] = index->pos[i];
      passages[pnum++][2] = docid;
    }
    return pnum;
  }

Otherwise, I call my passage-retrieval function recursively for the left and right branches of the parse tree. I compute pairwise intersections of the passages in each set, saving the resulting passages that are within the specified range. The used array serves to mark passages as I find them, since duplicate intersections may easily occur.

  distance = parse->distance;
  pnum1 = add_passages(passages, pnum+400, docid, index, parse->left);
  pnum2 = add_passages(passages, pnum1, docid, index, parse->right);
  for (i = pnum+400; i < pnum1; i++)
    for (j = pnum1; j < pnum2; j++) {
      x = passages[i][0] < passages[j][0] ? i : j;
      y = passages[i][0] < passages[j][0] ? j : i;
      a = passages[x][0];
      b = passages[x][1];
      c = passages[y][0];
      d = passages[y][1];
      if ((c < b || c-b <= distance+1) && !used[25*a+(b<d?d:b)]) {
        passages[pnum][0] = a;
        passages[pnum][1] = b < d ? d : b;
        passages[pnum++][2] = docid;
        used[25*a+(b<d?d:b)] = 1;
      }
    }
  free(used);
  return pnum;
}

Each element of passages is a three-dimensional integer array containing the start position, end position, and document number of the words in a passage. To compare these according to the problem specification and in a manner compatible with the qsort function, I define a comparison function thus.

int cmp(const void *a, const void *b) {
  int *sa = *((int **) a), *sb = *((int **) b);
  int da = sa[1] - sa[0], db = sb[1] - sb[0];
  if (da != db)
    return da - db;
  if (sa[2] != sb[2])
    return sa[2] - sb[2];
  return sa[0]-sb[0];
}

Preliminary to the search proper, I allocate space for the passages and characters spans, then parse the query.

void proximity_search(char **docs, char *query) {
  struct Index *index;
  struct Parse *parse;
  int i, j, **passages = calloc(20000, sizeof(int *)), pnum = 0;
  int ***spans = calloc(50, sizeof(int **)), p, q, a, b, docid;
  char buf[1000];
  for (i = 0; i < 20000; i++)
    passages[i] = calloc(3, sizeof(int));
  for (i = 0; i < 50; i++) {
    spans[i] = calloc(25, sizeof(int *));
    for (j = 0; j < 25; j++)
      spans[i][j] = calloc(2, sizeof(int));
  }
  parse = make_parse(query, 0, strlen(query)); 

For each document, I make an index and call my passage-retrieval function, which returns the number of passages found thus far. Finally, I sort the passages and cull the top ten.

  for (i = 0; i < 50; i++) {
    index = make_index(docs[i], spans[i]);
    pnum = add_passages(passages, pnum, i, index, parse);
  }
  qsort(passages, pnum, sizeof(int *), cmp);
  for (i = 0; j < (pnum < 10 ? pnum : 10); i++) {
    a = passages[i][0];
    b = passages[i][1];
    docid = passages[i][2];
    p = spans[docid][a][0];
    q = spans[docid][b][1];
    strncpy(buf, &docs[docid][p], q-p);
    buf[q-p] = '\0';
    printf("%d %d [%s]\n", docid, p, buf);
  }
}

The solution to this problem consists of three parts: building an index, parsing the query, and finding passage intersections. I do not find any one of these parts to be very dull or very difficult, but it appears from the match results that it would have been wiser to assign them as separate problems rather than rolling all three into one.