Talk:Odd word problem

Promote?

Is this task now sufficiently clear that we can promote it to full task status? It's certainly got enough implementations, and it's got a short sample text to try it out with too. Are we waiting for anything now? –Donal Fellows (talk) 16:32, 11 May 2014 (UTC)

Explanations

Obviously, this task is not about text processing. Rather, it's about conditional code execution order. The even words are straightforward, while reversing odd words are easy with, say, recursion, with the catch that the word end marker (punctuation) needs to be processed after the recursion has returned. If peeking ahead is allowed, then this difficulty is removed and the whole thing becomes quite moot. --Ledrug 20:06, 3 November 2011 (UTC)

So this is a modified version of the problem that has been linked to? The solutions there seem to use buffers and peeking a lot. The site also says that the words will be a maximum of 20 characters long. Unless I'm missing changes in the spec later in the discussion, maybe there should be no link at all to that site (just to avoid confusion). --Mwn3d 20:12, 3 November 2011 (UTC)

I only linked there for the problem description, not their solutions. C2.com isn't exactly known for its example code qualities. I couldn't find a good ref to the problem anywhere else, and Dijkstra's original is in a 200+ page pdf that requires subscription to download. If you think this task description is clear enough, feel free to remove the link. --Ledrug 20:46, 3 November 2011 (UTC)

I guess I need to further clarify: this is not about text processing. Reversing English words and reading/writing a-z is about as unineresting as it can get, just pretend they are some token irreversible action that's potentially very complicated and cannot be simply queued as data, and you need to perform them in certain order depending on the input. In a strict sense, the current python and go code aren't correct, either (passing saved data by return). --Ledrug 22:21, 3 November 2011 (UTC)

I'm not seeing the problem with the previous Python code. Why not allow returning a character from the recursive function? How is returning a boolean any different that returning a character? —Sonia 23:34, 3 November 2011 (UTC)

The operations required by the task are only symbolic. "Reading a char" could represent arbitrarily complex data input, while "writing a char" could be be arbitrarily complex manipulation on such data. The boolean return only indicates if input is exhausted, while swapping variables or returning a value for deferred processing may mean detaching that data from the state under which it was obtained, and may be questionable. Using a closure or continuation to capture both data and state is maybe more to the spirit, but then since there's no way to precisely state what "complex" means here, I'd say the Go solution is acceptible. --Ledrug 00:09, 4 November 2011 (UTC)

If it's not about text processing, why the constraints on how the text is processed? It's hard to believe that there's any useful calculation that cannot be refactored. Also, a constraint on ordering does not makes sense as a constraint on memory use. In essence, here, you seem to have three unrelated constraints: character at a time processing without buffering (specified explicitly). Character at a time processing with buffering (required for the reversal needed by the even/odd algorithm). And the even/odd algorithm itself. (Personally, if this is supposed to represent something useful, I would much rather be tackling the useful problem without any constraints on how I implement anything that's not a part of the interface.) Anyways, as things stand right now, it seems like any interesting educational elements would buried in the noise. --Rdm 05:06, 4 November 2011 (UTC)

