[Challenge] Smallest table copy

classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[Challenge] Smallest table copy

Soni "They/Them" L.
So I have a challenge for you all: A table copy script in less than 270
chars

Rules:
1. It has to have table.copy.deep and table.copy.shallow
2. It has to be smaller than 270 chars
3. It has to handle the following tables:
============================================
local t1,t2,t3,t4,t5 = {},{},{},{},{}

t1[t2]=t3
t1[t3]=t1
t1[t1]=t1
t1[t4]=t3
t1["test"]="it works"
t1[0]=true
t1[true]=false
t1[false]=true
t1[math.huge]="yes"
t1[-math.huge]="no"
t2[t1]=t3
t3[t1]=t4
t4[t4]=t5
t5[t1],t5[t2],t5[t3],t5[t4],t5[t5]=t1,t2,t3,t4,t5
============================================
4. Deep copies must deepcopy table keys (you may use an argument to
enable/disable this one)
5. You are not required to copy metatables, but doing so will earn you
extra points

Finally, here is the 270 chars long script made: [1]
local k,o,n,s,d=pairs,type,"table"s,d=function(a,b)b={}for x,y in k(a)do
b[x]=y end return b end,function(a,r,t)t={}r=r or{}r[a]=t for x,y in
k(a)do if n==o(x)then x=r[x]or d(x,r)end if n==o(y)then y=r[y]or
d(y,r)end t[x]=y end return t end table.copy={shallow=s,deep=d}


[1] - This one might be a bit easier to read/understand:
https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.

On 07/05/2014 10:40, Thiago L. wrote:

> So I have a challenge for you all: A table copy script in less than
> 270 chars
>
> Rules:
> 1. It has to have table.copy.deep and table.copy.shallow
> 2. It has to be smaller than 270 chars
> 3. It has to handle the following tables:
> ============================================
> local t1,t2,t3,t4,t5 = {},{},{},{},{}
>
> t1[t2]=t3
> t1[t3]=t1
> t1[t1]=t1
> t1[t4]=t3
> t1["test"]="it works"
> t1[0]=true
> t1[true]=false
> t1[false]=true
> t1[math.huge]="yes"
> t1[-math.huge]="no"
> t2[t1]=t3
> t3[t1]=t4
> t4[t4]=t5
> t5[t1],t5[t2],t5[t3],t5[t4],t5[t5]=t1,t2,t3,t4,t5
> ============================================
> 4. Deep copies must deepcopy table keys (you may use an argument to
> enable/disable this one)
> 5. You are not required to copy metatables, but doing so will earn you
> extra points
>
> Finally, here is the 270 chars long script made: [1]
> local k,o,n,s,d=pairs,type,"table"s,d=function(a,b)b={}for x,y in
> k(a)do b[x]=y end return b end,function(a,r,t)t={}r=r or{}r[a]=t for
> x,y in k(a)do if n==o(x)then x=r[x]or d(x,r)end if n==o(y)then
> y=r[y]or d(y,r)end t[x]=y end return t end table.copy={shallow=s,deep=d}
>
>
> [1] - This one might be a bit easier to read/understand:
> https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131
Oh and I forgot to add:
Rule 6. No external libs.

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Scott Morgan
In reply to this post by Soni "They/Them" L.
On 07/05/14 14:40, Thiago L. wrote:
> So I have a challenge for you all: A table copy script in less than 270
> chars
...
> Finally, here is the 270 chars long script made: [1]
> local k,o,n,s,d=pairs,type,"table"s,d=function(a,b)b={}for x,y in k(a)do
> b[x]=y end return b end,function(a,r,t)t={}r=r or{}r[a]=t for x,y in
> k(a)do if n==o(x)then x=r[x]or d(x,r)end if n==o(y)then y=r[y]or
> d(y,r)end t[x]=y end return t end table.copy={shallow=s,deep=d}
>
> [1] - This one might be a bit easier to read/understand:
> https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131

Would it not be better to compare luac output than source size?

Also, run times?

Scott


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.

On 07/05/2014 11:34, Scott Morgan wrote:

