From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,cafc372bafbed3f1 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-04-17 15:08:06 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.stueberl.de!teaser.fr!enst.fr!melchior!cuivre.fr.eu.org!melchior.frmug.org!not-for-mail From: Samuel Tardieu Newsgroups: comp.lang.ada Subject: Re: writing an "artful" algorithm Date: Thu, 17 Apr 2003 22:08:04 +0000 (UTC) Organization: DnS network Message-ID: References: NNTP-Posting-Host: m34.net81-65-250.noos.fr X-Trace: melchior.cuivre.fr.eu.org 1050617284 11297 81.65.250.34 (17 Apr 2003 22:08:04 GMT) X-Complaints-To: usenet@melchior.cuivre.fr.eu.org NNTP-Posting-Date: Thu, 17 Apr 2003 22:08:04 +0000 (UTC) User-Agent: slrn/0.9.7.4 (FreeBSD) Cache-Post-Path: willow.dyn.rfc1149.net!unknown@localhost X-Cache: nntpcache 3.0.1 (see http://www.nntpcache.org/) Xref: archiver1.google.com comp.lang.ada:36257 Date: 2003-04-17T22:08:04+00:00 List-Id: 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 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;