# What's the most efficient algorithm to determine the relative ordering of an unknown set of values?

This comes from a question on Arqade.

The background is, there's a mall level. Vlad the organized crime boss wants $50,000 worth of mall property destroyed. Your task is to shoot and blow stuff up until that happens. There are 12 stores in the mall, and you have 3 grenades. After you blow up the first three stores, if you haven't ruined$50,000 worth of stuff in three explosions, you switch to your rifle and shatter store windows until you reach that limit. Then you leave.

Good wholesome fun.

The absolute value of the stores is unknown, but I'm interested in determining the relative value - obviously, I want to use my three grenades where they'll do the most good. As I see it, I have a set of 12 unknown variables, representing the value of each of the individual stores:

${O,P,Q,R,S,T,U,V,W,X,Y,Z}$

and one constant $C$, representing the value of windows.

I know which three stores I've destroyed and I can count how many windows I need to shoot to give me a Mission Accomplished.

Knowing only those two pieces of information, it should be possible through experimentation to order the unknown set. Let's say on trial #1 I destroy stores X,Y,Z and it takes me 4 windows to reach $50k. On trial #2, I destroy stores W,Y,Z and it takes 3 windows. If$X + Y + Z + 4C = W + Y + Z + 3C$, then we can say that$W > X$. What's the most efficient way to run this algorithm to conclusion for all 12 stores? Each trial takes about 6 minutes and I don't want to duplicate effort. - ## 1 Answer Here's a good mathematical solution: Run 12 trials, starting with$O+P+Q$, then$P+Q+R$, then$Q+R+S\$, etc., and for each one record the number of windows as a negative integer. For example, \begin{align}O+P+Q&=-w_1\\ P+Q+R&=-w_2\\ Q+R+S&=-w_3\\ \vdots\\ X+Y+Z&=-w_{10}\\ Y+Z+O&=-w_{11}\\ Z+O+P&=-w_{12}\end{align}

This gives you an almost-tridiagonal matrix problem: $$\left[\begin{array}{cccccccccccc}1&1&1&0&0&0&0&0&0&0&0&0\\ 0&1&1&1&0&0&0&0&0&0&0&0\\ 0&0&1&1&1&0&0&0&0&0&0&0\\ &&&\ddots&\ddots&\ddots&\\ 0&0&0&0&0&0&0&0&0&1&1&1\\ 1&0&0&0&0&0&0&0&0&0&1&1\\ 1&1&0&0&0&0&0&0&0&0&0&1\\ \end{array}\right]\left[\begin{array}{c}O\\P\\Q\\R\\S\\T\\U\\V\\W\\X\\Y\\Z\end{array}\right]=\left[\begin{array}{c}-w_1\\-w_2\\-w_3\\\vdots\\-w_{10}\\-w_{11}\\-w_{12}\end{array}\right],$$ which you can either use your favorite package to solve, or calculate the actual inverse ahead of time if you'll be doing this a lot of times.

This will give you negative values for each store, and the largest (i.e., least negative) ones are the highest values.

I think it's not possible to know all the stores' values in fewer than 12 tests. It may be possible to determine the 3 largest values in fewer than 12 tests, but I don't have such an algorithm handy.

-