Challenge: Write the shortest implementation of a stack

[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 ).

[Plu]

Aren't these basically just table.insert, table.remove and the == operator? You can't get much shorter than the built-in functions.

[kikito]

Here you go:

Code: Select all

s={}

(I would prefer to make s local, but that would duplicate the size of my implementation)

[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.

[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.

[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.

[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"?

[LuaWeaver]

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.

[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.

[Inny]

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