in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #10

Algorithm 6.2: Design and implement a procedure that will left and right justify text in a way that avoids splitting words and leaves paragraphs indented. An attempt should also be made to distribute the additional blanks as evenly as possible in the justified line.

Let’s take the example from above. Same sentence, same n. Our output should be something like

    This  is a
    which   is
    quite long

We already know how to create lines with a maximum length, now we need to add additional spaces. That’s actually what I did by hand. I copied the above text and insert spaces. If you look back at our function, you can see its output.

user=> (wrap-word "This is a sentence which is quite long" 10)
((\space) (\q \u \i \t \e \space \l \o \n \g) (\w \h \i \c \h \space \i \s \space) (\s \e \n \t \e \n \c \e \space) (\T \h \i \s \space \i \s \space \a \space))

Let’s take the first part of the sentence:

(\T \h \i \s \space \i \s \space \a \space)

We need to delete trailing spaces first. There’s a short solution which is a probably a bit slow. However, this is just a learning experience, therefore performance isn’t that important. Also in production code I would use the library function trimr.

First we reverse the string, then we drop all spaces and then we reverse the string again.

user=> sentence
(\T \h \i \s \space \i \s \space \a \space)
user=> (reverse sentence)
(\space \a \space \s \i \space \s \i \h \T)
user=> (drop-while #(= \space %) (reverse sentence))
(\a \space \s \i \space \s \i \h \T)
user=> (reverse (drop-while #(= \space %) (reverse sentence)))
(\T \h \i \s \space \i \s \space \a)

Now we can apply that function, which I called delete-right-spaces on our complete sentence:

user=> (map delete-right-spaces (wrap-word "This is a sentence which is quite long" 10))
(() (\q \u \i \t \e \space \l \o \n \g) (\w \h \i \c \h \space \i \s) (\s \e \n \t \e \n \c \e) (\T \h \i \s \space \i \s \space \a))

Looks good. The next step is to calculate

a) How many white spaces we need to justify the text
b) Were to put them

We can calculate the current length of a line quite easily, we now the maximum aka. n therefore we need (n – length) additional white spaces.

For our cleaned sentence, we need:

user=> (- 10 (count sentence))

one additional whitespace. Were should we put them? Depends on the white spaces. One idea is that we ‘duplicate’ our existing white spaces starting with the first one. Here’s an example of the imagined function:

Input: (\T \h \i \s \space \i \s \space \a) and n = 10

=> we need one additional white space

Output: (\T \h \i \s \space \space \i \s)

In case we need two or more it should be evenly spaced. That is we need to know how many white spaces there are:

user=> (count (filter #(= \space %) sentence))

Here we have two. Now we know how many each whitespace needs: 1/2. However, that isn’t possible. Therefore, I want an other
imagined function which returns a partition which is as evenly distributed as possible given the needed white spaces and the available whitespace.

Input: 1 needed 2 available
Output: (1 0)

Continues tomorrow.

Write a Comment


This site uses Akismet to reduce spam. Learn how your comment data is processed.