# Google Code Jam - T9 Spelling with C++

I am trying to improve my coding skills. As a result, I solved the T9 Spelling question from the Google Code Jam dashboard. I will appreciate it if anyone could critique the code, and provide illustrations (if possible) of how I could make my code clean and simple. For me, simple is really beautiful.

Google judges the output of the code to be correct. Here is the problem statement.

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

using namespace std;
string process_ln(string line);

int main(){
ifstream infile;
ofstream outfile;
infile.open("C-large-practice.in");
outfile.open("C-large-practice-result.in");

int i=0,n=1;
int N;
string line;
vector<string> all;

infile>>N;  //number of test cases
while(i<N+1){
if(i<1){
getline(infile,line);
i++;
}
else{
string result;
getline(infile,line);
result = process_ln(line);
all.push_back(result);
outfile<<"Case #"<<n<<": "<<all[i-1]<<endl;
n++,i++;
}
}
return 0;
}

string process_ln(string line){
int j;
char letter;
vector<string> val,temp;
vector<char> v;
string keep;

for(j=0; j<line.length(); j++)
v.push_back(line[j]);

for(int i=0; i<j; i++){
switch(v[i]){
case ' ': val.push_back("0"); temp.push_back("0"); break;
case 'a': val.push_back("2"); temp.push_back("2"); break;
case 'b': val.push_back("2"); temp.push_back("22"); break;
case 'c': val.push_back("2"); temp.push_back("222"); break;
case 'd': val.push_back("3"); temp.push_back("3"); break;
case 'e': val.push_back("3"); temp.push_back("33"); break;
case 'f': val.push_back("3"); temp.push_back("333"); break;
case 'g': val.push_back("4"); temp.push_back("4"); break;
case 'h': val.push_back("4"); temp.push_back("44"); break;
case 'i': val.push_back("4"); temp.push_back("444"); break;
case 'j': val.push_back("5"); temp.push_back("5"); break;
case 'k': val.push_back("5"); temp.push_back("55"); break;
case 'l': val.push_back("5"); temp.push_back("555"); break;
case 'm': val.push_back("6"); temp.push_back("6"); break;
case 'n': val.push_back("6"); temp.push_back("66"); break;
case 'o': val.push_back("6"); temp.push_back("666"); break;
case 'p': val.push_back("7"); temp.push_back("7"); break;
case 'q': val.push_back("7"); temp.push_back("77"); break;
case 'r': val.push_back("7"); temp.push_back("777"); break;
case 's': val.push_back("7"); temp.push_back("7777"); break;
case 't': val.push_back("8"); temp.push_back("8"); break;
case 'u': val.push_back("8"); temp.push_back("88"); break;
case 'v': val.push_back("8"); temp.push_back("888"); break;
case 'w': val.push_back("9"); temp.push_back("9"); break;
case 'x': val.push_back("9"); temp.push_back("99"); break;
case 'y': val.push_back("9"); temp.push_back("999"); break;
case 'z': val.push_back("9"); temp.push_back("9999"); break;
default : break;
}//end switch
if(i>0 && val[i]==val[i-1])
keep +=" ";
keep += temp[i];
}//end for loop
return keep;
}//end process_ln

-
As you've now acquired 15 rep on this site, please be sure to upvote any answer you've found helpful. After a while (whatever you choose), you may accept the most helpful answer. – Jamal Aug 2 '14 at 19:30
Honestly, I deeply appreciate all Experts insights and quick response. Thank you all. – Sam Obeng Aug 2 '14 at 19:56

I see several opportunities for simplification and improvement in your main() function:

