3
\$\begingroup\$

I'm hoping for someone to help me use the best practices and further make my code better that I used to accomplish the DailyProgrammer Challenge "Balancing Words".

The challenge is to check if a word will "balance" and if it will, where it balances. For a word to balance at a letter, all of the weight to the left and to the right of the letter have to be equal. Weight is calculated by the letter's index in the alphabet (A = 1, B = 2 ... Z = 26) multiplied by the letter's distance from the balance point.

For example, with the input of STEAD, the program should output "S T EAD - 19" since STEAD balances at the T. The left hand side of T is just S. S = 19(th letter in the alphabet) * 1(distance from T) = 19. The right hand side of T is EAD = 1 * 5 + 2 * 1 + 3 * 4 = 19. Since both sides are 19 when T is the middle, T is the balance point so I print out the word STEAD with spaces around T "S T EAD" and the weight of either side (since they're equal) " - 19".

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    /*
     * Enter multiple lines of input separated by '\n', when a line is empty stop collecting input.
     */
    cout << "Enter input in capital letters, just press enter to stop." << endl;
    vector<string> input;
    string inputLine;
    while (getline(cin, inputLine)) {
        if (inputLine != "") {
            input.push_back(inputLine);
        }
        else {
            break;
        }
    }

    /*
     * This initial for loop is just cycling
     * through all of the words from the input.
     */
    bool balances = false;
    for (string &word : input) {
        /*
         * This for loop goes through all of
         * the letters in the current word.
         */
        for (int i = 0; i < word.length(); ++i) {
        int leftWeight = 0;
        int rightWeight = 0;
            /*
             * This loop goes through all of the letters to the left
             * of the currently selected "balance point" and calculates
             * the total "weight" on the left side.
             */ 
            for (int j = 0; j < i; ++j) { // Left of index
                leftWeight += (1 + word[j] - 'A') * (i - j);
            }
            /*
             * Same as above, but for the right-side of the "balance point."
             */
            for (int j = i; j < word.length(); ++j) {
                rightWeight += (1 + word[j] - 'A') * (j - i);
            }

            balances = leftWeight == rightWeight;
            /*
             * This exits out as soon as the working "balance point" is found!
             */
            if (balances) {
                cout << word.substr(0, i) << " " << word[i] << " " << word.substr(i + 1, word.length()) << " - " << leftWeight << endl;
                break;
            }
        }
        if (!balances) { 
            cout << word << " DOES NOT BALANCE." << endl;
        }
        cout << endl;
    }
}
\$\endgroup\$
2
\$\begingroup\$

General Coding Advice

  • Do not use using namespace std. See here and here.
  • Wrap your logic into a function. This typically allows for better control flow.

    // Returns the position that the word balances
    // Returns 0 if the word does not balance (since words can never balance at 0)
    int balances(const std::string& word)
    {
        // Some loop
            // If it balances return the position
            // Also note that a word can only balance in one position
        // End of loop
        // Return 0 since it does not balance
    }
    
    for (string&& word : input) {
        int pos = balances(word);
        if(pos)
        {
            // print something
        }
        else
        {
            // print something else
        }
    }
    
  • Personally I would prefer using unsigned int or better yet size_t to index the string but you can run into problems using unsigned int so you can stick to int for now.

Faster stop condition

leftWeight is monotically increasing while rightWeight is monotonically decreasing. So a faster stop condition is leftWeight > rightWeight

Algorithm hint

You do not need to recompute everything each iteration.

Note that \$A\$, \$B\$, \$C\$, ... arbitrary values here and not letters in the alphabet.

Assume we have some number \$N_i = 5A + 4B + 3C + 2D + E\$ and we desire some number \$N_{i+1} = 4A + 3B + 2C + D\$.

It sure would be nice if we had some number \$M_i = A + B + C + D + E\$ so that \$N_{i+1} = N_i - M_i\$

But then how do we update \$M_i\$ to \$M_{i+1}\$ so that \$N_{i+2} = 3A + 2B + C = N_{i+1} - M_{i+1}\$?

And if for some reason we had \$N_{i+1}\$, \$M_{i+1}\$, and some new value \$E\$ could we use these to compute \$N_i\$?

If we could do all of the above \$O(1)\$ then our overall algorithm would be \$O(n)\$ instead of the \$O(n^2)\$ solution where you recalculate everything.

\$\endgroup\$
  • \$\begingroup\$ Wow, thanks for such a detailed answer. What do you mean by wrapping logic into functions provides better "control flow"? Thank you very much. \$\endgroup\$ – Dylan Jul 7 '15 at 18:56
1
\$\begingroup\$
  • Don't trust input

    The code presumes that the input indeed consists of the capital letters. It is a good habit to test the input against the assumptions.

  • Unnecessary variable

    Testing condition directly

    if (leftWeight == rightWeight)
    

    expresses your intentions better than an intermediate assignment.

  • Algorithm

    is quadratic. There is a linear solution.

    As a side note, there is no need to subtract 'A'; it doesn't affect the balance.

\$\endgroup\$
  • \$\begingroup\$ Okay, I will update the code shortly checking the input. However, the variable isn't unnecessary as it is what allows me to check if there was no answer later on in the program. And subtracting 'A' is necessary as I need the "weight" from either side at the end of the program. I'm not sure what you mean about the algorithm though. \$\endgroup\$ – Dylan Jul 7 '15 at 16:34
  • \$\begingroup\$ @ChemicalStudios Instead of breaking you should return. Then the only way control reaches the end of the for loop is if the word does not balance. Whoops, I see now that you are running this on multiple words. But the concept still stands if you wrap your logic into a function instead. \$\endgroup\$ – twohundredping Jul 7 '15 at 16:45
  • \$\begingroup\$ @twohundredping I'm not sure what you mean. I can't replace "break;" with "return;" or I get a compilation error. But even if I could, it would need to reach the end of the for loop to start on the next word if the input consisted of more than one word. \$\endgroup\$ – Dylan Jul 7 '15 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.