fork download
copy 
  1. import functools
  2.  
  3. def linelen(words):
  4.     """Number of characters in a line created from words."""
  5.     if not words: return 0
  6.     # words + spaces between them
  7.     return sum(map(len, words)) + len(words) - 1
  8.  
  9. def cost(lines, width):
  10.     """
  11.     - each line except last costs `(width - w)**3`, where `w` is the
  12.       line width
  13.  
  14.     - cost is infinite if `w > width` and the line has more than one word
  15.     """
  16.     if not lines: return 0
  17.     s = 0
  18.     for i, words in enumerate(lines, 1):
  19.         w = linelen(words)
  20.         if width >= w:
  21.             if i != len(lines): # last line has zero cost
  22.                 s += (width - w)**3
  23.         elif len(words) != 1: # more than one word in the line
  24.             return float("inf") # penalty for w > width
  25.     return s
  26.  
  27. def memoize(func):
  28.     cache = {}
  29.     @functools.wraps(func)
  30.     def wrapper(*args):
  31.         try: return cache[args]
  32.         except KeyError:
  33.             ret = cache[args] = func(*args)
  34.             return ret
  35.     return wrapper
  36.  
  37. @memoize
  38. def best_partition(words, cost):
  39.     """The best partition of words into lines according to the cost function."""
  40.     best = [words] # start with all words on a single line
  41.     for i in range(1, len(words)):
  42.         lines = [words[:i]] + best_partition(words[i:], cost)
  43.         if cost(lines) < cost(best):
  44.             best = lines
  45.     return best
  46.  
  47. def wrap(text, width):
  48.     """
  49.     >>> wrap('This is a sample text', 7)
  50.     ['This', 'is a', 'sample', 'text']
  51.     """
  52.     _cost = functools.partial(cost,width=width)
  53.     words = tuple(text.split())
  54.     for i in reversed(range(len(words))): best_partition(words[i:], _cost)
  55.     return [' '.join(line) for line in best_partition(words, _cost)]
  56.  
  57. if __name__=="__main__":
  58.     text = """
  59. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  60. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features  to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  61. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private about Version Targeting, and two new features then called WebSlice and Activities. The readiness toleast March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to make Internet Explorer 8 'light up'."
  62. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  63. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  64. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  65. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  66. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  67. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  68. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  69. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  70. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  71. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  72. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  73. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  74. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  75. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  76. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  77. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  78. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  79. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  80. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 Readiness Toolkit website promoting IE8 white papers, related software tools, and new features in addition to download links to the Beta. The Microsoft Developer Network (MSDN) added new sections detailing new IE8 technology. Major press focused on a controversy about Version Targeting, and two new features then called WebSlice and Activities. The readiness toolkit was promoted as something "developers can exploit to make Internet Explorer 8 'light up'."
  81. IE8 development started in at least March 2006. In February 2008, Microsoft sent out private invitations for IE8 Beta 1, and on March 5, 2008, released Beta 1 to the general public, although with a focus on web developers. The release launched with a Windows Internet Explorer 8 
  82.     """
  83.     print('\n'.join(wrap(text, 80)))
  84.  
Time limit exceeded #stdin #stdout -1s 6600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aZUXo
language:
Python 3 (python  3.9.5)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!