# Pretty Print Problem

#1

Hi,

I completely understood the problem of pretty print and I am able to understand how minimum messiness is calculated. I found the solution pretty elegant. My question is: Can we use the very same program to calculate where exactly we will put line breaks? I am having a hard time to convert these messiness values to line break indices.

0 Likes

#2

Yeah it’s tricky. One way of recovering the line breaks is to have another array of words.size() called “lineBreaks”. lineBreaks[i] = for a line ending with the ith word, what is the index of the optimal line break (the index of the word in words that starts a new line that ends with the ith word).

For a lot of these path recovery things (like shortest path or other DP), you need to leave “breadcrumbs” / clues when you find the optimal solution for a subproblem. So that means you should be setting lineBreaks whenever you set the memo[] with a new optimal value.

Then when everything has run, you start by looking at lineBreaks of words.size() - 1. For the book example, this will be 6. Now look 1 less than 6 (the next line will end with the word at index 5), lineBreaks[5] = 2 or 3 (2 or 3 since they give the same messiness whether c is on first line or on second line, depends on your algo implementation). Say its 3. Then we need to look at lineBreaks[2] = 0. 0 is obviously the first line break to start everything, so the path is 0, 3, 6.

0 Likes

#3

I believe this code works, I added it into their solution:

``````public static int minimumMessiness(List<String> words, int lineLength) {

// minimumMessiness[i] is the minimum messiness when placing
// words.subList(0, i + 1).
int[] lineBreaks = new int[words.size()];   //new
int[] minimumMessiness = new int[words.size()];
Arrays.fill(minimumMessiness, Integer.MAX_VALUE);
int numRemainingBlanks = lineLength - words.get(0).length();
minimumMessiness[0] = numRemainingBlanks * numRemainingBlanks;
lineBreaks[0] = 0;   //new
for (int i = 1; i < words.size(); ++i) {
numRemainingBlanks = lineLength - words.get(i).length();
minimumMessiness[i] =
minimumMessiness[i - 1] + numRemainingBlanks * numRemainingBlanks;
lineBreaks[i] = i;  //new
// Try adding words.get(i - 1), words.get(i - 2), ...
for (int j = i - 1; j >= 0; --j) {
numRemainingBlanks -= (words.get(j).length() + 1);
if (numRemainingBlanks < 0) {
// Not enough space to add more words.
break;
}
int firstJMessiness = j - 1 < 0 ? 0 : minimumMessiness[j - 1];
int currentLineMessiness = numRemainingBlanks * numRemainingBlanks;
if (firstJMessiness + currentLineMessiness < minimumMessiness[i]) {  //new
lineBreaks[i] = j;  //new
minimumMessiness[i] = firstJMessiness + currentLineMessiness;  //new
}
}
}

// print the lineBreak array and see
for(int i : lineBreaks) {
System.out.print(i + " ");
}
System.out.println();

return minimumMessiness[words.size() - 1];
}``````
0 Likes