Dictionary

Approach 1: Indexing with Integerlandese (C++)

We can see similarities between this problem and the previous one - even the way the data is presented is similar. So we might try to solve this problem in a similar way.

Assume for now that all our Integerlandese words (the ones we're translating from) are non-negative. Then we can have an array which lets us directly look up the Wholenumberlandese counterpart to an Integerlandese word. For example, if the number 2 translates to 71, we might set translation[2] = 71;.

Our code to read in the first half of the input might then look like this:

• C++

for (int i = 0; i < D; i++) {
    // TODO: Read a pair of integers into val_1 and val_2
    translation[val_1] = val_2;
}

After this, our code to perform the translations would be nearly the same as for Encyclopædia:

• C++

for (int i = 0; i < W; i++) {
    // TODO: Read an integer into current_word
    if (...) { // TODO: Check if translation[current_word] exists
        // TODO: Output translation[current_word]
    } else {
        // TODO: Output "C?"
    }
}

This is certainly a correct approach. However there are a few issues we need to consider. How do we decide if a translation exists? How do we translate negative numbers? How much space do we require to implement this solution?

This last point causes us problems. Looking at the problem statement, the possible range of input values goes from -2,000,000,000 to 2,000,000,000: that's roughly 4 billion slots we need in our array. An int in C requires 4 bytes of space, so that comes to 4 x 4 billion = 16 billion bytes, or 16GB in total.

Our current approach requires around 16GB of memory to work. This is far too much for most computers.

Instead of trying to tweak this algorithm (which would be a slow and painful process), let's turn our attention to another approach, one that requires less memory.

Approach 2: Searching for answers

Let's simplify our input handling code by just reading in the dictionary entries into two parallel arrays, like this:

• C++

for (int i = 0; i < D; i++) {
    // TODO: Read a pair of integers into dict_1[i] and dict_2[i]
}

This uses less memory - we only need to store a thousand values in each array in the worse case. But now it's not so obvious how we are going to answer the queries.

How would we solve this problem without a computer? If you were given a dictionary like the one in the input and asked, "What does 55 translate to?", there is a fairly obvious approach you might take. You could look down all of the entries on the left-hand (Integerlandese) side of the dictionary, and see if any of those numbers were 55.

The following code uses the above idea to search the dict_1[] array for a given value.

• C++

// TODO: Read an integer into current_word
for (int j = 0; j < D; j++) {
    if (dict_1[j] == current_word) {
        // TODO: Output dict_2[j]
    }
}

Convince yourself that this code works. It tries every entry in the dictionary, and compares the corresponding value to our target value. Once it finds the value we're after, it prints out the translation.

What if there isn't a translation? Right now, our program doesn't print anything out if if doesn't find a match. But the problem statement requires us to print out the string "C?". We need some way of telling whether we have found an answer.

Here are two possible approaches:

• Use a variable to keep track of whether we've found the answer. For example, we could have some variable, found, which is set to 0 while we haven't found an answer and set to 1 once we have.

  • C++

  // TODO: Read an integer into current_word
  int found = 0;
  for (int j = 0; j < D; j++) {
      if (dict_1[j] == current_word) {
          // TODO: Output dict_2[j]
          found = 1;
      }
  }
  if (!found) {
      // TODO: Output "C?"
  }

  (The (!found) acts like a (found == 0). If you prefer you can write that instead.)

• Manipulating the loop flow. Using an appropriately placed break statement, we can make the program exit the loop as soon it has found the answer. If it makes it all the way through D iterations of the loop, then that means it's checked the entire dictionary to no avail.

  • C++

  // TODO: Read an integer into current_word
  for (int j = 0; j < D; j++) {
      if (dict_1[j] == current_word) {
          // TODO: Output dict_2[j]
          break;
      }
      if (j == D-1) {
          // We've searched the whole list
          // TODO: Output "C?"
      }
  }

Of these two options, I'd recommend the first. Using an appropriate variable name, it's a lot easier to tell what's going on with the first method. Also, in more complicated situations where we introduce other break and continue statements into the loop, the second method may not work the way we expect it to.

All we need to do now is to place our list-searching code into another loop so that it handles all W translations. We then have a working solution for Dictionary.