From 20bda975f02bdf906e924f176c27fd95df8c8424 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 12 Mar 2019 21:33:24 -0500
Subject: Hashing with chains done!

I was tricked by how to create a list of empty list. This line
solved the problem:
self.elems = [[] for i in range(n)]
---
 sources/hash_chains.py   | 68 ++++++++++++++++++++++++++++++++++++++++++++++++
 tests/hash_chainsTest.py | 35 +++++++++++++++++++++++++
 2 files changed, 103 insertions(+)
 create mode 100644 sources/hash_chains.py
 create mode 100644 tests/hash_chainsTest.py

diff --git a/sources/hash_chains.py b/sources/hash_chains.py
new file mode 100644
index 0000000..cbd0fbb
--- /dev/null
+++ b/sources/hash_chains.py
@@ -0,0 +1,68 @@
+# python3
+
+
+class Query:
+
+    def __init__(self, query):
+        self.type = query[0]
+        if self.type == 'check':
+            self.ind = int(query[1])
+        else:
+            self.s = query[1]
+
+
+class QueryProcessor:
+    _multiplier = 263
+    _prime = 1000000007
+
+    def __init__(self, bucket_count):
+        self.bucket_count = bucket_count
+        # store all strings in one list
+        self.elems = []
+
+    def hash_func(self, s):
+        ans = 0
+        for c in reversed(s):
+            ans = (ans * self._multiplier + ord(c)) % self._prime
+        return ans % self.bucket_count
+
+    def write_search_result(self, was_found):
+        print('yes' if was_found else 'no')
+
+    def write_chain(self, chain):
+        print(' '.join(chain))
+
+    def read_query(self):
+        return Query(input().split())
+
+    def process_query(self, query):
+        if query.type == "check":
+            # use reverse order, because we append strings to the end
+            self.write_chain(cur for cur in reversed(self.elems[query.ind]))
+        else:
+            try:
+                ind = self.hash_func(query.s)
+            except ValueError:
+                ind = -1
+            if query.type == 'find':
+                self.write_search_result(query.s in self.elems[ind])
+            elif query.type == 'add':
+                if query.s not in self.elems[ind]:
+                    self.elems[ind].append(query.s)
+            else:
+                try:
+                    self.elems[ind].remove(query.s)
+                except ValueError:
+                    pass
+
+    def process_queries(self):
+        n = int(input())
+        self.elems = [[] for i in range(n)]
+        for i in range(n):
+            self.process_query(self.read_query())
+
+
+if __name__ == '__main__':
+    bucket_count = int(input())
+    proc = QueryProcessor(bucket_count)
+    proc.process_queries()
diff --git a/tests/hash_chainsTest.py b/tests/hash_chainsTest.py
new file mode 100644
index 0000000..5bdac8f
--- /dev/null
+++ b/tests/hash_chainsTest.py
@@ -0,0 +1,35 @@
+import unittest
+
+from sources.hash_chains import QueryProcessor, Query
+
+class MyTestCase(unittest.TestCase):
+    def test_something(self):
+        proc = QueryProcessor(5)
+        self.assertEqual(4, proc.hash_func('world'))
+        self.assertEqual(4, proc.hash_func('HellO'))
+        self.assertEqual(2, proc.hash_func('GooD'))
+        self.assertEqual(2, proc.hash_func('luck'))
+
+    def test_something1(self):
+        proc = QueryProcessor(3)
+        self.assertEqual(1, proc.hash_func('add'))
+        self.assertEqual(1, proc.hash_func('help'))
+        self.assertEqual(2, proc.hash_func('del'))
+
+        proc.elems = [[] for i in range(12)]
+        proc.process_query(Query(['check', 0]))
+        proc.process_query(Query(['find', 'help']))
+        proc.process_query(Query(['add', 'help']))
+        proc.process_query(Query(['add', 'del']))
+        proc.process_query(Query(['add', 'add']))
+        proc.process_query(Query(['find', 'add']))
+        proc.process_query(Query(['find', 'del']))
+        proc.process_query(Query(['del', 'del']))
+        proc.process_query(Query(['find', 'del']))
+        proc.process_query(Query(['check', 0]))
+        proc.process_query(Query(['check', 1]))
+        proc.process_query(Query(['check', 2]))
+
+
+if __name__ == '__main__':
+    unittest.main()
-- 
cgit v1.2.3