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. **

## 4 Comments

Perhaps an over-literal response, but could you not do this in thirds: split the pile into three, if the two weighed portions are an integer number of boxes then the ring is in the unweighed portion, otherwise we know which of the weighed portions it is in, we can then split this in three, and then repeat, ..., working by thirds should only take ten goes (3 ** 10 = 59,049).

I'm not sure if the elves would manage the additional logistic complexity of three piles, although it would mean that globes could be released for delivery more quickly, since we eliminate two-thirds of the remainder at each iteration.

There are a number of different ways to tackle this problem. The solution I gave comes from a series of divide and conquer algorithms. As long as the box count is a power of the number of scales, the program can be generalized to a number of different scenarios.

Smart elves and fun program! However, by using the ROUND function, there is a small probability of getting u=0. Have the elves use the CEIL function instead, and point them to the article "How to generate random numbers in SAS" if they have any questions.

What would the elves do if the number of boxes is not a power of 2?

Great point on the CEIL function. Thanks for sharing. If the number of boxes isn't a power of 2, splitting the boxes in two equal portions each time will only work until the elves reach an odd number of boxes.

For example if there are 20 boxes, dividing by two and weighing each half will narrow the location of the ring down to 10 boxes. Dividing 10 by two and weighing each half will narrow the ring's location to 5 boxes. Since 5 is odd, repeating the process above, as it stands, isn't an option. The elves would need to weigh 2 boxes on each scale with 1 on the sidelines, and make the best decision based on what the scales show. I plan to include the solution in a follow-up post.

Now if the number of boxes isn't a power of the number of scales AND the elves have more than 2 scales, your post on how to create a function to find the greatest common divisor will come in very handy!

http://blogs.sas.com/content/iml/2013/11/10/the-gcd-and-lcm-functions-in-sas.html