you are viewing a single comment's thread.

view the rest of the comments →

[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (0 children)

I see. My solution is different. Each card follows some path through the deck and returns to its original position. Each card in a path takes the same number of shuffles to return to its original position. So the solution is the least common multiple of the lengths of all the paths in the deck.

local Luan = require "luan:Luan.luan"
local error = Luan.error
local range = Luan.range or error()
local Math = require "luan:Math.luan"
local min = Math.min or error()
local Number = require "luan:Number.luan"
local long = Number.long or error()
local Io = require "luan:Io.luan"
local print = Io.print or error()

local function lcm(x,y)
    local rtn = x
    while rtn % y ~= 0 do
        rtn = long(rtn + x)
    end
    return rtn
end

local function shuffles(n_cards,i_cut)

    local map = {}
    do
        local n = min( i_cut, n_cards - i_cut )
        for i in range( 0, n - 1 ) do
            local j = n_cards - 2*i
            map[ i_cut - i ] = j
            map[ n_cards - i ] = j - 1
        end
        if n == i_cut then
            for i in range( 1, n_cards - 2*i_cut ) do
                map[ i_cut + i ] = i
            end
        else
            for i in range( 1, i_cut - n ) do
                map[i] = i
            end
        end
    end

    local a = {}
    for i in range(1,n_cards) do
        a[i] = true
    end

    local rtn = 1
    for i in range(1,n_cards) do
        if a[i] then
            local n = 0
            local j = i
            while a[j] do
                a[j] = false
                n = n + 1
                j = map[j]
            end
            rtn = lcm(rtn,n)
        end
    end
    return rtn
end

print( shuffles(1002,101) )