An interesting programming challenge

Geoff Canyon gcanyon at gmail.com
Fri Apr 10 10:48:33 EDT 2015


One thing that occurred to me about brute-forcing it: the sum of the entire
list is 129,161,818. If there is a set that adds up to 100,000,000, then
that means that the rest of the numbers have to add up to 129,161,818 -
 100,000,000 = 29,161,818. So to make the brute force consider fewer
options/be quicker, you could search for sets that add up to 29,161,818 and
bail out whenever your total goes over that number instead of 100,000,000.
Once you find such a set, take the numbers *not* in that set, and you're
done.

gc

On Fri, Apr 10, 2015 at 9:36 AM, Ben Rubinstein <benr_mc at cogapp.com> wrote:

> On 10/04/2015 13:47, dunbarx wrote:
>
>> My kluge took the same tack, that is to break the list into two parts, and
>> play one against the other.
>>
>> This came about weeks ago because the routine I used to find all
>> combinations of the 26 list items ran into a memory limit within LC that
>> was
>> less than the stated value of about 4GB (about 1GB, bug #15041).
>>
>
> I think the thing is that you can do recursion either depth-first or
> breadth-first.  Because we don't need to build up all the combinations (or
> even all the sums), but just test them as we go; and because some
> combinations never need to be explored (because they go over the desired
> sum before all the numbers have been added); if you do it depth-first, it
> doesn't use very much memory at all.
>
> Ben
>
>
> _______________________________________________
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your
> subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
>



More information about the use-livecode mailing list