Comment by gcanyon

1 year ago

As far as I can see, all the proposed solutions calculate the sums by doing division, and badly. This is in LiveCode, which I'm more familiar with than Python, but it's roughly twice as fast as the mod/div equivalent in LiveCode:

   repeat with i = 0 to 9
      put i * 10000 into ip
      repeat with j = 0 to 9
         put j * 1000 into jp
         repeat with k = 0 to 9
            put k * 100 into kp
            repeat with l = 0 to 9
               put l * 10 into lp
               repeat with m = 0 to 9
                  put i + j + k + l + m into R[ip + jp + kp + lp + m]
               end repeat
            end repeat
         end repeat
      end repeat
   end repeat

4 comments

gcanyon

masfuerte 1 year ago

I had a similar idea iterating over the previously calculated sums. I implemented it in C# and it's a bit quicker taking about 78% of the time to run yours.

    int[] sums = new int[100000];
    for (int i = 9; i >= 0; --i)
    {
        sums[i] = i;
    }
    int level = 10;
    while (level < 100000)
    {
        for (int p = level - 1; p >= 0; --p)
        {
            int sum = sums[p];
            for (int i = 9; i > 0; --i)
            {
                sums[level * i + p] = i + sum;
            }
        }
        level *= 10;
    }

gcanyon 1 year ago

Yep, I had a vague notion that I was doing too much work, but I was headed out the door so I wrote the naive/better than the original solution, benchmarked it quickly, and posted it before leaving. Yours also has the advantage of being scalable to ranges other than 1-100,000 without having to write more loop code.

zahlman 1 year ago

HyperTalk was the first programming language I taught myself as opposed to having an instructor; thanks for the nostalgia. Unfortunately it seems the LiveCode project has been idle for a few years now.

gcanyon 1 year ago

LiveCode is still a thing! They just released version 10 a bit ago. If you need to build standard-ish interface apps -- text, images, sliders, radio buttons, checkboxes, menus, etc. -- nothing (I've seen) compares for speed-of-delivery.
I use LC nearly every day, but I drool over Python's math libraries and syntax amenities.