Santa Claus and his elves are gearing up for another holiday season, busy filling orders and wrapping gifts for all of the good little boys and girls. Since snowglobes are popular gifts this year, Santa Claus has dedicated an entire department to build and wrap the 32,768 snowglobe orders that came across his desk. After several long days and nights, Santa and the elves have finished wrapping each snowglobe in preparation to be loaded onto Santa's sleigh.

However, just before loading all 32,768 boxes of snowglobes into Santa's sleigh, one of the elves realizes her wedding ring accidentally fell into one of the boxes that she was wrapping. The question is..."Which one?" The problem is the boxes are indistinguishable from each other and have been shuffled around so much, there's no way to narrow down which box, or even which group of boxes, is more likely to contain the missing ring.

One of the elves suggests opening all of the boxes to find the ring. That would take too much time, another elf points out. "We've only got a couple of days until Christmas Eve... there's no way we can re-wrap the snowglobe boxes in time."

Another elf, realizing they have two industrial-sized scales on hand, recommends weighing each package, two at a time, to find the package weighing the most. Each snowglobe box weighs exactly 3 pounds. Whichever package weighs more than 3 pounds, the elf reasons, must contain the missing ring. However, it will still take a considerable amount of time to weigh two boxes at a time, potentially as many as 16,384 different times.

A third elf chimes in and says, "Why not weigh half of the 32,768 boxes on the first scale and half on the second scale? We'll be able to see which scale weighs more, thus we'll be able to narrow the box containing the ring down to 16,384 boxes. Then, we'll split the 16,384 boxes in half and weigh 8,192 on one scale , and 8,192 on the other. We'll continue in a similar fashion until we're down to only two boxes. Then we'll be able to easily determine which box contains the ring. It turns out we'll only need to do this 15 times, since 2^15 = 32,768." The elves agree this process is more efficient and conclude it will allow them to locate the box containing the missing ring before Santa begins his journey.

How can PROC IML help solve the missing ring problem?

First, create a 32,768 x 2 matrix containing a unique box number and a gift weight of 3 pounds for each of the 32,768 boxes.

proc iml;
 
boxes=32768;
 
col={"Box #" "Gift Wt"};
n=t(1:boxes); 
w=j(boxes,1,3); /*Assigning a gift weight of 3 pounds to all boxes*/
x=n||w;

Generate a random number from 1 to 32,768 and assign it to the randomized row with a weight of 3.25. Using the uniform distribution, each box has an equal likelihood of containing the missing ring. Since all other boxes weigh exactly 3 pounds, knowing the exact weight of the ring isn't necessary. Any value above 3 will work.

call streaminit(1234);
u=round((rand("Uniform")*boxes),1);
x[u,2]=3.25;

Begin placing an equal number of boxes on each scale, weighing each half separately, and keeping the half whose combined weight exceeds the other half. By repeating this process 15 times, the value of w, the elves will be able to determine which box contains the missing ring.

w=log(boxes)/log(2); 
   do i=1 to w;
 
	box=2**(w-i+1);
 
	a=x[1:(box/2),1:2];
	b=x[(box/2)+1:box,1:2];
 
	sumwta=a[+,2];
	sumwtb=b[+,2];
 
	if sumwta > sumwtb then x=a; else a=a;
	if sumwtb > sumwta then x=b; else b=b;
 
	if i=w then do;
	  print x[colname=col];
	end;
   end;

You can check the value of u to verify the process works.

print u[colname=col];
quit;

For more fun problems (and solutions) with PROC IML, follow the Do Loop blog and the IML Support Community.