How to justify and print a paragraph using a 2d array in C?

I have an assignment that basically is asking to justify a paragraph given line length. So for instance the paragraph "I am a student of C, this is my first assignment. I hope I finish on time." given line length of 17 should be as follows:

output
I am a student of
C,   this  is  my 
first assignment.
I  hope  I finish
on          time.

I am having trouble with dynamically placing spacing in between the words. I currently have a function that counts the words in a paragraph and stores them into a 2d array but I have no idea how to a) calculate the amount of spacing in between words and b) how to dynamically print that justified paragraph. Here is the code I have so far:


int getAllWordsFrom2DArray(char *paragraph, char words[MAX_NUMBER_OF_WORDS][MAX_WORD_LENGTH]) {
    int i,j,totalWords = 0;
    for(i=0; i < strlen(paragraph); i++) {
        int wordLength;
        if (paragraph[i] == ' ' || paragraph[i+1] == '\0') {
            totalWords++;
            wordLength = i;
            for(j=0; j < wordLength; j++) {
                words[i][j] = paragraph[j];
            }
        }
    }
    printf("%s", words);

    return totalWords;
}


//Code in progress
int getNumberOfWordsForNextLine(int totalWords, int lineLength, char words[MAX_NUMBER_OF_WORDS][MAX_WORD_LENGTH]) {
    int wordsForNextLine = 0;
    for(int i=0; i < totalWords; i++) {
        wordsForNextLine = 0 ;
    }
}

//code in progress
void printNextLine(int wordsForNextLine) {

}


//skeleton code provided by instructor
void justifyAndPrintParagraph(char* paragraph, int lineLength) {
    char words[MAX_NUMBER_OF_WORDS][MAX_WORD_LENGTH];
    int totalWords = getAllWordsFrom2DArray(paragraph, words);
    int processedWords = 0;

    while (processedWords < totalWords) {
        int wordsForNextLine = getNumberOfWordsForNextLine(totalWords, lineLength, words);
        printNextLine(wordsForNextLine);
        processedWords += wordsForNextLine;
    }
}

To clarify, we are not allowed to use strlok. Essentially we are expected to just use the basics in doing this. I need to use the void justifyAndPrintParagraph function and signature but other than that I'm free to do whatever.

Edit: I forgot to add that if spaces cannot be evenly divided then the extra spaces are to be allocated left to right.

Any help is greatly appreciated.

Solution

Consider how many spaces you have to distribute. For example, given the input:

18
I am the very model of a modern Major-General.

Computing the number of words that fit on the line goes:

"I" + "am" + "the" + "very"           + (4-1 words) --> 13
"I" + "am" + "the" + "very" + "model" + (5-1 words) --> 19

So only the first 4 words fit on an 18-character line. The number of space characters to distribute are then easily calculated:

N = max_line_width - sum_of_word_lengths

Now for the hard part: how many spaces between each word? Your homework expects you to divvy extra unbalanced spaces left-to-right, meaning that each pair of words may have a different number of space characters.

However, the difference will always be a single space character. Take a moment to convince yourself this is true:

I···am···the··very
-2-4-6-8-0-2-4-6-8

In our little example, we find that there are three space characters in the first two inter-word spacings, and two space characters in the last.

The minimum number of space characters per inter-word spacing is easy enough to caluclate:

nsp = N / (number_of_words_in_line - 1)

^{Beware! What happens if you have only one word on the line? (Do you really need to distribute spaces for such a line?)}

And now, for the cool tricky math part, you can calculate the number of times you need to add a space to the inter-word spacing as:

nplus1 = N - nsp * (number_of_words_in_line - 1)

or just:

nplus1 = N % (number_of_words_in_line - 1)

^{Keep in mind that it is possible that all inter-word spacings are the same number of space characters, and may be exactly one space character even. Notice how our calculations work just as well in those cases.}

Now you can print the words for the line in a loop, adding nsp space characters after every word, plus an extra space after the first nplus1 words.

^{Remember, the last word of the line doesn’t get any spaces. It is followed by a newline!}

Hopefully this should help you work your way through this assignment. (I personally think it is a bit of a careless assignment as your first ever, introduction to C class.)

And now, if I have made errors, it is because I am very, very sleepy. Someone will surely point it out if I have.