Puzzle - RPL and others

[Albert Chan]

(04-28-2021 10:14 PM)3298 Wrote:  

(04-28-2021 03:30 AM)Albert Chan Wrote:  restricting odd digits odd, even digits even, speed up a lot !

I was going to say that this doesn't work for odd bases, but as we just found out, we can reject those before we get here, since they can't have solutions anyway...

This optimization actually force code to quit early, for odd base.
For odd base, even digits must have same parity as the digit before it.

odd * odd = odd
even * odd = even

Quote:But thinking about why it wouldn't apply to odd bases pushed me into another idea building on this: the shortcut works for any number that divides the base. You already applied this with the number 5 in base 10 ... the fifth position has to be 5, as it is the only base-10 digit divisible by 5.

Yes, bucket idea work, but code would get complicated ... fast.

Also, gain may not be what you expected.

Example, with even base, we already have 2 factors.
Odd digits odd, even digits even use the factor 2.
At the cost of slight complexity, we can add the other factor: base/2

Code:

def recurse2(lst, n, k=1, x=0):
    if k+k==n: return recurse2(lst, n, k+1, n*x+k)
    if k==n: print x; return
    x, d0 = n*x, lst[k]
    for i in xrange(k, n, 2):
        d = lst[i]
        if d+d==n or (x+d)%k: continue
        lst[i] = d0
        recurse2(lst, n, k+1, x+d)
        lst[i] = d      # restore

Code work the same way, just faster

>>> recurse2(range(10), 10)
381654729

Compare against recurse(), recurse2() was expected to cut down search time.
But, numbers are not impressive (factor also closely matched speed-up ratio)

For n=10, recursive calls reduced from 156 to 131, factor of 1.19
For n=14, recursive calls reduced from 1085 to 790, factor of 1.37