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 21:57:41 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!arclight.uoregon.edu!wn13feed!wn12feed!wn14feed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi.com!rwcrnsc54.POSTED!not-for-mail From: "Steve" Newsgroups: comp.lang.ada References: Subject: Re: writing an "artful" algorithm X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 Message-ID: <9BLna.232134$OV.289871@rwcrnsc54> NNTP-Posting-Host: 12.211.13.75 X-Complaints-To: abuse@attbi.com X-Trace: rwcrnsc54 1050641861 12.211.13.75 (Fri, 18 Apr 2003 04:57:41 GMT) NNTP-Posting-Date: Fri, 18 Apr 2003 04:57:41 GMT Organization: AT&T Broadband Date: Fri, 18 Apr 2003 04:57:41 GMT Xref: archiver1.google.com comp.lang.ada:36274 Date: 2003-04-18T04:57:41+00:00 List-Id: "John Stoneham" 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) >