Line Breaks
January 27, 2017
Here is our program; the upper-triangular matrix is called spaces
, the minimum cost is never computed, and the output is built up from end to beginning:
(define (line-break str width) (define (not-null? str) (< 0 (string-length str))) (define (min-non-neg-at m x c) (let ((min #e1e15) (at (+ x 1))) (for (r 0 x 1) (when (and (< (matrix-ref m r c) min) (not (negative? (matrix-ref m r c)))) (set! min (matrix-ref m r c)) (set! at r))) at)) (define (slice xs first past) (let loop ((i first) (zs (list))) (if (= i past) (string-join #\space (reverse zs)) (loop (+ i 1) (cons (vector-ref xs i) zs))))) (let* ((words (filter not-null? (string-split #\space str))) (lens (list->vector (map string-length words))) (count (length words)) (words (list->vector words))) (let ((spaces (make-matrix count count -1))) (for (r 0 count 1) (matrix-set! spaces r r (- width (vector-ref lens r))) (for (c (+ r 1) count 1) (matrix-set! spaces r c (- (matrix-ref spaces r (- c 1)) (vector-ref lens c) 1)))) (let loop ((end count) (lines (list))) (let ((start (min-non-neg-at spaces count (- end 1)))) (if (zero? start) (cons (slice words start end) lines) (loop start (cons (slice words start end) lines))))))))
And here’s some sample output:
> (line-break "aaa bb cc ddddd" 6) ("aaa" "bb cc" "ddddd") > (for-each (lambda (line) (display line) (newline)) (line-break "It was the best of times, it was the worst of times." 15)) It was the best of times, it was the worst of times. > (for-each (lambda (line) (display line) (newline)) (line-break "It was the best of times, it was the worst of times." 20)) It was the best of times, it was the worst of times.
We used string-split, string-join, and the matrix operations from the Standard Prelude. You can run the program at http://ideone.com/QPEK3f.