Text justification
Hi everyone, in this article I'll try to explain how to implement text justification algorithm. We'll use python for this. Let's get started.
I saw this task at codewars a few month ago and solved it. The task formulates in the following way: "task is to emulate text justification in monospace font. You will be given a single-lined text and the expected justification width".
- Use spaces to fill in the gaps between words.
- Each line should contain as many words as possible.
- Use '\n' to separate lines.
- Gap between words can't differ by more than one space.
- Lines should end with a word not a space.
- '\n' is not included in the length of a line.
- Large gaps go first, then smaller ones ('Lorem--ipsum--dolor--sit-amet,' (2, 2, 2, 1 spaces)).
- Last line should not be justified, use only one space between words.
- Last line should not contain '\n'
- Strings with one word do not need gaps ('somelongword\n').
So, the result of justified text should look like this:
The idea of implementation of the algorithm is described in following text.
While we can add words to line we are doing it, if next word + current line length is bigger, than width, we don't add this word to the current line. If current line width still less, than width, we add spaces to line in the direction from left to right.
def justify(text, width):
# starting variables
line = ''
linelength = 0
finished_text = ''
# iterate over text, item represents each word
for item in text.split():
# check if current line + new word is bigger than given width
if linelength + len(item) > width:
# delete space after last word
line = line[:-1]
linelength -= 1
# if length of line is less than width, then add spaces to this line
if width - linelength > 0:
line = add_spaces(line, width - linelength)
# add line with all needed spaces to the final text version
finished_text += line + '\n'
# setup variables to starting positions
line = ''
linelength = 0
# if current line + new_word is less than width, then add new_word to current line
else:
linelength += len(item)
line += item
linelength += 1
line += ' '
# delete last space because of conditions on Codewars
line = line[:-1]
finished_text += line
return finished_text
Let's see on the code in order. It's starting from initializing starting variables. Further, I start to iterate over string and face main condition.
if linelength + len(item) > width:
It's really important to have > sign and not >=, because anyway line width will be (width + 1) size.
Next nested condtion is about adding additional spaces to line.
if width - linelength > 0:
line = add_spaces(line, width - linelength)The realization of add_spaces function will be below.
If line width + word is less than width we don't do anything special, just adding word to line and one space after it.
Now let's dive into add_spaces function.
The idea of this function is next: Count needed amount of additional spaces, iterate over line (from the left to the right side) and put additional spaces between words, also decrease variable with needed amount of spaces. If after one circle there is still not enough spaces -> repeat it.
def add_spaces(line, count_spaces):
i = 0
splitted_line = line.split()
total_words = sum(1 for _ in splitted_line)
if total_words == 1:
return line
# start iterate over list if there are more than one word
while True:
# if it's last word and it's line still needed more spaces then iterate over list from the start (i = 0)
if count_spaces != 0 and i == (total_words - 1):
i = 0
# check if it's still needed to add spaces to line
if count_spaces > 0:
splitted_line[i] += ' '
count_spaces -= 1
i += 1
else:
break
return ' '.join(splitted_line)Firstly, count amount of words in given line. Then, based on amount of words, add spaces to the line.
if count_spaces != 0 and i == (total_words - 1):
This condition detects, if already has been made one iteration over list but we still got spaces to add.
As always full code can be found at my GitHub: https://github.com/rastr-0/teletype_source_files/tree/main/text_justification