Algorithm practice: justify a paragraph

John Fajardo
Feb 12, 2020 · 5 min read
Image for post
Image for post

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’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);

The Startup

Medium's largest active publication, followed by +771K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store