Well,
load 'strings'
f =. x:1%2+10000%~i.10001 NB. Generate equal-spaced floating fractions
between 1/3 and 1/2
k =. 12001>".(": f) rplc ' ';',';'r';',' NB. Find all numerators and
denominators less than 12001
counts all numerators and denominators below 12000 as separate entities.
Unfortunately, that
wasn't what the problem asked.
In order to count only rational fractions between 0.5 & 0.333 where both
the numerator and the denominatorhave values of 12000 or less, we need to
add one more line to the program that pairs the
numerator and denominator comparisons, and then "ands" them, to find
fractions that have
both the numerator and denominator below 12001.
+/ *./"1(10001 2) $ k NB. And values pairwise & sum.
That should get the correct answer. The whole thing takes less that 2
seconds to run on my machine.
Skip
Skip Cave
Cave Consulting LLC
On Sun, Jun 15, 2014 at 6:39 PM, Raul Miller <[email protected]> wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
