Calculate the cost for word wrapping algorithm in Python using dynamic programming

Posted on 2014-11-16
Last Modified: 2014-11-22
I am trying to implement word wrapping in Python using dynamic programming.

Given a sequence of words from a file, 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. Assume that the length of each word is smaller than the line width This problem must be solved using dynamic programming.

This function should take in a list of strings (each string in the list is a word from the file) and an integer M (which represents the max number of characters per line, including spaces). This function should return the cost (an integer that represents the optimal value of the function, as seen in dynamic programming) and a string that contains the entire text from the file as one string with newline characters. It should not end with a blank line.

I have not implemented the word wrapping functionality yet, so the function currently only returns the cost, not the string of text contents.

I implemented an algorithm to calculate the cost of the function based on the pseudocode on page 15-38 of this document ( as well as an implementation in C++ (

My main issue is that I cannot get my function to compute the cost correctly using dynamic programming. I believe I have implemented the function correctly using dynamic programming, but I still cannot arrive to the correct answer. When I run, it prints out the cost. I am not sure what specifically is wrong with my algorithm.

When you run the file, the correct output for the cost of the function for each particular sample text file should be generated into a log file. The output is shown below (this can also be viewed in the output.log file that I have attached):

cost =  1545
true cost =  1545
bad lines =  0

cost =  13910
true cost =  13910
bad lines =  0

How can I optimize my word wrapping/cost algorithm so that it calculates the cost both correctly and efficiently (so that it takes only a couple of minutes to calculate it rather than an hour)?

Thank you for your help.
Question by:AttilaB
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
LVL 45

Expert Comment

ID: 40447076
Do you have to use that algorithm?

I transformed the text into CrLf delimited strings, replacing the existing (CrLf) line breaks with space characters.  After applying the following regular expression, I get the word wrap results in the captured groups.
(.{1,50})(?: |\r\n|$)

Open in new window

LVL 45

Expert Comment

ID: 40447097
You can even use the replace method to insert your linefeed characters
LVL 45

Expert Comment

ID: 40448896
An even simpler solution would be to use the module.

import textwrap

for l in textwrap.wrap(sData,40):
    print l

Open in new window

Of course, you would package this into a form where you would pass the desired width to the wrap() method.
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.


Author Comment

ID: 40448936
I have to make the word wrap function from scratch, though. I can't use a built-in library.
LVL 45

Expert Comment

ID: 40448957
Sounds like coursework to me.  There is limited help for homework problems due to academic integrity issues.

Accepted Solution

AttilaB earned 0 total points
ID: 40448981
I got it working using Java I have much more experience with and and managed to cross-code into Python.
Now it works. At least I found a solution.

Author Closing Comment

ID: 40459181
The person who looked like wanted to help refused to help later because  he felt that it would be against 'academic integrity'. I did not ask
for a solution handed to me just help to get to the solution. Luckily I found a solution myself.

Featured Post

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Using bootstrap with french text 13 104
Merge lists using index in Python 1 113
sorting efficency of sorting algorithm 30 134
Python 3.5.2 32 virtualenv problems 3 87
This article will show the steps for installing Python on Ubuntu Operating System. I have created a virtual machine with Ubuntu Operating system 8.10 and this installing process also works with upgraded version of Ubuntu OS. For installing Py…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Learn the basics of lists in Python. Lists, as their name suggests, are a means for ordering and storing values. : Lists are declared using brackets; for example: t = [1, 2, 3]: Lists may contain a mix of data types; for example: t = ['string', 1, T…
Learn the basics of modules and packages in Python. Every Python file is a module, ending in the suffix: .py: Modules are a collection of functions and variables.: Packages are a collection of modules.: Module functions and variables are accessed us…

730 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question