7
\$\begingroup\$

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
\$\endgroup\$
  • 6
    \$\begingroup\$ This 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). \$\endgroup\$ – Martin Ender May 30 '14 at 21:47
  • \$\begingroup\$ I wonder if I should allow C... \$\endgroup\$ – SoniEx2 May 31 '14 at 13:02
  • 1
    \$\begingroup\$ I'm now allowing the use of the C API because that may make it a bit more possible... \$\endgroup\$ – SoniEx2 Jun 2 '14 at 1:40
  • 1
    \$\begingroup\$ While 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. \$\endgroup\$ – Tal Jun 3 '14 at 5:54
  • 1
    \$\begingroup\$ @SoniEx2 so you're disqualifying all answers that don't help you specifically? That's not what this site is for. \$\endgroup\$ – Martin Ender Jun 3 '14 at 14:21
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is amazing! Hmm I wonder what happens if you shallow copy _G... \$\endgroup\$ – SoniEx2 Feb 7 '16 at 16:15
  • \$\begingroup\$ So I added a _G testcase. See if you can get that to work. \$\endgroup\$ – SoniEx2 Feb 11 '16 at 2:23
  • \$\begingroup\$ 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. \$\endgroup\$ – tehtmi Feb 11 '16 at 5:11
  • \$\begingroup\$ 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 \$\endgroup\$ – ATaco Nov 27 '16 at 22:17
  • \$\begingroup\$ @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. \$\endgroup\$ – tehtmi Dec 4 '16 at 20:16
1
\$\begingroup\$

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)"}))()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.