Puzzle - RPL and others
05-07-2021, 02:56 AM
Post: #30
 Albert Chan Senior Member Posts: 2,687 Joined: Jul 2018
RE: Puzzle - RPL and others
Previous post Python code, translated to Lua.
Since Lua does not have infinite precision integer built-in, I just loop the digits for MOD.

As expected, speed improved quite a bit, about 5X. (LuaJIT 1.1.8)
I have confirmed n=60 has no solution ... in an hour.

Code:
do local gcd, recurse5 = require 'factor'.gcd function puzzle5(n)     local lst = {}     for i=1,n do lst[i] = i end     for i=1,n do lst[n+i] = (gcd(n,i) == 1) end     lst[floor(n/2)] = false     -- skip center     return recurse5(lst, n, 1, {}) end function recurse5(lst, n, k, X)        if k==n then return print(table.concat(X,',')) end     if k+k==n then X[k]=k; k=k+1 end -- skip center     local d, step = 0, k+k     for i=1,k-1 do d = (d*n + X[i]) % k end     d = k - d*n%k               -- first valid (mod k)     if k%2~=0 then              -- k is odd -> d odd too         if d%2==0 then d = d+k end     elseif k==2 then            -- mod4 restricted         d = (n%4~=0) and 4 or 2     else         local bad = ((n+k-d)%4 ~= 0)         if k%4 ~= 0 then if bad then d=d+k end         elseif bad  then return -- can't fix by +k         else step = k           -- step = 0 (mod4)         end            end     while d < n do         if lst[d] and lst[n+d] == lst[n+k] then             X[k] = d                         lst[d] = false      -- mark taken                  recurse5(lst, n, k+1, X)             lst[d] = d          -- restore         end         d = d + step     end end end

lua> puzzle5(8)
3,2,5,4,1,6,7
5,2,3,4,7,6,1
5,6,7,4,3,2,1

lua> puzzle5(10)
3,8,1,6,5,4,7,2,9

lua> puzzle5(14)
9,12,3,10,5,4,7,6,11,8,1,2,13
 « 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)