This has been pulled out of OddWordProblemSolutions as a first step in distilling the information from the exchange. It all became very unpleasant, but I am unwilling to try to perform the distillation because I happen to agree strongly with one of the participants. I don't think I could be objective.
Please, I think WardsWiki would benefit if this were cleaned up.
I must interject here. It seems to me that this implementation (and perhaps others on this page) is not quite what the author of the exercise intended. You have broken the rule that characters are read and written one at a time, by using the ArrayList named "word" and applying Collections.reverse() to it. The problem is to read and write one character at a time, and not buffer any construct as a "word" to be reversed as a group.
- That would be an interesting variation, but looking at Dijkstra's solution, he uses an array of 20 characters, so your interpretation is not the original intention (see OddWordProblem for citation). And it really isn't kosher to change the problem statement after various people have been submitting code for a while, eh?
- This is a good point. I hadn't realized that Dijkstra himself implemented a solution using a word buffer. Nevertheless, the requirement that "characters be read and written one at a time" is unclearly stated thanks to the English language... the difference between "characters be READ and WRITTEN" and "characters be READ AND WRITTEN" is subtle but real.
It's not all that hard, though I am loth to actually implement it at the moment. The algorithm is quite close to what a bona fide Turing machine would do, but luckily for us there are no constraints about keeping a variable around to hold the starting position. As far as I can tell, it will go like this:
- 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.
The above fails to check for the final "." character.
- Suggested correction -- in step 1, add the condition "If a stop character is found, stop." In step 2, add the condition "If a stop character is found, stop." In step 3, change it to "Read forward until the next space or the stop character is found." In step 7, add the condition "If a stop character is found, stop."
- Words are no longer than 20 characters.
That's a constraint on the input, not the program.
Given where the problem originally comes from I believe the latter implies that your program must use a fixed amount of storage, yet be able to deal with arbitrary length input. How well does your solution cope with a string of length 10^15 characters?
I replaced the strings with file I/Os. (I thought it was obvious that if I read a string one character at a time and generated a string one character at a time I could do the same with a file, but now it's explicit.) It should be able to accept an input file of any length.
Sorry, but I'm obviously not making myself clear. The two points I made above (one at a time and no overly long words) were not meant to be answered separately. I know your code "reads" and "writes" one character at a time. Actually, to be more accurate, it accesses one character at a time and generates the output string one character at a time. That's not the point. I was observing that the problem when taken in its original context is clearly intended to be able to work on arbitrary size input with fixed bounded memory. That's where the read and write one at a time comes from, along with the statement that the input words will be no longer than 20 characters.
And this program can work on an arbitrary size input with fixed bounded memory. Yes - agreed
It may just be me, but your responses seem very antagonistic. Your final demand of "What's the point" says it all. Let me try to explain. This is a programming challenge. I use it to assess the skill balance of people I might employ. Here is the specification in point form:
- Input and output one character at a time
- You get "words" separated by one or more spaces
- Input is terminated by zero or more spaces and a "."
- No "word" is longer than 20 characters
I find it surprising that you feel I have to, but for your sake I further add:
- There is no limit on the input stream length
I suspect that you thought the problem was easy, you coded the solution, I've found a problem with it, and now you're angry. If I'm wrong then I'd be pleased to hear why you deemed satisfactory a solution that fails without warning on sufficiently large input.
I'm not angry. It doesn't fail without warning on sufficiently large input. The problem is easy, unless I misunderstand some aspect of the requirements. I thought it might contain some hidden difficulty, so I went ahead and implemented it to find out. I'm honestly asking what the point of the problem is. I still don't understand what you're trying to show here. What is your motivation? -- EricHodges
There are several points here.
- Your first solution used strings to store the input and the output. I pointed out that that was not the way the specification was given and your program failed without warning if the input was sufficiently large. You've now changed it.
Correction: My first example used strings to simulate files. The strings were read and written one character at a time. I changed it to make it more explicit, and because I had some time to kill while I waited for a performance test to finish.
- Your first solution did not deal correctly with multiple spaces between words. You've now changed it.
True.
- I suspect that most readers at first glance would think your program is excessively complex. I know it's not because I think this problem has several potential pitfalls which your code now avoids.
And?
You ask what my point is, what's my motivation. I read the original page and found several people claiming it was easy and I suspect that none of them had tried solving it. That really annoys me, so I suggested people have a go, and put this page here to give them somewhere to show their efforts. You did, which impresses me, and now you appear to have it right. Your first attempt wasn't (the multiple space problem) which shows either that the problem is hard, you're incompetent, or that you thought the problem is easier than it really is.
Or that I missed the part of the requirements that said words could be separated by multiple spaces.
I don't believe you're incompetent, so the fact that your first version was wrong shows that the problem is harder than you initially thought. That was my point. When you posted your first version you said "What's so hard about that?" and it was wrong.
And I fixed it and still don't know what's so hard about it. If your intent was to show that the problem is difficult, you haven't convinced me.
- It's not at all clear that it was just plain "wrong", anyway, because "input" is an ambiguous word, and is often used to refer to string input, parameters passed, etc, not only to terminal/file I/O "input". And even aside from that, solving a toy problem for strings does demonstrate the algorithm required; it is only a nitpick that you wanted it to do exactly the same thing for file I/O. Your white and black attitude of wrong! is misguided. -- dm
Now, how should this page be refactored. Do you think your code is the simplest possible?
No. It is merely my first solution. I assume it can be refactored by removing the discussion that follows the code.
- It is always an interesting challenge to see just how small code can be made, so anyone who has time to burn can probably find smaller approaches here, too, just for the fun of it.
Added in proof: I find that my original response which mentioned the multiple spaces between words problem is no longer here. I suspect that one of us removed it without comment. It may have been me, and if so then the above will not read coherently. If it was me then I may have to apologize. I thought I said it.
I removed it when I fixed that bug.
Ah.
[As an onlooker, I find your attitude towards Eric and his efforts inappropriate and offensive. He made some really rather trivial mistakes, and you're making a federal case out of it. See my quote of Dijstra I just added to the original page.]
[Apparently you're looking for someone who can solve trivial problems flawlessly on the first try, rather than someone talented enough to solve difficult problems, although perhaps with some easily fixable bugs. You'll deserve the kinds of employees you end up with, with that approach.]
-
- As another bystander, I wonder if perhaps the point is this:
-
- If someone cannot solve even trivial problems without bugs, how can they be expected to solve difficult problems?
-
- Or, turned around:
-
- If someone is capable of solving difficult problems, surely they can solve trivial ones without bugs.
-
- We may regard this reasoning as flawed, but perhaps not everyone considers it so.
- It's flawed because it's unrealistic. People make small mistakes in casual contexts, such as this page, and certainly when they're nervous when they are interviewing. It is unrealistic to the point of stupidity to ignore this fact about human nature. If someone fails, on either a large or a small problem, to demonstrate any understanding whatsoever of how to solve it, then you can safely dismiss them as not being the person you want to hire. If you dismiss them because they misspelled a word or had a trivial bug such as an off by one error, then you are demonstrating your own shortcomings as a manager.
How is this challenge related to interviewing? I didn't see anything about that on OddWordProblem or CoRoutine. I feel like I'm missing the context of this debate. I also feel like some nameless person thinks they are interviewing me. -- EricHodges
- That is correct, you were being interviewed. And you were hired. And then fired. Then those responsible for sacking you were sacked. It was a busy day. (The OddWordProblem appears at the top of ProgrammingChallengesForInterview, a page that was active simultaneously today with OddWordProblemSolutions.)
- I have never heard of a job where day to day performance had to do with solving toy problems flawlessly on the first try, as you are requiring on this page or in a job interview; in these contexts, speed is important, and we don't have a compiler to help us find errors, and we aren't allowed to write and run a unit test, or to double-check the published literature, etc.
- Any manager who failed to hire EH because he solved the problem on this page originally for strings, instead of file input, is incompetent beyond words, and their company should fire them and find a better manager.
I'm not going to reply to this at length now because clearly today I'm having trouble making myself clear while avoiding offending people. Eric has admitted that first version had a bug. He accompanied that first version with "What's so hard about that?" I find this attitude odd, that someone writes code that's wrong and then still claims the problem is trivial. I claim that if the problem results in clever people producing code with bugs then the problem is non-trivial. Am I wrong?
In this case, yes. As I've said, I missed the requirement that said there could be multiple spaces. That doesn't make the problem non-trivial, it was just a mistake on my part.
I apologize without reservation if I've been offensive. I honestly have trouble understanding how programmers continue to be unashamed about producing buggy code for trivial problems. If you find that offensive then I'm at a loss. Please, help me to understand.
I'm unashamed because it was a simple mistake. Once I understood the requirement I fixed it in a few minutes. What is there to be ashamed of? What good will shame do me? -- EH
I agree with Eric. No one wants to make mistakes, but no one is perfect, either, and it is offensive to take the position that people should be. The "should" is that we should attempt it, knowing in advance that we cannot fully succeed. We should not feel shame at making mistakes, and you should not browbeat someone who makes trivial mistakes, even in simple circumstances. There is nothing at stake here. It's no big deal. We're all just chit-chatting, and the code is merely part of the conversation. You might as well get up in arms over a spelling mistake (which is well known to be a faux pas, btw, ask Miss Manners).
If this were medical software that could cost lives, that would be different; we should do proofs and tests and peer review before ever pretending to have the solution. But that's not the case here! -- dm
This entire discussion has exploded into a big ball of mud and it's now virtually impossible to follow anything. To try to recap on the sequence:
- I read about the OddWordProblem years ago and have always had it as an interview question, along with several others.
- I noticed that on the OddWordProblem page many people were saying that the problem was trivial, and yet I suspect none had actually programmed it.
- I thought it would be interesting to have people actually do the work before saying the problem was easy, so I created this page.
- Eric posted a solution, his first. He claimed the problem was trivial. (Actually he said "What's so hard about that?")
- I pointed out that
- It didn't appear to read and write one character at a time
- Eric was using strings to simulate IO, I had expected solutions to include 'getChar() and putChar() routines, Eric modified his version to make the character basis of the IO obvious.
- It didn't deal correctly with multiple spaces
- Eric modified his version and said that he hadn't understood the requirement
- I observed that claiming a problem is easy and then getting it wrong seems to be a contradiction
Since then it seems that I've consistently been attacked, saying that I should be sacked for expecting people to write correct programs for trivial problems. Not once have I said that I wouldn't hire Eric, not once have I said that people should get this right first time, not once have I said that not getting it right would lead to being sacked.
I did mis-speak myself when I said that people should be ashamed for producing buggy programs. I intended to say that people should take pride in producing programs that work, and learn from every bug they produce to try to avoid producing bugs in the future. In a field where people claim that bugs are inevitable, and also say that bugs cost money and lead to project failure, it only seems prudent and professional to try to learn from mistakes to avoid repeating them.
And for what it's worth, based on the code he produced I most likely would have hired Eric. I don't see why anyone assumed otherwise. Can anyone point to where I ever said that Eric's solution would cause him either not to get the job, or to be fired from a job?
Finally, I'm not going to say any more on this. It seems clear that at least one of the following is true:
- I don't make myself clear
- People don't actually read what I write
Attack me all you like and I'll learn what I can from it. You obviously all know so much more about it than I do.
Who are you and when is my first pay check? -- EricHodges
Odd Word Problem Solution Argument