[Jprogramming] Quora Problem

[james faure]

Lazy evaluation won't help you cut the processing time, but it does reduce the memory footprint to practically null, and the  lambda calculus involved opens the possibility for further optimisations. I guess I don't like having to think about optimizing my J code (if it makes it any less readable), and perhaps I'm overestimating the interpreter's opportunities for optimizing heavy brute force algorithms like this one.

________________________________
From: Programming <programming-bounces at forums.jsoftware.com> on behalf of 'Pascal Jasmin' via Programming <programming at jsoftware.com>
Sent: Sunday, May 20, 2018 1:06:09 AM
To: programming at jsoftware.com
Subject: Re: [Jprogramming] Quora Problem

This is more math, than eager/lazy evaluation issue.

Though if lazy (programmer), you might use solution for 10 and 100 to guess at 1M.

It's an extention of unique pairs that add up to a sum. <. at -: sum

The extention is a matter of avoiding duplicates while summing to 1M less the largest of the triplets, for eacch "largest triplet"



________________________________
From: Henry Rich <henryhrich at gmail.com>
To: programming at jsoftware.com
Sent: Saturday, May 19, 2018 6:41 PM
Subject: Re: [Jprogramming] Quora Problem



I don't think it's the interpreter's strategy that is at fault. odo
3#1e6 is asking the machine to create a set of 1e18 triplets, which you
will then presumably check to see if they add to 1e6, and then cast out
duplicates.  If somehow the interpreter could feed you the 1e18 values
one at a time, you still wouldn't get to a solution.

A better strategy is to read about partitions and generating functions
thereof.

Henry Rich

On 5/19/2018 5:58 PM, james faure wrote:
> This is a good example of a very annoying limitation of the current interpreter's eager evaluation strategy, in this case one is forced to come up with some sort of non-idiomatic iterative 'hack' to get a result. Concretely, I guess you're forced to use an accumulator with ^: or an explicit loop, which hurts.
>
> ________________________________
> From: Programming <programming-bounces at forums.jsoftware.com> on behalf of Skip Cave <skip at caveconsulting.com>
> Sent: Saturday, May 19, 2018 10:43 PM
> To: Programming at jsoftware.com
> Subject: [Jprogramming] Quora Problem
>
> Another interesting quora problem:
>
> How many distinct triplets have a sum of 1,000,000 (provided all numbers
> are integers and are positive)?
> <https://www.quora.com/qemail/track_click?al_imp=eyJ0eXBlIjogMzUsICJoYXNoIjogMTcxMDQ0NjU4Mn0%3D&al_pri=QuestionLinkClickthrough&aoid=oMo937UDzj8&aoty=2&aty=4&click_pos=1&ct=1526747413834671&et=103&id=62216bf7b30d40aea1d79bf4401c8317&request_id=289&src=1&st=1526747413838426&stories=2518686273&uid=bqluVqSeN78&v=0>
>
> The obvious straightforward solution would be to use the odometer verb:
>
> odo=: #: i.@(*/)
>
> 1e6=+/"1 odo 3#1e6
>
> |limit error: odo
>
> | 1000000=+/"1 odo 3#1000000
>
>
> Ooops. Unfortunately, I don't have near enough memory to use this approach.
>
> Any suggestions?
>
>
> Skip
>
>
>
> Skip Cave
> Cave Consulting LLC
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm


---
This email has been checked for viruses by AVG.
http://www.avg.com


----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm