I was at first surprised that the faery sequence approach is so slow, when its
supposed to be an improvement, but then I realized that it is an algorithm that
lists all fractions, and so will do 7.3M loops, on each loop adjusting at least
5 memory locations, and if done through ^:_ or some other recursive approach,
reparsing all inputs.
My fairly slow faery sequence approach: (15-30 seconds)
(>:@:{: ,~ {.,3&{,4&{, (1&{ , 2&{ ) -~ (3&{ ,4&{ ) * 4&{ <.@:%~ {. +
2&{)^:(2 ~: 4&{)^:_ ]12000 1 3 4000 11999 2
12000 5999 11999 1 2 7295374
By contrast, my "brute force" method is less than 12k "loops" (/), a single
data parsing pass, and uses J's fast +/ +./ and i. functions to quickly get
totals at high rank.
----- Original Message -----
From: David Lambert <[email protected]>
To: programming <[email protected]>
Cc:
Sent: Monday, June 16, 2014 2:56:22 PM
Subject: Re: [Jprogramming] Project Euler 73
Wow. The version I posted yesterday that tries all the fractions using
Raul's floating point modification runs "over night". A translation of
a python solution found on the internet using a Farey sequence generator
(I think) runs in half a minute. Your approach---awesome!
On 06/16/2014 02:25 PM, [email protected] wrote:
> Date: Mon, 16 Jun 2014 10:49:26 -0700
> From: "'Pascal Jasmin' via Programming"<[email protected]>
> To:"[email protected]" <[email protected]>
> Subject: Re: [Jprogramming] Project Euler 73
> Message-ID:
> <[email protected]>
> Content-Type: text/plain; charset=iso-8859-1
>
> an explicit version for clarity
> ? ?rangei
> [ + >:@] i.@- [
> ? ?2 rangei 5
> 2 3 4 5
>
> dyad verb where y just holds the total so far.
> 4 : 'y + +/ 1= x +./ (>. x % 3) rangei (<. x % 2)'/ 2,~ 4+ i.11997
> 7295374 NB. includes 1/3 and 1/2
>
> ? ?timespacex '4 : ''y + +/ 1= x +./ (>. x % 3) rangei (<. x % 2)''/ 2,~ 4+
> i.11997'
> 0.999943 446592
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
