Text justification program

Question

I'm looking for code review comments for text justification problem described here.

Problem:

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example, words: ["This", "is", "an", "example", "of", "text", "justification."] L: 16.

Response:

[
 "This is an",
 "example of text",
 "justification. "
]

/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
var fullJustify = function(words, maxWidth) {
 let text = new Text(maxWidth);
 
 text.parse(words);
 
 return text.toStringArr();
};
function Text (maxWidth){
 this.lines = [];
 this.currLineIndex = -1;
 
 Text.prototype.parse = parse;
 Text.prototype.toStringArr = toStringArr;
 
 function parse(words) {
 words.forEach(function(word) {
 let line = this.lines[this.currLineIndex];
 
 if(line && line.canAddWord(word)){
 line.add(word);
 } else {
 
 // Justify current row, if exists
 if(line) {
 line.justify(); 
 }
 
 // Create new row and add element to that
 this.currLineIndex++;
 line = new Line(maxWidth);
 this.lines[this.currLineIndex] = line;
 
 line.add(word);
 }
 }, this);
 
 // Justify last line
 let lastLine = this.lines[this.currLineIndex];
 lastLine.justify(true);
 }
 
 function toStringArr() {
 let result = [];
 
 this.lines.forEach(function(line) {
 result.push(line.toString());
 });
 
 return result;
 }
}
function Line (maxLen){
 this.words = [];
 this.spaces = []; // 
 this.size = 0; // Initial size of array
 this.maxLen = maxLen;
 
 function add(word) {
 if(this.canAddWord(word)) {
 this.words.push(word);
 this.size += word.length;
 return true;
 } else {
 return false;
 }
 }
 
 function toString() {
 let result = [];
 this.words.forEach(function(word, i) {
 result.push(word + " ".repeat(this.spaces[i]));
 }, this);
 
 return result.join("");
 }
 
 function justify(isLastLine) {
 let spacesCount = this.words.length - 1;
 let extraSpaces = this.maxLen - this.size;
 
 let quotient = extraSpaces / spacesCount;
 let mod = extraSpaces % spacesCount;
 
 if(isLastLine) {
 // Add one space between each word
 for(let i = 0; i < this.words.length - 1; i++) {
 this.spaces[i] = 1;
 } 
 } else {
 // Distribute (maxLen - size) in $(spacesCount) evenly
 for(let i = 0; i < this.words.length - 1; i++) {
 this.spaces[i] = quotient + ((mod-- > 0)? 1 : 0);
 } 
 }
 }
 
 function canAddWord(word) {
 return (this.size + (this.words.length - 1) + word.length <= this.maxLen)
 }
 
 Line.prototype.add= add;
 Line.prototype.toString = toString;
 Line.prototype.justify = justify;
 Line.prototype.canAddWord = canAddWord;
}

• Stephen Rauch: Welcome to StackExchange Code Review! In general all of the stack exchange sites prefer that questions and answers are able to standalone. Links have a tendency to age poorly, and thus later this question would be incomplete without the linked material. Can you please edit your question to include the essential portions of the linked material so that this post can stand on it own?
• eckes: Is,that a programming exercise or are you planning to really use that. I would not use a fixed with self-rendered version and stick to CSS formatting in the real world.
• Rohit: This is a programming exercise

Answer 1

Interesting problem.

I think your answer is quite a bit longer than it needs to be. Consider rethinking what the solution entails, essentially. Also, your code will be quite a bit more readable if you avoid nesting statement -- especially thing like loops nested inside conditionals, such as you have here:

 } else {
 // Distribute (maxLen - size) in $(spacesCount) evenly
 for(let i = 0; i < this.words.length - 1; i++) {
 this.spaces[i] = quotient + ((mod-- > 0)? 1 : 0);
 } 
 }

You have the right idea to break the problem down into the subproblems of line breaks and justification, but trying to do so with objects, rather than simple functions, seems to have added complexity for you.

Consider this rewrite, which expresses the line breaking problem using recursion, and also takes advantage of es6 features. It's about a third the size of the original, even with lots of intermediate variables which exist only for the sake of readability

function fullJustify(words, maxLen) {
 return asLines(words, maxLen).map(x => justify(x, maxLen))
}
function asLines(words, maxLen, curLine=[], charCount = 0, lines = []) {
 if (!words.length)
 return lines.concat([curLine])
 const nextWord = words[0]
 const remainingWords = words.slice(1)
 const additionalChars = nextWord.length + (curLine.length ? 1 : 0)
 const nextCharCount = charCount + additionalChars
 const breakLine = nextCharCount > maxLen
 if (breakLine)
 return asLines(words, maxLen, [], 0, lines.concat([curLine]))
 return asLines( remainingWords, maxLen, curLine.concat(nextWord),
 nextCharCount, lines )
}
function justify(words, len) {
 if (words.length == 1)
 return words[0] + ' '.repeat(len - words[0].length)
 const numPaddedWords = words.length - 1
 const totalChars = words.reduce((m, w) => m + w.length, 0)
 const extraChars = len - totalChars
 const spaceBetween = Math.floor(extraChars / numPaddedWords)
 const spacer = ' '.repeat(spaceBetween)
 const extraSpaces = extraChars - spaceBetween * numPaddedWords
 const leftPaddedWords = words.slice(1).map(
 (w, i) => spacer + (i < extraSpaces ? ' ' : '') + w
 )
 return [words[0], ...leftPaddedWords].join('')
}

additional improvement

my asLines function above is still too complex for my taste, so i did one more improvement, using a few utility functions from ramda.js:

function asLines(words, len, lines=[]) {
 if (!words.length) return lines
 let charCount = -1 // bc the first word is not left-padded
 const fitsOnLine = w => (charCount += w.length + 1) < len
 const nextLine = takeWhile(fitsOnLine, words)
 const remaining = drop(nextLine.length, words)
 return asLines(remaining, len, lines.concat([nextLine]))
}

• Rohit: but trying to do so with objects, rather than simple functions, seems to have added complexity for you. Thanks
• Rohit: I liked the original solution.
• Jonah: :). I think it's fine. I think the improvement is better, not only because it's shorter but because it better expresses the essence of the algorithm: "1. grab a new line that's not too long. 2. add it to your final answer 3. stop when all the words are gone". Also notice I was able to get rid of two extra parameters, which are essentially implementation detail.