Function to check for repetitive arrays

Solar2D Lua Language
#1

** EDITED AGAIN - sorry I seem to be having trouble with the lua block codes, it’s being interpreted as one line of code which clearly it isn’t, so I’ve removed the lua tags - if anyone knows how to correct this problem I’ll reinstate them **

Whenever I see other people’s code I’m always amazed at how elegant and concise it is, so I was wondering if there was a better way to write this function. My current code feels very long-winded and as a coding newbie I get a lot by learning from other’s coding styles.

What I need the function to do is check for repetition in a simple array. The contents might be numbers, strings or references to tables. There’s no possibility of having to confirm that the tables are identical without having identical references, which simplifies things a little bit.

Just to clarify what I mean by repetition, it should return true if the table consists of exactly repetitive sequences, and false otherwise.

E.g. {0,1,0,1} returns true but {0,1,0,1,2} returns false. Even though the second table has some repetition, it is not wholly repetitive.

My current function seems to work ok, and it’s not in a performance critical section of my game, but I thought it might be an interesting exercise. I may be wrong of course!

function checkForRepetition( tab )

    

    if type( tab ) ~= “table” then print(“Invalid input for repetition check”) end

    local max = #tab

    – takes a table of values and checks if they’re all the same

    local function checkSame(arg)

        

        for i = 1, (#arg-1) do

            print(arg[i], arg[i + 1])

            if arg[i] ~= arg[i + 1] then

                return false

            end

        end

        return true

        

    end

    – checks for periodic repetition and returns true if it finds it

    local function subDivisorCheck( start, divisor)

        

        print(“checking start”, start, “divisor”, divisor)

        local i = start

        local coll = {}

        while i <= max do

            coll[#coll + 1] = tab[i]

            i = i + divisor

        end

        return checkSame(coll)

        

    end

    – default assumption is that there’s no repetition

    

    local isThereRepetition = false

    

    – check each possible sub-sequence length (called a divisor) e.g. for length 12 check 2,3,4,6

    local maxDivisor = math.floor(max/2)

    local divisor

    for divisor = 1, maxDivisor do

        local divisorRepetition = true

        for start = 1, divisor do

            if not subDivisorCheck(start, divisor) then

                divisorRepetition = false

            end

        end

        if divisorRepetition then

            print(“Yes there is repetition”)

            return true

        end

        

    end

    print(“There is no repetition”)

    return false

    

end

#2

For starters we need to know more about the sequence:

Is there a limit to the length of the “sub-sequence”, or the number of repetitions?

Cheers,

Thomas

#3

Ditto on the last question.

If you need arbitrary subsequences, I guess I’d try adapting one of these: Algorithm to find all the exact divisors of a given integer

You only need to recompute that when your length changes. If your length did have a limit, you could even precompute these and save them to a file.

Some lengths will be prime, and won’t have any duplication.

Otherwise, I guess just do something like (untested!):

local TryDivisor (t, n, divisor) for i = 1, divisor do local first = t[i] for j = i + divisor, n, divisor do -- start at second entry, skip ahead by divisor if t[j] ~= first then return false end end end return true end function checkForRepetition (tab) local max = #tab local divisors = GetDivisors(max) -- memoized, as mentioned above for i = 1, #Divisors do if TryDivisor(tab, max, Divisors[i]) then return true end end return false end

I guess these arrive fully-formed, or can do so? If so, then you definitely shouldn’t check per-frame, but only on arrival or on even on demand.

Also, building a new closure ( checkSame ) on every call certainly won’t do your performance any favors. Doesn’t look like you’re capturing any upvalues anyhow.

#4

Thanks for the replies all, I’ve had trouble posting my code because the lua blocks don’t seem to be working for me (which is strange, I’ve been able to use them before).

To answer @thomas6 's question, the function should work for any length of repeated sequence.  Basically, if the table could be expressed as being the same as a shorter table repeated n times (where n is an integer > 1) then the function should return true.

I suppose I should have also added that I’m not dealing with particularly long tables here - maximum 20 items in them.  And it’s not performance critical code (certainly not running it every frame, just a few times before a level), so getting divisors should be a simple matter of:

[lua]

function getDivisors( max )

   local divisor = math.floor(max / 2)

   local tab = {}

   for i = 1, divisor do

      if ( max / i ) = math.floor( max / i) then

         tab[#tab + 1] = i

      end

   end
  return tab

end

[/lua]

Or creating a lookup table.

@StarCrunch - I don’t follow your reference to building a new closure and the impact on performance.  Closures are a concept I haven’t fully grasped (I told you I was a newbie) even though I’ve read the relevant bit of “Programming in Lua” multiple times.  Are you saying it’s better for checkSame to sit outside the function?

#5

Oh, whoops, I misread the above as “it’s in a performance critical section of my game” (no “not”)!  :o 

It’s probably not a big deal either way, then.

#6

This is what I ended up with, a variant on StarCrunch’s suggestion.  I don’t bother doing anything complicated with getting divisors, I just add in an extra check (does max%divisor == 0) before passing a prospective divisor to the tryDivisor function.  Much shorter / more elegant than my original, thank you!

[lua]

local function tryDivisor(t, n, divisor)

    local i

    for i = 1, divisor do

        local first = t[i]

        local j

        for j = i + divisor, n, divisor do – start at second entry, skip ahead by divisor

            if t[j] ~= first then

                return false

            end

        end

    end

    

    return true

end

function checkForRepetition (tab)

    local max = #tab

    local maxDivisor = math.floor(max/2)

    local divisor

    for divisor = 1, maxDivisor do

        if (max%divisor == 0) and tryDivisor(tab, max, divisor) then

            return true

        end

    end

    return false

end

[/lua]

#7

For starters we need to know more about the sequence:

Is there a limit to the length of the “sub-sequence”, or the number of repetitions?

Cheers,

Thomas

#8

Ditto on the last question.

If you need arbitrary subsequences, I guess I’d try adapting one of these: Algorithm to find all the exact divisors of a given integer

You only need to recompute that when your length changes. If your length did have a limit, you could even precompute these and save them to a file.

Some lengths will be prime, and won’t have any duplication.

Otherwise, I guess just do something like (untested!):

local TryDivisor (t, n, divisor) for i = 1, divisor do local first = t[i] for j = i + divisor, n, divisor do -- start at second entry, skip ahead by divisor if t[j] ~= first then return false end end end return true end function checkForRepetition (tab) local max = #tab local divisors = GetDivisors(max) -- memoized, as mentioned above for i = 1, #Divisors do if TryDivisor(tab, max, Divisors[i]) then return true end end return false end

I guess these arrive fully-formed, or can do so? If so, then you definitely shouldn’t check per-frame, but only on arrival or on even on demand.

Also, building a new closure ( checkSame ) on every call certainly won’t do your performance any favors. Doesn’t look like you’re capturing any upvalues anyhow.

#9

Thanks for the replies all, I’ve had trouble posting my code because the lua blocks don’t seem to be working for me (which is strange, I’ve been able to use them before).

To answer @thomas6 's question, the function should work for any length of repeated sequence.  Basically, if the table could be expressed as being the same as a shorter table repeated n times (where n is an integer > 1) then the function should return true.

I suppose I should have also added that I’m not dealing with particularly long tables here - maximum 20 items in them.  And it’s not performance critical code (certainly not running it every frame, just a few times before a level), so getting divisors should be a simple matter of:

[lua]

function getDivisors( max )

   local divisor = math.floor(max / 2)

   local tab = {}

   for i = 1, divisor do

      if ( max / i ) = math.floor( max / i) then

         tab[#tab + 1] = i

      end

   end
  return tab

end

[/lua]

Or creating a lookup table.

@StarCrunch - I don’t follow your reference to building a new closure and the impact on performance.  Closures are a concept I haven’t fully grasped (I told you I was a newbie) even though I’ve read the relevant bit of “Programming in Lua” multiple times.  Are you saying it’s better for checkSame to sit outside the function?

#10

Oh, whoops, I misread the above as “it’s in a performance critical section of my game” (no “not”)!  :o 

It’s probably not a big deal either way, then.

#11

This is what I ended up with, a variant on StarCrunch’s suggestion.  I don’t bother doing anything complicated with getting divisors, I just add in an extra check (does max%divisor == 0) before passing a prospective divisor to the tryDivisor function.  Much shorter / more elegant than my original, thank you!

[lua]

local function tryDivisor(t, n, divisor)

    local i

    for i = 1, divisor do

        local first = t[i]

        local j

        for j = i + divisor, n, divisor do – start at second entry, skip ahead by divisor

            if t[j] ~= first then

                return false

            end

        end

    end

    

    return true

end

function checkForRepetition (tab)

    local max = #tab

    local maxDivisor = math.floor(max/2)

    local divisor

    for divisor = 1, maxDivisor do

        if (max%divisor == 0) and tryDivisor(tab, max, divisor) then

            return true

        end

    end

    return false

end

[/lua]