Challenge: Write the shortest implementation of a stack

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
LuaWeaver
Party member
Posts: 183
Joined: Wed Mar 02, 2011 11:15 pm
Location: Ohio, USA

Challenge: Write the shortest implementation of a stack

Post by LuaWeaver » Tue Sep 09, 2014 4:17 pm

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 :awesome: ).
"your actions cause me to infer your ego is the size of three houses" -finley

User avatar
Plu
Inner party member
Posts: 722
Joined: Fri Mar 15, 2013 9:36 pm

Re: Challenge: Write the shortest implementation of a stack

Post by Plu » Tue Sep 09, 2014 4:38 pm

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

User avatar
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

Post by kikito » Tue Sep 09, 2014 6:27 pm

Here you go:

Code: Select all

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

:P
When I write def I mean function.

User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Challenge: Write the shortest implementation of a stack

Post by vrld » Tue Sep 09, 2014 9:05 pm

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.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine

LuaWeaver
Party member
Posts: 183
Joined: Wed Mar 02, 2011 11:15 pm
Location: Ohio, USA

Re: Challenge: Write the shortest implementation of a stack

Post by LuaWeaver » Tue Sep 09, 2014 9:49 pm

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

User avatar
slime
Solid Snayke
Posts: 2900
Joined: Mon Aug 23, 2010 6:45 am
Location: Nova Scotia, Canada
Contact:

Re: Challenge: Write the shortest implementation of a stack

Post by slime » Tue Sep 09, 2014 9:53 pm

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
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Challenge: Write the shortest implementation of a stack

Post by davisdude » Tue Sep 09, 2014 10:09 pm

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

LuaWeaver
Party member
Posts: 183
Joined: Wed Mar 02, 2011 11:15 pm
Location: Ohio, USA

Re: Challenge: Write the shortest implementation of a stack

Post by LuaWeaver » Tue Sep 09, 2014 11:33 pm

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.
"your actions cause me to infer your ego is the size of three houses" -finley

User avatar
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

Post by kikito » Wed Sep 10, 2014 12:43 am

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.
When I write def I mean function.

User avatar
Inny
Party member
Posts: 652
Joined: Fri Jan 30, 2009 3:41 am
Location: New York

Re: Challenge: Write the shortest implementation of a stack

Post by Inny » Fri Sep 12, 2014 1:31 am

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

Post Reply

Who is online

Users browsing this forum: No registered users and 34 guests