Puzzle - RPL and others

[Albert Chan]

(04-27-2021 08:16 PM)3298 Wrote:  Small note on the theory side: I identified another reason for checking divisibility first, like Claudio and I did: it has a higher rejection rate than the duplicate digits check - and as you probably know it's usually prudent to run the more strict check first, giving you a higher chance to skip the other one altogether for a quicker rejection. (Unless the check with the higher rejection rate is significantly slower, that is. But in this case it's definitely not.)

There is another side to this.
If we did check divisibility first, then we need to check for duplicates, an O(n) operation.

However, if we have O(1) array access, we could "check" duplicates in O(1)
I tried this in Python. For n=10, this simple version is 60% faster.

At the end of the day, both ways generate same test cases (albeit not same order)

Code:

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

>>> recurse(range(10), 10)
381654729

>>> recurse(range(14), 14) # = 9c3a5476b812d₁₄
559922224824157

Update: restricting odd digits odd, even digits even, speed up a lot !
Not bad for a 3 bytes ", 2" patch. See the numbers:

For n=10, mod calculations reduced from 1580 to 424, factor of 3.73
For n=14, mod calculations reduced from 29045 to 4422, factor of 6.57

Reduced search space is not quite as much.
For n=10, recursive calls reduced from 311 to 156, factor of 1.99
For n=14, recursive calls reduced from 3928 to 1085, factor of 3.62

Overall, speed factor = 2.42X for n=10, 4.25X for n=14.