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: [email protected]
[mailto:[email protected]] 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
