I generally avoid project euler, because I do not like working under its constraint on disclosure. So I'm pleased when something leaks out that I can play with. But I also try to live within the implied spirit of the contest, so I'm not going to release my code.
Still: a quick calculation suggests that J's floating point representation is adequate for this problem (and gives a 30x speed improvement over use of rationals). Also, a trivial approach seems plenty adequate here Thanks, -- Raul On Sun, Jun 15, 2014 at 7:07 PM, David Lambert <[email protected]> wrote: > On 15/06/2014 16:59, Jon Hough wrote: >> >>> >Another Project Euler... (apologies) >>> >#73http://projecteuler.net/problem=73 >>> >>> >I found this one more tricky than it first seems. >>> >My attempt fails. >>> >My reasoning of solution. Trying to find all reduced fractions with >>> denominator and numerator in range 1... 12000 that are greater than 1/3 but >>> less than 1/2.The most naive way would be to make a 12000x12000 grid of >>> fractions, nubbing out duplicates. >>> >> > Note 'Naive solution to PE 73' > Generate all the fractions one denominator at a time > using low memory. The program exceeds the one > minute time requirement even on your new computer. > > Method: insert a verb into a list of denominators. > The verb is necessarily a dyad. y retains the list > of unique fractions, x (a scalar) is the next > denominator to evaluate. Therefor the verb could be > a hook that generates new fractions of one argument > which it appends and nubs with the other, producing > a "current result". We'll start with a "current > result" of 0, removed as a post-processing step. > ) > > Filter=: (#~`)(`:6) > odd=: 2&| > odd Filter i.5 > 1 3 > > NB. generate the denominators and initial solution of 0 > NB. Accumulating the results from few to many decreases > NB. the computational work. > data=: i.@:(_1x&-) > data 8 > 8 7 6 5 4 3 2 1 0 > > numerators=: >.@:-: (] + i.@:-) <.@:(1r3&*) > > boxdraw_j_ 1 > > numerators&.> 8 14 > +---+-----+ > > |2 3|4 5 6| > +---+-----+ > fractions =: %~ numerators > > ~.@:(, fractions)~/ data 8 > 0 1r3 1r4 1r5 2r5 2r7 3r7 3r8 > > (1r3&< *. <&1r2)Filter ~.@:(, fractions)~/ data 8 > 2r5 3r7 3r8 > > # (1r3&<*.<&1r2)Filter~.@:(, fractions)~/ data 8 > 3 > > > NB. watch progress > > show=: [ smoutput > > # (1r3&<*.<&1r2)Filter~.@:(, fractions@:show)~/ data 500 > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
