Having trouble getting a program running

[kikito]

You can trade loops for memory. See how I use the "existing" table on the following example.

Code: Select all

function allDifferent(t)
  local existing = {} -- this table holds the values that you have already found, like this: existing[v]=true
  for _,v in ipairs(t) do -- can also use pairs here - more flexible, less fast
    if(existing[v]) then return false end
    existing[v]=true
  end
  return true
end

allDifferent({1,2,3,4,5,6,7,8,9}) -- returns true
allDifferent({1,2,3,1,2,3,1,2,3}) -- returns false when it finds the second "1"

EDIT: Ruby isn't lua

[thelinx]

why do all of the LÖVE smileys have ears?

Why, master of derailing, those are arms!

[Jasoco]

Arms? I thought they were ears too!

Also, when you say "unequal", what do you mean? That you want to make sure every item is a different value? Yeah, nested FOR loops would work. Something like...

Code: Select all

local v
local f = false
for i, a in pairs(tablename) do
  v = a
  for j, b in pairs(tablename)
    if i ~= j then
      if v == b then
        f = true
        break
      end
    end
  end
end
if f == false then
  --SUCCESS... I guess
end

I have NOT tested this. So feel free to laugh at my coding horribleness. And feel free to put it in a function that returns true or false or whatever other info you want.

[Robin]

Arms? I thought they were ears too!

I thought it was sarcasm!

@code: I think that one makes Daddy Big O cry.

If kikito's version works, it would be much better, O(n) I think. Note that it only works for equality testing, not equivalence testing. Pass it {{1}, {1}} and it would return False.

[vrld]

If kikito's version works, it would be much better, O(n) I think.

O(n logn) actually, as the

Code: Select all

if (existing[v]) then return false

needs to find the key (which can be done in O(logn)). Still faster than two nested loops though.
I also find kikito's version a lot more readable, which is why I would choose his approach.

[Robin]

Hm. I thought hash-lookup was constant time?

[vrld]

Oops, my bad. I thought they were saved in some kind of tree. You are right.

[kikito]

Oops, my bad. I thought they were saved in some kind of tree. You are right.

I only use tress for dealing with multidimensonal stuff But yes, it's O(n) instead of O(n²). As Robin says, it doesn't deal with multi-dimensional arrays, but I didn't seem to me that was a requirement.

[Robin]

As Robin says, it doesn't deal with multi-dimensional arrays, but I didn't seem to me that was a requirement.

I made a mistake btw, passing it {{1}, {1}} returns true, because they are two different tables.

And while Jasoco's implementation has the same limitation, it would be easier to implement. But if you don't want to look at the contents of tables, the smart way is the way to go.

[vrld]

If you compare tables of the same kind (i.e. same metatable), have a look at __eq: http://lua-users.org/wiki/MetatableEvents