Re: writing an "artful" algorithm

[Samuel Tardieu <sam@rfc1149.net>]

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;