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

Problem

There are \(10\) rubber ducks arranged in a row on a desk. On the bottom of each duck there is one of the following letters: A, B, C, D, E, F, G, H, I, or J. Each letter occurs exactly once.

Amina has written the following algorithm to find a particular letter.

Pick up the leftmost duck and look on the bottom. If it’s the letter you’re looking for, put the duck back down and stop. Otherwise pick up the next duck and look on the bottom. If it’s the letter you’re looking for, put the duck back down, swap it with the duck to its left, and stop. Repeat this until you find the letter you’re looking for.

For example, suppose the ducks were in the following order.

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

Suppose Amina 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 duck, sees the J, and swaps ducks F and J. The ducks would now be in the following order.

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

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

Solution

If no swaps were required as a result of finding a duck, how many ducks would Amina 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 Amina is looking for the duck in position \(1\). She would have to look at \(1\) duck to find it. At some point she is looking for the duck in position \(2\). She would have to look at \(2\) ducks to find it. At some point she is looking for the duck in position \(3\). She would have to look at \(3\) ducks to find it. This continues until at some point she is looking for the duck in position \(10\). She would have to look at \(10\) ducks to find it. To locate all \(10\) ducks, Amina would have to look at \(1+2+3+\cdots +10=55\) ducks.

Since Amina 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 ducks looked at for the letter on the preceding duck by one. The number of ducks looked at to find other letters would not be affected. Therefore, swapping can only increase the number of ducks looked at (by one) for all but the first search. This means swapping can increase the number of ducks looked at by at most \(9\) in total making the maximum total number of ducks looked at equal to \(55+9=64\).

What follows is an illustration of how this maximum can be achieved.

Is \(64\) an achievable maximum?

First we will put the ducks 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\) ducks to find it. We then swap A and B.

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

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

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

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

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

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

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

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

Finally, since A is in the tenth position, we must look at \(10\) ducks 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\) ducks to find each of the letters.

Finally, we look at a possible extension and a connection to Computer Science.

Extension:

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

Connection to Computer Science:

This problem was inspired by a problem from the Beaver Computer Challenge in 2012. You can see the problem and others like it at http://www.cemc.uwaterloo.ca/contests/bcc.html.

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 Amina 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\).