[Coco] Project Euler and the Coco
flexser at fiu.edu
Sat Nov 15 17:26:24 EST 2008
Better yet, use a+1 as the lower bound for b if a > 250, since b must be
strictly greater than a. Changing the lower bound if a > 250 is not only
efficient, but also necessary to avoid violating the requirement that b > a.
(I'd originally considered the possiblity that b could equal a, overlooking the
problem specification that b>a. In any case, b could not equal a, since that
would make c equal to a times the square root of 2, inconsistent with the
requirement that c be an integer.) Similarly, if a <= 250, use (501-a) as the
lower bound for b, since b must be at least one greater than (500-a). Also on
the same theme, the requirement that c be at least one greater than b means the
upper bound for b should be (999-a)/2 rather than (1000-a)/2.
I'd do it as two successive FOR/NEXT loops, the first taking A from 2 to 250
with B ranging from (501-A) to (999-A)/2, and the second taking A from 251 to
333 with B ranging from (A+1) to (999-A)/2. (Come to think of it, the upper
bound for A should be 332 rather than 333, since if A were 333, then the
minimums for B and C would be 334 and 335, which adds to 1002.)
A more satisfying comparison than how many iterations are needed to find the
solution would be how many iterations are necessary to search the parameter
space to completion, in order to verify that there is only one solution.
It is a bit puzzling that the problem asks for the value of a*b*c for no obvious
reason. The only explanation that occurs to me is that it is possible to deduce
this value mathematically without doing a trial-and-error search of all eligible
a-b-c combinations and without knowing the individual values of a, b, and c that
constitute the complete solution. (By the way, what ARE those values?)
On Sat, 15 Nov 2008, Arthur Flexser wrote:
> While I agree that b > (500-a), (and nice work to you, too), b must also be
> greater than or equal to a. So, for maximum efficiency, the lower bound of b
> should be either a or (500-a), whichever is greater. That is, use a as the
> lower bound if a > 250, and (500-a) as the lower bound otherwise, to save yet
> more iterations when a is between 250 and 333.
> On Sat, 15 Nov 2008, Mark McDougall wrote:
> > Arthur Flexser wrote:
> > > The ascending length requirement means that B must
> > > take up no more than half of the remaining board, or (1000-A)/2.
> > (a^2 + b^2)= c^2
> > (a^2 + b^2) = (a+b)^2 - 2ab = c^2
> > therefore, a+b > c
> > a + b > (1000 - a - b)
> > 2a + 2b > 1000
> > (a+b) > 500
> > ie, b > (500-a)
> > and using Arthur's observation (nice work)
> > FOR B=500-A TO (1000-A)/2
> > reduces the number of iterations to find the solution to 10,174 from the
> > original 66,174 iterations - a massive 85% reduction!
> > Regards,
> > --
> > | Mark McDougall | "Electrical Engineers do it
> > | <http://members.iinet.net.au/~msmcdoug> | with less resistance!"
> > --
> > Coco mailing list
> > Coco at maltedmedia.com
> > http://five.pairlist.net/mailman/listinfo/coco
> Coco mailing list
> Coco at maltedmedia.com
More information about the Coco