6
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – Stephen Rauch Apr 23 '17 at 23:57
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – eckes Apr 24 '17 at 5:36
  • \$\begingroup\$ This is a programming exercise \$\endgroup\$ – Rohit Apr 24 '17 at 17:34
3
\$\begingroup\$

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]))
}
\$\endgroup\$
  • 1
    \$\begingroup\$ but trying to do so with objects, rather than simple functions, seems to have added complexity for you. Thanks \$\endgroup\$ – Rohit Apr 24 '17 at 17:38
  • \$\begingroup\$ I liked the original solution. \$\endgroup\$ – Rohit Apr 24 '17 at 22:00
  • 1
    \$\begingroup\$ :). 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. \$\endgroup\$ – Jonah Apr 24 '17 at 22:10

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.