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

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]))
}