Puzzle - RPL and others
05-05-2021, 06:29 PM
Post: #27
 Albert Chan Senior Member Posts: 2,686 Joined: Jul 2018
RE: Puzzle - RPL and others
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
 « Next Oldest | Next Newest »

 Messages In This Thread Puzzle - RPL and others - Gene - 04-22-2021, 06:55 PM RE: Puzzle - RPL and others - Valentin Albillo - 04-22-2021, 11:52 PM RE: Puzzle - RPL and others - rprosperi - 04-23-2021, 04:21 PM RE: Puzzle - RPL and others - EdS2 - 04-23-2021, 07:30 AM RE: Puzzle - RPL and others - Dave Britten - 04-23-2021, 12:06 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:17 AM RE: Puzzle - RPL and others - ijabbott - 04-23-2021, 03:57 PM RE: Puzzle - RPL and others - Albert Chan - 04-23-2021, 04:08 PM RE: Puzzle - RPL and others - Albert Chan - 04-27-2021, 12:14 PM RE: Puzzle - RPL and others - Didier Lachieze - 04-23-2021, 04:23 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:05 PM RE: Puzzle - RPL and others - C.Ret - 04-24-2021, 04:40 PM RE: Puzzle - RPL and others - C.Ret - 04-25-2021, 09:25 AM RE: Puzzle - RPL and others - Claudio L. - 04-26-2021, 04:56 PM RE: Puzzle - RPL and others - 3298 - 04-27-2021, 08:16 PM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 02:33 AM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 03:30 AM RE: Puzzle - RPL and others - 3298 - 04-28-2021, 10:14 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 03:25 AM RE: Puzzle - RPL and others - Allen - 04-28-2021, 08:45 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 05:16 PM RE: Puzzle - RPL and others - Allen - 04-29-2021, 07:03 PM RE: Puzzle - RPL and others - C.Ret - 05-02-2021, 06:40 AM RE: Puzzle - RPL and others - 3298 - 05-03-2021, 03:43 PM RE: Puzzle - RPL and others - Albert Chan - 05-04-2021, 03:29 AM RE: Puzzle - RPL and others - 3298 - 05-04-2021, 06:48 AM RE: Puzzle - RPL and others - Albert Chan - 05-05-2021 06:29 PM RE: Puzzle - RPL and others - 3298 - 05-06-2021, 04:24 PM RE: Puzzle - RPL and others - Albert Chan - 05-06-2021, 09:09 PM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 10:35 AM RE: Puzzle - RPL and others - 3298 - 05-07-2021, 04:17 PM RE: Puzzle - RPL and others - Albert Chan - 05-09-2021, 01:21 AM RE: Puzzle - RPL and others - 3298 - 05-09-2021, 01:39 PM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 03:57 AM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 02:56 AM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 05:13 PM RE: Puzzle - RPL and others - 3298 - 05-10-2021, 08:23 PM RE: Puzzle - RPL and others - Albert Chan - 05-11-2021, 11:58 AM RE: Puzzle - RPL and others - 3298 - 05-11-2021, 02:14 PM RE: Puzzle - RPL and others - John Keith - 05-11-2021, 03:55 PM RE: Puzzle - RPL and others - ijabbott - 05-11-2021, 10:37 PM RE: Puzzle - RPL and others - Albert Chan - 05-13-2021, 11:38 PM

User(s) browsing this thread: 1 Guest(s)