; line breaks

(define (make-matrix rows columns . value)
  (do ((m (make-vector rows)) (i 0 (+ i 1)))
      ((= i rows) m)
    (if (null? value)
        (vector-set! m i (make-vector columns))
        (vector-set! m i (make-vector columns (car value))))))

(define (matrix-ref m i j) (vector-ref (vector-ref m i) j))

(define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x))

(define-syntax for
  (syntax-rules ()
    ((for (var first past step) body ...)
      (let ((ge? (if (< first past) >= <=)))
        (do ((var first (+ var step)))
            ((ge? var past))
          body ...)))
    ((for (var first past) body ...)
      (let* ((f first) (p past) (s (if (< first past) 1 -1)))
        (for (var f p s) body ...)))
    ((for (var past) body ...)
      (let* ((p past)) (for (var 0 p) body ...)))))

(define (string-split sep str)
  (define (f cs xs) (cons (list->string (reverse cs)) xs))
  (let loop ((ss (string->list str)) (cs '()) (xs '()))
    (cond ((null? ss) (reverse (if (null? cs) xs (f cs xs))))
          ((char=? (car ss) sep) (loop (cdr ss) '() (f cs xs)))
          (else (loop (cdr ss) (cons (car ss) cs) xs)))))

(define (string-join sep ss)
  (define (f s ss)
    (string-append s (string sep) ss))
  (define (join ss)
    (if (null? (cdr ss)) (car ss)
      (f (car ss) (join (cdr ss)))))
  (if (null? ss) "" (join ss)))

(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))))))))

(display (line-break "aaa bb cc ddddd" 6)) (newline)
(newline)

(for-each (lambda (line) (display line) (newline))
  (line-break "It was the best of times, it was the worst of times." 15))
(newline)

(for-each (lambda (line) (display line) (newline))
  (line-break "It was the best of times, it was the worst of times." 20))