> On 07/05/14 14:40, Thiago L. wrote:
>> So I have a challenge for you all: A table copy script in less than 270
>> chars
> ...
>> Finally, here is the 270 chars long script made: [1]
>> local k,o,n,s,d=pairs,type,"table"s,d=function(a,b)b={}for x,y in k(a)do
>> b[x]=y end return b end,function(a,r,t)t={}r=r or{}r[a]=t for x,y in
>> k(a)do if n==o(x)then x=r[x]or d(x,r)end if n==o(y)then y=r[y]or
>> d(y,r)end t[x]=y end return t end table.copy={shallow=s,deep=d}
>>
>> [1] - This one might be a bit easier to read/understand:
>> https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131
> Would it not be better to compare luac output than source size?
I can't shove luac output down IRC
>
> Also, run times?
Small and fast? Well I could give extra points for that...
>
> Scott
>
>

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Philipp Janda
In reply to this post by Soni "They/Them" L.
Am 07.05.2014 15:40 schröbte Thiago L.:
> So I have a challenge for you all: A table copy script in less than 270
> chars
>

239 bytes. Stole some of your tricks. Not extensively tested but seems
to work ...

Philipp


tc.lua (240 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.

On 07/05/2014 12:00, Philipp Janda wrote:

> Am 07.05.2014 15:40 schröbte Thiago L.:
>> So I have a challenge for you all: A table copy script in less than 270
>> chars
>>
>
> 239 bytes. Stole some of your tricks. Not extensively tested but seems
> to work ...
>
> Philipp
>
Uhh it doesn't handle replacing _G.pairs with nil... Also I don't like
that wrapper function nonsense... (table.copy.shallow(t,1) etc... bugs
and obfuscation...)

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Scott Morgan
In reply to this post by Philipp Janda
On 07/05/14 16:00, Philipp Janda wrote:
> Am 07.05.2014 15:40 schröbte Thiago L.:
>> So I have a challenge for you all: A table copy script in less than 270
>> chars
>>
>
> 239 bytes. Stole some of your tricks. Not extensively tested but seems
> to work ...

Ah, this show something interesting (Thiago == tcopy, Philipp == tcopy2):

$ luac -v ; uname -m
Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio
x86_64

$ luac -s -o tcopy.luac tcopy.lua
$ wc -m tcopy.lua*
271 tcopy.lua
536 tcopy.luac
807 total


$ luac -s -o tcopy2.luac tcopy2.lua
$ wc -m tcopy2.lua*
240 tcopy2.lua
557 tcopy2.luac
797 total

Shorter source, longer bytecode.

Was also surprised to see the bytecode take up more than the source in
general (something to do with 64-bit word sizes?)

Scott


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Philipp Janda
In reply to this post by Soni "They/Them" L.
Am 07.05.2014 17:13 schröbte Thiago L.:

>
> On 07/05/2014 12:00, Philipp Janda wrote:
>> Am 07.05.2014 15:40 schröbte Thiago L.:
>>> So I have a challenge for you all: A table copy script in less than 270
>>> chars
>>>
>>
>> 239 bytes. Stole some of your tricks. Not extensively tested but seems
>> to work ...
>>
>> Philipp
>>
> Uhh it doesn't handle replacing _G.pairs with nil...

That is true. Of course you could add a local one-letter alias for
`pairs` at the cost of 4 extra characters. While you are at it, replace
`pairs(a)` with `next,a ` which saves another byte. So it's about 242
bytes now.

> Also I don't like that wrapper function nonsense...
> (table.copy.shallow(t,1) etc... bugs and obfuscation...)

There are no wrapper functions. I just used one function to implement
the other via an extra boolean parameter (which you suggested in your
OP, btw.).

Both versions can't handle extra arguments correctly (my `shallow`, your
`deep`), and both are properly obfuscated. I optimized specifically for
code size which I thought was the challenge (obviously I misunderstood) ...

Of course, I wouldn't write nor use either version under normal
circumstances.

Philipp



Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.

On 07/05/2014 12:46, Philipp Janda wrote:

