Your approach looks very sensible. But I am curious about this result,
which is not what I expected:
bestmn 1e3
7 8 8 7
If I change the second to last line in bestmnv to read
i =. (i. <./) d
I get
bestmn 1e3
7 8
Are there cases where this would be a problem?
Thanks,
--
Raul
On Tue, Oct 14, 2014 at 5:39 AM, Mike Day <mike_liz....@tiscali.co.uk> wrote:
> OK - I've re-engineered a solution method which deals with
> required numbers several orders of magnitude higher than
> 2e6. I expect my original approach was the whole array
> approach as recently discussed, but I can't find it anywhere
> in my files.
>
> Apologies for any silly line-throws.
>
> The maths shows that the number of embedded rectangles
> in a grid of size (m,n) is tri(m)*tri(n) where tri is a triangular
> number, ie one in the series 0 1 3 6 10 15 ....
> tri(n) is n(n+1)%2
>
> It's easy to find which (m,m) most closely approximates the
> required number, req, by solving the quadratic
> m(m+1) = 2 sqrt(req)
>
> Let mmax = ceil(m)
>
> Also, for a given m, we can solve the quadratic
> n(n+1) = 4 req % m(m+1)
>
> In general, we get two integers bounding the non-
> integer solution, one of which will generally give
> a number of rectangles closer to the required
> value.
>
> Find the best pair (m,n) over m in [1,mmax]
>
> NB. Number of rectangles in mxn is tri(m)*tri(n)
>
> nrec =: *&(-:*>:)
>
>
> NB. best (m,n) over given vector m=y for target x
>
> bestmnv =: 3 : 0
>
> :
>
> req =. x [ m =. y
>
> NB. solve n(n+1)m(m+1) = 4*req
>
> NB. ie n^2 + n + 1-4.req/m(m+1) = 0
>
> NB. Get upper & lower integer bounds to each (usually) real solution
>
> n =. (<.,>.) _0.5 + %:_0.75 + 4*req% (*>:) m
>
> d =. (m=.m,m) (req |@-nrec) n NB. absolute errors
>
> i =. ((I.@(=(<./))@,)) d NB. index of least error
>
> m (,&(i&{) )n
>
> )
>
>
> NB. Find best m,n for required number of rectangles y
>
> bestmn =: 3 : 0
>
> req =. y
>
> NB. get maximum m, when n=m
>
> mmax=. >. _0.5 + %:_0.75 + 2*%:req NB. round up solution when m=n
>
> req bestmnv >:i.mmax
>
> )
>
>
> Here are a couple of targets suggested in the Project Euler discussion
> on this topic. The whole array approach discussed in the J forum would
>
> find them challenging.
>
>
> timer'bestmn x:<.9.87654321e19'
>
> +-----+------------+
>
> |5.628|20214 983262|
>
> +-----+------------+
>
> timer'bestmn 123456789123456789x'
>
> +--------+----------+
>
> |0.830002|7198 97621|
>
> +--------+----------+
>
>
> Thanks,
>
> Mike
>
>
>
>
> On 12/10/2014 11:30, Linda Alvord wrote:
>>
>> At the moment, I'm rooting for 54 by 54 as the answer!
>>
>> ff=: 13 :'(>:i.x) */>:i.y'
>> f=: 13 :'*/~ >:i.y'
>> (7 ff 7)-:f 7
>> good=: 13 :'}:1,x>+/\,y'
>> sum=: 13 :'+/(x good y)#, y'
>>
>> 400 < 400 sum 5 ff 5
>> 400 < 400 sum 6 ff 6
>> 400 < 400 sum 7 ff 7
>> 400 sum f 6
>> 400 sum f 7
>> 400 sum f 8
>> 6 ff 6
>> 400 sum 6 ff 6
>>
>> 2e6 < 2e6 sum 52 ff 52
>> 2e6 < 2e6 sum 53 ff 53
>> 2e6 < 2e6 sum 54 ff 54
>> 2e6 sum f 53
>> 2e6 sum f 54
>> 2e6 sum f 55
>> 2e6 sum 54 ff 54
>>
>> This stays in 2 dimensions.
>>
>> Linda
>>
>>
>> -----Original Message-----
>> From: programming-boun...@forums.jsoftware.com
>> [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Raul Miller
>> Sent: Saturday, October 11, 2014 6:10 PM
>> To: Programming forum
>> Subject: Re: [Jprogramming] Project Euler 85, Python and J
>>
>> I understand that boxed index lists can be used to index multi-dimensioned
>> arrays. And that can be a convenient abstraction.
>>
>> However, I have been dealing with very large datasets recently, and boxed
>> data on the critical path, at least for some operations, becomes
>> prohibitively slow.
>>
>> When I can use regular numeric structures to replace irregular boxed
>> structures, the overall speedup from the representation change usually
>> more
>> than makes up for the cost of changing representation.
>>
>> Thanks,
>>
>
>
>
> ---
> This email is free from viruses and malware because avast! Antivirus
> protection is active.
> http://www.avast.com
>
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 2014.0.4765 / Virus Database: 4040/8386 - Release Date: 10/14/14
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
