Smallest Lua table copy

7

1

So I really like to mess with tables and shallow and deep copies and I can do it in 239 chars! I wonder if there's a shorter way to do it...

Rules:

  • It must be done in less than 239 chars.
  • You must set table.copy.shallow and table.copy.deep.
  • A deep copy must maintain recursion. (so if I had tx.t == tx, a deep copy must have ty.t == ty (where ty is a deep copy of tx))
  • You must make a local copy of every function you use. (for speed)
  • You must be able to pass in a custom recursion table with a metatable to override default copy behavior. (at least on the deep copy function, see examples here)
  • If needed, use metatables. If possible, abuse them.
  • It must work in Lua 5.1 and 5.2.
  • You may use load/loadstring.
  • You may use the C API.
  • Some input/output examples (actually unit test): https://gist.github.com/SoniEx2/7942bdd0658b719ab275

SoniEx2

Posted 2014-05-30T21:42:23.417

Reputation: 357

6This looks like a rare example of a good language-specific challenge to me, but especially with Lua I'm afraid your audience on here may be very small, so don't be disappointed if you get very few answers and some downvotes by people who don't like language-specific challenges (which are generally discouraged around here). – Martin Ender – 2014-05-30T21:47:39.797

I wonder if I should allow C... – SoniEx2 – 2014-05-31T13:02:44.147

1I'm now allowing the use of the C API because that may make it a bit more possible... – SoniEx2 – 2014-06-02T01:40:20.577

1While I'm not against specific language challenges, and thought of having a go at this, the "I can do it in X chars, see if you can beat me" part is a bit discouraging, as I have no reason to assume your solution isn't already the best one. – Tal – 2014-06-03T05:54:34.240

@Tal Yep, but I kinda want it smaller... – SoniEx2 – 2014-06-03T13:02:19.380

1@SoniEx2 so you're disqualifying all answers that don't help you specifically? That's not what this site is for. – Martin Ender – 2014-06-03T14:21:20.650

@m.buettner I'm not disqualifying all answers that don't help me, just the ones which aren't smaller than my code... (even if that means I'm asking for something impossible) – SoniEx2 – 2014-06-03T19:18:22.167

@SoniEx2 I don't see the difference. The limit seems arbitrary and spoils the fun for your participants. If you leave it out you're less likely to put people off, which could give you more submissions - which will try to beat each other, and are more likely than not beat your target line anyway. Especially if you tell him how short you got it without requiring them to best your score. Because someone might have an answer with 250 characters, but wouldn't post it, because it's disqualified anyway. But if he posted it, he might revisit it later, discover a new trick, and save 20 characters. – Martin Ender – 2014-06-03T19:27:33.233

So now that an answer has been accepted can we see the 239 char version? – Jerry Jeremiah – 2014-07-08T07:54:13.057

@JerryJeremiah Click the link that says "I can do it in 239 chars!" – SoniEx2 – 2014-07-09T16:44:30.657

Answers

2

235

Substantially based on the guts of SoniEx2's 239 answer.

local o,k,F=type,next,{}for n=0,2 do
F[n]=function(a,r,t,G)if n<1 or o{}~=o(a)then return a end
t={}r=r or{}r[a]=n<2 and t G=F[n%2]for x,y in k,a do
t[r[x]or G(x,r)]=r[y]or G(y,r)end
return t end end
table.copy={shallow=F[2],deep=F[1]}

The advantage comes from using the same function prototype for both functions. Instantiating the same function prototype with different upvalues allows it to fill both roles.

Ungolfed:

-- ungolfed
-- note that type and next must have local copies to meet the spec
local o, k, F = type, next, {}
for n = 0, 2 do
  -- F[0] will be the identity function
  -- F[1] will be table.copy.deep
  -- F[2] will be table.copy.shallow
  F[n] = function(a, r, t, G)
    -- a is the table input
    -- r is the optional "custom recursion table" that is required
    -- t and G are just locals
    -- the spec implies (but does not state) that the global environment shouldn't be polluted
    -- r will only be used by recursive calls

    -- if n < 1, this is F[0], so act is the identity
    -- o is type, o{} is "table"
    -- if a is not a table, just return it
    if n < 1 or o{} ~= o(a) then
      return a
    end

    -- t will be the copy
    t = {}

    -- r will be the map that remembers which tables in the original map to which tables in the copy
    -- or, if it is passed in, it is a table that controls the behavior of the copy
    r = r or {}

    -- F[0] doesn't each here
    -- F[1] must add t to the map
    -- F[2] must not add t to the map
    -- (adding false will not hurt F[2] -- only true values will be picked up below)
    -- (behavior may not be exactly as desired for shallow copy, but spec doesn't require this feature)
    r[a] = n < 2 and t

    -- this is the function we will call to copy members
    -- for F[1] table.copy.deep, this is F[1] itself
    -- for F[2] table.copy.shallow, this is F[0] the identity
    -- (for F[0], we never get this far)
    -- the byte count seems equivalent making this a local vs putting it
    -- in both places it is used, but this is probably more efficient
    G=F[n%2]

    -- loop over and copy members
    -- first try r (which will only have non-1 entries for tables in F[1])
    -- then try G
    -- note that instead of calling "pairs" as usual, we can observe that pairs(a)
    -- is defined to return next, a, nil -- we use these (with implicit nil) directly
    for x, y in k, a do
      t[r[x] or G(x,r)] = r[y] or G(y,r)
    end

    return t
  end
end

-- export the functions as required
table.copy = {
  shallow = F[2],
  deep = F[1]
}

Hopefully I understood the spec correctly. This passes the provided test cases and there is enough similarity in the construction that I'm reasonably sure it does the same thing.

Note -- Initially I didn't understand the part about the "custom recursion table", but I have edited my answer to support it.

Note 2 -- Improved answer. I've also decided that the provided reference solution in 239 bytes does not exactly match my understanding of how the custom recursion table ought to work, since it cannot be used to add false into the copy. However, I believe my solution works as well as the provided one.

tehtmi

Posted 2014-05-30T21:42:23.417

Reputation: 446

This is amazing! Hmm I wonder what happens if you shallow copy _G... – SoniEx2 – 2016-02-07T16:15:05.917

So I added a _G testcase. See if you can get that to work. – SoniEx2 – 2016-02-11T02:23:19.640

The reason your test case fails (for me) is that you're defining a global "G" after doing the copy, so the tables don't match anymore. It will pass if you declare "G" as a local. – tehtmi – 2016-02-11T05:11:14.123

You can golf a few bytes out, Any number followed by a letter where the letter doesn't match [a-eA-ExX] does not need whitespace. So n<1 or can become n<1or – ATaco – 2016-11-27T22:17:26.390

@ATaco: Thanks for pointing that out. I remember reading about this on lua-l. Unfortunately, I don't think it's appropriate for this answer because it doesn't work in PUC-Rio Lua 5.1.

– tehtmi – 2016-12-04T20:16:57.533

1

238 chars!

Turns out, it wasn't impossible!

loadstring(("local k,o,d=next,type dDif o{}~=o(a)thenBaAt={}r=r or{}r[a]=tCt[r[x]or d(x,r)]=r[y]or d(y,r)ABtAtable.copy={shallowDt={}Ct[x]=yABtA,deep=d}"):gsub("%u",{A=" end ",B=" return ",C=" for x,y in k,a do ",D="=function(a,r,t)"}))()

SoniEx2

Posted 2014-05-30T21:42:23.417

Reputation: 357