Google Code Jam - reverse words

Question

As a sequel from my previous question, I decided to solve the next problem statement from the GCJ dash board. Any thorough critique, this time, with much attention to skill and technicalities would be much appreciated.

I have few questions:

1. According to the problem statement, the number of test cases was to be read from the first line in the file but I didn't need to use it. Will this have any consequence that I do not yet know?

2. You will see from the code that, I read a line without using it (only for formatting purposes). Is there a better way to handle such a situation?

3. The for-loop in the rvrs_ln function throws segmentation fault if I do not reduce the number of elements by 1.

Here is the link to problem statement.

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <fstream>

std::string rvrs_ln(const std::string& line);

int main(){
   std::ifstream infile("B-small-practice.in");
   std::ofstream oufile("B-small-practice-result.out");
   if(!infile)
    std::cout<<"Could not open input file"<<std::endl;
   if(!oufile)
    std::cout<<"Could ont open output file"<<std::endl;

   int x = 1;       //index for formatting output file
   std::string line;
   int test_cases;
   infile>>test_cases;      //this is never used
   getline(infile,line);    //discards first line

   for(; std::getline(infile,line); x++){
       std::string all = rvrs_ln(line);
       oufile<<"Case #"<<x<<": "<<all<<std::endl;
   }
   infile.close();
   oufile.close();
}

std::string rvrs_ln(const std::string& line){
    std::istringstream buffer(line);
    std::string wrd,rvrs;
    std::vector<std::string> hold;
    int count_wrd = 0;

    while(buffer>>wrd){
        hold.push_back(wrd);
        count_wrd++;
    }
    for(int i=count_wrd-1; i>=0; --i){
        rvrs += hold[i];
        rvrs += " ";
    }
    return rvrs;
}

Answer 1

Extract constant values to constant variables

It's good to put string constants into constant variables, for example:

const std::string INFILE = "B-small-practice.in";

Handle problems immediately

Instead of:

std::ifstream infile("B-small-practice.in");
std::ofstream oufile("B-small-practice-result.out");
if(!infile)
  std::cout<<"Could not open input file"<<std::endl;
if(!oufile)
  std::cout<<"Could ont open output file"<<std::endl;

It's good to handle errors as soon as they can occur, that is, create outfile only after you know that infile is ok:

std::ifstream infile("B-small-practice.in");
if(!infile)
  std::cout<<"Could not open input file"<<std::endl;
std::ofstream oufile("B-small-practice-result.out");
if(!oufile)
  std::cout<<"Could ont open output file"<<std::endl;

Actually, the program won't work well if there is no input file, so you could just exit:

if (!infile) {
    std::cout << "Could not open input file" << std::endl;
    return EXIT_FAILURE;  // thanks @Jamal ;-)
}

Ergonomy

The program will be easier to use if the input filename is a command line argument:

