writing an "artful" algorithm

writing an "artful" algorithm

[John Stoneham]

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)

Re: writing an "artful" algorithm

[Samuel Tardieu]

John Stoneham wrote:

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

Job done, thanks, it was fun :)

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

Hopefully, neither nested "for" loops nor multi-line conditionals
are needed (this would be a maintenance nightmare in a big project).
The worst nesting used in my proposed solution is a "if" within a
"for" loop, at the price of several exit points in the two procedures
used.

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

As soon as you nest two loops, you should stop, look at your code,
look at the problem you are trying to solve and ask to yourself
"what am I doing wrong?". Sometimes, it makes perfect sense, as you
underline.  Quite often, it means that the solution you are
implementing may be way too complex.

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

You have probably added too many checks. As you can see in comments
of my solution, those cases can be automatically handled by the
general algorithm.

In short: do not overcomplicate the problem. Zero does not deserve
any special consideration there.

Disclaimer: this is a quick response to an amusing problem. It can
probably be improved (I mean "shortened" and "factored") a lot by
careful thinking. "To attain knowledge, add things every day; to
obtain wisdom, remove things every day" (Lao Tzu, in _Tao Te Ching_).

  Sam
-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/sam


package Artful is

   --   Build with:
   --     gnatmake -z -O -gnatp artful
   --   Execute with:
   --     ./artful

   --  Problem description (from John Stoneham <captnjameskirk@moc.oohay> on
   --  comp.lang.ada): find all pairs of five digits decimal numbers with
   --  all 10 digits used whose product use all 10 digits.

   --  Simplification of the problem (with the same result):
   --    + eliminate cases where the right term would be bigger than the left
   --      term (cut off duplicate results and trim entire branches in
   --      resolution tree)
   --    + do not test for the number of digits in the result:
   --      - if the result has too few digits, duplicate leading zeroes will be
   --        detected (as we test 10 successive digits using a shift register)
   --      - if the result has too many digits, a duplicate digit will be found
   --    + do not test for any special condition (leading zero) on the terms,
   --      as we impose 10 digits too, so all 10 will be used (including
   --      exactly one zero somewhere)

   pragma Elaborate_Body;

end Artful;


with Ada.Text_IO;