Operations are restricted precisely because it's not about text processing. You can ungetc a getchar, but you can't necessary unget a generic get_some_input. I never said anything about memory; output with buffering is your interpretation (data saved in a callstack frame or closure isn't normally considered "buffering"). The only actual constraint is "no saving in an array", which could tick J people off, but the intention here is to suppress, in your words, output with buffering, and favor ways of reordering of code flow constructs. Of course any useful calculation can be refactored, Turing showed that with his tape. The question here is, can you refactor some task in certain ways. --[User:Ledrug|Ledrug]] 13:03, 4 November 2011 (UTC)

This is exactly the kind of discussions we hit with The Longest String Challenge and took several rounds of discussion to get settled down. And the J folks will naturally ask how do you interpret the intent of this in a language that depends on arrays. You're also going to see discussions around solutions that use something that bends the restrictions and if they should be considered a cheat. Probably both where people try to get around the restrictions and where they will be wondering if they crossed a line by mistake. Hence there is an element of challenge in it. In any event you're likely going to have to spend more time explaining intent and such in the task description. Please understand, I'm not trying to be critical - it's just that I've been through all of this before. It took up way more of everyone's time than I expected. --Dgamey 13:27, 4 November 2011 (UTC)

If the task really intends "no saving in an array" that makes the Omit/J I placed on this one even more appropriate. In J, "array" is the same thing as "memory" or "storage" or "register" -- there just isn't anything else, in J. But I would still like to make sense of the task, if that is possible. (And, right now, I have to admit that the task does not make sense to me -- especially the one about how one is not supposed to reverse the string.) --Rdm 17:48, 4 November 2011 (UTC)

I don't know how to better describe it other than "making order of executation flexible." Maybe it's best to infer it by examples, just take a look at the defer in second Go example and coroutines in the TCL one. --Ledrug 18:46, 4 November 2011 (UTC)

So... I took a look at the go example <lang go>odd := func() byte {

       for {
           b := byte_in()
           if unicode.IsPunct(int(b)) {
               return b
           }
           defer byte_out(b)
       }
       panic("impossible")
   }</lang> it looks to me exactly like it is buffering a sequence of characters for later reversal.  Except, of course, it is not buffering them in an efficient fashion (just storing the characters), instead, it is buffering them as a sequence of some internal data structure that allows code to be resumed. The TCL version must be doing something similar, with coroutines?  Except that's still an array, it's just an array of something else.  (For that matter a byte is an array of 8 bits...).  Anyways, if the point is to use an array of incomplete function executions, I can do that in J.  But the architecture would be exactly the same as the architecture I would use for reversing a sequence of characters, except bulkier (both in code, to create the wrapper functions, and execute them, and in data, to store the wrapper functions).  And, since it is J, which you do not understand, this would be even harder to understand than a more simpler implementation.  That said: RUN=: ] bind 'a' creates verb (a function) RUN which always returns the letter 'a', and RUNING=: RUN f.`'' takes the verb RUN and returns a gerund (which is a noun -- an array, that represents the same concept that the original verb represented) which in this case is the definition of RUN (because f. extracts an anonymous definition from a name). which it saves under the name RUNNING.  Or, I could have just done ] bind 'a'`'' and gotten a gerund wrapper for the character 'a'.  ... anyways, I can build up a list of these and then later on apply J's reverse operator |. and then convert the resulting sequence of gerund to a verb which returns the sequence of results from the represented verbs, and give that verb its argument.  In other words:<lang j>   (|.] bind 'a'`(] bind 'b')`(] bind 'c'))`:0 

cba</lang> ... but I am not avoiding buffering here. I am not avoiding use of arrays. I am doing exactly what was forbidden. I am just wrapping each character with some bulk and then unwrapping it later, after reversing them... do you understand my dilemma now? --Rdm 12:30, 5 November 2011 (UTC)

Oh, and the mandated use of (in this case character-at-a-time) streams (which J does not implement natively, since they are useless (edit: worse than useless) within the language itself) would add significantly more bulk and require platform dependent code (J does not natively support unbuffered character-at-a-time streams, but it does support dynamically linking to shared libraries...) so any educational value from the illustration of data wrapping/unwrapping would be lost in the noise... --Rdm 12:49, 5 November 2011 (UTC)

The Tcl version is indeed holding values on the stack (with single assignment, as it happens) but that's explicitly allowed, whereas using an explicit queue or stack data structure would be not allowed. Also note that Tcl doesn't really like char-by-char input either, but it can work. If it's too onerous with J (can it read fixed with binary records, and if it can, can it read a record of size 1?) then that would be a good reason for omitting the task. –Donal Fellows 13:53, 5 November 2011 (UTC)

J stream input is line at a time, unless, for example, you are using sockets (the socket interface uses predeclared fixed-sized buffers). And, ok, yes, a hands off approach (using the call stack) would avoid using an explicit stack. But that's really still just a buffer... And, meanwhile, if I use sockets, I have to run another program to feed the socket (and that program would itself have to store a buffered string, which defeats the point of not using buffers, as a coding constraint -- why does it have to be a coding constraint and not an interface constraint?). --Rdm 17:54, 5 November 2011 (UTC)

