Repository: keon/algorithms (python)

Issue:
Test fail. arrays/plus_one makes tests fail
The function plus_one_v3() tries to access the index as if it was an actual index (number) but since it's being used in a for loop with an enumerate, it is actually a tuple of (idx,value) for all the items in the list

I discovered this while making a PR for another issue since it would reject my build.

Already making a PR changing it so the tests run again. 

Pull request:
Fix array plus one v3

(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [ ] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [ ] included tests with it ?
  - [ ] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [X] **if done some changes :**
  - [X] wrote short description in the PR explaining what the changes do ?
  - [X] Fixes #431 ad #337 

- [ ] **other**


Patch:
diff --git a/algorithms/arrays/plus_one.py b/algorithms/arrays/plus_one.py
index f63aafa..473b6c7 100644
--- a/algorithms/arrays/plus_one.py
+++ b/algorithms/arrays/plus_one.py
@@ -42,7 +42,7 @@ def plus_one_v2(digits):
 def plus_one_v3(num_arr):
 
     for idx in reversed(list(enumerate(num_arr))):
-        num_arr[idx] = (num_arr[idx] + 1) % 10
-        if num_arr[idx]:
+        num_arr[idx[0]] = (num_arr[idx[0]] + 1) % 10
+        if num_arr[idx[0]]:
             return num_arr
     return [1] + num_arr
diff --git a/algorithms/linkedlist/__init__.py b/algorithms/linkedlist/__init__.py
index 21263bf..1c9c3b9 100644
--- a/algorithms/linkedlist/__init__.py
+++ b/algorithms/linkedlist/__init__.py
@@ -6,3 +6,4 @@ from .rotate_list import *
 from .is_cyclic import *
 from .merge_two_list import *
 from .is_palindrome import *
+from .copy_random_pointer import *
diff --git a/algorithms/linkedlist/copy_random_pointer.py b/algorithms/linkedlist/copy_random_pointer.py
index 7653d49..b3ef462 100644
--- a/algorithms/linkedlist/copy_random_pointer.py
+++ b/algorithms/linkedlist/copy_random_pointer.py
@@ -4,35 +4,45 @@ pointer which could point to any node in the list or null.
 
 Return a deep copy of the list.
 """
-# from collections import defaultdict
+from collections import defaultdict
 
-# TODO: This requires to be rewritten -- commenting it out for now
-# class Solution0:
-  # @param head, a RandomListNode
-  # @return a RandomListNode
-  # def copyRandomList(self, head):
-  #   dic = dict()
-  #   m = n = head
-  #   while m:
-  #       dic[m] = RandomListNode(m.label)
-  #       m = m.next
-  #   while n:
-  #       dic[n].next = dic.get(n.next)
-  #       dic[n].random = dic.get(n.random)
-  #       n = n.next
-  #   return dic.get(head)
-#
-#
-# class Solution1:  # O(n)
-#   @param head, a RandomListNode
-#   @return a RandomListNode
-  # def copyRandomList(self, head):
-  #   copy = defaultdict(lambda: RandomListNode(0))
-  #   copy[None] = None
-  #   node = head
-  #   while node:
-  #       copy[node].label = node.label
-  #       copy[node].next = copy[node.next]
-  #       copy[node].random = copy[node.random]
-  #       node = node.next
-  #   return copy[head]
+
+class RandomListNode(object):
+    def __init__(self, label):
+        self.label = label
+        self.next = None
+        self.random = None
+
+
+def copy_random_pointer_v1(head):
+    """
+    :type head: RandomListNode
+    :rtype: RandomListNode
+    """
+    dic = dict()
+    m = n = head
+    while m:
+        dic[m] = RandomListNode(m.label)
+        m = m.next
+    while n:
+        dic[n].next = dic.get(n.next)
+        dic[n].random = dic.get(n.random)
+        n = n.next
+    return dic.get(head)
+
+
+# O(n)
+def copy_random_pointer_v2(head):
+    """
+    :type head: RandomListNode
+    :rtype: RandomListNode
+    """
+    copy = defaultdict(lambda: RandomListNode(0))
+    copy[None] = None
+    node = head
+    while node:
+        copy[node].label = node.label
+        copy[node].next = copy[node.next]
+        copy[node].random = copy[node.random]
+        node = node.next
+    return copy[head]


Test patch:
diff --git a/tests/test_linkedlist.py b/tests/test_linkedlist.py
index 435ac72..6b7f1f4 100644
--- a/tests/test_linkedlist.py
+++ b/tests/test_linkedlist.py
@@ -1,3 +1,5 @@
+import unittest
+
 from algorithms.linkedlist import (
     reverse_list, reverse_list_recursive,
     is_sorted,
@@ -6,16 +8,17 @@ from algorithms.linkedlist import (
     rotate_right,
     is_cyclic,
     merge_two_list, merge_two_list_recur,
-    is_palindrome, is_palindrome_stack, is_palindrome_dict
+    is_palindrome, is_palindrome_stack, is_palindrome_dict,
+    RandomListNode, copy_random_pointer_v1, copy_random_pointer_v2
 )
 
-import unittest
 
 class Node(object):
     def __init__(self, x):
         self.val = x
         self.next = None
 
+
 # Convert from linked list Node to list for testing
 def convert(head):
     ret = []
@@ -26,6 +29,7 @@ def convert(head):
             current = current.next
     return ret
 
+
 class TestSuite(unittest.TestCase):
     def setUp(self):
         # list test for palindrome
@@ -69,7 +73,6 @@ class TestSuite(unittest.TestCase):
         self.assertFalse(is_sorted(head))
 
     def test_remove_range(self):
-
         # Test case: middle case.
         head = Node(0)
         head.next = Node(1)
@@ -163,12 +166,50 @@ class TestSuite(unittest.TestCase):
     def test_is_palindrome(self):
         self.assertTrue(is_palindrome(self.l))
         self.assertFalse(is_palindrome(self.l1))
+
     def test_is_palindrome_stack(self):
         self.assertTrue(is_palindrome_stack(self.l))
         self.assertFalse(is_palindrome_stack(self.l1))
+
     def test_is_palindrome_dict(self):
         self.assertTrue(is_palindrome_dict(self.l))
         self.assertFalse(is_palindrome_dict(self.l1))
 
+    def test_solution_0(self):
+        self._init_random_list_nodes()
+        result = copy_random_pointer_v1(self.random_list_node1)
+        self._assert_is_a_copy(result)
+
+    def test_solution_1(self):
+        self._init_random_list_nodes()
+        result = copy_random_pointer_v2(self.random_list_node1)
+        self._assert_is_a_copy(result)
+
+    def _assert_is_a_copy(self, result):
+        self.assertEqual(5, result.next.next.next.next.label)
+        self.assertEqual(4, result.next.next.next.label)
+        self.assertEqual(3, result.next.next.label)
+        self.assertEqual(2, result.next.label)
+        self.assertEqual(1, result.label)
+        self.assertEqual(3, result.next.next.next.next.random.label)
+        self.assertIsNone(result.next.next.next.random)
+        self.assertEqual(2, result.next.next.random.label)
+        self.assertEqual(5, result.next.random.label)
+        self.assertEqual(4, result.random.label)
+
+    def _init_random_list_nodes(self):
+        self.random_list_node1 = RandomListNode(1)
+        random_list_node2 = RandomListNode(2)
+        random_list_node3 = RandomListNode(3)
+        random_list_node4 = RandomListNode(4)
+        random_list_node5 = RandomListNode(5)
+
+        self.random_list_node1.next, self.random_list_node1.random = random_list_node2, random_list_node4
+        random_list_node2.next, random_list_node2.random = random_list_node3, random_list_node5
+        random_list_node3.next, random_list_node3.random = random_list_node4, random_list_node2
+        random_list_node4.next = random_list_node5
+        random_list_node5.random = random_list_node3
+
+
 if __name__ == "__main__":
     unittest.main()