Programming Praxis

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.

Pages: 1 2