Challenge scenario requiring the use of a stack

[byorgey]

I was thinking the other day that it would be really cool to have stacks somehow. Like a physical thing that you could push and pop entities on. This would let you simulate pushdown automata and would probably allow for some cool automated production scenarios.

However, I don't necessarily want to just create a new device or built-in thing. What I really want to think about is, what would you need to be able to program a stack yourself? I'm thinking something like this:

• We might need recursive types (Recursive types #154) to be able to store the stack itself, though you might be able to get away with a Church-encoded list (but popping would be expensive).
• You need some way to communicate (Inter-robot communication #94) at close range to be able to "invoke methods" on the stack robot. e.g. I'm imagining to push, you place the item you want to push and then send a push message to the stack robot, which will pick up the item and store it. To pop, you send a pop message, and it will place an item down.

Would be happy to hear about other approaches I haven't thought of.

[kostmo]

I think you can emulate a stack within the "environment" of a recursive function¹. Have the "state machine" of whatever algorithm you're carrying out exist inside the body of the recursive function. The "top" of the stack is an argument to the function. Recurse again with a new argument to "push" onto the stack, or allow the current layer to exit to "pop" from the stack.

Footnotes

1. This came to mind from the way I implemented the fence loop detector. The premise of the detector is to find the surrounding water by heading straight in one direction. Along the way, one might encounter walls with arbitrarily many "spiral twists". While following the wall, need to keep track of the turns that were made to eventually "unwind" and continue along the original direction. I use the recursion stack for this bookkeeping. ↩

[kostmo]

In parallel, we should contrive a challenge scenario where the player is required to use a stack.

[byorgey]

Ah, excellent, this got me on the right track. Something like this (pseudocode) should work:

def stackNE : text -> cmd unit =
  while a pop is not requested:
    wait for a signal
    if a push is requested:
      thing2 <- grab
      stackNE thing2
    else if a pop is requested:
      place thing
    end if
  end while
end

def stack : cmd unit =
  while true:
    wait for a "push" signal
    thing <- grab
    stackNE thing
end

[byorgey]

Hmm, I had a potentially interesting idea for a challenge scenario: there is a line of entities on the ground, and you are required to reverse them, i.e. pick them up and place them down in the same locations but in reversed order. However, you have a limited number of ticks in which to complete the challenge --- so that you have to use an O(n) solution instead of O(n^2). i.e. you can't walk back and forth swapping the items on the ends, then the items one from the ends, and so on. You have to walk down the line and pick them all up, then walk back and somehow place them down in reverse order --- of course the way to do this is to simulate a stack internally with recursion. To solve the challenge you would have to program a solution and run it with --run in order to get it to finish in the time limit. (#927 would be nice for this since when the timer runs out it could pop up a dialog telling you that you can no longer win.)

Of course someone could always cheese it by writing a really tedious program like thing1 <- grab; move; thing2 <- grab; move; thing3 <- grab; move ... but, their loss. (Though that does make me wonder about defining challenges with "secret test scenarios" that your code has to also pass in addition to the "public example scenario"...)

[kostmo]

defining challenges with "secret test scenarios" that your code has to also pass in addition to the "public example scenario"

I've been thinking about that, too. I've fleshed out a concept in #967.

Another mitigation to "cheesing" would be scoring the solution based on the AST size (#866).