I really do not know what you mean by "making order of execution flexible" -- it seems to me that you are doing exactly the opposite? Moreover, you earlier stated that you are explicitly trying to make the problem difficult -- but that strikes me as the essence of bad design? Anyways, I am not seeing the point or the gist, here. --Rdm 22:03, 4 November 2011 (UTC)

I understand your frustration. I don't know enough APL or J to even begin but I do know that there is a different way of looking at things. We saw it with the Longest String Puzzle/Challenge as well. I still think the task is under (or incorrectly specified) with respect to intent. I now thing that puzzles/challenges of this type are really properly categorized as 'curiosities'. So if I were to paraphrase, the basic problem is clear but the restrictions muddy the waters (also familiar). The 'read' method is given as unbuffered and destructive hence the no peeking, putting back, etc. The curiosity/challenge is in finding a way to reverse through program control alone without intermediate buffers. This works for most languages but I confess that I very quickly hit a wall when I try and think about this in APL or J. --Dgamey 02:41, 5 November 2011 (UTC)

One thing that I think is missing in curiosities of this type is documentation about what we coded. It's one thing to have a very specific and comparable task as comparisons can be more easily made. But when there is more variation and style it becomes harder to compare and see how things work. BTW. As I was trying to read the TCL, I'd love to see a tightly prescribed task for simple co-routine transfers. --Dgamey 02:42, 5 November 2011 (UTC)

I had a version which was a bunch of coroutines yielding directly to each other, but it was longer and not nearly as elegant, whereas this one arose from a bug when trying to tidy up. (To understand the core of the Tcl code, it helps to know that puts has an empty result and so that [foo][puts ...] effectively evaluates foo to produce some value, prints a message and then produces that value from before; it has a lot in common with the classic K combinator.) Overall, this is an easy task to solve, but harder to solve elegantly; I'm really pleased by the outcome. I would welcome something that has interesting coroutine transfers as the best solution (in this case, putting the main loop outside a coroutine simplified the handling of the end of the input a lot, which leads to the pattern I'm using). –12:10, 5 November 2011 (UTC)

Other References

• Dr. Dobbs The problem definition given here is slighty different. Punctuation is one or more blanks or a period. --Dgamey 22:17, 3 November 2011 (UTC)

Yes I changed that, because with blanks you can't tell if the delimiters have been incorrectly swapped. --Ledrug 22:21, 3 November 2011 (UTC)

Just thinking aloud here as I have been down the path of a programming challenge before and there will be lots of discussion about the usefulness of the task or why this or that restriction is in place, how it's artificial, etc. --Dgamey 10:41, 4 November 2011 (UTC)

• If you modify the original challenge, you risk breaking it. I'm not sure if that happened here or not. But when it's something that a Knuth or a Dijkstra published there is some historical value to it. If it's a modified challenge, then the task description should at least be clear on that point. --Dgamey 10:41, 4 November 2011 (UTC)
• Not being easily able to find a solution or statement of the problem creates problems. It makes it harder to have a clear discussion about the intent. Or for that matter to compare. I've been disappointed by the small number of available references online for this and the general low quality of them. BTW did I mention I hate paywalls. --Dgamey 10:41, 4 November 2011 (UTC)
• The code examples on c2 are not helpful. They code about breaking the rules right off the start. Very disorganized. --Dgamey 10:41, 4 November 2011 (UTC)
• Some of what I've found (sorry forgot the reference) refers to a 20 character limitation per word and I've seen snippets that suggest that this is used inside the readword as a buffer to reverse the word. This would fly in face of the no buffer rule (2). But again it really is hampered by not having a visible source for the original problem and an example of the solution that Dijkstra's class/group came up with. --Dgamey 10:41, 4 November 2011 (UTC)

