An interesting programming challenge

[Ben Rubinstein]

On 10/04/2015 06:59, Geoff Canyon wrote:
 > This is stream-of-conscious code, but it produces the solution in under a
 > second. Spoiler returns:
...
 > There are 2^26 possible sets, or about 64 million. On the assumption that's
 > too many to brute force, I do the following:

On 10/04/2015 06:04, dunbarx wrote:
> I found a bug in my code. There is indeed a solution to the 100,000,000
> problem. I still needed a kluge to allow LC to process the way I did it in a
> reasonable amount of time.
>
> It took about three minutes on a Macbook Air, 1.86 GHz, OS 10.9.

Interesting.  Geoff obviously wins!  I didn't scroll down to read Geoff's 
intelligent dissection of the problem before having a go (if I had I wouldn't 
have attempted it!), and hence did attack it brute force; as it happens it 
found the answer within a few seconds, but took about 3 minutes (MacBook Pro 
2.7Ghz i7, doing other work, and allowing for me clicking OK when it first 
announced a solution was found) to complete the full exploration and not find 
any other solutions.  But it didn't need any kluges:

command exactSum tNumbers, tRequiredSum, tPath
    local n
    global gSolutions
    repeat until tNumbers = empty
       put first word of tNumbers into n
       delete first word of tNumbers
       if n = tRequiredSum then
          put tPath && n
          answer "Found one!"
          put tPath && n & return after gSolutions
       else if n < tRequiredSum then
          if tNumbers is not empty then
             exactSum tNumbers, tRequiredSum - n, tPath && n
          end if
          -- else n > required sum, no use to us here
       end if
    end repeat
end exactSum

(called with an empty 'path', i.e.
    global gSolutions
    put empty into gSolutions
    exactSum the uMetroPops of me, 100000000
)

Ben