Tag: Optimization

the Algorithm of division and conquest to break lines It is described below, in both Python and Dart (which is similar to Java / C #).

Line breaking is also known as "line wrapping", "word wrapping", or "paragraph formation", and this algorithm is used to achieve minimal irregularity.

This algorithm works, but consider that each space has exactly width = 1.0 .

My question:

How can I modify this algorithm so that it ignores spaces? In other words, have him consider spaces with width 0.0? (or would it also work for me if I could define the width I wanted for the spaces including 0.0)

Python implementation:

def divide(text, width):
    words = text.split()
    count = len(words)
    offsets = (0)
    for w in words:
        offsets.append(offsets(-1) + len(w))

    minima = (0) + (10 ** 20) * count
    breaks = (0) * (count + 1)

    def cost(i, j):
        w = offsets(j) - offsets(i) + j - i - 1
        if w > width:
            return 10 ** 10
        return minima(i) + (width - w) ** 2

    def search(i0, j0, i1, j1):
        stack = ((i0, j0, i1, j1))
        while stack:
            i0, j0, i1, j1 = stack.pop()
            if j0 < j1:
                j = (j0 + j1) // 2
                for i in range(i0, i1):
                    c = cost(i, j)
                    if c <= minima(j):
                        minima(j) = c
                        breaks(j) = i
                stack.append((breaks(j), j+1, i1, j1))
                stack.append((i0, j0, breaks(j)+1, j))

    n = count + 1
    i = 0
    offset = 0
    while True:
        r = min(n, 2 ** (i + 1))
        edge = 2 ** i + offset
        search(0 + offset, edge, edge, r + offset)
        x = minima(r - 1 + offset)
        for j in range(2 ** i, r - 1):
            y = cost(j + offset, r - 1 + offset)
            if y <= x:
                n -= j
                i = 0
                offset += j
                break
        else:
            if r == n:
                break
            i = i + 1

    lines = ()
    j = count
    while j > 0:
        i = breaks(j)
        lines.append(' '.join(words(i:j)))
        j = i
    lines.reverse()
    return lines

Dart implementation:

class MinimumRaggedness {

  /// Given some (boxWidths), break it into the smallest possible number
  /// of lines such as each line has width not larger than (maxWidth).
  /// It also minimizes the difference between width of each line,
  /// achieving a "balanced" result.
  /// Spacing between boxes is 1.0.
  static List> divide(List boxWidths, num maxWidth) {

    int count = boxWidths.length;
    List offsets = (0);

    for (num boxWidth in boxWidths) {
      offsets.add(offsets.last + min(boxWidth, maxWidth));
    }

    List minimum = (0)..addAll(List.filled(count, 9223372036854775807));
    List breaks = List.filled(count + 1, 0);

    num cost(int i, int j) {
      num width = offsets(j) - offsets(i) + j - i - 1;
      if (width > maxWidth)
        return 9223372036854775806;
      else
        return minimum(i) + pow(maxWidth - width, 2);
    }

    void search(int i0, int j0, int i1, int j1) {
      Queue> stack = Queue()..add((i0, j0, i1, j1));

      while (stack.isNotEmpty) {
        List info = stack.removeLast();
        i0 = info(0);
        j0 = info(1);
        i1 = info(2);
        j1 = info(3);

        if (j0 < j1) {
          int j = (j0 + j1) ~/ 2;

          for (int i = i0; i < i1; i++) {
            num c = cost(i, j);
            if (c <= minimum(j)) {
              minimum(j) = c;
              breaks(j) = i;
            }
          }

          stack.add((breaks(j), j + 1, i1, j1));
          stack.add((i0, j0, breaks(j) + 1, j));
        }
      }
    }

    int n = count + 1;
    int i = 0;
    int offset = 0;

    while (true) {
      int r = min(n, pow(2, i + 1));
      int edge = pow(2, i) + offset;
      search(0 + offset, edge, edge, r + offset);
      num x = minimum(r - 1 + offset);

      bool flag = true;
      for (int j = pow(2, i); j < r - 1; j++) {
        num y = cost(j + offset, r - 1 + offset);
        if (y <= x) {
          n -= j;
          i = 0;
          offset += j;
          flag = false;
          break;
        }
      }

      if (flag) {
        if (r == n) break;
        i = i + 1;
      }
    }

    int j = count;

    List> indexes = ();

    while (j > 0) {
      int i = breaks(j);
      indexes.add(List.generate(j - i, (index) => index + i));
      j = i;
    }

    return indexes.reversed.toList();
  }
}