Algorithm practice: justify a paragraph

23 Sep 2019 - John

For today’s exercise, we are given a paragraph in the form of a very long string. We are also instructed to have each line be no longer than 30 characters including spaces and punctuation. Also, words cannot wrap lines and each line must end in a word or a word with its respective punctuation. In addition to that, the spaces on the same line must be spread evenly between words.

Before we start: Divide and conquer

As always, we need to fully articulate out intentions in plain English, so in this case:

We need to split the string into an array of its contained words.
We then need two more empty arrays. In the first one, we’re going to add our words back until we hit the line limit. The second one will hold all the lines we’ve reconstructed.
Then we need a variable to count the characters per line. Each time we go through a word, we’re going to update this number to keep track of our character limit per line.

We’re going to build two functions to accomplish our goals. The first one will create the lines and the second one will add spaces until we reach the target character limit. Let’s focus on the first one.
Our skeleton function, along with the text to align:

const paragraph = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.';
lineBuilder = (text) => {
}
lineBuilder(paragraph);

Now we need to initialize a few variables:

lineBuilder = (text) => {
// This will hold all the words in an array
const splitParagraph = longText.split(' '); 
// This one will hold a line at a time.
let wordLine = [];
// This one will hold ALL of our lines
let allLines = [];
// We'll use this one to keep track of our characters per line.
let wordCharsSubtotal = 0;
}

Now we need to iterate over our array of words:

lineBuilder = (text) => {
const splitParagraph = longText.split(' ');
let wordLine = [];
let allLines = [];
let wordCharsSubtotal = 0; 
splitParagraph.forEach(word => {
    wordCharsSubtotal += word.length;
    const lineCharsRemaining = charLimit - wordCharsSubtotal - (wordLine.length - 1);
    if (lineCharsRemaining > 0) {
      wordLine.push(word);
    } else {
    allLines.push(wordLine);
    wordLine = [word];
    wordCharsSubtotal = word.length;
    }
  });
}

What’s happening here is we’re going through each word, adding the amount of its characters to the count and then figuring out how many characters we have left. If we have the space, we push this word to the array, and if not, we start all over with the next word until we’re done.
If we were to console.log our current results, we would get something like this:

[
  [ 'Lorem', 'ipsum', 'dolor', 'sit', 'amet,' ],
  [ 'consectetur', 'adipiscing', 'elit,' ],
  [ 'sed', 'do', 'eiusmod', 'tempor' ],
  [ 'incididunt', 'ut', 'labore', 'et', 'dolore' ],
  [ 'magna', 'aliqua.', 'Ut', 'enim', 'ad', 'minim' ],
  [ 'veniam,', 'quis', 'nostrud' ],
  [ 'exercitation', 'ullamco', 'laboris' ],
  [ 'nisi', 'ut', 'aliquip', 'ex', 'ea', 'commodo' ],
  [ 'consequat.', 'Duis', 'aute', 'irure' ],
  [ 'dolor', 'in', 'reprehenderit', 'in' ],
  [ 'voluptate', 'velit', 'esse', 'cillum' ],
  [ 'dolore', 'eu', 'fugiat', 'nulla' ],
  [ 'pariatur.', 'Excepteur', 'sint' ],
  [ 'occaecat', 'cupidatat', 'non' ],
  [ 'proident,', 'sunt', 'in', 'culpa', 'qui' ],
  [ 'officia', 'deserunt', 'mollit', 'anim' ]
]

Ok, we got a multidimensional array that we need to go through to add all the spaces we need:

allLines.push(wordLine);
const finalLines = allLines.map(line => {
  const numLetterChars = line.join('').length;
  const spaceCharsNeeded = charLimit - numLetterChars;
  const lineWithSpaces = addSpaces(line, spaceCharsNeeded, 0);
  return lineWithSpaces.join('');
});
finalLines.forEach(line => {
  console.log(line);
});

You might recall that we already pushed all lines into wordLine. We’re doing it here again because if we don’t, we eventually run out of words and don’t hit the else statement. If you want to test it, run it both with and without the second push, you’ll see how it misses the last line.
So we’re mapping over our multidimensional array and counting the amount of characters by counting all the characters and then substracting this amount from our character limit to figure out how many spaces we need to hit our character limit. Then we’re running another function (that we haven’t written yet) to add the neccessary spaces.

Final step: adding the spaces

Now we need to write the last function we invoked in the last one. As you can guess, this one takes three parameters: the line, how many characters we need and a counter to keep track of the added spaces:

function addSpaces(line, spaceCharsNeeded, spacesCharsAdded) {
  for (let i = 0; i < line.length - 1; i++) {
    if (spaceCharsNeeded - spacesCharsAdded > 0) {
      line[i] += ' ';
      spacesCharsAdded += 1;
     }
  }
  if (spaceCharsNeeded > spacesCharsAdded) {
    return addSpaces(line, spaceCharsNeeded, spacesCharsAdded);
  }
  return line;
}

So we’re starting a for loop with a counter, and as long as the counter is less than the length of the current line-1, we increment the counter. On each iteration, we’re using the counter to get the position of the current word in the array and add a space, then we add a space to it and increment our character counter. This only happens if there are still characters to fill. Then we’re adding a little bit of recursion to make the function invoke itself if there’s still room to add more spaces.

The complete code:

const paragraph = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.';
const charLimit = 30;
function lineBuilder(text) {
const splitParagraph = text.split(' ');
let allLines = [];
let wordLine = [];
let wordCharsSubtotal = 0;
splitParagraph.forEach(word => {
  wordCharsSubtotal += word.length;
  const lineCharsRemaining =
  charLimit - wordCharsSubtotal - (wordLine.length - 1);
  if (lineCharsRemaining > 0) {
    wordLine.push(word);
  } else {
      allLines.push(wordLine);
      wordLine = [word];
      wordCharsSubtotal = word.length;
    }
  });
  allLines.push(wordLine);
  const finalLines = allLines.map(line => {
    const numLetterChars = line.join('').length;
    const spaceCharsNeeded = charLimit - numLetterChars;
    const lineWithSpaces = addSpaces(line, spaceCharsNeeded, 0);
    return lineWithSpaces.join('');
  });
  finalLines.forEach(line => {
    console.log(line);
  });
}
addSpaces = (line, spaceCharsNeeded, spacesCharsAdded) => {
  for (let i = 0; i < line.length - 1; i++) {
    if (spaceCharsNeeded - spacesCharsAdded > 0) {
      line[i] += ' ';
      spacesCharsAdded += 1;
    }
  }
  if (spaceCharsNeeded > spacesCharsAdded) {
    return addSpaces(line, spaceCharsNeeded, spacesCharsAdded);
  }
return line;
}
lineBuilder(paragraph);

John Fajardo

Algorithm practice: justify a paragraph

Before we start: Divide and conquer

Final step: adding the spaces

The complete code: