Calculate the target size to truncate to fit strings inside a specific size

The problem

I'm writing a program to display tags (strings) in the console, and I need to fit them inside a specific width. I need to truncate the some tags when their total length is too large. I'm looking for an efficient algorithm to calculate the maximum size for all strings to truncate to.

For example, assume that we have 3 tags to display, and the total available size is 12 characters. The following code block shows how to fit them inside the available space. (In the real situation we also need separators between them, but for simplicity they are omitted here.)

The tags:
 11111         5 chars wide
 2222222       7 chars
 333           3 chars

The space:
|------------| 12 chars

Not truncated:
 111112222222333   5+7+3 = 15 chars, too long

Truncate every tag to 4 chars:
 11112222333   4+4+3 = 11 chars, fits

Similarly, if the space is 13 characters long, the trucated size is 5 chars:

|-------------|
 1111122222333  5+5+3 = 13 chars, fits

My current solution

I currently use a trivial way to solve this problem. Here's the pseudocode:

// the input
tags = [...]
target_width = ...

tag_widths = tags.map(x => x.width).sort()
total_width = tag_width.sum()

truncated_count = 0
truncate_to = tag_widths[0]

// list of items
// v      | <- truncation line
// *******| 
// *****  |
// ***    |

while true {
  // find the next group of tags with the same length
  //
  //      |
  // ******* <-
  // *****|
  // ***  |
  truncated_count += 1
  while truncated_count < tags.length 
        && tag_widths[truncated_count] == truncate_to {
    truncated_count += 1
  }
  // new_truncate_to is the width of the next group
  new_truncate_to = tag_widths[truncated_count] or 0 if truncated_count > tags.length
  
  // calculate the length after truncating all of them
  //
  //      |
  // *****|-- 
  // *****|
  // ***  |
  new_total_width = total_width - truncated_count * (new_truncate_to - truncate_to)

  if new_total_width <= target_width {
    // the target length is between truncate_to and new_truncate_to
    //       |
    // ******|- 
    // ***** |
    // ***   |
    new_truncate_to += floor((target_width - new_total_width) / truncated_count)
    truncate_to = new_truncate_to
    break
  } else {
    // the current truncation is not enough
    total_width = new_total_width
    truncate_to = new_truncate_to
  }
}

// the result
truncate_to

Is there any algorithm that is more efficient?

1 answer

  • answered 2021-05-15 18:13 Rocco

    I cannot fully understand your code, but I propose a slightly more efficient algorithm.

    The most of the cost is the initial sorting of the widths O(n*log n), then the rest is done with a single pass on the array.

    Pseudo-code:

    let remainingwidth = total available width
    sort tags array by width
    for i=0, i<tags.length; i=i+1
       let avg_avail_width = remainingwidth / (tags-length - i)  //Integer division, rounded down
       if tags[i].width > avg_avail_width
          tags[i].width = avg_avail_width
       end if      
       remainingwidth -= tags[i].width
    end for each
    

    Note that in case the available width cannot be distributed evenly (e.g. total width 20, tag widths [3,7,8,9], 20-3 = 17 so we cannot have equal widths for the remaining tags) this strategy assign the extra space to the tags with the longest original widths.