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=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,1b41412c7bc28c47 X-Google-Attributes: gid103376,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news1.google.com!postnews.google.com!t54g2000hsg.googlegroups.com!not-for-mail From: amado.alves@gmail.com Newsgroups: comp.lang.ada Subject: Re: Suffix _T for types found good Date: Wed, 6 Aug 2008 16:25:08 -0700 (PDT) Organization: http://groups.google.com Message-ID: <57454243-fca7-4292-96c5-7ce7b8380631@t54g2000hsg.googlegroups.com> References: <2e9ebb23-a68b-43cf-8871-febcb173f951@56g2000hsm.googlegroups.com> <188191be-d2c6-4d94-8d6b-082015954332@t54g2000hsg.googlegroups.com> <489A0440.9080201@obry.net> <594cdbb8-4018-44bd-a8db-0df3f23df247@z72g2000hsb.googlegroups.com> <2dqmk.286756$yE1.10484@attbi_s21> NNTP-Posting-Host: 92.250.114.147 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Trace: posting.google.com 1218065108 15286 127.0.0.1 (6 Aug 2008 23:25:08 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Wed, 6 Aug 2008 23:25:08 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: t54g2000hsg.googlegroups.com; posting-host=92.250.114.147; posting-account=3cDqWgoAAAAZXc8D3pDqwa77IryJ2nnY User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 6.0; SLCC1; .NET CLR 2.0.50727; Media Center PC 5.0; .NET CLR 3.0.04506; .NET CLR 1.1.4322),gzip(gfe),gzip(gfe) Xref: g2news1.google.com comp.lang.ada:1482 Date: 2008-08-06T16:25:08-07:00 List-Id: The domain is problem 68 of ProjectEuler.net Program attached. The lexicon Node_Value, Node_Index, Triad_Value (aka line total) was the most clear that I could think of. I do not try to avoid essential work. I do try to avoid the inessential and even counterproductive work of increasing the lexicon. with Ada.Text_IO; use Ada.Text_IO; procedure Pentagon is -- This is my solution to problem 68 on ProjectEuler.net -- (C) 2008 Marius Amado-Alves -- marius@amado-alves.info -- marius63 on ProjectEuler.net -- Currently this program produces the solution -- 6 7 3 4 3 9 2 9 5 10 5 1 8 1 7 -- which is *not* accepted by ProjectEuler.net -- Debug away! -- 2008-08-05 -- The overall approach is to generate candidate strings in descending order and -- stop at the first valid pattern. -- We establish a few theorems to reduce the set of candidate strings. -- Theorem 1. -- 10 is an outer node. -- This derives from the requirement that the solution have 16 digits. -- Theorem 2. -- The lowest outer number is at most 6. -- This derives from theorem 1 and the requirement -- that the solution start at the lowest outer node. -- Theorem 3. -- The possible line totals are in [14, 19]. -- This is proved later. -- Theorem 4. -- A sequence with 10 more to the right is greater. -- This derives from Theorem 1, via the fact that there is always -- at least one number bigger than 1 in any triad to the left of 10, -- and so more triads to the left entail a higher total, -- (because left means more significance). -- To clarify: we give preference to higher numbers more to the left, -- except 10 which is placed as most to the right as possible. -- We index the nodes as follows: -- -- (1) -- * -- * -- (6) (2) -- * * * -- * * * -- (10) (7) -- * * * -- * * * -- (5) (9) * * (8) * * (3) -- * -- * -- (4) -- -- We assume node 1 is the lowest external node. -- So the nodes in the sequence for the digit string are as defined in H below. type Node_Index_T is range 1 .. 10; type Sequence_Index_T is range 1 .. 15; subtype Triad_Index_T is Sequence_Index_T range 1 .. 5; H : array (Sequence_Index_T) of Node_Index_T := -- triad 1 triad 2 triad 3 triad 4 triad 5 ( 1, 6, 7, 2, 7, 8, 3, 8, 9, 4, 9, 10, 5, 10, 6 ); -- : :.......: :.......: :.......: :........: : -- :................................................: -- This convention helps prove theorem 3, as follows. -- Clearly each external node 1,2,3,4,5 occurs exactly once, -- and each shared node 6,7,8,9,10 occurs exactly twice, in a sequence, -- as illustrated above. -- So the sum z of all values in a sequence is -- -- z = x1 + x2 + x3 + x4 + x5 + 2 * (x6 + x7 + x8 + x9 + x10) -- -- where xI is the value (the number) at node I. -- Clearly the minimum and maximum values of z are -- -- 6 + 7 + 8 + 9 + 10 + 2 * (1 + 2 + 3 + 4 + 5 ) = 70 -- 1 + 2 + 3 + 4 + 5 + 2 * (6 + 7 + 8 + 9 + 10) = 95 -- -- Also clearly each possible line total t is such that -- -- t = z / 5 -- -- And so the minimum and maximum values of t are 14 and 19. subtype Triad_Total_T is Natural range 14 .. 19; subtype Node_Value_T is Natural range 1 .. 10; type Node_T is record Value : Node_Value_T; Defined : Boolean; end record; type Solution_T is array (Node_Index_T) of Node_T; type Precedence_T is range 1 .. 10; W : array (Precedence_T) of Node_Value_T := (9,8,7,6,5,4,3,2,1,10); function Img (X : Node_T) return String is begin if X.Defined then return Node_Value_T'Image (X.Value); else return " *"; end if; end; procedure Put_Img (X : Solution_T) is begin for I in Sequence_Index_T loop Put (Img (X (H(I)))); end loop; New_Line; end; function Triad_Total (Solution : Solution_T; Triad : Triad_Index_T) return Triad_Total_T is I : Sequence_Index_T := Sequence_Index_T ((Triad - 1) * 3 + 1); begin return Triad_Total_T (Solution (H(I)).Value + Solution (H(I + 1)).Value + Solution (H(I + 2)).Value); end; procedure Find_Next_Unset_Node (Solution : Solution_T; I : out Node_Index_T; Found : out Boolean) is begin for J in Sequence_Index_T loop if not Solution (H(J)).Defined then I := H(J); Found := True; return; end if; end loop; Found := False; end; Found : exception; procedure Inc (X : in out Integer) is begin X := X + 1; end; procedure Examine_Triad (Solution : Solution_T; Triad : Triad_Index_T; Possibly_Partial_Total : out Natural; Qt_Of_Defined_Nodes : out Natural) is I : Sequence_Index_T := Sequence_Index_T ((Triad - 1) * 3 + 1); begin Possibly_Partial_Total := 0; Qt_Of_Defined_Nodes := 0; for J in Sequence_Index_T range I .. I + 2 loop if Solution (H(J)).Defined then Inc (Qt_Of_Defined_Nodes); Possibly_Partial_Total := Possibly_Partial_Total + Natural (Solution (H(J)).Value); end if; end loop; end; function Legal (Solution : Solution_T; Triad : Triad_Index_T := 1; Min : Triad_Total_T := 14; Max : Triad_Total_T := 19) return Boolean is I : Sequence_Index_T := Sequence_Index_T ((Triad - 1) * 3 + 1); Val, Def : Natural; begin Examine_Triad (Solution, Triad, Val, Def); if Def = 3 then if Val < Min or Val > Max then return False; elsif Triad = 5 then return True; else return Legal (Solution, Triad + 1, Val, Val); end if; elsif Def = 2 then if Val + 9 < Min or Val + 1 > Max then return False; elsif Triad = 5 then return True; else return Legal (Solution, Triad + 1, Min, Max); end if; elsif Def = 1 then if Val + 1 + 2 > Max then return False; elsif Triad = 5 then return True; else return Legal (Solution, Triad + 1, Min, Max); end if; elsif Def = 0 then if Triad = 5 then return True; else return Legal (Solution, Triad + 1, Min, Max); end if; end if; -- just to avoid no return compiler warning raise Program_Error; return False; end; Checked : Natural := 0; procedure Check (Solution : Solution_T) is K : Triad_Total_T; begin Inc (Checked); K := Triad_Total (Solution, 1); if Triad_Total (Solution, 2) = K and then Triad_Total (Solution, 3) = K and then Triad_Total (Solution, 4) = K and then Triad_Total (Solution, 5) = K then raise Found; end if; exception when Found => Put_Line (Natural'Image (Checked) & " solutions checked."); Put (" Solution:"); Put_Img (Solution); raise; when others => null; end; function Has_Value (Solution : Solution_T; X : Node_Value_T) return Boolean is begin for I in Node_Index_T loop if Solution (I).Defined and then Solution (I).Value = X then return True; end if; end loop; return False; end; procedure Complete (Solution_In : Solution_T) is Solution : Solution_T := Solution_In; I : Node_Index_T; Found : Boolean; X : Node_Value_T; begin if Legal (Solution) then Put_Img (Solution); Find_Next_Unset_Node (Solution, I, Found); if Found then for Y in Precedence_T loop X := W (Y); if not Has_Value (Solution, X) then Solution (I) := (Value => X, Defined => True); Complete (Solution); Solution (I).Defined := False; end if; end loop; else Check (Solution); end if; end if; end; Solution : Solution_T := (others => (Defined => False, others => <>)); begin Solution (1).Defined := True; for X in reverse Node_Value_T range 1 .. 6 loop Solution (1).Value := X; Complete (Solution); end loop; end;