I thought I'd check back and see how I solved this: but there's no trace in my saved APL or J files, so I suppose I must have done a brute-force one-liner on the original, smaller problem.
So I've just had another look, and today's pretty naive solution works in about 2 seconds and about 200 kB on my 2GB laptop; it's order O(n^2), so doesn't scale well, but is fine for the size of problem given. (I still think Problem 289, "Eulerian Cycles", is the hardest of the lot! see http://projecteuler.net/problem=289 I haven't yet solved it but I'm _not_ looking for spoilers. Perhaps it needs what Crossword Solvers call the PDM, the "Penny Drop Moment." Anyway, that's another topic.) Mike On 10/10/2011 12:56 AM, Nick Simicich wrote: > They increased the program space in Euler 73 to up to 12000 fractions. > Euler 73 requires that you determine how many exclusive numerators and > denominators there are between 1r3 and 1r2 given that the numerators and > denominators can be up to 12000. > > I'm trying to do this in limited space on a 32 bit netbook with not too much > extra memory, 2 gig total. > > Read about it here. http://projecteuler.net/problem=73 > > The sample space they give is up to 8. This makes it clear that I can't > just say ~. (>:1.8)%8, it has to be more like > > #~.(#~ (>&1r3 *.<&1r2)),%/~>:i.8 > > That works perfectly for 8 and 12, and when you try it with 10000 it runs > out of memory. With 12000 it gives a "limit error". I tried breaking the > problem into smaller tables, and it fails, out of memory when I try to > combine tables and nub them. > > I finally decided I could not keep separate tables, and looked at a 16 by 16 > table to get ideas. When I looked at (* (<&1r2 *.>&1r3))%/~>:i.16x I > didn't see anything, but when I looked at |:(* (<&1r2 *.>&1r3))%/~>:i.16x I > finally realized that any fraction that was reduced would come up somewhere > else. > > That led to this program: > > e73a =: verb define > count =. 0 > for_i.>:i. x: y do. > j=.<.i%3x > count =. count + +/i = {:"_1 ]2 x: (#~ (>&1r3 *.<&1r2)) > i%~j+>:i.((<.i%2x)-j) > end. > ) > > Essentially, I loop over 1<: i<: y where y is 8 or 16 for testing, and > 12000 for the "final answer" > > It builds a vector where the numbers in the vector are all extended > fractions, and the numerator is between about a third and a half of the > denominator. Then it trims that vector so that the survivors are greater > than 1/3 and less than 1/2. > > Finally, it looks at the denominators and counts all of the fractions that > were not reduced. > > I took a couple of half hearted attempts at making it into a one liner,and I > could not figure out how to. > > What stops me is that, well, I would have to assign the number to a variable > before using it in the expression. I could unfactor j and so forth, but, > well, if someone could point me to an online example, or explain, I'd > appreciate it. > > I've seen the item in the forum that applies the method I thought about > using, but they fit it into 32 bits: > > $~.;(<@#~>&(%3) *.<&0.5)@:%"0 1/~>:@i.10000 > > Now > > $~.;(<@#~>&(%3) *.<&0.5)@:%"0 1/~>:@i.12000 > > So far as I see it, well, I didn't understand how the "0 1 part worked, then > I tried this expression: > > ;"0 1/~>:@i.16 > > So if I wanted to do a lot of unneeded arithmetic, I could rewrite my deal > to use this to generate the half of the stuff I didn't care about. But then > I'd have to somehow figure out how to put the original denominator into the > boxes at the head, say. Instead of everything by everything, you only get > n(m max) by 1..m. But it is not at all clear whether that would have worked > for me, as I would have had to stash the original denominator or maybe use > the greatest denominator, if that worked. > > > - > Of course I can ride in the carpool lane, officer. Jesus is my constant > companion. > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
