Thursday, August 24th

 Text Justification

Given an array of words and a maximum width, format the text so that each line has exactly a maximum width for characters fully justified

Text justification examples courtesy of Volker Schnebel via Wikipedia.  Licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made.

First, we will collect and organize the words that will belong in each line.

Declare a vector of vector of strings to store the result.  A vector of strings will represent words in the line being processed, and the variable lineLength measures the size of the current line, initialized to 0

vector<vector<string> > result;

vector<string> line;

int lineLength = 0;

Iterate through each word in the input words.  If adding the new word to the current line is less than or equal to the maximum width, add the word to the line and update the length.  Otherwise, push the line back in the result, and start a new line with the word.  Don't forget to push back the final line.

for (string word : words) {

if (lineLength + line.size() + word.length() <= maxWidth) {

line.push_back(word);

lineLength += word.length();

} else {

result.push_back(line);

line.clear();

line.push_back(word);

lineLength = word.length();

}

}

result.push_back(line);

Now we have a structure holding the words that go into each line.   Initialize a vector to store the final justified lines

vector<string> justifiedLines;

Now we want to calculate the spaces for the lines that will be justified.  Iterate through all lines, except the last one because it is justified differently

for (int i = 0; i < result.size() - 1; i++) {

        ....

    }

For each line, calculate the number of spaces by adding up the number of letters in the words and subtracting from maxWidth

    line = result[i];

int numWords = line.size();

int numSpaces = maxWidth;

for ( string word : line) {

numSpaces -= word.length();

}

Determine the number of spaces due to gaps in a word, with at least 1 (this won't effect the justification if the line has only 1 word, but avoids division by 0)  

Use the number of gaps to determine the spaces in each gap.  Also calculate the number of extra spaces that will distributed unevenly among the gaps

int spaceGaps = max(numWords - 1, 1);

int spacesPerGap = numSpaces / spaceGaps;

int extraSpaces = numSpaces % spaceGaps;

Use the spacesPerGap and extraSpaces to build the line.  Start with an empty line, and iterate through each word in the line, adding it

    string justifiedLine = "";

for (string word : line) {

justifiedLine += word;

        ...

    }

If the spaceGaps remain, determine how many spaces to add.  This will be spacesPerGap, plus an extra space if there are extraSpaces remaining.  Add the number of spaces to the end of the string, and decrement extraSpaces and spaceGaps;

    if (spaceGaps > 0) {

    int spacesToAdd = spacesPerGap + (extraSpaces > 0 ? 1 : 0);

justifiedLine += string(spacesToAdd, ' ');

extraSpaces -= 1;

spaceGaps -= 1;

}

Push back the newly justified line

justifiedLines.push_back(justifiedLine);

Lastly, the last line is left justified.  Add a space between every word, and append spaces at the end until it's full

string lastLine = "";

for (string word : result[result.size() - 1]) {

lastLine += word + " ";

}

lastLine.pop_back();

lastLine += string(maxWidth - lastLine.length(), ' ');

justifiedLines.push_back(lastLine);

Return the result

return justifiedLines;

Not particularly difficult in the sense of tricks, pretty straight-forward, but the challenge comes from staying organized and presenting a clear solution, especially under a short amount of time

Shout out to niits for a simple but thorough implementation