Essays/Text Formatting
Given: a string of words separated by blanks and a positive integer w of the desired width. Replace appropriate blanks in the string by the newline character LF , so that lines are no wider than w and each line contains all the words that fit within the line. To focus on essentials, assume words are at most w in length, adjacent words are separated by exactly one blank, and the input string does not contain newlines.
The solution:
tc =: # (i.~{.]) [: }. (,#) {~^:a: 0: fmt=: 4 : 0 e=. (' ' I.@:= y),#y LF (e {~ <: tc e I. (x+2)+}:_1,e)} y )
tc solves a version of the transitive closure problem. The argument y represents a directed acyclic graph whose nodes are labelled i.#y , and i{y is the terminus of the arc originating at node i . (If (i{y)>:#y , node i has no outgoing arc.) tc y computes the nodes reachable from node 0 (but excluding 0 itself). For example:
y=: 1 3 4 6 7 8 9 10 12 13 15 15 15 15 15 (i.#y) ,: y 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 3 4 6 7 8 9 10 12 13 15 15 15 15 15 tc y 1 3 6 9 13
fmt works as follows: first, compute e , the indices of the blanks following each word, whence }:0,e+1 are the indices of the starting letters of the words. If a line were to start at word i , then the next line starts at the first word which ends beyond i{x+1+}:0,e+1 -- at word i{e I. x+1+}:0,e+1 or equivalently, i{e I. (x+2)+}:_1,e . We know the first line starts at word 0, so the lines (except the first) start at words tc e I. (x+2)+}:_1,e . Replace with newlines the characters that precede these words (equivalently, the characters that follow the preceding words), and we are done.
t=: 'Stop all the clocks, cut off the telephone, ' t=: t,'prevent the dog from barking with a juicy bone. ' t=: t,'The quick brown fox jumps over the lazy dog. ' t=: t,'Assiduously avoid any and all asinine alliterations.' 25 fmt t Stop all the clocks, cut off the telephone, prevent the dog from barking with a juicy bone. The quick brown fox jumps over the lazy dog. Assiduously avoid any and all asinine alliterations. 35 fmt t Stop all the clocks, cut off the telephone, prevent the dog from barking with a juicy bone. The quick brown fox jumps over the lazy dog. Assiduously avoid any and all asinine alliterations.
fmt can be written tacitly as:
end =: #@] ,~ ' ' I.@:= ] candidates =: ] I. 2&+@[ + }:@(_1&,)@] ix =: [ (<:@tc@candidates { ]) end fmtt =: LF"_`ix`] }
fmtcheck has the same arguments and result as fmt , but incorporates checks.
fmtcheck=: 4 : 0 assert. 1 >: #$y assert. (''-:y) +. 2=3!:0 y assert. -. LF e. y assert. (0=#$x) *. (x=<.x) *. 0<:x assert. x (0&< *. >:) #;._2 y,' ' e=. (' ' I.@:= y),#y z=. LF (e {~ <: tc e I. (x+2)+}:_1,e)} y assert. y -: ' ' (I. z=LF)}z assert. x >: n=. #;._2 z,LF assert. x <: (}:n) + }. i.&' ';._2 z,LF ) >./ #;._2 t,' ' NB. length of the longest word 14 (14+i.5 10) 1:@fmtcheck"0 _ t 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
See also
Contributed by Roger Hui. An earlier version of this text appeared in Section 1.2 of R.K.W. Hui, Some Uses of { and }, APL87, 1987-05-10.