> Am 07.05.2014 17:13 schröbte Thiago L.:
>>
>> On 07/05/2014 12:00, Philipp Janda wrote:
>>> Am 07.05.2014 15:40 schröbte Thiago L.:
>>>> So I have a challenge for you all: A table copy script in less than
>>>> 270
>>>> chars
>>>>
>>>
>>> 239 bytes. Stole some of your tricks. Not extensively tested but seems
>>> to work ...
>>>
>>> Philipp
>>>
>> Uhh it doesn't handle replacing _G.pairs with nil...
>
> That is true. Of course you could add a local one-letter alias for
> `pairs` at the cost of 4 extra characters. While you are at it,
> replace `pairs(a)` with `next,a ` which saves another byte. So it's
> about 242 bytes now.
>
>> Also I don't like that wrapper function nonsense...
>> (table.copy.shallow(t,1) etc... bugs and obfuscation...)
>
> There are no wrapper functions. I just used one function to implement
> the other via an extra boolean parameter (which you suggested in your
> OP, btw.).
What I talked about was deep KEY copy...
So for a table where t[x]=y where x is a table, you could make it keep x
as it is or copy it by setting a boolean...

>
> Both versions can't handle extra arguments correctly (my `shallow`,
> your `deep`), and both are properly obfuscated. I optimized
> specifically for code size which I thought was the challenge
> (obviously I misunderstood) ...
>
> Of course, I wouldn't write nor use either version under normal
> circumstances.
>
> Philipp
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Daniel Stephens
In reply to this post by Soni "They/Them" L.
Your original submission can be shortened by making deep copy deal with
the 'is this a table' question on its input and using it always:

local k,o,n,s,d=pairs,type,"table"s,d=function(a,b)b={}for x,y in k(a)do
b[x]=y end return b end,function(a,r,t)if n~=o(a)then return a end
t={}r=r or{}r[a]=t for x,y in k(a)do x=r[x]or d(x,r)y=r[y]or
d(y,r)t[x]=y end return t end table.copy={shallow=s,deep=d}

Daniel.


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Daniel Stephens
Borrowing a trick from above, rearranging slightly, and some _G trickery
- down to 253

local k,o,n,d=next,type,"table"d=function(a,r,t)if n~=o(a)then return a
end t={}r=r or{}r[a]=t for x,y in k,a do x=r[x]or d(x,r)y=r[y]or
d(y,r)t[x]=y end return t end _G[n].copy={shallow=function(a,b)b={}for
x,y in k,a do b[x]=y end return b end,deep=d}


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.

On 07/05/2014 15:08, Daniel Stephens wrote:
> Borrowing a trick from above, rearranging slightly, and some _G
> trickery - down to 253
>
> local k,o,n,d=next,type,"table"d=function(a,r,t)if n~=o(a)then return
> a end t={}r=r or{}r[a]=t for x,y in k,a do x=r[x]or d(x,r)y=r[y]or
> d(y,r)t[x]=y end return t end _G[n].copy={shallow=function(a,b)b={}for
> x,y in k,a do b[x]=y end return b end,deep=d}
>
>
#"table" = 5
#"_G[n]" = 5

Really? (I also think the former may be faster, and more readable)

Also 246:
local k,o,n,d=next,type,"table"d=function(a,r,t)if n~=o(a)then return a
end t={}r=r or{}r[a]=t for x,y in k,a do t[r[x]or d(x,r)]=r[y]or
d(y,r)end return t end table.copy={shallow=function(a,b)b={}for x,y in
k,a do b[x]=y end return b end,deep=d}

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.
In reply to this post by Philipp Janda

On 07/05/2014 12:46, Philipp Janda wrote:

> Am 07.05.2014 17:13 schröbte Thiago L.:
>>
>> On 07/05/2014 12:00, Philipp Janda wrote:
>>> Am 07.05.2014 15:40 schröbte Thiago L.:
>>>> So I have a challenge for you all: A table copy script in less than
>>>> 270
>>>> chars
>>>>
>>>
>>> 239 bytes. Stole some of your tricks. Not extensively tested but seems
>>> to work ...
>>>
>>> Philipp
>>>
>> Uhh it doesn't handle replacing _G.pairs with nil...
>
> That is true. Of course you could add a local one-letter alias for
> `pairs` at the cost of 4 extra characters. While you are at it,
> replace `pairs(a)` with `next,a ` which saves another byte. So it's
> about 242 bytes now.
>
>> Also I don't like that wrapper function nonsense...
>> (table.copy.shallow(t,1) etc... bugs and obfuscation...)
>
> There are no wrapper functions. I just used one function to implement
> the other via an extra boolean parameter (which you suggested in your
> OP, btw.).
>
> Both versions can't handle extra arguments correctly (my `shallow`,
> your `deep`), and both are properly obfuscated. I optimized
> specifically for code size which I thought was the challenge
> (obviously I misunderstood) ...
When you say my deep can't handle extra arguments correctly: you're
right, it errors if you pass in anything but a table, nil or false! (the
latter 2 get replaced with a table)
It also lets you pass in your own table so you can get an oldkey->newkey
map!

Your shallow would just silently deepcopy everything... and only error
with an invalid 3rd argument...
>
> Of course, I wouldn't write nor use either version under normal
> circumstances.
>
> Philipp
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Daniel Stephens
In reply to this post by Soni "They/Them" L.
On 5/7/14, 11:12 AM, Thiago L. wrote:
> #"table" = 5
> #"_G[n]" = 5
>
> Really? (I also think the former may be faster, and more readable)
Doh! That's what I get for measuring the impact of several changes at
once -- I totally agree without a saving the _G thing is worthless.

Putting all the call work into the assigment expression is a nice
compaction too.


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Hans Hagen
In reply to this post by Daniel Stephens
On 5/7/2014 7:46 PM, Daniel Stephens wrote:
> Your original submission can be shortened by making deep copy deal with
> the 'is this a table' question on its input and using it always:
>
> local k,o,n,s,d=pairs,type,"table"s,d=function(a,b)b={}for x,y in k(a)do
> b[x]=y end return b end,function(a,r,t)if n~=o(a)then return a end
> t={}r=r or{}r[a]=t for x,y in k(a)do x=r[x]or d(x,r)y=r[y]or
> d(y,r)t[x]=y end return t end table.copy={shallow=s,deep=d}

one byte less:

local k,o,n,s,d=next,type,"table"s,d=function(a,b)b={}for x,y in k,a do
b[x]=y end return b end,function(a,r,t)if n~=o(a)then return a end
t={}r=r or{}r[a]=t for x,y in k,a do x=r[x]or d(x,r)y=r[y]or
d(y,r)t[x]=y end return t end table.copy={shallow=s,deep=d}

and a few less:

local k,o,s,d=next,type s,d=function(a,b)b={}for x,y in k,a do b[x]=y
end return b end,function(a,r,t)if"table"~=o(a)then return a end t={}r=r
or{}r[a]=t for x,y in k,a do x=r[x]or d(x,r)y=r[y]or d(y,r)t[x]=y end
return t end table.copy={shallow=s,deep=d}

(given that you're after less bytes of code)

-----------------------------------------------------------------
                                           Hans Hagen | PRAGMA ADE
               Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
     tel: 038 477 53 69 | voip: 087 875 68 74 | www.pragma-ade.com
                                              | www.pragma-pod.nl
-----------------------------------------------------------------

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.

On 07/05/2014 17:17, Hans Hagen wrote:

> On 5/7/2014 7:46 PM, Daniel Stephens wrote:
>> Your original submission can be shortened by making deep copy deal with
>> the 'is this a table' question on its input and using it always:
>>
>> local k,o,n,s,d=pairs,type,"table"s,d=function(a,b)b={}for x,y in k(a)do
>> b[x]=y end return b end,function(a,r,t)if n~=o(a)then return a end
>> t={}r=r or{}r[a]=t for x,y in k(a)do x=r[x]or d(x,r)y=r[y]or
>> d(y,r)t[x]=y end return t end table.copy={shallow=s,deep=d}
>
> one byte less:
>
> local k,o,n,s,d=next,type,"table"s,d=function(a,b)b={}for x,y in k,a
> do b[x]=y end return b end,function(a,r,t)if n~=o(a)then return a end
> t={}r=r or{}r[a]=t for x,y in k,a do x=r[x]or d(x,r)y=r[y]or
> d(y,r)t[x]=y end return t end table.copy={shallow=s,deep=d}
>
> and a few less:
>
> local k,o,s,d=next,type s,d=function(a,b)b={}for x,y in k,a do b[x]=y
> end return b end,function(a,r,t)if"table"~=o(a)then return a end
> t={}r=r or{}r[a]=t for x,y in k,a do x=r[x]or d(x,r)y=r[y]or
> d(y,r)t[x]=y end return t end table.copy={shallow=s,deep=d}
>
> (given that you're after less bytes of code)
>
> -----------------------------------------------------------------
>                                           Hans Hagen | PRAGMA ADE
>               Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
>     tel: 038 477 53 69 | voip: 087 875 68 74 | www.pragma-ade.com
>                                              | www.pragma-pod.nl
> -----------------------------------------------------------------
>
I managed to get 242 bytes/chars... I could probably do less tho...
local k,o,d=next,type d=function(a,r,t)if"table"~=o(a)then return a end
t={}r=r or{}r[a]=t for x,y in k,a do t[r[x]or d(x,r)]=r[y]or d(y,r)end
return t end table.copy={shallow=function(a,b)b={}for x,y in k,a do
b[x]=y end return b end,deep=d}

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Paul K
> I managed to get 242 bytes/chars... I could probably do less tho...
> local k,o,d=next,type d=function(a,r,t)if"table"~=o(a)then return a end t={}r=r

replace "table" with o{} to save few more bytes...

Paul.

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Daniel Stephens
On 5/7/14, 2:19 PM, Paul K wrote:
>> I managed to get 242 bytes/chars... I could probably do less tho...
>> local k,o,d=next,type d=function(a,r,t)if"table"~=o(a)then return a end t={}r=r
> replace "table" with o{} to save few more bytes...
>
> Paul.
>
It's actually shorter to keep the constant string but not assign type to
a local, since it's only called once - at 238:

local k,d=next d=function(a,r,t)if"table"~=type(a)then return a end
t={}r=r or{}r[a]=t for x,y in k,a do a[r[x]or d(x,r)]=r[y]or d(y,r)end
return t end table.copy={shallow=function(a,b)b={}for x,y in k,a do
b[x]=y end return b end,deep=d}


Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Coroutines
In reply to this post by Paul K
On Wed, May 7, 2014 at 2:19 PM, Paul K <[hidden email]> wrote:
>> I managed to get 242 bytes/chars... I could probably do less tho...
>> local k,o,d=next,type d=function(a,r,t)if"table"~=o(a)then return a end t={}r=r
>
> replace "table" with o{} to save few more bytes...

Well, your message triggered GMail's spam filter so I imagine you're
doing something right :o)

Reply | Threaded
Open this post in threaded view
|

Re: [Challenge] Smallest table copy

Soni "They/Them" L.
In reply to this post by Daniel Stephens

On 07/05/2014 18:52, Daniel Stephens wrote:

> On 5/7/14, 2:19 PM, Paul K wrote:
>>> I managed to get 242 bytes/chars... I could probably do less tho...
>>> local k,o,d=next,type d=function(a,r,t)if"table"~=o(a)then return a
>>> end t={}r=r
>> replace "table" with o{} to save few more bytes...
>>
>> Paul.
>>
> It's actually shorter to keep the constant string but not assign type
> to a local, since it's only called once - at 238:
>
> local k,d=next d=function(a,r,t)if"table"~=type(a)then return a end
> t={}r=r or{}r[a]=t for x,y in k,a do a[r[x]or d(x,r)]=r[y]or d(y,r)end
> return t end table.copy={shallow=function(a,b)b={}for x,y in k,a do
> b[x]=y end return b end,deep=d}
>
>
Not sure why you're doing a[r[x]or d(x,r)]=r[y]or d(y,r)... it should be
t[r[x]or d(x,r)]=r[y]or d(y,r)...

But I think we have a winner, with 238 chars:

local k,d=next d=function(a,r,t)if"table"~=type(a)then return a end
t={}r=r or{}r[a]=t for x,y in k,a do t[r[x]or d(x,r)]=r[y]or d(y,r)end
return t end table.copy={shallow=function(a,b)b={}for x,y in k,a do
b[x]=y end return b end,deep=d}

Or a bug free version, with 239 chars:

local k,o,d=next,type d=function(a,r,t)if o{}~=o(a)then return a end
t={}r=r or{}r[a]=t for x,y in k,a do t[r[x]or d(x,r)]=r[y]or d(y,r)end
return t end table.copy={shallow=function(a,b)b={}for x,y in k,a do
b[x]=y end return b end,deep=d}

I wonder if less than 239 chars is possible (maybe with some
load()/loadstring() trickery?)

12