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