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 ).
Challenge: Write the shortest implementation of a stack
Challenge: Write the shortest implementation of a stack
"your actions cause me to infer your ego is the size of three houses" -finley
Re: Challenge: Write the shortest implementation of a stack
Aren't these basically just table.insert, table.remove and the == operator? You can't get much shorter than the built-in functions.
- kikito
- Inner party member
- Posts: 3153
- Joined: Sat Oct 03, 2009 5:22 pm
- Location: Madrid, Spain
- Contact:
Re: Challenge: Write the shortest implementation of a stack
Here you go:
(I would prefer to make s local, but that would duplicate the size of my implementation)
Code: Select all
s={}
When I write def I mean function.
Re: Challenge: Write the shortest implementation of a stack
Alternative implementation:
Usage:
It's arguably very clean, because there is no way to change the stack without using the provided functions.
Code: Select all
function push(s,v) return function() return v,s end end
function pop(s) return (s or function() end)() end
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
Re: Challenge: Write the shortest implementation of a stack
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.
"your actions cause me to infer your ego is the size of three houses" -finley
- slime
- Solid Snayke
- Posts: 3166
- Joined: Mon Aug 23, 2010 6:45 am
- Location: Nova Scotia, Canada
- Contact:
Re: Challenge: Write the shortest implementation of a stack
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
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"?
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"?
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
Re: Challenge: Write the shortest implementation of a stack
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.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"?
"your actions cause me to infer your ego is the size of three houses" -finley
- kikito
- Inner party member
- Posts: 3153
- Joined: Sat Oct 03, 2009 5:22 pm
- Location: Madrid, Spain
- Contact:
Re: Challenge: Write the shortest implementation of a stack
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.
I suggest you write an example main.lua which exemplifies the interface that the stacks should satisfy.
When I write def I mean function.
Re: Challenge: Write the shortest implementation of a stack
OMG. I love it.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
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
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
Who is online
Users browsing this forum: No registered users and 3 guests