Problem of the Week
Problem E and Solution
Containers in a Row

Problem

There are \(10\) containers arranged in a row on a table. On the bottom of each container there is one of the following letters:

Each letter occurs exactly once.

Anneke has written the following algorithm to find a particular letter: Pick up the leftmost container and look on the bottom. If it’s the letter you’re looking for, put the container back down and stop. Otherwise, pick up the next container and look on the bottom. If it’s the letter you’re looking for, put the container back down, swap it with the container to its left, and stop. If it is not the letter you’re looking for, pick up the next container and repeat this until you find the letter you’re looking for.

For example, suppose the containers were in the following order:

Anneke uses her algorithm to find the letter E. She looks at the first \(6\) containers and returns each of them to the table. When she looks at the seventh container and sees that it is the E, she swaps containers E and I. So to locate the letter E, Anneke looked at \(7\) containers, and the containers would now be in the following order.

Suppose Anneke now wants to find the letter J. She looks at the G, B, and F and puts them back down. She then looks at the fourth container, sees the J, and swaps containers F and J. The containers would now be in the following order.

After searching for the E and the J, Anneke has looked at a total of \(7+4=11\) containers.

If the \(10\) containers begin in some unknown order and Anneke uses her algorithm to search for each of the ten letters exactly once, what is the maximum possible number of containers that Anneke picks up to look on the bottom?

This problem was inspired by a past Beaver Computing Challenge (BCC) problem.

Solution

If no swaps were required as a result of finding a container, how many containers would Anneke have to look at in total?

Let’s number the positions \(1\) through \(10\), starting with the leftmost position as number \(1\). At some point Anneke is looking for the container in position \(1\). She would have to look at \(1\) container to find it. At some point she is looking for the container in position \(2\). She would have to look at \(2\) containers to find it. At some point she is looking for the container in position \(3\). She would have to look at \(3\) containers to find it. This continues until at some point she is looking for the container in position \(10\). She would have to look at \(10\) containers to find it. To locate all \(10\) containers, Anneke would have to look at \(1+2+3+\cdots +10=55\) containers.

Since Anneke looks for each letter exactly once, swapping the position of one letter with the position of another letter can only have the effect of increasing the number of containers looked at for the letter on the preceding container by one. The number of containers looked at to find other letters would not be affected. Therefore, swapping can only increase the number of containers looked at (by one) for all but the first search. This means swapping can increase the number of containers looked at by at most \(9\) in total making the maximum total number of containers looked at equal to \(55+9=64\).

On the next page, an illustration of how this maximum can be achieved is shown. Is \(64\) an achievable maximum?

First we will put the containers in order, left to right, from A to J.

Now we will search for each letter in order from B to J and search for A last.

Since B is in the second position, we must look at \(2\) containers to find it. We then swap A and B.

Since C is in the third position, we must look at \(3\) containers to find it. We then swap A and C.

Since D is in the fourth position, we must look at \(4\) containers to find it. We then swap A and D.

Since E is in the fifth position, we must look at \(5\) containers to find it. We then swap A and E.

Since F is in the sixth position, we must look at \(6\) containers to find it. We then swap A and F.

Since G is in the seventh position, we must look at \(7\) containers to find it. We then swap A and G.

Since H is in the eighth position, we must look at \(8\) containers to find it. We then swap A and H.

Since I is in the ninth position, we must look at \(9\) containers to find it. We then swap A and I.

Since J is in the tenth position, we must look at \(10\) containers to find it. We then swap A and J.

Finally, since A is in the tenth position, we must look at \(10\) containers to find it. We then swap A and J (again).

We have looked at a total of \(2+3+4+5+6+7+8+9+10+10=64\) containers to find each of the letters.

Extension:

Suppose you have \(n\) containers, each with something different on them. You lay the containers out in a similar manner to how we handled the \(10\) different containers. You search for each of the different containers, one at a time. What is the maximum number of containers you must look at in order to locate all of the containers using the search described in the problem?

Connection to Computer Science:

One of the fundamental problems in computer science is how to organize data in order to search within it quickly. There are many ways to do this: using binary trees, splay trees, skip lists, sorted arrays, etc. The technique outlined in this problem is the idea of moving found items closer to the "front", with the assumption that if we search for something once, it is quite likely that the same item will be searched for again. The transpose (swap) heuristic used by Anneke in this problem is one technique for doing this. Other heuristics include move-to-front, which moves a found element to the very front of the list. Moreover, this problem highlights the process of performing worst-case analysis for an algorithm. Computer scientists care about "what is the worst possible input for this algorithm, and how long will it take to execute on that input?" In this question, we are asking about the worst-case performance of the transpose heuristic on a list of size \(10\).