New exercise: organize a Queue from 2 Stack's

[ybod]

I want to introduce new exercise where You have access to only one data structure: Stack. And the task is to implement Queue using only 2 Stacks as efficiently as possible.

I can make such exercise for C#, and also try to do something for JS and Elixir I think...

[NobbZ]

Do I understand you right? You are proposing to build an okasaki queue as an exercise?

https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

I'd be happy to have this for my track!

Yurii Bodarev notifications@github.com schrieb am Fr., 3. März 2017, 17:51:

I want to introduce new exercise where You have access to only one data structure: Stack. And the task to implement Queue using only 2 Stacks as efficiently as possible.

I can make such exercise for C#, and also try to do something for JS and Elixir I think...

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/exercism/x-common/issues/623, or mute the thread https://github.com/notifications/unsubscribe-auth/AADmRxHI_8V8f1M5A0BJLTrfUkNzBvWJks5riEUmgaJpZM4MSfWL .

[petertseng]

Oh interesting!

• I imagine it will be hard to test that the student's submission is implemented only with the two stacks and efficiently (rather than cheating and using a queue from the language's standard library)
  • But that is okay, that is for reviews
  • binary-search and sieve deal with the same: they talk about specific implementations, but it's hard to enforce
  • If one really wanted to enforce efficiency of course one could keep access counters to the stacks (see Lua's TracedArray for binary-search tests)
• If we come up with a way to group related problems (as in #326) we should consider grouping this new exercise, binary-search-tree, custom-set, linked-list, simple-linked-list, zipper, maybe list-ops as well.

[ybod]

@NobbZ I'm not sure about Okasaki, need to find some time to read this paper. But I solved this task as a part of one of my interviews :) and I believe the implementation can be challenging.

@petertseng Yes, we cannot guarantee that user implementation will be based on Stack. But there are some other tasks that require You to implement some functionality already presented in standard libraries yourself. So I think it's pretty normal do describe all limitations in the README. I'm not sure that we should limit a number of Stacks. Maybe the requirement of using only particular data structure will be enough?

[NobbZ]

Okasaki doesn't use "stacks" but "linked lists" which do behave very similar to stacks in many points (in fact, stacks are often implemented on top of of them), while a queue is basically some kind of double ended "stack" that you can push and pop on both sides but not peek or even change in between.

Okasaki does implement the queue interface over 2 lists, one is a "view" from the "front" the other one from the "back". when one tries to pop from an end that currently has an empty "view", then the other one gets reversed and poped.

Thats the idea of Okasaki queue.

Yurii Bodarev notifications@github.com schrieb am Di., 7. März 2017 um 12:59 Uhr:

@NobbZ https://github.com/NobbZ I'm not sure about Okasaki, need to find some time to read this paper. But I solved this task as a part of one of my interviews :) and I believe the implementation can be challenging. @petertseng https://github.com/petertseng Yes, we cannot guarantee that user implementation will be based on Stack. But there are some other tasks that require You to implement some functionality already presented in standard libraries yourself. So I think it's pretty normal do describe all limitations in the README. I'm not sure that we should limit a number of Stacks. Maybe the requirement of using only particular data structure will be enough?

— You are receiving this because you were mentioned.

Reply to this email directly, view it on GitHub https://github.com/exercism/x-common/issues/623#issuecomment-284702481, or mute the thread https://github.com/notifications/unsubscribe-auth/AADmR7vZ7Q5QQi_hgjIYXYXBEbwITdAjks5rjUa5gaJpZM4MSfWL .

[ybod]

@NobbZ Yes, than we are talking about Okasaki queue for sure. Because that was the "optimal" implementation with 2 stacks I was talking about! The problem is that if we provide the description of Okasaki queue in the task README than we will literally give the key to solution of the problem :) So task must be formulated something like: "implement a queue utilizing only list/stack data structure" (depending on the language)?

[NobbZ]

We can't decide text to put in the read me based on the track because it is just an assembly of a couple of static files in a static order.

But if course we could say "2 stacks/linked lists" or just stick to the term "list".

Also I do not like the term "in an efficient manor". My professor always said, if it does the job in time with the average size of data, it is efficient enough for that usecase. And since there are only a very little number of tracks that have benchmarks, most won't even care about needing efficient.

I think it is totally fine to talk about the term Okosaki queue and maybe even a link to a short introduction as it is done in the sieve of erasthostenes exercise. This way we have a formal specification of what the student is meant to implement and don't have to argue witch him/her about efficiency.

Yurii Bodarev notifications@github.com schrieb am Fr., 10. März 2017, 21:52:

@NobbZ https://github.com/NobbZ Yes, than we are talking about Okasaki queue for sure. Because that was the "optimal" implementation with 2 stacks I was talking about! The problem is that if we provide the description of Okasaki queue in the task README than we will literally give the key to solution of the problem :) So task must be formulated something like: "implement a queue utilizing only list/stack data structure" (depending on the language)?

— You are receiving this because you were mentioned.

Reply to this email directly, view it on GitHub https://github.com/exercism/x-common/issues/623#issuecomment-285781389, or mute the thread https://github.com/notifications/unsubscribe-auth/AADmR6JxTvbWbSyJaPSWuhpj2QIXcu2Gks5rkbgJgaJpZM4MSfWL .

[rbasso]

This seems related to exercism/discussions#124.

[ybod]

So according to @rbasso comments we should not introduce the problems like this into Exercism at all? Because it's not very practical, doesn't allow the freedom of implementation and can not show any practical ways of applying stacks...

[rbasso]

So according to @rbasso comments we should not introduce the problems like this into Exercism at all?

I just argued - in an issue that someone else opened - that instantiating theoretical problems in more concrete contexts usually make the exercises more interesting. It believe this approach could also motivate some people to learn computer science.

Because it's not very practical...

That was not my argument.

... doesn't allow the freedom of implementation

I think that this kind of exercise usually fells more restrictive than others that just state a goal, without specifying how to solve it. The former usually results in less diverse solutions and less reviews.

... and can not show any practical ways of applying stacks...

I'm not saying that!

Maybe it is possible to come up with a good story to motivate this exercise. Who knows?!

But that was just my opinion! I have no desire to force my will on anyone. 😄

Finally, I mentioned that issue here so that people could be aware of the discussion. I had no intent to dissuade anyone from creating a new exercise.

[ErikSchierboom]

This issue has been stagnant for quite a long while. I'm therefore closing this. If anyone feels like they want to continue working on this, feel free to reopen.