Repository: keon/algorithms
Pull request #371 (2018-07-02 09:27:19)

add text_justification and test text_justification
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [X] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


coveralls: ## Pull Request Test Coverage Report for [Build 668](https://coveralls.io/builds/17787362)

* **56** of **62**   **(90.32%)**  changed or added relevant lines in **2** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.2%**) to **71.754%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/strings/text_justification.py](https://coveralls.io/builds/17787362/source?filename=algorithms%2Fstrings%2Ftext_justification.py#L50) | 45 | 51 | 88.24%
<!-- | **Total:** | **56** | **62** | **90.32%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/17787362/badge)](https://coveralls.io/builds/17787362) |
| :-- | --: |
| Change from base [Build 667](https://coveralls.io/builds/17775144): |  0.2% |
| Covered Lines: | 3841 |
| Relevant Lines: | 5353 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/README.md b/README.md
index e8c4e80..8a0ef8e 100644
--- a/README.md
+++ b/README.md
@@ -1,6 +1,6 @@
 <p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
-English | [Brazilian Portuguese](README_PTBR.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md)
+English | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md) | [Português](README_PTBR.md)
 
 [![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
@@ -15,7 +15,6 @@ Minimal and clean example implementations of data structures and algorithms in P
 ## Contributing
 Thanks for your interest in contributing! There are many ways to contribute to this project. [Get started here](CONTRIBUTING.md)
 
-
 ## Tests
 
 ### Use unittest
diff --git a/README_CN.md b/README_CN.md
index b2fe38f..f3dc87f 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -1,6 +1,6 @@
 <p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
-[English](README.md) | [Brazilian Portuguese](README_PTBR.md) | 简体中文 | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md)
+[English](README.md) | 简体中文 | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md) | [Português](README_PTBR.md)
 
 [![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
diff --git a/README_GE.md b/README_GE.md
index 7476957..226deee 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -1,6 +1,6 @@
 <p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
-[English](README.md) | [Brazilian Portuguese](README_PTBR.md) | [简体中文](README_CN.md) | Deutsch | [日本語](README_JP.md) | [한국어](README_KR.md)
+[English](README.md) | [简体中文](README_CN.md) | Deutsch | [日本語](README_JP.md) | [한국어](README_KR.md) | [Português](README_PTBR.md)
 
 [![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
@@ -14,7 +14,7 @@ In diesem Repository finden Sie eine große Auswahl an Algorithmen und Datenstru
 
 ## Beteiligen  
 
-Sie können sich gerne auch an diesem Projekt beteiligen. Zum Beispiel selbst Algorithmen und Datenstrukturen beisteuern, oder bereits bestehende Implementierungen verbessern, oder auch dokumentieren. Fühlen Sie sich frei und machen Sie einen Pull-Request. Alternativ können Sie auch den Issue-Tracker benutzen um auf Probleme (Bugs) in bereits bestehenden Implementierungen hinzuweisen.  
+Sie können sich gerne auch an diesem Projekt beteiligen. Zum Beispiel selbst Algorithmen und Datenstrukturen beisteuern, oder bereits bestehende Implementierungen verbessern, oder auch dokumentieren. Fühlen Sie sich frei und machen Sie einen Pull-Request. Alternativ können Sie auch den Issue-Tracker benutzen um auf Probleme (Bugs) in bereits bestehenden Implementierungen hinzuweisen.
 
 In diesem Projekt halten wir uns an die [PEP8](https://www.python.org/dev/peps/pep-0008/) Codestyle Konventionen.  
 
diff --git a/README_JP.md b/README_JP.md
index 1fea3b8..7e3062e 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -1,6 +1,6 @@
 <p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
-[English](README.md) | [Brazilian Portuguese](README_PTBR.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | 日本語 | [한국어](README_KR.md)
+[English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | 日本語 | [한국어](README_KR.md) | [Português](README_PTBR.md)
 
 [![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
diff --git a/README_KR.md b/README_KR.md
index 52c7da6..91bfc0a 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -1,6 +1,6 @@
 <p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
-[English](README.md) | [Brazilian Portuguese](README_PTBR.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | 한국어
+[English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | 한국어 | [Português](README_PTBR.md)
 
 [![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
@@ -15,7 +15,6 @@ Python 3로 구현한 간단하고 명확한 자료구조와 알고리즘들의
 ## 기여 활동
 프로젝트 활동 참여에 관심을 가져주셔서 감사합니다! 여러가지 방법으로 이 프로젝트에 기여해주세요. [기여 방법 소개](CONTRIBUTING.md)
 
-
 ## 테스트 종류들
 
 ### unittest 사용
diff --git a/README_PTBR.md b/README_PTBR.md
index 6a4973a..2a9e05f 100644
--- a/README_PTBR.md
+++ b/README_PTBR.md
@@ -1,6 +1,6 @@
 <p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
-[English](README.md) | Brazilian Portuguese | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md)
+[English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md) | Português
 
 [![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
@@ -15,7 +15,6 @@ Exemplos de implementações mínimas e limpas de estruturas de dados e algoritm
 ## Contribuir
 Obrigado pelo seu interesse em contribuir! Há muitas maneiras de contribuir para este projeto. [Comece aqui](CONTRIBUTING.md)
 
-
 ## Testes
 
 ### Usando unittest
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
index 4040c9e..4f4f20c 100644
--- a/algorithms/strings/__init__.py
+++ b/algorithms/strings/__init__.py
@@ -28,3 +28,4 @@ from .caesar_cipher import *
 from .contain_string import *
 from .count_binary_substring import *
 from .repeat_string import *
+from .text_justification import *
\ No newline at end of file
diff --git a/algorithms/strings/text_justification.py b/algorithms/strings/text_justification.py
new file mode 100644
index 0000000..a14a8ba
--- /dev/null
+++ b/algorithms/strings/text_justification.py
@@ -0,0 +1,89 @@
+"""
+Given an array of words and a width maxWidth, format the text such that each line
+has exactly maxWidth characters and is fully (left and right) justified.
+
+You should pack your words in a greedy approach; that is, pack as many words as
+you can in each line. Pad extra spaces ' ' when necessary so that each line has
+exactly maxWidth characters.
+
+Extra spaces between words should be distributed as evenly as possible. If the
+number of spaces on a line do not divide evenly between words, the empty slots
+on the left will be assigned more spaces than the slots on the right.
+
+For the last line of text, it should be left justified and no extra space is
+inserted between words.
+
+Note:
+A word is defined as a character sequence consisting of non-space characters only.
+Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
+The input array words contains at least one word.
+
+Example:
+Input:
+words = ["What","must","be","acknowledgment","shall","be"]
+maxWidth = 16
+Output:
+[
+  "What   must   be",
+  "acknowledgment  ",
+  "shall be        "
+]
+"""
+
+
+def text_justification(words, max_width):
+    '''
+    :type words: list
+    :type max_width: int
+    :rtype: list
+    '''
+    ret = []  # return value
+    row_len = 0  # current length of strs in a row
+    row_words = []  # current words in a row
+    index = 0  # the index of current word in words
+    is_first_word = True  # is current word the first in a row
+    while index < len(words):
+        while row_len <= max_width and index < len(words):
+            if len(words[index]) > max_width:
+                raise ValueError("there exists word whose length is larger than max_width")
+            tmp = row_len
+            row_words.append(words[index])
+            tmp += len(words[index])
+            if not is_first_word:
+                tmp += 1  # except for the first word, each word should have at least a ' ' before it.
+            if tmp > max_width:
+                row_words.pop()
+                break
+            row_len = tmp
+            index += 1
+            is_first_word = False
+        # here we have already got a row of str , then we should supplement enough ' ' to make sure the length is max_width.
+        row = ""
+        # if the row is the last
+        if index == len(words):
+            for word in row_words:
+                row += (word + ' ')
+            row = row[:-1]
+            row += ' ' * (max_width - len(row))
+        # not the last row and more than one word
+        elif len(row_words) != 1:
+            space_num = max_width - row_len
+            space_num_of_each_interval = space_num // (len(row_words) - 1)
+            space_num_rest = space_num - space_num_of_each_interval * (len(row_words) - 1)
+            for j in range(len(row_words)):
+                row += row_words[j]
+                if j != len(row_words) - 1:
+                    row += ' ' * (1 + space_num_of_each_interval)
+                if space_num_rest > 0:
+                    row += ' '
+                    space_num_rest -= 1
+        # row with only one word
+        else:
+            row += row_words[0]
+            row += ' ' * (max_width - len(row))
+        ret.append(row)
+        # after a row , reset those value
+        row_len = 0
+        row_words = []
+        is_first_word = True
+    return ret


Test patch:
diff --git a/tests/test_strings.py b/tests/test_strings.py
index c8b9182..be44fb9 100644
--- a/tests/test_strings.py
+++ b/tests/test_strings.py
@@ -30,7 +30,8 @@ from algorithms.strings import (
     caesar_cipher,
     contain_string,
     count_binary_substring,
-    repeat_string
+    repeat_string,
+    text_justification
 )
 
 import unittest
@@ -62,10 +63,13 @@ class TestBreakingBad(unittest.TestCase):
         self.words = ['Amazon', 'Microsoft', 'Google']
         self.symbols = ['i', 'Am', 'cro', 'le', 'abc']
         self.result = ['M[i]crosoft', '[Am]azon', 'Mi[cro]soft', 'Goog[le]']
+
     def test_match_symbol(self):
-        self.assertEqual(self.result, match_symbol(self.words,self.symbols))
+        self.assertEqual(self.result, match_symbol(self.words, self.symbols))
+
     def test_match_symbol_1(self):
-        self.assertEqual(['[Am]azon', 'Mi[cro]soft', 'Goog[le]'], match_symbol_1(self.words,self.symbols))
+        self.assertEqual(['[Am]azon', 'Mi[cro]soft', 'Goog[le]'], match_symbol_1(self.words, self.symbols))
+
     def test_bracket(self):
         self.assertEqual(('[Am]azon', 'Mi[cro]soft', 'Goog[le]'), bracket(self.words, self.symbols))
 
@@ -105,6 +109,7 @@ class TestDomainExtractor(unittest.TestCase):
 
     def test_valid(self):
         self.assertEqual(domain_name_1("https://github.com/SaadBenn"), "github")
+
     def test_invalid(self):
         self.assertEqual(domain_name_2("http://google.com"), "google")
 
@@ -119,6 +124,7 @@ class TestEncodeDecode(unittest.TestCase):
 
     def test_encode(self):
         self.assertEqual("4:keon2:is7:awesome", encode("keon is awesome"))
+
     def test_decode(self):
         self.assertEqual(['keon', 'is', 'awesome'], decode("4:keon2:is7:awesome"))
 
@@ -133,7 +139,7 @@ class TestGroupAnagrams(unittest.TestCase):
 
     def test_group_anagrams(self):
         self.assertEqual([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']], \
-        group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
+                         group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
 
 
 class TestIntToRoman(unittest.TestCase):
@@ -162,14 +168,17 @@ class TestIsPalindrome(unittest.TestCase):
         # 'Otto' is a old german name.
         self.assertTrue(is_palindrome("Otto"))
         self.assertFalse(is_palindrome("house"))
+
     def test_is_palindrome_reverse(self):
         # 'Otto' is a old german name.
         self.assertTrue(is_palindrome_reverse("Otto"))
         self.assertFalse(is_palindrome_reverse("house"))
+
     def test_is_palindrome_two_pointer(self):
         # 'Otto' is a old german name.
         self.assertTrue(is_palindrome_two_pointer("Otto"))
         self.assertFalse(is_palindrome_two_pointer("house"))
+
     def test_is_palindrome_stack(self):
         # 'Otto' is a old german name.
         self.assertTrue(is_palindrome_stack("Otto"))
@@ -232,6 +241,7 @@ class TestMergeStringChecker(unittest.TestCase):
 
     def test_is_merge_recursive(self):
         self.assertTrue(is_merge_recursive("codewars", "cdw", "oears"))
+
     def test_is_merge_iterative(self):
         self.assertTrue(is_merge_iterative("codewars", "cdw", "oears"))
 
@@ -263,6 +273,7 @@ class TestOneEditDistance(unittest.TestCase):
         self.assertTrue(is_one_edit("abc", "abd"))
         self.assertFalse(is_one_edit("abc", "aed"))
         self.assertFalse(is_one_edit("abcd", "abcd"))
+
     def test_is_one_edit2(self):
         self.assertTrue(is_one_edit2("abc", "abd"))
         self.assertFalse(is_one_edit2("abc", "aed"))
@@ -292,10 +303,13 @@ class TestReverseString(unittest.TestCase):
 
     def test_recursive(self):
         self.assertEqual("ereht olleh", recursive("hello there"))
+
     def test_iterative(self):
         self.assertEqual("ereht olleh", iterative("hello there"))
+
     def test_pythonic(self):
         self.assertEqual("ereht olleh", pythonic("hello there"))
+
     def test_ultra_pythonic(self):
         self.assertEqual("ereht olleh", ultra_pythonic("hello there"))
 
@@ -322,7 +336,7 @@ class TestReverseWords(unittest.TestCase):
 
     def test_reverse_words(self):
         self.assertEqual("pizza like I and kim keon am I", \
-        reverse_words("I am keon kim and I like pizza"))
+                         reverse_words("I am keon kim and I like pizza"))
 
 
 class TestRomanToInt(unittest.TestCase):
@@ -367,11 +381,12 @@ class TestValidateCoordinates(unittest.TestCase):
     """
 
     def test_valid(self):
-        valid_coordinates = ["-23, 25","4, -3","90, 180","-90, -180"]
+        valid_coordinates = ["-23, 25", "4, -3", "90, 180", "-90, -180"]
         for coordinate in valid_coordinates:
             self.assertTrue(is_valid_coordinates_0(coordinate))
+
     def test_invalid(self):
-        invalid_coordinates = ["23.234, - 23.4234","99.234, 12.324","6.325624, 43.34345.345","0, 1,2","23.245, 1e1"]
+        invalid_coordinates = ["23.234, - 23.4234", "99.234, 12.324", "6.325624, 43.34345.345", "0, 1,2", "23.245, 1e1"]
         for coordinate in invalid_coordinates:
             self.assertFalse(is_valid_coordinates_0(coordinate))
 
@@ -386,46 +401,74 @@ class TestWordSquares(unittest.TestCase):
 
     def test_word_squares(self):
         self.assertEqual([['wall', 'area', 'lead', 'lady'], ['ball', 'area', 'lead', 'lady']], \
-        word_squares(["area","lead","wall","lady","ball"]))
+                         word_squares(["area", "lead", "wall", "lady", "ball"]))
+
 
 class TestUniqueMorse(unittest.TestCase):
     def test_convert_morse_word(self):
         self.assertEqual("--...-.", convert_morse_word("gin"))
         self.assertEqual("--...--.", convert_morse_word("msg"))
+
     def test_unique_morse(self):
         self.assertEqual(2, unique_morse(["gin", "zen", "gig", "msg"]))
 
+
 class TestJudgeCircle(unittest.TestCase):
     def test_judge_circle(self):
         self.assertTrue(judge_circle("UDLRUD"))
         self.assertFalse(judge_circle("LLRU"))
 
+
 class TestStrongPassword(unittest.TestCase):
     def test_strong_password(self):
-        self.assertEqual(3, strong_password(3,"Ab1"))
-        self.assertEqual(1, strong_password(11,"#Algorithms"))
+        self.assertEqual(3, strong_password(3, "Ab1"))
+        self.assertEqual(1, strong_password(11, "#Algorithms"))
+
 
 class TestCaesarCipher(unittest.TestCase):
     def test_caesar_cipher(self):
         self.assertEqual("Lipps_Asvph!", caesar_cipher("Hello_World!", 4))
         self.assertEqual("okffng-Qwvb", caesar_cipher("middle-Outz", 2))
 
+
 class TestContainString(unittest.TestCase):
     def test_contain_string(self):
         self.assertEqual(-1, contain_string("mississippi", "issipi"))
         self.assertEqual(0, contain_string("Hello World", ""))
         self.assertEqual(2, contain_string("hello", "ll"))
 
+
 class TestCountBinarySubstring(unittest.TestCase):
     def test_count_binary_substring(self):
         self.assertEqual(6, count_binary_substring("00110011"))
         self.assertEqual(4, count_binary_substring("10101"))
         self.assertEqual(3, count_binary_substring("00110"))
 
+
 class TestCountBinarySubstring(unittest.TestCase):
     def test_repeat_string(self):
-        self.assertEqual(3, repeat_string("abcd","cdabcdab"))
+        self.assertEqual(3, repeat_string("abcd", "cdabcdab"))
         self.assertEqual(4, repeat_string("bb", "bbbbbbb"))
 
+
+class TestTextJustification(unittest.TestCase):
+    def test_text_justification(self):
+        self.assertEqual(["This    is    an",
+                          "example  of text",
+                          "justification.  "],
+
+                         text_justification(["This", "is", "an", "example", "of", "text", "justification."]
+                                            , 16)
+                         )
+
+        self.assertEqual(["What   must   be",
+                          "acknowledgment  ",
+                          "shall be        "],
+
+                         text_justification(["What", "must", "be", "acknowledgment", "shall", "be"]
+                                            , 16)
+                         )
+
+
 if __name__ == "__main__":
     unittest.main()