Repository: keon/algorithms
Pull request #356 (2018-06-16 05:46:28)

Add some String algorithm
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [x] **If creating a new file :**
  - [x] 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 636](https://coveralls.io/builds/17527054)

* **29** of **29**   **(100.0%)**  changed or added relevant lines in **3** files are covered.
* **1** unchanged line in **1** file lost coverage.
* Overall coverage increased (+**0.2%**) to **70.831%**

---


|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/linkedlist/is_palindrome.py](https://coveralls.io/builds/17527054/source?filename=algorithms%2Flinkedlist%2Fis_palindrome.py#L85) | 1 | 93.33% |
<!-- | **Total:** | **1** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/17527054/badge)](https://coveralls.io/builds/17527054) |
| :-- | --: |
| Change from base [Build 635](https://coveralls.io/builds/17483544): |  0.2% |
| Covered Lines: | 3606 |
| Relevant Lines: | 5091 |

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


Patch:
diff --git a/README.md b/README.md
index c03bece..73877e4 100644
--- a/README.md
+++ b/README.md
@@ -284,6 +284,9 @@ If you want to uninstall algorithms, it is as simple as:
     - [reverse_words](algorithms/strings/reverse_words.py)
     - [roman_to_int](algorithms/strings/roman_to_int.py)
     - [word_squares](algorithms/strings/word_squares.py)
+    - [unique_morse](algorithms/strings/unique_morse.py)
+    - [judge_circle](algorithms/strings/judge_circle.py)
+    - [strong_password](algorithms/strings/strong_password.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
index b4d1bb4..a74dbf0 100644
--- a/algorithms/strings/__init__.py
+++ b/algorithms/strings/__init__.py
@@ -21,3 +21,6 @@ from .roman_to_int import *
 from .strip_url_params import *
 from .validate_coordinates import *
 from .word_squares import *
+from .unique_morse import *
+from .judge_circle import *
+from .strong_password import *
diff --git a/algorithms/strings/judge_circle.py b/algorithms/strings/judge_circle.py
new file mode 100644
index 0000000..46468a1
--- /dev/null
+++ b/algorithms/strings/judge_circle.py
@@ -0,0 +1,25 @@
+"""
+Initially, there is a Robot at position (0, 0). Given a sequence of its moves,
+judge if this robot makes a circle, which means it moves back to the original place.
+
+The move sequence is represented by a string. And each move is represent by a
+character. The valid robot moves are R (Right), L (Left), U (Up) and D (down).
+The output should be true or false representing whether the robot makes a circle.
+
+Example 1:
+Input: "UD"
+Output: true
+Example 2:
+Input: "LL"
+Output: false
+"""
+def judge_circle(moves):
+    dict_moves = {
+        'U' : 0,
+        'D' : 0,
+        'R' : 0,
+        'L' : 0
+    }
+    for char in moves:
+        dict_moves[char] = dict_moves[char] + 1
+    return dict_moves['L'] == dict_moves['R'] and dict_moves['U'] == dict_moves['D']
diff --git a/algorithms/strings/strong_password.py b/algorithms/strings/strong_password.py
new file mode 100644
index 0000000..85acd02
--- /dev/null
+++ b/algorithms/strings/strong_password.py
@@ -0,0 +1,43 @@
+"""
+The signup page required her to input a name and a password. However, the password
+must be strong. The website considers a password to be strong if it satisfies the following criteria:
+
+1) Its length is at least 6.
+2) It contains at least one digit.
+3) It contains at least one lowercase English character.
+4) It contains at least one uppercase English character.
+5) It contains at least one special character. The special characters are: !@#$%^&*()-+
+She typed a random string of length  in the password field but wasn't sure if it was strong.
+Given the string she typed, can you find the minimum number of characters she must add to make her password strong?
+
+Note: Here's the set of types of characters in a form you can paste in your solution:
+numbers = "0123456789"
+lower_case = "abcdefghijklmnopqrstuvwxyz"
+upper_case = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+special_characters = "!@#$%^&*()-+"
+
+Input Format
+The first line contains an integer  denoting the length of the string.
+The second line contains a string consisting of  characters, the password
+typed by Louise. Each character is either a lowercase/uppercase English alphabet, a digit, or a special character.
+
+Sample Input 1: strong_password(3,"Ab1")
+Output: 3 (Because She can make the password strong by adding  characters,for example, $hk, turning the password into Ab1$hk which is strong.
+2 characters aren't enough since the length must be at least 6.)
+
+Sample Output 2: strong_password(11,"#Algorithms")
+Output: 1 (Because the password isn't strong, but she can make it strong by adding a single digit.)
+
+"""
+def strong_password(n, password):
+    count_error = 0
+    # Return the minimum number of characters to make the password strong
+    if any(i.isdigit() for i in password) == False:
+        count_error = count_error + 1
+    if any(i.islower() for i in password) == False:
+        count_error = count_error + 1
+    if any(i.isupper() for i in password) == False:
+        count_error = count_error + 1
+    if any(i in '!@#$%^&*()-+' for i in password) == False:
+        count_error = count_error + 1
+    return max(count_error, 6 - n)
diff --git a/algorithms/strings/unique_morse.py b/algorithms/strings/unique_morse.py
new file mode 100644
index 0000000..6d86186
--- /dev/null
+++ b/algorithms/strings/unique_morse.py
@@ -0,0 +1,94 @@
+"""
+International Morse Code defines a standard encoding where each letter is mapped to
+a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c"
+maps to "-.-.", and so on.
+
+For convenience, the full table for the 26 letters of the English alphabet is given below:
+        'a':".-",
+        'b':"-...",
+        'c':"-.-.",
+        'd': "-..",
+        'e':".",
+        'f':"..-.",
+        'g':"--.",
+        'h':"....",
+        'i':"..",
+        'j':".---",
+        'k':"-.-",
+        'l':".-..",
+        'm':"--",
+        'n':"-.",
+        'o':"---",
+        'p':".--.",
+        'q':"--.-",
+        'r':".-.",
+        's':"...",
+        't':"-",
+        'u':"..-",
+        'v':"...-",
+        'w':".--",
+        'x':"-..-",
+        'y':"-.--",
+        'z':"--.."
+
+Now, given a list of words, each word can be written as a concatenation of the
+Morse code of each letter. For example, "cab" can be written as "-.-.-....-",
+(which is the concatenation "-.-." + "-..." + ".-"). We'll call such a
+concatenation, the transformation of a word.
+
+Return the number of different transformations among all words we have.
+Example:
+Input: words = ["gin", "zen", "gig", "msg"]
+Output: 2
+Explanation:
+The transformation of each word is:
+"gin" -> "--...-."
+"zen" -> "--...-."
+"gig" -> "--...--."
+"msg" -> "--...--."
+
+There are 2 different transformations, "--...-." and "--...--.".
+"""
+
+morse_code = {
+    'a':".-",
+    'b':"-...",
+    'c':"-.-.",
+    'd': "-..",
+    'e':".",
+    'f':"..-.",
+    'g':"--.",
+    'h':"....",
+    'i':"..",
+    'j':".---",
+    'k':"-.-",
+    'l':".-..",
+    'm':"--",
+    'n':"-.",
+    'o':"---",
+    'p':".--.",
+    'q':"--.-",
+    'r':".-.",
+    's':"...",
+    't':"-",
+    'u':"..-",
+    'v':"...-",
+    'w':".--",
+    'x':"-..-",
+    'y':"-.--",
+    'z':"--.."
+}
+def convert_morse_word(word):
+    morse_word = ""
+    word = word.lower()
+    for char in word:
+        morse_word = morse_word + morse_code[char]
+    return morse_word
+
+def unique_morse(words):
+    unique_morse_word = []
+    for word in words:
+        morse_word = convert_morse_word(word)
+        if morse_word not in unique_morse_word:
+            unique_morse_word.append(morse_word)
+    return len(unique_morse_word)


Test patch:
diff --git a/tests/test_strings.py b/tests/test_strings.py
index 31e0d3e..0cda82c 100644
--- a/tests/test_strings.py
+++ b/tests/test_strings.py
@@ -23,7 +23,10 @@ from algorithms.strings import (
     strip_url_params1, strip_url_params2, strip_url_params3,
     is_valid_coordinates_0, is_valid_coordinates_1,
     is_valid_coordinates_regular_expression,
-    word_squares
+    word_squares,
+    convert_morse_word, unique_morse,
+    judge_circle,
+    strong_password
 )
 
 import unittest
@@ -291,7 +294,7 @@ class TestReverseString(unittest.TestCase):
         self.assertEqual("ereht olleh", pythonic("hello there"))
     def test_ultra_pythonic(self):
         self.assertEqual("ereht olleh", ultra_pythonic("hello there"))
-    
+
 
 class TestReverseVowel(unittest.TestCase):
     """[summary]
@@ -381,6 +384,22 @@ class TestWordSquares(unittest.TestCase):
         self.assertEqual([['wall', 'area', 'lead', 'lady'], ['ball', 'area', 'lead', 'lady']], \
         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"))
 
 if __name__ == "__main__":
     unittest.main()