AIOC Banner

Dictionary

Let's solve Dictionary.

Approach 1: Indexing with Integerlandese

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:

for (int i = 0; i < D; i++) {
	<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:

for (int i = 0; i < W; i++) {
	<Read an integer into current_word>
	if (<translation[current_word] exists>) {
		<Output translation[current_word]>
	} else {
		<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 in total.

Our current approach requires around 16GB of memory to work. This is far too much for most computers. On the training site, it's safe to expect around 50MB at most. Normally 50 megabytes is much more than we need, but right now it's not nearly enough.

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:

for (int i = 0; i < D; i++) {
	<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.

<Read an integer into current_word>
for (int j = 0; j < D; j++) {
	if (dict_1[j] == current_word) {
		<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:

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.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 17 August 2019,  8:54pm AEST