// 68. Text Justification #include #include /* * given an array of strings 'words', and a width 'max_width', format the text * such that each line has exactly 'max_width' characters and is fully (left and * right) justified. you should pack your words in a greedy approach; that is, * pack as many words as you can in each line. pad extra spaces ' ' when * necessary so that each line has exactly 'max_width' characters. extra spaces * between words just be distributed as evenly as possible. if the number of * spaces on a line does not divide evenly between the words, the empty slots on * the left will be assigned more spaces than the slots on the right. for the * last line of text, it should be left-justified, and no extra space is * inserted between words. */ int get_len(char *s) { int len = 0; while (s[len]) len++; return len; } char *centre_justify(char **words, int words_size, int *len, int start_idx, int end_idx, int max_width) { int width = 0; for (int i = start_idx; i <= end_idx; i++) width += len[i]; int total_space = max_width - width; int space = total_space / (end_idx - start_idx); int bonus_space = total_space % (end_idx - start_idx); char *line = (char *)malloc(sizeof(char) * (max_width + 1)); int idx = 0; for (int i = start_idx; i <= end_idx; i++) { if (i > start_idx) { for (int j = 0; j < space; j++) line[idx++] = ' '; if (bonus_space--) line[idx++] = ' '; } for (int j = 0; j < len[i]; j++) line[idx++] = words[i][j]; } line[idx] = 0; return line; } char *left_justify(char **words, int words_size, int *len, int start_idx, int end_idx, int max_width) { char *line = (char *)malloc(sizeof(char) * (max_width + 1)); int idx = 0; for (int i = start_idx; i <= end_idx; i++) { if (i > start_idx) line[idx++] = ' '; for (int j = 0; j < len[i]; j++) line[idx++] = words[i][j]; } for (int i = idx; i < max_width; i++) line[idx++] = ' '; line[idx] = 0; return line; } char **fullJustify(char **words, int words_size, int max_width, int *return_size) { if (!words_size) { char **ans = (char **)malloc(sizeof(char *)); ans[0] = (char *)malloc(sizeof(char) * max_width + 1); // hmm, pemdas? int idx = 0; for (int i = 0; i < max_width; i++) ans[0][idx++] = ' '; ans[0][idx] = 0; *return_size = 1; return ans; } int *len = (int *)calloc(words_size, sizeof(int)); for (int i = 0; i < words_size; i++) len[i] = get_len(words[i]); int *start_idx = (int *)malloc(sizeof(int) * words_size); int start_len = 0, width = 0, new_width; start_idx[start_len++] = 0; for (int i = 0; i < words_size; i++) { new_width = width + len[i]; if (width) new_width++; if (new_width > max_width) { start_idx[start_len++] = i; width = len[i]; } else width = new_width; } char **ans = (char **)malloc(sizeof(char *) * start_len); int idx = 0; for (int i = 0; i < start_len - 1; i++) { if (start_idx[i + 1] - start_idx[i] >= 2) ans[idx++] = centre_justify(words, words_size, len, start_idx[i], start_idx[i + 1] - 1, max_width); else ans[idx++] = left_justify(words, words_size, len, start_idx[start_len - 1], words_size - 1, max_width); } ans[idx] = left_justify(words, words_size, len, start_idx[start_len - 1], words_size - 1, max_width); free(start_idx); *return_size = start_len; return ans; } int main() { char w1[7][14] = {"This", "is", "an", "example", "of", "text", "justification."}; char w2[6][14] = {"What", "must", "be", "acknowledgment", "shall", "be"}; int rs1[] = {}, rs2[] = {}; char **fj1 = fullJustify(w1, 7, 16, rs1); char **fj2 = fullJustify(w2, 6, 16, rs2); for (int i = 0; i < 7; i++) printf("%s ", fj1[i]); printf("\n"); for (int i = 0; i < 6; i++) printf("%s ", fj2[i]); printf("\n"); }