Many of you know my affinity for challenging problems and puzzles. For me, they are fun ways to expand my knowledge. There is a currently unsolved math problem of an order 10 Perfect Magic Cube. To prove that an order 10 magic cube is not possible by brute force, 1000! permutations of arranging the numbers 1 - 1000 must be tried. I was hoping to find and prove the existence of a cube so I knew that I was going to have to find ways to significantly reduce my search space and hope I got lucky. I succeeded in finding ways to reduce the search space but failed in getting lucky. This meditation is about the methodology I used and not about the problem I was trying to solve. If anyone is interested in a list of techniques I used, /msg me and I will be glad to go over them. What was important to me was the knowledge not the answer.

If you were trying to figure out how many different outfits you could make with your current wardrobe, you may create the following code:

for my $feet ( qw/black brown sneaker/ ) {
    for my $legs ( qw/shorts dress_pants jeans/ ) {
        for my $torso ( qw/t-shirt dress_shirt sweater/ ) {
            print "$torso $legs $feet\n";
        }
    }
}
[download]

Now imagine that you wanted to do the same thing but you were doing it for your upcoming birthday gifts. Since you won't know until the gifts arrive (runtime) what you are going to receive, you can't pre-construct the loops. You know you may need to extend the number of loops to include things like gloves to cover your hands and hats to cover your head and sunglasses for your eyes.

Abritrary nested loops is not knowing in advance the number of loops or the number of items in each loop. It may seem like a difficult problem to solve, but in fact it is quite easy.

Dominus uses the concept of an odometer with dials of different ranges in HOP to give a visual representation of the process. When I first figured out how to it, I thought of a combination lock on a briefcase with different size dials. The idea is the same.

Assume that you have received a list of lists that need to be looped through. Each list represents a dial that must be turned. When you the dial you are turning reaches its maximum value, the dial to its left increments by one and the current one rolls over to the start. When the leftmost dial reaches exceeds its maximum number - you know you are finished.

(black, brown, sneakers), (shorts, dress_pants, jeans), (t-shirt, dres
+s_shirt, sweater)

# Start position
0, 0, 0 = black, shorts, t-shirt
0, 0, 1 = black, shorts, dress_shirt
0, 0, 2 = black, shorts, sweater
0, 1, 0 = black, shorts, t-shirt
0, 1, 1 = black, shorts, dress_shirt
0, 1, 2 = black, shorts, sweater
0, 2, 0 = black, dress_pants, t-shirt
...
2, 2, 2 = sneakers, jeans, sweater
[download]

To make this an iterator you need to use closures which I won't cover. Instead of rolling your own you should probably use tye's Algorithm::Loops 'NestedLoops'. There is still value in removing the veil of mystery to understand how it works even if you are not going to implement it yourself.

What if the problem you are trying to solve requires the construction of a loops values to be based off 1 or more of the preceeding values selected? For instance, when you are selecting wardrobes - perhaps you don't want to mix business wear with beach wear. This can be handled with a code ref. In Algorithm::Loops, $_ is the currently selected value immediately to the left of the current dial and @_ is all of the selected values with 0 being the outer most dial.

Now it is a simple matter of checking when a dial rolls over to the beginning if the dial was a fixed list or generated from a code ref. If it was from a code ref, replace the current list with the return value of the the executed code ref.

This meditation is not intended to be an explanation of Algorithm::Loops. In fact, I rarely grok tye's code and this is no exception. If my explanation fits the Algorithm::Loops code it is not a result of me studying the code. He however does have some great ideas which I shamelessly steal.

You might want the ability to filter out some of the results. We may allow the user to pass in a code ref that we will execute at the end of each dial turn. If the code ref returns a true value we return the list and if not, we spin the dial again - wash, rinse, repeat.

You may also want to execute some arbitrary piece of code after each loop. Again, this is as simple as designing your API such that the user can pass in a code ref that you execute at the end of each dial turn.

Handling arbitrarily nested loops that are dynamically constructed in Perl is fairly simple. This does not mean you should go rolling your own without due cause as Algorithm::Loops is a wonderful module. I needed to for my task because Perl was just too slow. I ended up using C. While I was able to produce some extremely fast code (25-30 million iterations per second), I was unable to make a generic reusable library. Perl rawks!