Puzzle - RPL and others

[Albert Chan]

I was unsatisfied with recurse3().
Although it added mod4 buckets, the search for duplicates is O(n), instead of previously O(1).



x stored the "running total" of the solution, we could use lst for something else.
This version use lst to track what were taken. (by marking the cell 0)
Lookup for duplicates now back to O(1).

New code is actually shorter than before. So, I added bucket, n/2.
Implementation is trivial. Just set center of list, range(n), to 0.

Code:

def puzzle4(n):
    lst = range(n)  # assume even n
    lst[n//2] = 0   # skip center
    return recurse4(lst, n)

Then, recurse4() just skip pass center, if found.

Code:

def recurse4(lst, n, k=1, x=0):
    if k==n: print x; return
    if k+k==n: x=n*x+k; k+=1    # skip center
    x, step = n*x, k+k
    d1 = k-x%k  # first valid (mod k)
    if k&1:     # odd k
        if not (d1&1): d1 += k  # d1 also odd
    elif k==2:
        d1 = 4 if (n&3) else 2
    else:       # even k >= 4
        bad = (n+k-d1) & 3
        if k&3: d1 += bad and k # d1 (mod4) = n+k
        elif bad: return        # can't fix by +k
        else: step = k          # step (mod4) = 0
    for d in xrange(d1, n, step):
        if not lst[d]: continue
        lst[d] = 0              # lst[d] mark taken
        recurse4(lst, n, k+1, x+d)
        lst[d] = d              # restore

>>> puzzle4(10)
381654729

Here is (lst, x) when first digit is 3:

[0, 1, 2, 0, 4, 0, 6, 7, 8, 9] 3
[0, 1, 2, 0, 0, 0, 6, 7, 8, 9] 34
[0, 1, 2, 0, 4, 0, 6, 7, 0, 9] 38
[0, 0, 2, 0, 4, 0, 6, 7, 0, 9] 381
[0, 0, 0, 0, 4, 0, 6, 7, 0, 9] 3812
[0, 0, 2, 0, 4, 0, 0, 7, 0, 9] 3816
[0, 0, 2, 0, 0, 0, 0, 7, 0, 9] 381654
[0, 0, 2, 0, 0, 0, 0, 0, 0, 9] 3816547
[0, 0, 0, 0, 0, 0, 0, 0, 0, 9] 38165472
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 381654729

With this, I confirmed there is no solution for 16 ≤ n ≤ 44
Interestingly, it take less time to run n=42, than n=40

n        time (sec), on my Toshiba A665 laptop
32      2
34      8
36      11
38      55
40      114
42      110
44      843 ≈ 14 minutes