The Rolling Counter Algorithm Pattern

Question: Write an algorithm that, when given some number of pennies, will print out all the ways that this value can be represented in nickels, dimes, quarters, and dollars. And don't use recursion.

Why not recursion? First, because the solution is more elegant. Second, because I don't like recursion. For more on why, see my next post "why I don't like recursion" ... or something like that but the short answer is that it is less efficient.

Before I get into this question, I’m going to discuss the rolling counter algorithm pattern for which this blog post is named: This pattern is often useful in interviews (almost as useful as the "just model it as a graph and traverse it or find the spanning tree" pattern) and usually ends up tripping me up, especially when I fail to recognize that I need to use it rather than (say) a bunch of nested for loops or worse: recursion. Maybe it trips you up too. Hopefully this post will make the pattern clear enough that it’ll stop tripping you and me up.

BTW: any time someone asks you to print the set BLA{…} where condition FOO holds true, you should think of this pattern. Ill try to make the why clear later.

You should think of a rolling counter as being analogous to the odometer on a car. As you’re driving the first roller of the odometer increases one mile at a time until you drive past nine miles. At this point, rather than increasing that roller to 10, it goes back to 0 and increments the second roller. Then you go back to incrementing the first roller for another ten miles. Eventually you have to increment the third roller, and so on. Until you run out of rollers, but you've usually replaced your car by then.

In code, you first, initialize the counter (note that if you are using java as I am, you'll get the initialization to zero done for you).

int[] mRollingCounter = new int[length];
for(int i = 0; i < mRollingCounter.length; i++) {
mRollingCounter[i] = 0;
}

Now the code to roll the counter:

int mCounterPointer = 0
while(mCounterPointer < mRollingCounter.length) {
mRollingCounter[mCounterPointer]++;
if( rollcondition() == true) {
   mRollingCounter[mCounterPointer] = 0
} else {
   break;
}
}

That is all there is to execute a single increase of the counter. The critical bit is the rollcondition() function. It is what tells the odometer that we've tried to roll past 0009 miles and should increment the second roller to 1. Or that you've tried to roll past 0099 miles and you need to increment the third roller.

We start with the first element of the counter and increment it. (This is equivalent to the odometer going from [0][0][0][0] to [0][0][0][1].) If this change triggers the counter rolling condition, set that element back to zero, move to the next element of the counter and continue. (this is what happens when we’re already at [0][0][0][9], first we go to [0][0][0][10] and since any element being greater than 9 is a roll condition for an odometer, we set the counter back to [0][0][0][0], move the pointer one over, and again increment to [0][0][1][0] at which point we break.

If this isn’t clear, code it up in your favorite IDE and play with it for a while (full code sample is below for the lazy) until you understand it or you can just TRUST ME and memorize it to be spit out in your next interview. Your choice, but I’d suggest understanding it.

So implementing an odometer isn’t that interesting but other things are. For example, if you can write a non recursive string permuter with this (ie, given a string of characters, print all the possible re-arrengements of characters). Or something to spit out all the possible ways that 50 cups of beer can be represented with various imperial units. I’m going to now get into the question that I started this post with.

 public static String[] mLabels =
     {"Nickles", "Dimes", "Quarters", "Dollars"};
 public static int[] mUnitBases = {5, 10, 25, 100};

 public static void convertPennies(int pennies) {

     int mCounterPointer = 0;
     int[] mRollingCounter = new int[mUnitBases.length];

     while(mCounterPointer < mRollingCounter.length) {
         printCurrency(pennies, mRollingCounter);
         mCounterPointer = 0;
         while(mCounterPointer < mRollingCounter.length) {
             mRollingCounter[mCounterPointer]++;

             if(getValue(mRollingCounter) > pennies) {
                 mRollingCounter[mCounterPointer] = 0;
             } else {
                 break;
             }
             mCounterPointer++;
         }
     }
 }

 public static int getValue(int[] currency) {
     int mTotalValue = 0;
     for(int i = 0; i < currency.length; i++) {
         mTotalValue += currency[i] * mUnitBases[i];
     }
     return mTotalValue;
 }

 private static void printCurrency(int pennies, int[] currency) {
     for(int i = 0; i < currency.length; i++) {
         System.out.print(String.valueOf(currency[i]));
         System.out.print(" " + mLabels[i] + " ");
     }
     System.out.println(" and " +
         (pennies - getValue(currency)) + " pennies");
 }

And there you have it.

Take home lesson:

Any time you need to iterate through all the permutations of a thing, consider using a rolling counter.