{"id":26445,"date":"2017-12-20T21:18:00","date_gmt":"2017-12-20T15:48:00","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26445"},"modified":"2017-12-20T21:18:00","modified_gmt":"2017-12-20T15:48:00","slug":"c-programming-word-wrap-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-word-wrap-problem\/","title":{"rendered":"C Programming &#8211; Word Wrap Problem"},"content":{"rendered":"<p>Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly.<span id=\"more-21567\"><\/span> Assume that the length of each word is smaller than the line width.<\/p>\n<p>The word processors like MS Word do task of placing line breaks. The idea is to have balanced lines. In other words, not have few lines with lots of extra spaces and some lines with small amount of extra spaces.<\/p>\n<pre>The extra spaces includes spaces put at the end of every line except the last one.  \r\nThe problem is to minimize the following total cost.\r\n Cost of a line = (Number of extra spaces in the line)^3\r\n Total Cost = Sum of costs for all lines\r\n\r\nFor example, consider the following string and line width M = 15\r\n \"Geeks for Geeks presents word wrap problem\" \r\n     \r\nFollowing is the optimized arrangement of words in 3 lines\r\nGeeks for Geeks\r\npresents word\r\nwrap problem \r\n\r\nThe total extra spaces in line 1, line 2 and line 3 are 0, 2 and 3 respectively. \r\nSo optimal value of total cost is 0 + 2*2 + 3*3 = 13\r\n<\/pre>\n<p>Please note that the total cost function is not sum of extra spaces, but sum of cubes (or square is also used) of extra spaces. The idea behind this cost function is to balance the spaces among lines. For example, consider the following two arrangement of same set of words:<\/p>\n<ul>\n<li>There are 3 lines. One line has 3 extra spaces and all other lines have 0 extra spaces. Total extra spaces = 3 + 0 + 0 = 3. Total cost = 3*3*3 + 0*0*0 + 0*0*0 = 27.<\/li>\n<li>There are 3 lines. Each of the 3 lines has one extra space. Total extra spaces = 1 + 1 + 1 = 3. Total cost = 1*1*1 + 1*1*1 + 1*1*1 = 3.<\/li>\n<\/ul>\n<p>Total extra spaces are 3 in both scenarios, but second arrangement should be preferred because extra spaces are balanced in all three lines. The cost function with cubic sum serves the purpose because the value of total cost in second scenario is less.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Method 1 (Greedy Solution)<\/strong><br \/>\nThe greedy solution is to place as many words as possible in the first line. Then do the same thing for the second line and so on until all words are placed. This solution gives optimal solution for many cases, but doesn\u2019t give optimal solution in all cases. For example, consider the following string \u201caaa bb cc ddddd\u201d and line width as 6. Greedy method will produce following output.<\/p>\n<pre>aaa bb \r\ncc \r\nddddd<\/pre>\n<p>Extra spaces in the above 3 lines are 0, 4 and 1 respectively. So total cost is 0 + 64 + 1 = 65.<\/p>\n<p>But the above solution is not the best solution. Following arrangement has more balanced spaces. Therefore less value of total cost function.<\/p>\n<pre>aaa\r\nbb cc\r\nddddd<\/pre>\n<p>Extra spaces in the above 3 lines are 3, 1 and 1 respectively. So total cost is 27 + 1 + 1 = 29.<\/p>\n<p>Despite being sub-optimal in some cases, the greedy approach is used by many word processors like MS Word and OpenOffice.org Writer.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Method 2 (Dynamic Programming)<\/strong><br \/>\nThe following Dynamic approach strictly follows the algorithm given in solution of Cormen book. First we compute costs of all possible lines in a 2D table lc[][]. The value lc[i][j] indicates the cost to put words from i to j in a single line where i and j are indexes of words in the input sequences. If a sequence of words from i to j cannot fit in a single line, then lc[i][j] is considered infinite (to avoid it from being a part of the solution). Once we have the lc[][] table constructed, we can calculate total cost using following recursive formula. In the following formula, C[j] is the optimized total cost for arranging words from 1 to j.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-26473\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Word-Wrap.png\" alt=\"Word Wrap Problem\" width=\"449\" height=\"113\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Word-Wrap.png 449w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Word-Wrap-300x76.png 300w\" sizes=\"(max-width: 449px) 100vw, 449px\" \/><\/p>\n<p>The above recursion has overlapping subproblem property. For example, the solution of subproblem c(2) is used by c(3), C(4) and so on. So Dynamic Programming is used to store the results of subproblems. The array c[] can be computed from left to right, since each value depends only on earlier values.<br \/>\nTo print the output, we keep track of what words go on what lines, we can keep a parallel p array that points to where each c value came from. The last line starts at word p[n] and goes through word n. The previous line starts at word p[p[n]] and goes through word p[n\u008d] \u2013 1, etc. The function printSolution() uses p[] to print the solution.<br \/>\nIn the below program, input is an array l[] that represents lengths of words in a sequence. The value l[i] indicates length of the ith word (i starts from 1) in theinput sequence.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">\/\/ A Dynamic programming solution for Word Wrap Problem<br\/>#include &lt;limits.h&gt;<br\/>#include &lt;stdio.h&gt;<br\/>#define INF INT_MAX<br\/> <br\/>\/\/ A utility function to print the solution<br\/>int printSolution (int p[], int n);<br\/> <br\/>\/\/ l[] represents lengths of different words in input sequence. For example, <br\/>\/\/ l[] = {3, 2, 2, 5} is for a sentence like &quot;aaa bb cc ddddd&quot;.  n is size of <br\/>\/\/ l[] and M is line width (maximum no. of characters that can fit in a line)<br\/>void solveWordWrap (int l[], int n, int M)<br\/>{<br\/>    \/\/ For simplicity, 1 extra space is used in all below arrays <br\/> <br\/>    \/\/ extras[i][j] will have number of extra spaces if words from i <br\/>    \/\/ to j are put in a single line<br\/>    int extras[n+1][n+1];  <br\/> <br\/>    \/\/ lc[i][j] will have cost of a line which has words from <br\/>    \/\/ i to j<br\/>    int lc[n+1][n+1];<br\/>  <br\/>    \/\/ c[i] will have total cost of optimal arrangement of words <br\/>    \/\/ from 1 to i<br\/>    int c[n+1];<br\/> <br\/>    \/\/ p[] is used to print the solution.  <br\/>    int p[n+1];<br\/> <br\/>    int i, j;<br\/> <br\/>    \/\/ calculate extra spaces in a single line.  The value extra[i][j]<br\/>    \/\/ indicates extra spaces if words from word number i to j are<br\/>    \/\/ placed in a single line<br\/>    for (i = 1; i &lt;= n; i++)<br\/>    {<br\/>        extras[i][i] = M - l[i-1];<br\/>        for (j = i+1; j &lt;= n; j++)<br\/>            extras[i][j] = extras[i][j-1] - l[j-1] - 1;<br\/>    }<br\/> <br\/>    \/\/ Calculate line cost corresponding to the above calculated extra<br\/>    \/\/ spaces. The value lc[i][j] indicates cost of putting words from<br\/>    \/\/ word number i to j in a single line<br\/>    for (i = 1; i &lt;= n; i++)<br\/>    {<br\/>        for (j = i; j &lt;= n; j++)<br\/>        {<br\/>            if (extras[i][j] &lt; 0)<br\/>                lc[i][j] = INF;<br\/>            else if (j == n &amp;&amp; extras[i][j] &gt;= 0)<br\/>                lc[i][j] = 0;<br\/>            else<br\/>                lc[i][j] = extras[i][j]*extras[i][j];<br\/>        }<br\/>    }<br\/> <br\/>    \/\/ Calculate minimum cost and find minimum cost arrangement.<br\/>    \/\/  The value c[j] indicates optimized cost to arrange words<br\/>    \/\/ from word number 1 to j.<br\/>    c[0] = 0;<br\/>    for (j = 1; j &lt;= n; j++)<br\/>    {<br\/>        c[j] = INF;<br\/>        for (i = 1; i &lt;= j; i++)<br\/>        {<br\/>            if (c[i-1] != INF &amp;&amp; lc[i][j] != INF &amp;&amp; (c[i-1] + lc[i][j] &lt; c[j]))<br\/>            {<br\/>                c[j] = c[i-1] + lc[i][j];<br\/>                p[j] = i;<br\/>            }<br\/>        }<br\/>    }<br\/> <br\/>    printSolution(p, n);<br\/>}<br\/> <br\/>int printSolution (int p[], int n)<br\/>{<br\/>    int k;<br\/>    if (p[n] == 1)<br\/>        k = 1;<br\/>    else<br\/>        k = printSolution (p, p[n]-1) + 1;<br\/>    printf (&quot;Line number %d: From word no. %d to %d \\n&quot;, k, p[n], n);<br\/>    return k;<br\/>}<br\/> <br\/>\/\/ Driver program to test above functions<br\/>int main()<br\/>{<br\/>    int l[] = {3, 2, 2, 5};<br\/>    int n = sizeof(l)\/sizeof(l[0]);<br\/>    int M = 6;<br\/>    solveWordWrap (l, n, M);<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p><strong>Output :<\/strong><\/p>\n<pre>Line number 1: From word no. 1 to 1\r\nLine number 2: From word no. 2 to 3\r\nLine number 3: From word no. 4 to 4<\/pre>\n<p>Time Complexity: O(n^2)<br \/>\nAuxiliary Space: O(n^2) The auxiliary space used in the above program cane be optimized to O(n)<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>C Programming &#8211; Word Wrap Problem &#8211; Dynamic Programming Given a sequence of words, and a limit on the number of characters that can be put in one line<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,70145],"tags":[72845,78935,70483,72841,72848,72840,72849,72846,72843,72854,72844,78920,72850,72839,78942,78916,78921,78915,78918,72852,72855,4429,78919,78917,78913,78923,72853,78937,78936,78928,78926,78914,78924,78931,78946,78927,78945,78943,78932,78938,78930,78925,78929,78933,72851],"class_list":["post-26445","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-dynamic-programming","tag-definition-of-dynamic-programming","tag-definition-of-word-wrap","tag-dynamic-programming","tag-dynamic-programming-c","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-c","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-problems","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-dynamic-programming-word-break","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-how-to-word-wrap","tag-implementing-text-justification-with-dynamic-programming","tag-justify-text-algorithm","tag-line-breaking","tag-liner-time-complexity-for-wordwrap-problem","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-style-word-wrap","tag-text-alignment-dynamic-programming","tag-text-justification-algorithm","tag-text-justification-dynamic-programming","tag-text-justification-dynamic-programming-java","tag-types-of-dynamic-programming","tag-what-does-word-wrap-mean","tag-what-is-a-word-wrap","tag-what-is-word-wrap","tag-word-break-word-wrap","tag-word-wrap","tag-word-wrap-algorithm","tag-word-wrap-break-word-not-working","tag-word-wrap-c","tag-word-wrap-definition","tag-word-wrap-in-c","tag-word-wrap-in-c-code","tag-word-wrap-in-word","tag-word-wrap-means","tag-word-wrap-microsoft-word","tag-word-wrap-problem","tag-word-wrap-text","tag-word-wrap-word","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26445","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26445"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26445\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}