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: MEDIUM
Tags: String algorithms

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):
	(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()
		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)