int main(int argc, char ** argv) {
    std::ifstream infile(argv[1]);
    // ...

Also, instead of writing output to a file, it's easier to test the program if it writes to stdout instead. And the user can easily redirect the output to a file if needed.

Remove unnecessary things

In main, as you noted yourself, you're not using the test_cases variable at all:

int test_cases;
infile >> test_cases;      // this is never used
std::string line;
getline(infile, line);     // discards first line

You could just drop the test_cases variable.

The fact that you're not using N in the input can have the consequence of incorrect result in case the test evaluators want to mess with you. If you don't use this number and they add an extra line in the input, your program will produce different result from the benchmark solution which respects N. It's of course not very nice to trick you like that, but it can happen during a contest. To be safe I would use it.

The counter variable x

In main, you could declare the counter variable x inside the for statement:

for (int x = 1; std::getline(infile, line); x++) {
    std::string all = rvrs_ln(line);
    std::cout << "Case #" << x << ": " << all << std::endl;
}

And it's more common to call counter variables i, j, k, but that's not a big problem.

The segmentation fault

I suppose you're talking about this part maybe:

for (int i = count_wrd - 1; i>=0; --i) {
    rvrs += hold[i] + " ";
}

If you start counting from count_wrd (which is equal to hold.size(), then you'll be accessing hold[hold.size()], which is beyond the end of the vector.

Answer 2

• You report errors if any of the files fails to open, but continue execution anyway. If either of them fails to open, you should also return EXIT_FAILURE. In addition, you should be writing the errors to cerr instead of cout.

  On those same output lines, you're indenting by just one space, but you indent by four spaces everywhere else. You should try to keep the spacing consistent.

• Don't cram lines like this:

  oufile<<"Case #"<<x<<": "<<all<<std::endl;
  

  Add more whitespace between operators for readability:

  oufile << "Case #" << x << ": " << all << std::endl;
  

  Be sure to do this everywhere, not just with this line.

• You don't need to close files yourself, unless you're needing to check for errors. Since you're not, you can just remove these function calls.

• Since count_wrd is incremented with each call to hold.push_back(), you can just use hold.size() in place of count_wrd. You could also rename this vector to words.

• This doesn't need to be two separate lines:

  rvrs += hold[i];
  rvrs += " ";
  

  It can just be one:

  rvrs += hold[i] + " ";
  

Answer 3

In addition to what janos and Jamal said, use longer (more descriptive) method and variable names: rvrs_ln should be named reverse_line and wrd should be named word. You don't pay per character and it makes your code clearer.

Answer 4

I, at least, would rather see/use an approach based more closely on standard algorithms. The practicality of that can depend heavily upon existing code though. In particular, it makes it much easier to make use of existing components, but those components are often somewhat more difficult to write. For this answer I'm going to use some components I've previously posted. Without them, the practicality of this answer might be open to somewhat more question (when this problem is taken in isolation).

First, reverse_line can use istream_iterators and std::ostream_iterators to simplify the logic:

std::string reverse_line(std::string const &input) { 
    std::istringstream buffer(input);

    std::vector<std::string> words{std::istream_iterator<std::string>(buffer),
                                   std::istream_iterator<std::string>() };

    std::ostringstream ret;

    std::copy(words.rbegin(), words.rend(), 
              std::ostream_iterator<std::string>(ret, " "));
    return ret.str();
}

Note that this appends an extra space at the end of each line. I'd guess that's allowed, but if not you can use an infix_ostream_iterator in place of the ostream_iterator above.

Then, in main we can use std::transform to do most of the real work. The main difficulty here is that we need to read the input line-by-line, but transform uses iterators which (as shown in reverse_line) normally read word-by-word. There are a number of ways to deal with that, many of which are outlined in answers to an old SO question.

For the moment, I'm going to use the line class from my answer to that question. Using that, the main loop can look like this:

std::transform(std::istream_iterator<line>(infile), std::istream_iterator<line>(),
               std::ostream_iterator<std::string>(outfile, "\n"),
               reverse_line);

The next point would be to consider the real intent of your code. On one hand, you've hard-coded the names of the input and output files. This pretty much restricts the code to being used in its original setting. If that's your real intent, I'd probably also skip reporting errors when/if you can't open the input and/or output file. I'd just take for granted that opening them will work, and the user's indication of failure is that it either doesn't create an output file at all (if it couldn't open the output file) or creates an empty output file (if it couldn't open the input file). For a contest, this is almost certainly perfectly acceptable behavior.

If, however, you want to be able to put the code to wider use, you almost certainly want to let the user specify names for the input and output files (possibly including defaults, such as reading from cin and writing to cout). In this case, you almost certainly want to report errors (at least) a little more comprehensively, such as printing out the actual name of the file you couldn't open when a failure occurs. In particular, for a real tool it's rarely acceptable to just tell the user: "sorry, it didn't work". You need to provide information for the user to put to use in diagnosing and fixing the problem so they can make it work the next time around.

For this scenario, I'd also consider whether you want to check for pre-existence of the output file before opening it for writing (since opening in write mode will destroy whatever data it currently contains.

Oh--one more thing I'd meant to mention above, and almost forgot completely. Right now your code to skip that first line signifying the number of test cases seems unnecessarily complex. Right now you have:

infile>>test_cases;      //this is never used
getline(infile,line);    //discards first line

An istream has an ignore member function that's probably preferable to reading an integer; it makes it much more explicit that you're ignoring data from the input stream. Alternatively, you could just read all the data with getline:

std::string ignore;
getline(infile, ignore);

This makes it fairly apparent that you're reading and ignoring a line from the input stream.