Your task in this Kata is to emulate text justification in monospace font. You will be given a single-lined text and the expected justification width. The longest word will never be greater than this width.

Here are the rules:

  * Use spaces to fill in the gaps between words.
  * Each line should contain as many words as possible.
  * Use '\n' to separate lines.
  * Gap between words can't differ by more than one space.
  * Lines should end with a word not a space.
  * '\n' is not included in the length of a line.
  * Large gaps go first, then smaller ones ('Lorem--ipsum--dolor--sit-amet,' (2, 2, 2, 1 spaces)).
  * Last line should not be justified, use only one space between words.
  * Last line should not contain '\n'
  * Strings with one word do not need gaps ('somelongword\n').

Example with width=30:

```
Lorem  ipsum  dolor  sit amet,
consectetur  adipiscing  elit.
Vestibulum    sagittis   dolor
mauris,  at  elementum  ligula
tempor  eget.  In quis rhoncus
nunc,  at  aliquet orci. Fusce
at   dolor   sit   amet  felis
suscipit   tristique.   Nam  a
imperdiet   tellus.  Nulla  eu
vestibulum    urna.    Vivamus
tincidunt  suscipit  enim, nec
ultrices   nisi  volutpat  ac.
Maecenas   sit   amet  lacinia
arcu,  non dictum justo. Donec
sed  quam  vel  risus faucibus
euismod.  Suspendisse  rhoncus
rhoncus  felis  at  fermentum.
Donec lorem magna, ultricies a
nunc    sit    amet,   blandit
fringilla  nunc. In vestibulum
velit    ac    felis   rhoncus
pellentesque. Mauris at tellus
enim.  Aliquam eleifend tempus
dapibus. Pellentesque commodo,
nisi    sit   amet   hendrerit
fringilla,   ante  odio  porta
lacus,   ut   elementum  justo
nulla et dolor.
```

Also you can always take a look at how justification works in your text editor or directly in HTML (css: text-align: justify).

Have fun :)

Difficulty: interview

Starter code:

def justify(text, width):
	

Solutions:
def justify(text, width):
    length = text.rfind(' ', 0, width+1)
    if length == -1 or len(text) <= width: return text
    line = text[:length]
    spaces = line.count(' ')
    if spaces != 0:
        expand = (width - length) / spaces + 1
        extra = (width - length) % spaces
        line = line.replace(' ', ' '*expand)
        line = line.replace(' '*expand, ' '*(expand+1), extra)
    return line + '\n' + justify(text[length+1:], width)

def justify(text, width):
    output = ""
    while len(text) > width:
        line = text[0:width]
        if text[width] == ' ':
            output += line + '\n' 
            text = text[width+1:]
            continue
        line = line[0:line.rfind(' ')]
        text = text[len(line)+1:]
        words = line.split(" ")
        if len(words) > 1:
            for x in xrange(0,width - len(line)):
                words[x % (len(words)-1)] += ' '
        output += " ".join(words) + '\n'
    return output + text

import textwrap

def justify(text, width):
    def justify_line(line):
        if ' ' not in line: 
            return line
        places = line.count(' ')
        spaces = width - len(line) + places
        interval, extra = divmod(spaces, places)
        return ''.join(word + ' ' * (interval + (i < extra)) 
                       for i, word in enumerate(line.split())).strip()
                       
    lines = textwrap.wrap(text, width, break_on_hyphens=False)
    return '\n'.join(list(map(justify_line, lines[:-1])) + [lines[-1]])


  def justify(text, width):
      output = ""
      while len(text) > width:
          line = text[0:width]
          if text[width] == ' ': # Ideal case, cut on space, no need to justify anything
              output += line + '\n' 
              text = text[width+1:]
              continue
          line = line[0:line.rfind(' ')] # Remove the impartial word from the end of line
          text = text[len(line)+1:]
          words = line.split(" ")
          if len(words) > 1:
          # If there are more than one word, add missing spacing by adding one space
          # to each word except last one and repeat until there is no more missing spacing left.
              for x in xrange(0,width - len(line)):
                  words[x % (len(words)-1)] += ' '
          output += " ".join(words) + '\n'
      return output + text


