StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POTrying to print a single string on multiple lines of fixed length and minimizing the cost
text
Body
copied!<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 >>log, '----------------------' print >>log, source print >>log, '----------------------' print >>log, text print >>log, '----------------------' print >>log, 'cost = ', cost print >>log, 'true cost = ', truecost print >>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) <= max: attempt, attempt_cost = results[mycount] attempt = attempt + [line] attempt_cost += cost([line],max) if attempt_cost < best_cost: best = attempt best_cost = attempt_cost if mycount > 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>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload