Page 1 of 1
Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 4:17 pm
by LuaWeaver
Your task is to implement the shortest and cleanest form of a stack in Lua. To have your code pass this challenge, you need to have a "push" method of the stack object, which accepts a value and adds it to the top of the stack, and a "pop" method of the stack object, which removes and returns the top value of the stack. Lastly, all stack objects should be different, meaning stack1==stack2 will ALWAYS be false, assuming stack1 and stack2 are different.
I already have a solution in mind, but I want to see how you guys think (and if you can get it shorter than me
).
Re: Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 4:38 pm
by Plu
Aren't these basically just table.insert, table.remove and the == operator?
You can't get much shorter than the built-in functions.
Re: Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 6:27 pm
by kikito
Here you go:
(I would prefer to make s local, but that would duplicate the size of my implementation)
Re: Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 9:05 pm
by vrld
Alternative implementation:
Code: Select all
function push(s,v) return function() return v,s end end
function pop(s) return (s or function() end)() end
Usage:
Code: Select all
s = push(push(push(nil, 1), 2), 3)
v,s = pop(s)
print(v) --> 3
v,s = pop(s)
print(v) --> 2
v,s = pop(s)
print(v) --> 1
v,s = pop(s)
print(v) --> nil
It's arguably very clean, because there is no way to change the stack without using the provided functions.
Re: Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 9:49 pm
by LuaWeaver
The specifications are "create an object", meaning you can use :push and :pop to modify the stack. s={} doesn't give the "push" and "pop" methods, and the above doesn't quite create an object, although it's certainly interesting.
Re: Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 9:53 pm
by slime
Why mandate explicit object methods for the API? That seems unnecessarily restrictive and a design choice rather than a requirement for a real stack implementation.
Re: Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 10:09 pm
by davisdude
Liking the Illuminati icon, slime!
I do think the object API is a bit unnecessary, but I guess it makes it more challenging. For the point of the challenge: do spaces and newlines / tabs count as "characters"?
Re: Challenge: Write the shortest implementation of a stack
Posted: Tue Sep 09, 2014 11:33 pm
by LuaWeaver
davisdude wrote:Liking the Illuminati icon, slime!
I do think the object API is a bit unnecessary, but I guess it makes it more challenging. For the point of the challenge: do spaces and newlines / tabs count as "characters"?
Yes. Also, the point of forcing the methods was to make it a challenge. As kikito said, "a={}" is technically a stack, so that'd rather ruin the challenge. It's not an obvious method I used to get it as short as I did, although it's obvious in retrospect.
Re: Challenge: Write the shortest implementation of a stack
Posted: Wed Sep 10, 2014 12:43 am
by kikito
I still find it's difficult to know what can and can't be done after the explanations.
I suggest you write an example main.lua which exemplifies the interface that the stacks should satisfy.
Re: Challenge: Write the shortest implementation of a stack
Posted: Fri Sep 12, 2014 1:31 am
by Inny
vrld wrote:Code: Select all
function push(s,v) return function() return v,s end end
function pop(s) return (s or function() end)() end
OMG. I love it.
In the same vein (without trying to code-golf the variable names):
Code: Select all
function Stack(stack)
stack = stack or {}
return function(value, length)
length = #stack + ((value == nil) and 0 or 1)
value, stack[length] = stack[length], value
return value
end
end
myStack = Stack()
myStack(1)
myStack(2)
print(myStack()) -- 2
myStack(3)
print(myStack()) -- 3
print(myStack()) -- 1
print(myStack()) -- nil
myStack(4)
print(myStack()) -- 4
Edit: Golf, 97 chars
Code: Select all
function S(s)s=s or {}return function(v,l)l=#s+(v==nil and 0 or 1);v,s[l]=s[l],v;return v end end