An interesting programming challenge

[Ben Rubinstein]

On 10/04/2015 16:04, Colin Holgate wrote:
> Don’t you have to continue exploring, if the running total goes over 31? There may be a mixture of negative and positive numbers ahead, that will show up a different valid slice of numbers.
>
> I tried using Jerry’s approach under ActionScript, slightly modified to use arrays instead of strings, and it took just over 300 mS. Tried as Javascript too, and that seemed to be under 2 milliseconds!


Hi Colin,

No, that's the other challenge (the CleverCat one) - we're in a sub-thread 
talking about the metro populations one.  Depending on your email client, this 
may be more or less obvious!

But in regards to the CleverCat challenge, I had an interesting finding which 
I still can't understand - maybe the wisdom of this list will explain?

On 10/04/2015 02:36, Jerry Jensen wrote:
> Here’s my script that gave the right answer the first time too. It runs in
 > about 100 msec on a MacBookPro 2.6GHz i7 with Yosemite 10.10.3 and LC 6.7.4

Obviously, my attempt gave the right answer as well (otherwise I'd have kept 
my mouth shut - but when I then went back and looked at Jerry's code, it was 
very similar, but I smugly thought mine would probably be faster; because his 
solution involves a lot of cropping of the string, and mine doesn't change the 
string at all, instead making use of arrays which I always believe are 
insanely fast.

Then I timed mine, and the opposite is true: my function is about six times 
slower than Jerry's.

Looking at them more closely, this still seems surprising to me.  I think 
we're doing the same number of additions; the same number of loops.  I'm 
accessing the array twice as often as Jerry is accessing tRunningSum, but I 
would expect that to be more than offset by the effort of cropping the string.

Why is Jerry's function so much faster than mine?

function cleverCatJerry tRay
    local tSlices, tRunningSum, tLoopCount, tItem, tMsec
    put 0 into tSlices
    put 0 into tRunningSum
    put the number of items in tRay into tLoopCount
    repeat tLoopCount times
       put 0 into tRunningSum
       repeat for each item tItem in tRay
          add tItem to tRunningSum
          if tRunningSum >= 32 then add 1 to tSlices
       end repeat
       delete item 1 of tRay
    end repeat
    return tSlices
end cleverCatJerry

function cleverCatBen tNumbers
    local iNumSlices, aSumFromLoc, index, i
    put 0 into iNumSlices
    put empty into aSumFromLoc
    put 0 into index
    repeat for each item n in tNumbers
       add 1 to index
       repeat with i = 1 to index
          add n to aSumFromLoc[i]
          if aSumFromLoc[i] > 31 then add 1 to iNumSlices
       end repeat
    end repeat
    return iNumSlices
end cleverCatBen