package body Artful is

   type Term is range 0000000000 .. 9999999999;

   Left, Right : aliased Term := 00000;

   Used_Digits : array (0 .. 9) of Boolean := (others => False);

   procedure Check_Result;
   procedure Change_Digit (T : access Term; D : in Term);

   ------------------
   -- Change_Digit --
   ------------------

   --  Digits are changed from the leftmost to the rightmost one,
   --  starting with the left term. T is an access to the digit
   --  being worked on, D contains the increment corresponding
   --  to the digit we are currently working on (10**k).
   --  When all the digits of the right term are set, we go
   --  to the left term (leftmost digit).

   procedure Change_Digit (T : access Term; D : in Term) is
      T_Orig : Term;
   begin
      if Left < Right then
         return;                           --  Cut off symetric cases
      end if;

      if D = 0 and then T.all /= Left then    --  Both terms complete
         Check_Result;                      --  Test product validity
         return;
      end if;

      if D = 0 then                            --  Left term complete
         Change_Digit (Right'Access, 10000);   --  Work on right term
         return;
      end if;

      T_Orig := T.all;                             --  Preserve state

      for I in 0 .. 9 loop
         if not Used_Digits (I) then     --  Digit is not a duplicate
            Used_Digits (I) := True;           --  Mark digit as used
            Change_Digit (T, D/10);                    --  Next digit
            Used_Digits (I) := False;                  --  Free digit
         end if;
         T.all := T.all + D;              --  Increment current digit
      end loop;

      T.all := T_Orig;                     --  Restore original state
   end Change_Digit;

   ------------------
   -- Check_Result --
   ------------------

   procedure Check_Result is
      Prod    : constant Term             := Left*Right;
      Shifted : Term                      := Prod;
      Used    : array (0 .. 9) of Boolean := (others => False);
      Digit   : Natural;
   begin
      Shifted := Prod;        --  Rightmost digit tested at each pass
      Used    := (others => False);
      for I in 0 .. 9 loop
         Digit := Natural (Shifted mod 10);
         if Used (Digit) then
            return;         --  Duplicate digit in product => failure
         end if;
         Used (Digit) := True;
         Shifted := Shifted / 10;
      end loop;

      Ada.Text_IO.Put_Line ("Result found: " &
                            Term'Image (Left) &
                            " * " &
                            Term'Image (Right) &
                            " = " &
                            Term'Image (Prod));
   end Check_Result;

begin
   Change_Digit (Left'Access, 10000);
end Artful;

Re: writing an "artful" algorithm

[Samuel Tardieu]

>>>>> "Sam" == Samuel Tardieu <sam@rfc1149.net> writes:

Sam> -- if the result has too many digits, a duplicate digit will be
Sam> -- found

Oops, this comment is unnecessary (and even bogus as if it were needed,
the code would need to be changed to assume a possible overflow), as
we will *never* have too many digits (0<=left<10**5 and 0<=right<10**5
imply that 0<=left*right<10**10).

  Sam
-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/sam

Re: writing an "artful" algorithm

[Steve]

"John Stoneham" <captnjameskirk@moc.oohay> wrote in message
news:Tvzna.1484$Kb5.65920135@newssvr12.news.prodigy.com...
[snip]
> 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.
[snip]
>
> Take off your shoes, roll up your sleeves, and feel free to jump in!
>

The approach used here is to generate a list containing all 5 digit numbers
containing unique digits.  Then sequence through the list generating
products and testing the unique digits condition on the product.

The list of 5 digit numbers is created using the recursive "Gen" routine.
The "Level" argument indicates how many digits have been accumulated into
the "Value".  The
"Available" parameter is an array listing the digits that are not contained
in "Value".

This approach generates all combinations of 5 unique digits without ever
comparing digits.

with Ada.Integer_Text_IO;
with Ada.Long_Long_Integer_Text_Io;
with Ada.Text_Io;
procedure CLAexercise is

  subtype Digit_Type is Natural range 0 .. 9;
  type Digit_Array is array( Positive range <> ) of Digit_Type;

  type Five_Unique_Digits_Array_Type is array( 1 .. 99_999 ) of Natural;

  Five_Unique_Digits_Array      : Five_Unique_Digits_Array_Type;
  Number_Of_Five_Digit_Elements : Natural := 0;
  Product                       : Long_Long_Integer;

  procedure Gen( Level : Natural; Available : Digit_Array; Value : Natural )
is
  begin
    if Level = 5 then
      Number_Of_Five_Digit_Elements := Number_Of_Five_Digit_Elements + 1;
      Five_Unique_Digits_Array( Number_Of_Five_Digit_Elements ) := Value;
    else
      Gen( Level     => Level + 1,
           Available => Available( Available'First + 1 .. Available'Last ),
           Value     => Value * 10 + Available( Available'First ) );
      for Idx in Available'First + 1 .. Available'Last - 1 loop
        Gen( Level     => Level + 1,
             Available => Available( Available'First .. Idx - 1 ) &
Available( Idx + 1 .. Available'Last ),
             Value     => Value * 10 + Available( Idx ) );
      end loop;
      Gen( Level     => Level + 1,
           Available => Available( Available'First .. Available'Last - 1 ),
           Value     => Value * 10 + Available( Available'Last ) );
    end if;
  end Gen;

  function Has_Unique_Digits( Value : Long_Long_Integer ) return Boolean is
    type Digit_Bit_Array_Type is array( Long_Long_Integer range 0 .. 9 ) of
Boolean;
    Digit_Bit_Array : Digit_Bit_Array_Type := ( others => False );
    Test_Value : Long_Long_Integer := Value;
    Low_Digit  : Long_Long_Integer;
  begin
    for Iter in 1 .. 10 loop
      Low_Digit := Test_Value mod 10;
      if Digit_Bit_Array( Low_Digit ) then
        return False;
      end if;
      Digit_Bit_Array( Low_Digit ) := True;
      Test_Value := Test_Value / 10;
    end loop;
    return True;
  end Has_Unique_Digits;

begin
  Gen( 0, ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ), 0 );
  for Left in 1 .. Number_Of_Five_Digit_Elements loop
    for Right in 1 .. Number_Of_Five_Digit_Elements loop
      Product := Long_Long_Integer( Five_Unique_Digits_Array( Left ) )
                 * Long_Long_Integer( Five_Unique_Digits_array( Right ) );
      if Product > 99_999_999 and then
         Product < 10_000_000_000 and then
         Has_Unique_Digits( Product ) then
         Ada.Text_Io.Put( "Left: " );
         Ada.Integer_Text_Io.Put( Five_Unique_Digits_Array( Left ) );
         Ada.Text_Io.Put( "  Right: " );
         Ada.Integer_Text_Io.Put( Five_Unique_Digits_Array( Right ) );
         Ada.Text_Io.Put( "  Product: " );
         Ada.Long_Long_Integer_Text_Io.Put( Product );
         Ada.Text_Io.New_Line;
      end if;
    end loop;
  end loop;
end CLAexercise;

Steve
(The Duck)

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

Re: writing an "artful" algorithm

[tmoran]

> > 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
>
> The approach used here is to generate a list containing all 5 digit numbers
> containing unique digits.  Then sequence through the list generating
> products and testing the unique digits condition on the product.
  Clearly (casting out nines) the product must be a multiple of 9, so
either one of the multipliers is a multiple of 9, ie sum of its digits
mod 9 = 0, or both are multiples of 3, ie, sum of digits mod 3 = 0.
That should reduce the number of trial multiplies.

Re: writing an "artful" algorithm

[Dan Eilers]

John Stoneham <captnjameskirk@moc.oohay> wrote in message news:<Tvzna.1484$Kb5.65920135@newssvr12.news.prodigy.com>...

> 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?" ...

Well, you are in luck.  Knuth's techniques for generating permutations
are explained in gory detail in section 7.2.1.2 of The Art of Computer
Programming, (part of the long-awaited Volume 4), and available online
at:

  http://www-cs-staff.Stanford.EDU/~knuth/fasc2b.ps.gz

See in particular the answers to exercises 9 and 41.

	-- Dan Eilers

Re: writing an "artful" algorithm

[John Stoneham]

Dan Eilers wrote:
> Well, you are in luck.  Knuth's techniques for generating permutations
> are explained in gory detail in section 7.2.1.2 of The Art of Computer
> Programming, (part of the long-awaited Volume 4), and available online
> at:
> 
>   http://www-cs-staff.Stanford.EDU/~knuth/fasc2b.ps.gz
> 
> See in particular the answers to exercises 9 and 41.
> 
> 	-- Dan Eilers

Wow, thanks! I did not realize that "previews" of Vol. 4 were online. 
I've had an extremely busy week and haven't been able to revisit this 
problem, but I look forward to reading through those sections and 
exercises, and hopefully I'll be able to take another crack at it this 
weekend.


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

Re: writing an "artful" algorithm

[John Atwood]

John Stoneham  <captnjameskirk@moc.oohay> wrote:
>For those who like puzzles and have a little bit of free time, you may 
> <snip>
>
>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?


Here's a functional solution to a similar problem:
	http://www.cs.nott.ac.uk/~gmh/bib.html#countdown
	Graham Hutton. Journal of Functional Programming, 
	12(6):609-616, Cambridge University Press, November 2002.

	We systematically develop a functional program that 
	solves the countdown problem, a numbers game in 
	which the aim is to construct arithmetic expressions 
	satisfying certain constraints. Starting from a formal 
	specification of the problem, we present a simple but 
	inefficient program that solves the problem, and prove 
	that this program is correct. We then use program fusion 
	to calculate an equivalent but more efficient program, 
	which is then further improved by exploiting arithmetic 
	properties.




John