An interesting puzzle from Usenet

I encountered a cute programming problem recently on the comp.lang.c++ newsgroup: You have a supply of 2-cent, 7-cent, and 9-cent stamps, and you wish to figure out how to produce a given amount of postage using the smallest number of stamps.

This problem is interesting because it is hard enough that most programmers can't immediately dash off a solution, and easy enough that a solution will fit on one page. Even more interesting is how much trouble people seem to have with it, and how badly the sample programs are written.

I'm going to have more to say about this problem and its solution in coming articles. For now, I want to observe that several of the solutions I've seen have three nested loops: one for 2-cent stamps, one for 7-cent stamps, and one for 9-cent stamps.

My immediate impulse is that such a strategy is wrong--even without knowing what the right strategy might be. The reason is that the inventory of stamps that we have available is part of our data, whereas the number of loops in the program is part of its structure. The strategy is wrong, therefore, because it violates a fundamental principle:

The structure of a program should be independent of the values of its input data.

Of course, this general statement is a negative: It tells us what not to do, not what to do. So we still need to figure out how to solve the problem. We'll begin doing that in the next article.

Posted by Andrew Koenig at 11:23 AM  Permalink