def justify(text, width):
    lines, last = [[]], -1
    for word in text.split():
        if last + 1 + len(word) > width:
            lines.append([word])
            last = len(word)
        else:
            lines[-1].append(word)
            last += len(word) + 1

    def justify_line(words):
        if len(words) == 1:
            return words[0]
        interval, extra = divmod(width - sum(map(len, words)), len(words) - 1)
        init = (word + ' ' * (interval + (i < extra)) for i, word in enumerate(words[:-1]))
        return ''.join(init) + words[-1]

    return '\n'.join(map(justify_line, lines[:-1]) + [' '.join(lines[-1])])

def justify(t, w):
    c = t.rfind(' ', 0, w + 1)
    if c == -1 or len(t) <= w:
        return t
    c = t[:c]
    t = t[len(c) + 1:]
    x = ' '
    if c.count(' ') != 0:
        while len(c) != w:
            if w - len(c) >= c.count(x):
                c = c.replace(x, x + ' ')
                x += ' '
            else:
                c = c.replace(x, x + ' ', w - len(c))
    return c + '\n' + justify(t, w)

from itertools import cycle
def justify(s,n):
    m, s, final, i = [], s.split(), [], 0
    while i < len(s):
        e = s[i]
        if len(' '.join(final)) + len(e) + 1 <= n : final.append(e) ; i+=1
        else:
            final = "  ".join(final).split(' ')
            if len(final) == 1 : m.append(final[0])
            else:
                nex = cycle(range(1, len(final), 2))
                while len(''.join(final)) < n : final[next(nex)] += ' '
                m.append(''.join(final))
            final = []
    return '\n'.join(m + [' '.join(final)])

from textwrap import wrap
def justify(text, width):
    lines = wrap(text, width)

    def justify_line(line):
        spaces = line.count(' ')

        if not spaces:
            return line

        n, r = divmod(width - sum(map(len, line)), spaces)
        print(sum(map(len,line)))
        subs = ' ' * (n + 1)
        return line.replace(' ', subs).replace(subs, subs + ' ', r)

    return '\n'.join([*map(justify_line, lines[:-1]), lines[-1]])

def justify(txt, wid):
    result, i, j, n = [], 0, 0, txt.find(" ")
    while True:
        while -1 < n and n - i <= wid:
            j, n = n, txt.find(" ", n+1)
        if n < 0 and len(txt[i:]) <= wid:
            result.append(txt[i:])
            break
        result.append(expand(txt[i:j], wid))
        i = j+1
    return "\n".join(result)

def expand(line, wid):
    gap, spc, f = wid - len(line), line.count(" "), " ".center
    b, r = divmod(gap, spc) if spc else (0, 0)
    return line.replace(" ", f(b+1)).replace(f(b+1), f(b+2), r)


import textwrap


def justify(text, width):
    lines = textwrap.wrap(text, width)
    for line in lines:
        space = width - len(line)
        words = line.split()
        
        #prevent method being applied to last line
        if lines.index(line) == len(lines) -1:
            break

        if len(words) > 1:
            for i in range(space):   
                if i >= len(words)-1:
                    i = i % (len(words) -1)
                    
                words[i] = words[i] + ' '
               
        
        lines[lines.index(line)] =(' '.join(words))
            
    return('\n'.join(lines))

def iterate_over_lines(text, width):
    i, lim = 0, len(text) - width
    while i < lim:
        j = text.rfind(' ', i, i + width + 1)
        yield text[i: j]
        i = j + 1
    yield text[i:]
    
def justify_line(line, width):
    words = line.split()
    if len(words) < 2:
        return line
    ch = sum(len(w) for w in words)
    d, m = divmod(width - ch, len(words) - 1)
    gaps = [' ' * (d + int(i < m)) for i in range(len(words) - 1)] + ['']
    parts = [part for t in zip(words, gaps) for part in t]
    return ''.join(parts)

def justify(text, width):
    lines = list(iterate_over_lines(text, width))
    lines = [justify_line(s, width) for s in lines[: -1]] + [lines[-1]]
    return '\n'.join(lines)