DailyProgrammer Balancing Words Challenge

Question

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;
    }
}

Answer 1

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.

Answer 2

• 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.