int main(){
ifstream infile;
ofstream outfile;
infile.open("C-large-practice.in");
outfile.open("C-large-practice-result.in");


std::ifstream and std::ofstream both have constructors that take the filename to open as an argument. You can collapse these lines to:

    ifstream infile("C-large-practice.in");
ofstream outfile("C-large-practice-result.in");


You don't need the all vector; see below for why.

    int i=0,n=1;
int N;
string line;
vector<string> all;


This piece of code skips reads in the number of lines remaining in the file, then has special case handling to discard the remainder of the line:

    infile>>N;  //number of test cases
while(i<N+1){
if(i<1){
getline(infile,line);
i++;
}


Instead of putting a special case inside the while-loop, move that std::getline() call to above the while loop. Then the whole thing simplifies to:

    infile>>N;  //number of test cases
getline(infile,line); // Discard the rest of the line.

while(i < N) {
// Note: condition in the while() has changed because we don't have
// the extra line at the start
string result;
getline(infile,line);
result = process_ln(line);
all.push_back(result);
outfile<<"Case #"<<n<<": "<<all[i-1]<<endl;
n++,i++;
}


You're storing the processed line in a vector, but the only place you're using that vector is right on the next line, where you output the string that you just put in there. So you could simplify further to:

        string result = process_ln(line);
outfile << "Case #" << n << ": " <<  result << endl;


This eliminates the need for the all vector, as mentioned above. Note that I've combined the declaration and initialization of result. This is generally a good habit to get into when using C++.

Another useful optimization to note is that the return value from std::getline() is the stream that is passed as its first argument, and streams have an implicit conversion to bool so they can be used as the conditional in while() or for() loops. If you use the return from getline() as the conditional part of a for() loop, you can declare the string in the same for() statement:

    int n = 1;
for(string line; getline(infile, line); ++n) {
string result = process_ln(line);
outfile << "Case #" << n << ": " << result <<endl;
}


Then you don't need to declare i, line or all earlier in main()

The return at the end of main() is not necessary in C++; if you omit it, the compiler will generate code for the return 0 for you.

return 0;
}


In the process_ln() function, there are also some opportunities for improvement:

string process_ln(string line){
int j;
char letter;
vector<string> val,temp;
vector<char> v;
string keep;


std::string has an indexing operator, so you don't need to extract each character from line here, you can simply index into it in the switch statement below and remove this code:

for(j=0; j<line.length(); j++)
v.push_back(line[j]);


The C++ standard library has the std::ostringstream class which is very handy for building up strings one piece at a time, so in the big switch statement, where you've got temp.push_back("....") in your code, you could replace it with:

std::ostringstream  keep;
/// process the line, building it up a piece at a time.
return keep.str();


In the for loop, you're storing all the digits that you use in the val vector. You really only need the current and previous digits to keep track of this. You're also storing all the fragments for each digit, where you really only need to keep one. Since your original code also swallowed invalid input, I'm doing the same here:

        std::ostringstream  keep;

// Note: initialized to an invalid digit value to guarantee that we|
// don't inject a space at the start of the output string.
char    last_digit = 'X';
char    this_digit;
string  digits;

for(int i = 0; i < line.length(); i++){

switch(line[i]){
case ' ': this_digit = '0'; digits = "0"; break;
case 'a': this_digit = '2'; digits = "2"; break;
case 'b': this_digit = '2'; digits = "22"; break;
/// and so on for the rest of the letters.
default : this_digit = 'X'; digits = ""; break;
}//end switch

if(this_digit == last_digit)
{
keep << " ";
}
keep << digits;
last_digit = this_digit;
}//end for loop
return keep;
}//end process_ln


Note that if you follow all of my advice, you won't need any of the variables j, letter, val, temp or v declared at the start of the function (though I admit I did introduce a few new ones).

-
I would go one step further and change the while loop as a for loop. – 200_success Aug 2 '14 at 19:46
@Niall C, Thanks for your detailed illustration and explanations. Also the technicalities you have pointed out. Big thank you to you and all the experts. I continue to read all comments and suggestions. – Sam Obeng Aug 2 '14 at 20:27
I think that the switch statement inside the logic of the function is very distracting. Also it represents data more than program so I would use an iteration on a vector instead of a switch (as is shown in another answer). But even if one would keep the switch, I would put it in an auxiliary function. – Emanuele Paolini Aug 3 '14 at 5:45

Something that wasn't touched on by the other responses is naming.

Names should describe the underlying semantics/role (within reason).

• You named your function process_ln(std::string) which really doesn't tell me much about the output besides "a string that was processed". In this case, your function is transforming an std::string to a T9-encoded std::string. Appropriate names could possibly be transform_to_t9(std::string) or encode_as_t9(std::string). Be reasonable and remember that the name doesn't have to describe every micro-aspect of the underlying entity.

• The same applies to variable names. Someone here on CR mentioned it and I honestly can't remember who it was, but it is a good rule. The higher/wider a scope is in a program, the more descriptive a variable name should be.

infile>>N;  //number of test cases
infile >> test_case_total; // White-space also helps with readability.


Control structures on multiple lines should always be scoped for readability/maintainability purposes. If you do not want to scope it for whatever reason, use only a single line. I prefer to always scope my control structures and avoid using the single-line statements.

// Single-line
for(j=0; j<line.length(); j++) v.push_back(line[j]);

// Multi-line
for(j=0; j<line.length(); j++) {
v.push_back(line[j]);
}


The output filename "C-large-practice-result.in" bothers me as the extension implies the file is an input file. Change the extension to .out, .txt, or something that doesn't imply input. This would also be a good opportunity to use parameter passing from the command-line (argc/argv) so you could reuse the program on the 2 challenge inputs rather than rewriting the filename for each attempt.

-
Another way of solving this problem using a bit shift to calculate the keys. ideone.com/XovJJ9 – Snowhawk04 Aug 3 '14 at 2:23
However variable N is named in the problem statement, so it is a good point to keep that name. – Emanuele Paolini Aug 3 '14 at 5:34
• Although this is just a challenge, try not to get into the habit of using using namespace std in global scope. In larder programs, it can cause name-clashing problems if not handled well.

• You can, optionally, organize your headers in some way so that they're easy to locate. You can, for instance, list them in alphabetical order.

• Instead of having a function prototype, you can define main() lastly. It doesn't matter so much if you have just one additional function, but it could look a little more more clutter-y if you have a program with lots of functions.

• You don't need an explicit return 0 at the end of main(). The compiler will already do this return for you, since reach this point implies a successful execution.

• Your indentation is inconsistent in process_ln(). The first few lines are okay, but the rest of them are aligned towards the left, making it easy to think that that code doesn't belong to the function.

• In C++, unlike in C, you can initialize the for loop counter variable within the loop statement. There's no other reason not to do it, and not doing so will just make your code more C-like, which you should try to avoid.

-

Your solution is perfectly acceptable, and I just have a few stylistic and performance improvements.

Firstly, as you will see in many answers on this site; whilst it doesn't matter in this case, it is generally not a good idea to use the using namespace std; as it defeats the point of having a namespace and can result in conflict in function/class resolution (see this SO post).

You may also note that instead of keeping track of the number of elements in the file to read, which is somewhat cumbersome, you can simply use the return value of std::getline and wait until it returns false for end of file, for instance, you can read all of the lines in a file using:

std::string strLine;
while( std::getline( fileInput, strLine ) )
{
// Process the line
}


Moreover, instead of storing all of the resulting std::strings in a std::vector<std::string> as you do in your solution, it would be more memory efficient to simply write each line to the output file as you construct it, for instance; this will mean you only have to store two strings (your input string and current output string) rather than a whole vector of all the output strings.

A slight performance note is also that in your process_ln function, you pass the input string by value instead of by reference, which results in a copy having to be made, which for large strings can have a significant performance impact; instead, you should have the following function signature:

std::string process_ln( const std::string& strInput );


With regards to your solution itself, there are more optimal ways to calculate the output string, an obvious one would be to use the floored distance from a and then add one to it. You can then calculate the number of repetitions by calculating the number modulo 3, for instance:

std::string ConstructString( const std::string& strInput )
{
std::string strOutput;
for( char ch : strInput )
{
for( unsigned short sCurrRepetition = 0; sCurrRepetition < (1U + (static_cast<unsigned short>(ch - 'a') % 3)); ++sCurrRepetition )
{
strOutput += std::to_string( ch - 'a' );
}
}

return strOutput;
}

-
Sure, it does help a lot. I was worried about passing my function parameters by value. Thanks for pointing that out. – Sam Obeng Aug 2 '14 at 20:12
When input specifically has a line count as part of the data you should use it. There may be extra comment lines at the bottom of the file (specifically in coding tests like this). – Loki Astari Aug 3 '14 at 15:56

To complete what has already been said:

• You are not in C90, not only can you declare variables in a for, but you don't have to declare all your variables at the beginning of a block. Generally speaking, the later you declare it, the better. That way, you know that the variable is not used before some point in the function. It makes the whole thing easier to read.

• You should open your files directly with the constructor. Using open right after having declared your files is redundant:

ifstream infile("C-large-practice.in");
ofstream outfile("C-large-practice-result.in");

• It would be a good idea to check whether your files have been properly opened:

ifstream infile("C-large-practice.in");
if (not infile)
{
// throw an exception
}

• In C++, identifiers that only use capitals are generally used to warn the user that they are using macros and not regular variables/functions/classes. Therefore, you should avoid them when you don't use macros, and replace int N; by int n;.

• Also, it is not recommended to declare several variables on the same line. Whenever possible, try to keep one declaration per line. hat should be easier if you only declare variables when you need them, and not always at the beginning of the blocks.

• The comments like //end switch are unneeded. As proposed by @Jamal, you should fix your indentation instead. It should be sufficient to know which opening brace is closed by the closing brace. Any decent code editor colours matching braces anyway.

-
@dyp You're right, I should have specified C90. Just to be pedantic :) – Morwenn Aug 3 '14 at 22:45
C11 not begin popular is also a question of compiler support. Clang and GCC just finished implementing the main features. But I have to agree: it's a shame that C99 is not that popular compared to C90. – Morwenn Aug 3 '14 at 22:48

Use std::array (C++11):

#include <iostream>
#include <array>

std::string nums = "123456789*0#";
std::array<std::string, 12> keys = {""    , "abc", "def",
"ghi" , "jkl", "mno",
"pqrs", "tuv", "wxyz",
""    , " "  , ""};

std::string T9(std::string input) {
std::string res;
for(char c: input) {
for(int k = 0; k < keys.size(); ++ k) {
for(int i = 0; i < keys[k].size(); ++i) {
if (keys[k][i] == c) {
if (!res.empty() && res.back() == nums[k]) {
res.append(" ");
}
res.append(i+1, nums[k]);
}
}
}
}
return res;
}

int main() {
std::cout << "hello world: " << T9("hello world") << std::endl;
}


(Not the best performance, but simple)

PS: I didn't test this.

Probably a faster/shorter version:

std::string T9(std::string input) {
std::string res;
for(char c: input) {
char lc = (c!=' ')?(c-'a'+1):0;
char count  = "112312312312312312341231234"[lc]-'0';
char letter = "022233344455566677778889999"[lc];
if (!res.empty() && res.back() == letter) {
res.append(" ");
}
res.append(count, letter);
}
return res;
}

-
And if the OP (somehow) doesn't have C++11, then std::vector should suffice. – Jamal Aug 2 '14 at 18:51
@Jamal std::string::back wont work without C++11 and the for(char c: input).. – KoKuToru Aug 2 '14 at 18:52
@SamObeng If you worry about std::array, it has 0 overhead compared to a plain C array. – Morwenn Aug 2 '14 at 19:34
@SamObeng How much of a difference in performance have you measured compared to your original solution? – 200_success Aug 2 '14 at 19:40
@SamObeng I edited(added) a new version.. harder to read, but shorter. Still pretty clean.. – KoKuToru Aug 2 '14 at 20:40