The ** Divide & Conquer Algorithm for Line-Breaking** described here is given below, both in Python and in Dart (which is similar to Java/C#).

Line-breaking is also known as “line wrap”, “word wrap”, or “paragraph formation”, and this algorithm is used for achieving minimum raggedness.

This algorithm works, but it considers each space as having exactly `width = 1.0`

.

My Question:

**How can I modify this algorithm so that it ignores spaces? In other words, make it consider spaces as having width 0.0? (or it would also work for me if I could define any 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<List<int>> divide(List<num> boxWidths, num maxWidth) { int count = boxWidths.length; List<num> offsets = [0]; for (num boxWidth in boxWidths) { offsets.add(offsets.last + min(boxWidth, maxWidth)); } List<num> minimum = [0]..addAll(List<num>.filled(count, 9223372036854775807)); List<int> breaks = List<int>.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<List<int>> stack = Queue()..add([i0, j0, i1, j1]); while (stack.isNotEmpty) { List<int> 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<List<int>> indexes = []; while (j > 0) { int i = breaks[j]; indexes.add(List<int>.generate(j - i, (index) => index + i)); j = i; } return indexes.reversed.toList(); } } `