The changes in this task should not affect the essence, they are only to weed out bad examples such as ones on c2. The read a char/write a char operations represent some generic actions, and added restrictions are there to prevent people from taking the "char" aspect too literally. Now that people are complaining, this part clearly is working. As for being a challenge, it's not meant to be. Just pretend you were given blackbox routines input, which changes local state, and output and is_end_of_word, which both depend how it was changed, and try to find a way to arrange the order of those happening. --Ledrug 12:49, 4 November 2011 (UTC)

• There is a Dijkstra archive at Utexas that was linked from c2. Some of the material is searchable but for some reason isn't jumping out in google searches. This led to EWD302 and the Odd Word Problem. The problem was a working example in front of a class with commentary and less a fully structured solution than a teaching excercise. --Dgamey 10:59, 4 November 2011 (UTC)

Thank you for that link! It was interesting to see details of the problem as originally posed, interesting to see the context, and fun to translate, compile, and run the final solution given there. —Sonia 18:54, 4 November 2011 (UTC)

Welcome, I found it quite helpful to see where it came from and what had changed. --Dgamey 02:44, 5 November 2011 (UTC)

Recap and moving on...

This task instead of being a normal task (which asks us to accomplish something) is currently specifying *how* we achieve that end. Specifically, it asks us to buffer a sequence of characters implicitly and not explicitly. Personally, I think that this kind of task bends the spirit of rosettacode: operations that can be implicit in one language may need to be explicit in another.

So, I propose that we bend the task, to compensate. Specifically: I propose that when a task forbids certain programming constructs and mandates others, that the "forbidden constructs" be allowed in support code which is not a part of the task implementation itself (in other words: link to the support code but do not include it on the task page). This should ideally be generalized utility code which emulates facilities used in "acceptable" solutions, but I do not think it's fair (or even possible) to mandate that for the general case of tasks which step over the line from specifying the ends to specifying the means.

(Specifically, in this case, I would want to implement co-routines and character-at-a-time streams, for J. But in general we are supposed to be allowing "best effort" implementations, and not requiring specific language semantics.)

Unless someone has a better idea? --Rdm 17:50, 6 November 2011 (UTC)

This task is all about a language's ability to delay code execution, and I'm not the least bit interested in seeing actual reversed words. If you need to implement coroutines in J for this, good for you; if you want to implement char-at-a-time for streams, don't bother: put chars in an array or a string and pop them one at a time and pretend it's a stream, I'm fine with that. J can do that, right?

As to "fair", I call bogus. If your language is not good at doing something, it's either its design feature or an inadequacy, there's nothing inherently unfair about the task unless it's specifically tailored to suit some obscure features of one language in mind (to make other languages "look bad", I suppose). By your fairness argument, what kind of complaint should I lodge at the discussion page of OpenGL Pixel Shader if I were to write code in ZX spectrum basic? --Ledrug 18:51, 6 November 2011 (UTC)

And I feel that your "call bogus" is itself bogus: The distinction, here, was the distinction between "implicit" and "explicit" and, to rephrase, I am saying that it's not meaningful to characterize that distinction as a distinction between "good at" and "not good at". (That said, I do not understand your question about ZX Spectrum Basic.) --Rdm 19:11, 6 November 2011 (UTC)

On

" I propose that when a task forbids certain programming constructs and mandates others, that the "forbidden constructs" be allowed in support code which is not a part of the task implementation itself (in other words: link to the support code but do not include it on the task page)"

It can be good to have tasks that call for specific constructs and/or forbid others. Sometimes the resultant may not be worth having as a task and might form a candidate for deletion, but assuming it remains as a task then we can:

1. Exclude our language from the task.
2. Or sometimes it can be good to state up-front what aspects of the task your language cannot handle before adding an example that doesn't answer the task for just those stated reasons.

In the second case you shouldn't be surprised if the presence of the example is questioned, marked {{incorrect}}, or even deleted if people think it strays too far from the task description without much gain for the reader. --Paddy3118 12:19, 7 August 2012 (UTC)

I would prefer, however, if those "good tasks" could have non-paradoxical (and unambiguous) task specifications. --Rdm 13:23, 7 August 2012 (UTC)

Is it time to move this task from draft?