writing an "artful" algorithm

[John Stoneham <captnjameskirk@moc.oohay>]

For those who like puzzles and have a little bit of free time, you may 
want to try your hand at this, and I'd like any input from those who do. 
Here is my issue. While throwing together a quick program to solve a 
"simple" math puzzle, I realized that, even though the program worked 
and produced the desired result, the algorithm itself was *ugly*, with 
many nested for-loops and multi-line conditionals. Something like this:
for ...
  if ...
   for ...
    if ...
     for ...
      if ...
      ...continue to required depth...
      [solution test code]
      ... close if's and loop's back up to prev. depth...
      end if;
     end loop;
    end if;
   end loop;
  end if;
end loop;

Each if-condition was more complex than the previous, culminating in a 
monstrosity that spanned 7 lines in the body of the "solution test 
code", which in total was only an additional dozen or so lines. In 
short, the "solution test" was simple, but getting there was ugly. BUT 
IT MADE SENSE TO ME AT THE TIME.

So now I'm working on a different puzzle: write the most "artful" 
solution to the problem, or, to put it another way, "How would Knuth do 
it?" Now, I'm no computer scientist, and I'm certainly not an expert 
programmer, but I just feel there is a "better" way to write programs 
than this. It's like a person who does multiplication by counting on 
their fingers: it works but it sure ain't pretty.

The original math puzzle was based on an extra-credit problem that my 
daugher was assigned. For our purposes, I've decided to make the problem 
a little different, and here is my revised version (this also keeps the 
original problem and solution harder to find for other students):

Find two 5-digit numbers (base 10) whose product is a 10-digit number; 
there is the condition that no digit can be repeated in either 5-digit 
number, and all the digits in the product must be unique. One 
consequence of this condition with the number of digits required in each 
number, is that a solution which contains a number with a leading 0 is 
valid, even though it "appears" that this number would really be a 4- or 
9-digit number. For example, for the two 5-digit numbers, one may use 
(13_542 * 60_978) or ([0]9_231 * 84_756) but not (11_235 * 68_879) nor 
(12_345 * 56_789), and the product may be 3_245_786_109 or 
[0_]987_654_321 but not 1_123_456_789. Find all the solutions.

Going back to my example snippet above, I had decided to represent each 
digit as a single integer, and use the for loops to cycle through all 
the possible combinations (hence the nested loops). The if-conditions 
made sure that digits were not repeated (hence, the deeper the if into 
the loops the more complex it was). To construct the 5-digit numbers out 
of the digits, the first digit was multiplied by 10_000 and added to the 
second which was multiplied by 1_000, etc. The product was deconstructed 
in a reverse manner to get its individual digits, which were then 
compared with each other to make sure none repeated. Other small details 
were checked, such as testing for a leading 0, and products larger than 
10 digits, etc, to make sure we had a valid solution, and if so it was 
displayed. As I said before, this method made sense to me, and still 
does, but the resulting code just looks bad.

This does seem like the imperative way to work out the problem, and I 
think just about any other imperative approach would look about the 
same, even if it used vectors or records in its representation. It would 
still need to test individual digits and generate and test every 
possible combination. But what about the functional approach? Would it 
be more "artful" here? Would it even be possible to use a functional 
approach for such a problem?

Take off your shoes, roll up your sleeves, and feel free to jump in!

--
John S. (to email, reverse the domain)