Find the position of line breaks in a given string such that the lines are printed neatly. The string and the number of characters that can be put in one line are given as inputs. (https://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/) (https://www.youtube.com/watch?v=RORuwHiblPc)

Dynamic Programming : Text Justification.py

#!/usr/bin/env python3

import math


def main():
	# take inputs
	string = input("Enter the text to be justified:\n").split()
	width = int(input("Enter the width of the line: "))
	
	# create an array with the lengths of the words
	string_length = [len(x) for x in string]
	# create a dp table and initialise all values to 0
	dp = [[0 for i in range(len(string))] for j in range(len(string))]

	# fill the dp table with the square of the space remaining from the width after the words have been placed
	# when more than one word is placed, the space between them should also be accounted for
	# if the word(s) cannot be placed in the position fill the table with infinity
	# dp[i][j] -> words placed from index i to index j (i and j inclusive)
	for i in range(len(string)):
		for j in range(i,len(string)):
			if (sum(string_length[i:j+1]) + len(string_length[i:j+1]) - 1) <= width:
				dp[i][j] = (width - (sum(string_length[i:j+1]) + len(string_length[i:j+1]) - 1))**2
			else:
				dp[i][j] = math.inf

	# create two more lists to store the minimum cost and the final result
	min_cost = [dp[x][len(string)-1] for x in range(len(string))]
	result = [len(string) for x in range(len(string))]

	# both i and j moves backwards
	for i in range(len(string)-1,-1,-1):  # last index -> 0
		for j in range(len(string)-1,i,-1):  # last index -> i
			# min_cost[i] -> minimum cost needed to place words from index i to result[i]-1
			# result[i] -> gives the range of the words to be placed in one line
			# result[3] = 6 -> can place words from string[3] to string[5] (index to result[index]-1) in one line
			# for the last words of the string given
			if dp[i][len(string)-1] != math.inf:
				min_cost[i] = dp[i][j]
				result[i] = j + 1
			else:
				if dp[i][j-1] + min_cost[j] < min_cost[i]:
					min_cost[i] = dp[i][j-1] + min_cost[j]
					result[i] = j

	# prints out the justified text
	print()
	index = 0
	while (index != len(string)):
		print(' '.join(string[index:result[index]]))
		index = result[index]
	print()

if __name__ == '__main__':
	main()

'''
example

	string = 'The quick brown fox jumps over the lazy dog'
	width  = 10

	dp table
		0	1	2	3	4	5	6	7	8
	0	49	1	inf	inf	inf	inf	inf	inf	inf	
	1	0	25	inf	inf	inf	inf	inf	inf	inf	
	2	0	0	25	1	inf	inf	inf	inf	inf	
	3	0	0	0	49	1	inf	inf	inf	inf	
	4	0	0	0	0	25	0	inf	inf	inf	
	5	0	0	0	0	0	36	4	inf	inf	
	6	0	0	0	0	0	0	49	4	inf	
	7	0	0	0	0	0	0	0	36	4	
	8	0	0	0	0	0	0	0	0	49	
	
	min_cost =	35	59	34	9	33	8	53	4	49	
	result   =	2	2	4	5	5	7	8	9	9
	index		0	1	2	3	4	5	6	7	8

	output
		0 1 2 3 4 5 6 7 8 9
		T h e   q u i c k 
		b r o w n   f o x 
		j u m p s
		o v e r   t h e 
		l a z y   d o g
'''