Implementing an algorithm to justify multiple lines of text

Problem statement

Given a sequence of words and an integer line length k, return a list of strings which represents each line, fully justified. More specifically, you should have as many words as possible in each line. There should be at least one space between each word. Pad extra spaces when necessary so that each line has exactly length k. Spaces should be distributed as equally as possible, with the extra spaces, if any, distributed starting from the left. If you can only fit one word on a line, then you should pad the right-hand side with spaces. Each word is guaranteed not to be longer than k.

For example, given the list of words ["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"] and k = 16, you should return the following:

"the quick brown" # 1 extra space on the left

"fox jumps over" # 2 extra spaces distributed evenly

"the lazy dog" # 3 extra spaces distributed evenly.

Understand the problem

The best way to understand a problem in programming is to first brute force it.

Input: A list of words

Output: left aligned pretty printed text

Let imagine we have a scrabble box divided into k=16 slots. The objective is to fit as many words as possible into this space making sure both ends don't have white space.

 
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14|15 
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
 W | e |   | w | e | r | e |   | f | o | o | l | s |   | t | o 
 m | a | k | e |   | w | a | r |   | a | g | a | i | n | s | t 
 o | u | r |   |   | b | r | o | t | h | e | r | s |   | i | n
 a | r | m | s |   |   |   |   |   |   |   |   |   |   |   |   
 

Let's try the followings:

• Find the sequential words with sum of characters (sum_chars + # of words - 1) less than or equal to k.

• The number of white spaces should be (k - sum_chars)

• Distribute white spaces at end of each word so that they are fairly evenly spread.

---

Python Code

import unittest
def justifyWords(wordlist, k):
    justified_blob = ""
    wordslength = 0
    start_idx = end_idx = 0

    if len(wordlist) == 0:
        raise Exception("Empty wordlist")
        # clone the wordlist (only works in python3.3 or newer!)
        words = wordlist.copy()
        while words:
            if wordslength < k - (end_idx - start_idx) -1:
                try:
                    wordslength += len(words.pop(0))
                    end_idx+=1
                except IndexError:
                    # should be close to end of wordslist
                    if wordslength > 0:
                        sepa_length = (k - wordslength) // (end_idx - start_idx)
                        separator = ' ' * sepa_length
                        sentence = separator.join([wordlist[i] for i in range(start_idx, end_idx)])
                        if (len(sentence)) < k:
                            extra_space = k - wordslength - sepa_length 		
                            extras = ' ' * extra_space
                            sentence = sentence.replace(' ', extras, 1)
                            justified_blob += sentence + '\n'	
                            print(sentence)

                        break #exit while loop
            else:
                # process the k length of words
                if (k - wordslength) == (end_idx - start_idx)-1:
                    sepa_length = 1
                else:
                    sepa_length = (k - wordslength) // (end_idx - start_idx)

                separator = ' ' * sepa_length
                sentence = separator.join([wordlist[i] for i in range(start_idx, end_idx)])
                if (len(sentence)) < k:
                    extra_space = k - wordslength - sepa_length 		
                    extras = ' ' * extra_space
                    sentence = sentence.replace(' ', extras, 1)

                justified_blob += sentence + '\n'	
                print(sentence)

                # reset variables for the next line
                wordslength = 0
                start_idx = end_idx

        # last few words in the dangling pipe
        if wordslength > 0:
            sepa_length = (k - wordslength) // (end_idx - start_idx)
            separator = ' ' * sepa_length
            sentence = separator.join([wordlist[i] for i in range(start_idx, end_idx)])
            if (len(sentence)) < k:
                extra_space = k - wordslength - sepa_length -1 		
                if extra_space%(end_idx - start_idx) == 1:
                    sentence = sentence.replace(' ', '  ', extra_space)
                else:
                    extras = ' ' * extra_space
                    sentence = sentence.replace(' ', extras, 1)
			
            justified_blob += sentence
            print(sentence)

        return justified_blob

#
# Note: unittest needs pip3 install pytest
#
class TestJustifier(unittest.TestCase):
    def test_code(self):
        wordlist = []
        k = 16
        justified_blob = '''
the  quick brown
fox   jumps over
the    lazy  dog
'''
        with self.assertRaises(Exception):
            justifyWords(wordlist, k)
   

if __name__ == "__main__":
    wordlist = ["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]
    k = 16
    justifyWords(wordlist, k) 

    print("\n")
    wordlist = ["we", "were", "fools", "to", "make", "war", "against", "our", "brothers", "in" , "arms"]
    k = 16
    justifyWords(wordlist, k) 
    unittest.main()

Output

$ python3 codechallenge_012.py
the  quick brown
fox   jumps over
the    lazy  dog


we were fools to
make war against
our  brothers in
arms