summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2019-03-12 21:33:24 -0500
committerHaidong Ji2019-03-12 21:33:24 -0500
commit20bda975f02bdf906e924f176c27fd95df8c8424 (patch)
tree35a9cc2c3570aecc0ce0b55b283c6be8652e47c6
parent0c0755cd6087679207063d2d31fed9a2cda23f31 (diff)
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)]
-rw-r--r--sources/hash_chains.py68
-rw-r--r--tests/hash_chainsTest.py35
2 files changed, 103 insertions, 0 deletions
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()