title: Trying to print a single string on multiple lines of fixed length and minimizing the cost
body: <p>First some background I just started with Algorithms(which I now feel I lack the logic and reasoning power to excel at)I have been trying to print "This is a sample text "into various lines with max of 7 chars on each line so the first line will have :</p>
  
  <pre><code>this is  (no spaces left in the end so cost 0)
  a  
  [cost=6*6*6(The spaces left at the end of each line are cubed which will be the cost) ]
  sample [cost=1*1*1]
  text [cost= 3*3*3]
  
  (Total cost = 0+216+1+27=244)
  </code></pre>
  
  <p>Now this can be optimized by </p>
  
  <pre><code>this [cost 3*3*3]
  is a [cost 3*3*3]
  sample [cost 1*1*1]
  text [cost 3*3*3]
  
  [Total cost = 27+27+1+27 = 82]
  </code></pre>
  
  <p>So clearly we cannot use a greedy approach here instead use dynamic programming but my problem is I cannot figure out the sub structure that will be reused. I am really stuck with figuring out how I link the cost condition to the printing  in python, I can index each word and I can get the length of each word, sort of stuck with what I do next When print all that happens is the entire string gets printed on one line each (This is where I have got so far).
  I apologize if this is a really silly question, but I am stuck and really need some help on this. 
  Thanks</p>
  
  <hr>
  
  <p>This is how I have tried implementing the code although I tried running some tests on the code, the test were written by my friend and I dont think I am getting it right  Any help or suggestion is appreciated
  print_test.py </p>
  
  <pre><code> import os
   import sys
   from glob import glob
  
    #TODO -- replace this with your solution 
   from printing import print_neatly
  
   log = open('output.log', 'w')
  
   #This tests the code against my own text
   maxline = 80
   for source in glob('*.txt'):
   with open(source) as f:
      fulltext = f.read()
  
   words = fulltext.split()
   (cost, text) = print_neatly(words, maxline)
  
   #double check the cost
   #lines = text.split('\n')
   truecost = 0
   for line in text[0:-1]:
      truecost += (maxline - len(line))**3
  
  
     #print the output and cost
     print &gt;&gt;log, '----------------------'
     print &gt;&gt;log, source
     print &gt;&gt;log, '----------------------'
     print &gt;&gt;log, text
     print &gt;&gt;log, '----------------------'
     print &gt;&gt;log, 'cost = ', cost
     print &gt;&gt;log, 'true cost = ', truecost
     print &gt;&gt;log, '----------------------'
  
  
  log.close()
  
  #print the log
  with open('output.log') as f: print f.read()
  </code></pre>
  
  <p>printing.py</p>
  
  <pre><code>def print_neatly(wordlist, max):
     #strings='This is a sample string'
  
     #splitting the string and taking out words from it 
     #wordlist=strings.split()
     (cost, dyn_print) = print_line(wordlist, len(wordlist), max)
     for dyn in dyn_print:
        print dyn
     return cost, dyn_print
  
   def cost(lines, max):
  
      return sum([(max-len(x)) ** 3 for x in lines])
  
   def print_line(wordlist, count, max, results = {}):
    results = [([],0)]
    for count in range(1, len(wordlist) + 1):
      best = wordlist[:count]               
      best_cost = cost(best, max)
      mycount = count - 1
      line = wordlist[mycount]       
      while len(line) &lt;= max: 
          attempt, attempt_cost = results[mycount]
          attempt = attempt + [line]
          attempt_cost += cost([line],max)
          if attempt_cost &lt; best_cost:
              best = attempt
              best_cost = attempt_cost
          if mycount &gt; 0:
              mycount -= 1
              line = wordlist[mycount] + ' ' + line
          else:
              break
      results += [(best, best_cost)]
  
   #print best
   #print best_cost
   return (best_cost, best)
  
  
  #print_neatly(0,7)
  </code></pre>
  
  <p>The text files that need to be tested give me this output, here the two cost need to be the same which I am not getting, can some one point out where I am going wrong </p>
  
  <hr>
  
  <p>cost =  16036</p>
  
  <h2>true cost =  15911</h2>