Text Justify

text_justify.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>

int main(){
    char words[100][100];
    int word_count = 0, line_length;

    // Get words and M
    {
        FILE* inf = fopen("text.txt", "r");
        if(inf == NULL){
            printf("ERROR: Could not open the text.txt!");
            exit(-1);
        }

        printf("M(Line length): ");
        scanf("%d", &line_length);

        char result;
        do{ result = fscanf(inf, "%s", words[word_count++]); } while(result != EOF);
        --word_count;
        fclose(inf);
    }

    // Prepare the arrays
    int** space;
    int** spaceCost;
    int* cost;
    {
        space = (int**)calloc(word_count, sizeof(int*));
        spaceCost = (int**)calloc(word_count, sizeof(int*));
        cost = (int*)calloc(word_count, sizeof(int));

        int i;
        for(i = 0; i < word_count; ++i){
            space[i] = (int*)calloc(word_count, sizeof(int));
            spaceCost[i] = (int*)calloc(word_count, sizeof(int));
        }
    }

    // Find the spaceCosts
    {
        int i, j;
        for(i = 0; i < word_count; ++i){
            for(j = i; j < word_count; ++j){
                // Calculate the sum of lengths of words from i to j
                int sum_lk = 0, k;
                for(k = i; k <= j; ++k) sum_lk += strlen(words[k]);

                // Calculate the space cost
                space[i][j] = line_length - sum_lk - (j - i);
                
                if(space[i][j] < 0) spaceCost[i][j] = INT_MAX;
                else if(j == word_count-1) spaceCost[i][j] = 0;
                else spaceCost[i][j] = space[i][j]*space[i][j]*space[i][j];
            }
        }
    }

    // Print matrices
    {
       int i, j;
       printf("\n /// SPACE MATRIX\n");
       for(i = 0; i < word_count; ++i){
            for(j = 0; j < word_count; ++j){
                printf("%d \t", space[i][j]);
            }
            printf("\n");
       }
       
       printf("\n /// SPACECOST MATRIX\n");
       for(i = 0; i < word_count; ++i){
            for(j = 0; j < word_count; ++j){
                  if(spaceCost[i][j] != INT_MAX)
                    printf("%d \t", spaceCost[i][j]);
                  else printf("~ \t");
            }
            printf("\n");
       }
    }
    // Calculate the minimum cost and word for it
    int* word = (int*)calloc(word_count, sizeof(int));
    {
        int i, j;
        for(i = word_count - 1; i >= 0; i--){
            cost[i] = spaceCost[i][word_count - 1];
            word[i] = word_count;
            for(j = word_count - 1; j > i; j--){
                if(spaceCost[i][j - 1] != INT_MAX){
                    int this_cost = cost[j] + spaceCost[i][j - 1];
                    if(cost[i] > this_cost){
                        cost[i] = this_cost;
                        word[i] = j;
                    }
                }
            }
        }
    }

    // Print cost and word arrays
    {
       int i;
       printf("\n /// COST ARRAY\n");
       for(i = 0; i < word_count; ++i){
             printf("%d \t", cost[i]);
       }
       printf("\n");
       
       printf("\n /// WORD ARRAY\n");
       for(i = 0; i < word_count; ++i){
            printf("%d \t", word[i]);
       }
       printf("\n");
    }

    // Print the paragraph
    {
        int i = 0, j;
        do{
            j = word[i];
            int k;
            for(k = i; k < j; ++k) printf("%s ", words[k]);
            printf("\n");
            i = j;
        } while(j < word_count);
        printf("Total cost: %d ,  Space Cost: %d", cost[0], (int)ceilf(pow(cost[0], 1.0f/3)));
    }

    // Clean-up
    {
        int i;
        for(i = 0; i < word_count; ++i){
            free(space[i]);
            free(spaceCost[i]);
        }
        free(space);
        free(spaceCost);
        free(cost);
        free(word);
    }
    
    getch();
    return 0;
}