Add 1-sparse-recovery streaming algorithm (keon#762)

Renstrom · callmeGoldenboy · web-flow · commit 68be49ca496a · 2021-03-07T08:34:33.000+09:00
* feat:(first draft for the misra gries algorithm) keon#1 * feat:(Added examples and changed to correct name) keon#1 * feat:(Added init file for testing) keon#2 * test:(Added tests for misras_gries function) keon#2 * feat:(add 1-sparse recovery algorithm) keon#7 * Add finalized 1-sparse-recovery algorithm * Renamed sparse function name to work with import * Tests added for 1-sparse-recovery function * Tests added for 1-sparse-recovery function Co-authored-by: callmeGoldenboy <natanteferi@gmail.com>
diff --git a/README.md b/README.md
@@ -305,6 +305,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [is_consecutive](algorithms/stack/is_consecutive.py)
     - [remove_min](algorithms/stack/remove_min.py)
     - [is_sorted](algorithms/stack/is_sorted.py)
+- [streaming](algorithms/streaming)
+    - [1-sparse-recovery](algorithms/streaming/one_sparse_recovery.py)
 - [strings](algorithms/strings)
     - [fizzbuzz](algorithms/strings/fizzbuzz.py)
     - [delete_reoccurring](algorithms/strings/delete_reoccurring.py)
diff --git a/algorithms/streaming/__init__.py b/algorithms/streaming/__init__.py
@@ -0,0 +1 @@
+from .one_sparse_recovery import *
diff --git a/algorithms/streaming/one_sparse_recovery.py b/algorithms/streaming/one_sparse_recovery.py
@@ -0,0 +1,61 @@
+""" Non-negative 1-sparse recovery problem. This algorithm assumes we have a non negative dynamic stream.
+Given a stream of tuples, where each tuple contains a number and a sign (+/-), it check if the stream is 1-sparse, meaning if the elements 
+in the stream cancel eacheother out in such a way that ther is only a unique number at the end. 
+
+Examples:
+#1 
+Input:  [(4,'+'), (2,'+'),(2,'-'),(4,'+'),(3,'+'),(3,'-')],
+Output: 4 
+Comment: Since 2 and 3 gets removed.
+#2 
+Input:  [(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+')]
+Output: 2 
+Comment: No other numbers present
+#3
+Input:  [(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(1,'+')]
+Output: None 
+Comment: Not 1-sparse
+"""
+
+def one_sparse(array):
+  sum_signs = 0 
+  bitsum = [0]*32 
+  sum_values = 0 
+  for val,sign in array: 
+    if sign == "+": 
+      sum_signs += 1
+      sum_values += val
+    else:
+      sum_signs -= 1 
+      sum_values -= val
+    
+    _get_bit_sum(bitsum,val,sign)
+  
+  if sum_signs > 0 and _check_every_number_in_bitsum(bitsum,sum_signs):
+    return int(sum_values/sum_signs)
+  else:
+    return None
+   
+#Helper function to check that every entry in the list is either 0 or  the same as the
+#sum of signs
+def _check_every_number_in_bitsum(bitsum,sum_signs):
+  for val in bitsum: 
+    if val != 0 and val != sum_signs : 
+      return False
+  return True
+
+# Adds bit representation value to bitsum array
+def _get_bit_sum(bitsum,val,sign):
+  i = 0 
+  if sign == "+":
+    while(val):
+      bitsum[i] += val & 1
+      i +=1
+      val >>=1
+  else :
+    while(val):
+      bitsum[i] -= val & 1
+      i +=1
+      val >>=1
+
+
diff --git a/tests/test_streaming.py b/tests/test_streaming.py
@@ -0,0 +1,15 @@
+from algorithms.streaming import (
+    one_sparse
+)
+import unittest   
+
+class TestOneSparse(unittest.TestCase):
+    def test_one_sparse_correct(self):
+        self.assertEqual(4,one_sparse([(4,'+'), (2,'+'),(2,'-'),(4,'+'),(3,'+'),(3,'-')]))
+        self.assertEqual(2,one_sparse([(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+')]))
+
+
+    def test_one_sparse_incorrect(self):
+        self.assertEqual(None,one_sparse([(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'+'),(1,'+')])) #Two values remaining
+        self.assertEqual(None,one_sparse([(2,'+'),(2,'+'),(2,'+'),(2,'+'),(2,'-'),(2,'-'),(2,'-'),(2,'-')])) # No values remaining
+        self.assertEqual(None,one_sparse([(2,'+'),(2,'+'),(4,'+'),(4,'+')])) # Bitsum sum of sign is inccorect
