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

Essays/Text Formatting

See also

Navigation menu

Search