Odd Word Problem

(from an article about a CoRoutine implementation in C++ by George F. Frazier in DoctorDobbsJournal? March 2001):

By EwDijkstra (sec 16, pg 67, "Notes on Structured Programming", Structured Programming, Academic Press of London, 1972, available for free from http://portal.acm.org/citation.cfm?id=SERIES11430.1243380&coll=GUIDE&dl=GUIDE&CFID=47718376&CFTOKEN=97605407).

Consider a character set consisting of letters, a space, and a point. Words consist of one or more, but at most 20 letters. An input text consists of one or more words separated from each other by one or more spaces and terminated by 0 or more spaces followed by a point. Input should be read from, and including, the first letter of the first word, up to and including the terminating point. The output text is to be produced such that successive words are separated by a single space with the last word being terminated by a single point. Odd words are copied in reverse order while even words are merely echoed. For example, the input string

: whats the matter with kansas.

becomes

: whats eht matter htiw kansas.

The problem is further restricted in that the characters must be read and printed one at a time.

All who claim this problem is trivial should, in order to be taken seriously, first provide a working solution on OddWordProblemSolutions.

In the example, why are the 2nd and 4th words odd rather than even?

Presumably because being a programmer he's numbering from zero. So that isn't the 2nd word, it's word 1.

Spot on. If you look carefully, you'll notice the first page of his manuscripts are numbered 0.

If he really wants to do it this way, the zeroth word should be "" (initiator) and the terminating word "." (terminator). That way he can keep his programming conventions without defying "common sense" of all non-programmers and most programmers, or is there some value in being deliberately obtuse? I have never understood this aspect of programming culture. -- AndyPierce

Isn't it a stretch to call either "" or "." a word? Common sense suggests a word is a sequence of one or more letters.

[If numbering starts at zero, shouldn't the initial word be referred to as the zeroth word, not the first word, and page 0 of the manuscript be the zeroth page, rather than the first page?]

See WhyNumberingShouldStartAtZero

Being a programmer, I have to admit that I am sometimes surprised if someone starts numbering with 1. This happens less in common life, but I think I remember it happened once.

What's the significance of this problem? Presumably, Dijkstra used it to some pedagogical end, but what?

If not for the requirement that characters be read and written one by one this would be a trivial program in C++, Java, or Python. Probably other languages I don't know, too.

: Why does reading and writing one character at a time make it non-trivial?

If you can read forwards or backwards, handling one character at a time is not a big deal.

Start at the beginning
Copy the next (even) word
Find the end of the following (odd) word
Read that (odd) word backwards, and copy it in reverse order
Return to step 1, stopping when you reach the "."

Shouldn't you document what you mean by "next (even)" word? Taken literally, as you read backwards in step 4, you will end up at the beginning of the (odd) word. Returning to step 1 at that point will result in an infinite loop. Returning to step 2 at that point results in printing odd words both forward and backward. You need to skip the word you just read backward. Here is my suggestion: [sorry I botched your edit]

Read forward and print each character until a space is found.
Read forward until the next non-space is found.
Read forward until the next space is found. Save this as a restart position -- it is the end of the word to be reversed.
Print a space.
Read backward and print each character until a space is found.
Go back to the position you recorded in the third step.
Read forward until the next non-space is found. This is the start of the next forward-printing word.
Print a space.
Go back to the first step

If you can't read backwards or store multiple characters, you can't reverse a single word. It's not clear what's interesting about this problem.

My guess is that you haven't successfully written it.
- Not at all hard (for those words that need reversal) to maintain a stack of characters for the purpose of reversing those characters. Just read a character, put it on the stack. When a whitespace character is encountered (or some other word-terminator), empty the stack, printing characters as you go, then print the termination character.

[This attitude is very annoying. I quote Dijstra's comment on this problem (I own this book and have it open in front of me): "On the contrary, I feel tempted to remark that the problem is perhaps too trivial to act as a good testing ground for an orderly approach to the problem of program composition. This section has been included because it contains a true eye-witness account of what happened in the classroom." (p72) ]

{}

{}

So wait, when you use a recursive function to write the string backwards, is that considered reading more than one character at once? I mean it OBVIOUSLY is, but since each new function is like a new piece, and in each one you only hold 1 character in memory.. I dunno. Anyhow

{}

{}

[Hear that? It's "trivial", in Dijstra's own words.]

[It is a trivial problem, and as such, it is perhaps appropriate to pose to a junior programmer in a job interview, to see if they can program at all, but by the same token, it is offensive to test senior programmers in an interview with something like this. Anyone who does is presumably looking for every possible opportunity to nitpick over inessentials, rather than truly looking to see if they have the qualities needed for the job.]

[People are just at a loss as to how to interview, so they clutch at straws like this. Inappropriate.]

Not only that, the (rather bad-tempered) discussion on OddWordProblemSolutions suggests that at least one person who uses (or claims to) this exercise in employee selection has in mind the (unstated) requirement that the problem be solved under the constraints present to a student of Dijkstra's in the late 60's early 70's. Doubly inappropriate.

CoRoutines are mentioned at the top of this page...why? This is clearly not a problem that requires coroutines for an efficeint solution. (There are problems which are much more easily solved with CoRoutines, such as the SameFringeProblem; but that has nothing to do with the problem on this page).

[A number of authors over the years have found this to be a convenient problem to use to demonstrate coroutines. You are correct that they are not required.]

[The relationship between a parser and a lexer is that of two coroutines, yet they are rarely implemented as such. That's still the logical relationship, though. And although this is an extremely simplified system, it is still a language transducer.]

[To be more explicit: the reader and the printer in a transducer each may have some state to save between invocations. In this case, the most obvious necessary state is whether the word is odd or even. State can be represented either by data or by control; they're dual. Odd/even could be a data flag isOdd, or it could be represented as control information by alternately calling an odd handler and then an even handle. Coroutines are just functions that save state information (typically both data and control state) between invokations. There are usually alternate ways to save state, but sometimes coroutines are the simplest approach.]

I don't quite understand the point.

Either you have to read and write in tandem, in which case it's obviously impossible, or you don't.

If you don't need to read and write in tandem then The problem is further restricted in that the characters must be read and printed one at a time. is just a red herring. That is, fundamentally, how you read and write from character streams anyway. So this restriction doesn't actually make the program any more difficult, but merely mixes it in with another problem -- namely implementing your own buffering area.

What is this about?

Would someone please answer these two questions, without making personal remarks about people who feel the need to ask them?

1. What does "the characters must be read and printed one at a time" mean? Most of us have never heard of reading two characters at a time, especially from an input device like a keyboard where characters are typed only one at a time.

2. What is the significance of this problem? Any college freshman in comp sci can write a program to reverse the characters in every other word of an input string. It does not require any special fancy techniques or ideas. If the problem is meant to illustrate some interesting idea, what is it?

My experience of interviewing people with first class degrees from reputable universities in the US and the UK is that only about 20% can write a routine to reverse every other word in a string. Your claim is at odds with my experience. I'm content to believe that for you the problem is trivial, and for people you've worked with the problem is trivial. The problem doesn't seem hard to me, but it appears that the problem is hard for many for whom I think it shouldn't be.

Be careful of Unicode combining characters and ligatures when reversing a string! http://garbagecollected.org/2013/03/15/reverse-strings-like-a-pro/

See LanguageTestCase