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,start X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-04-17 08:19:17 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!headwall.stanford.edu!newshub.sdsu.edu!news-xfer.cox.net!prodigy.com!newsmst01.news.prodigy.com!prodigy.com!postmaster.news.prodigy.com!newssvr12.news.prodigy.com.POSTED!not-for-mail From: John Stoneham User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.4a) Gecko/20030326 X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: writing an "artful" algorithm Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Message-ID: NNTP-Posting-Host: 64.219.118.211 X-Complaints-To: abuse@prodigy.net X-Trace: newssvr12.news.prodigy.com 1050592371 ST000 64.219.118.211 (Thu, 17 Apr 2003 11:12:51 EDT) NNTP-Posting-Date: Thu, 17 Apr 2003 11:12:51 EDT Organization: Prodigy Internet http://www.prodigy.com X-UserInfo1: Q[R_@SZDWJTGRQHX@BCBNWX@RJ_XPDLMN@GZ_GYO^ZUDUWYAKVUOPCW[ML\JXUCKVFDYZKBMSFX^OMSAFNTINTDDMVW[X\THOPXZRVOCJTUTPC\_JSBVX\KAOTBAJBVMZTYAKMNLDI_MFDSSOLXINH__FS^\WQGHGI^C@E[A_CF\AQLDQ\BTMPLDFNVUQ_VM Date: Thu, 17 Apr 2003 15:12:51 GMT Xref: archiver1.google.com comp.lang.ada:36236 Date: 2003-04-17T15:12:51+00:00 List-Id: 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)