HASHING.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,elem,next):\n",
    "        self.elem=elem\n",
    "        self.next=next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "data={'CSE111' : 300,\n",
    "      'CSE220' : 250,\n",
    "      'CSE320' : 150,\n",
    "      'CSE250' : 170,\n",
    "      'CSE370' : 200}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "hash_table= [None]*4 #HASH TABLE CREATION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hash_function(key):\n",
    "    hash_value=ord(key[-1]) + ord(key[-2]) + ord(key[-3])  #CSE111 IT TAKES ONLY [111]\n",
    "    hash_value=hash_value % 4 \n",
    "    return hash_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# hash table creation\n",
    "for k,v in data.items():\n",
    "    index=hash_function(k)\n",
    "    if hash_table[index] == None:\n",
    "        temp=Node((k,v) , None)\n",
    "        hash_table[index]=temp\n",
    "    else:\n",
    "        temp=Node((k,v),None)\n",
    "        temp.next=hash_table[index]\n",
    "        hash_table[index]=temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[<__main__.Node object at 0x000001E19E4A67C0>, <__main__.Node object at 0x000001E19E4A64C0>, <__main__.Node object at 0x000001E19F578610>, <__main__.Node object at 0x000001E19F578DC0>]\n"
     ]
    }
   ],
   "source": [
    "print(hash_table) #printing node address"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_linked_list(head):\n",
    "    if head is None: return\n",
    "    while head is not None:\n",
    "        print(head.elem, end=\" -->\")\n",
    "        head=head.next\n",
    "    print(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 ('CSE220', 250) -->None\n",
      "1 ('CSE320', 150) -->None\n",
      "2 ('CSE370', 200) -->None\n",
      "3 ('CSE250', 170) -->('CSE111', 300) -->None\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(hash_table)):\n",
    "    print(i, end= ' ')\n",
    "    print_linked_list(hash_table[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "250\n"
     ]
    }
   ],
   "source": [
    "def search_key(key):\n",
    "    index=hash_function(key)\n",
    "    if hash_table[index] == None:\n",
    "        return 'key not found'\n",
    "    else:\n",
    "        head=hash_table[index]\n",
    "        while head is not None:\n",
    "            if head.elem[0] == key:\n",
    "                return head.elem[1]\n",
    "            head=head.next\n",
    "        return 'key not found'\n",
    "print(search_key('CSE220'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forward_chainning_insert(arr):\n",
    "    hashtable=[None]*size   \n",
    "    for elem in arr:\n",
    "        index=hash_function(elem)\n",
    "        if hashtable[index] == None:\n",
    "            hashtable[index]=Node(elem,None)\n",
    "        else:\n",
    "            temp=hash_table[index]\n",
    "            hash_table[index] = Node(elem,temp)\n",
    "   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forward_chainning_search(elem):\n",
    "    index=hash_func(elem)\n",
    "    temp=hash_table[index]\n",
    "    while temp is not None:\n",
    "        if temp.elem == elem:\n",
    "            return True\n",
    "        temp=temp.next\n",
    "    return False        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "================ Searching & Sorting ================\n",
      "\n",
      "Given Array: [-5, 8, 4, 6, 1, -8, -10]\n",
      "\n",
      "Searing for -> 4\n",
      "4 is in the list.\n",
      "\n",
      "Sorted List -> [-10, -8, -5, 1, 4, 6, 8]\n",
      "\n",
      "================ Hashtable & Hashing ================\n",
      "\n",
      "Printing Hashtable -> \n",
      "\n",
      "KD9LNX46TT2\n",
      "5YLHRBO79CT\n",
      "WN2NY54F22D\n",
      "YVRFKVUOH6Y\n",
      "ST1E89B8A32\n",
      "5W8UWJSDCJH\n",
      "X9ZAR2JD6F7\n",
      "ZJO9V49NDOU\n",
      "G94F5SMC2DG\n"
     ]
    }
   ],
   "source": [
    "# ================================ Searching & Sorting ================================\n",
    "\n",
    "\n",
    "def findMaxValue(list):\n",
    "    val = list[0]\n",
    "    for i in list:\n",
    "        if val < abs(i):\n",
    "            val = abs(i)\n",
    "    return val\n",
    "\n",
    "\n",
    "class KeyIndex:\n",
    "    def __init__(self, arr):\n",
    "\n",
    "        self.maxValue = findMaxValue(arr)\n",
    "\n",
    "        self.aux = [0] * ((self.maxValue * 2) + 1)\n",
    "\n",
    "        for i in arr:\n",
    "            if self.aux[self.maxValue + i] == 0:\n",
    "                self.aux[self.maxValue + i] = 1\n",
    "            else:\n",
    "                self.aux[self.maxValue + i] = self.aux[self.maxValue + i] + 1\n",
    "\n",
    "    def search(self, key):\n",
    "        key = int(key)\n",
    "\n",
    "        if key + self.maxValue < 0 or key + self.maxValue >= len(self.aux):\n",
    "            return False\n",
    "        else:\n",
    "            if self.aux[key + self.maxValue] != 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "    def sort(self):\n",
    "        index = 0\n",
    "\n",
    "        arrSize = 0\n",
    "        for item in self.aux:\n",
    "            arrSize += item\n",
    "\n",
    "        arr = [0] * arrSize\n",
    "\n",
    "        for i in range(0, len(self.aux)):\n",
    "            if index >= len(arr):\n",
    "                print(arr)\n",
    "                break\n",
    "\n",
    "            if self.aux[i] >= 1:\n",
    "                for _ in range(0, self.aux[i]):\n",
    "                    arr[index] = i - self.maxValue\n",
    "                    index += 1\n",
    "\n",
    "        return arr\n",
    "\n",
    "\n",
    "# ================================ Searching & Sorting Testing ================================\n",
    "print(\"================ Searching & Sorting ================\\n\")\n",
    "\n",
    "list = [-5, 8, 4, 6, 1, -8, -10]\n",
    "print(f\"Given Array: {list}\")\n",
    "\n",
    "key_indx = KeyIndex(list)\n",
    "print(\"\")\n",
    "\n",
    "# Searching\n",
    "try:\n",
    "    var = 4\n",
    "    # var = int(input(\"Search for : \"))\n",
    "    print(f\"Searing for -> {var}\")\n",
    "except ValueError:\n",
    "    var = 3\n",
    "    print(\n",
    "        \"User didn't manually entered the search value. Searching for default value 3.\\n\"\n",
    "    )\n",
    "\n",
    "if key_indx.search(var):\n",
    "    print(f\"{var} is in the list.\\n\")\n",
    "else:\n",
    "    print(f\"{var} is not in the list.\\n\")\n",
    "\n",
    "# Sorting\n",
    "print(\"Sorted List -> \", end=\"\")\n",
    "key_indx.sort()\n",
    "print()\n",
    "\n",
    "# ================================ Hashtable ================================\n",
    "\n",
    
    "\n",
    "\n",
    "class Hashtable:\n",
    "    def __init__(self, size=9, debug_mode=False) -> None:\n",
    "        self.size = size\n",
    "        self.table = [0] * size\n",
    "\n",
    "        # Debug Mode Flag for turning on/off some\n",
    "        # print statements to help debugging\n",
    "        self.debug_mode = debug_mode\n",
    "        if debug_mode:\n",
    "            print(f\"\\n[DEBUG MODE] Created Hashtable with Size - {self.size}\\n\")\n",
    "\n",
    "    def hashKey(self, string):\n",
    "\n",
    "        vowels = \"AEIOUaeiou\"\n",
    "        digits = \"0123456789\"\n",
    "\n",
    "        total_consonant = 0\n",
    "        digit_sum = 0\n",
    "\n",
    "        for char in string:\n",
    "            # If char is consonant\n",
    "            if char not in vowels and char not in digits:\n",
    "                total_consonant += 1\n",
    "\n",
    "            elif char.isdigit():\n",
    "                digit_sum += int(char)\n",
    "\n",
    "        hash_key = (total_consonant * 24) + digit_sum\n",
    "        return hash_key\n",
    "\n",
    "    def insert(self, string):\n",
    "\n",
    "        hash_key = self.hashKey(string)\n",
    "        position = hash_key % self.size\n",
    "\n",
    "        if self.debug_mode:\n",
    "            print(\n",
    "                f\"[DEBUG MODE] String - {string}\\n[DEBUG MODE] HashKey - {hash_key}\\n[DEBUG MODE] Position - {position}\"\n",
    "            )\n",
    "\n",
    "        # Loop start from 1 because we need to add 1\n",
    "        # with hashkey every iteration\n",
    "        for index in range(1, self.size):\n",
    "            if self.table[position] == 0:\n",
    "                self.table[position] = string\n",
    "\n",
    "                if self.debug_mode:\n",
    "                    print(f\"[DEBUG MODE] String inserted in Position - {position}\")\n",
    "                    print(f\"[DEBUG MODE] Current HashTable -> \\n{self.table}\\n\\n\")\n",
    "\n",
    "                break\n",
    "\n",
    "            else:\n",
    "                position = (hash_key + index) % self.size\n",
    "\n",
    "                if self.debug_mode:\n",
    "                    print(\n",
    "                        f\"> Current Position is not empty. New Position -> {position}\"\n",
    "                    )\n",
    "\n",
    "    def print(self):\n",
    "        print(\"Printing Hashtable -> \\n\")\n",
    "\n",
    "        for string in range(self.size):\n",
    "            print(self.table[string])\n",
    "\n",
    "\n",
    "# ================================ Hashtable Testing ================================\n",
    "print(\"================ Hashtable & Hashing ================\\n\")\n",
    "\n",
    "strings = [\n",
    "    \"ST1E89B8A32\",\n",
    "    \"ZJO9V49NDOU\",\n",
    "    \"X9ZAR2JD6F7\",\n",
    "    \"KD9LNX46TT2\",\n",
    "    \"G94F5SMC2DG\",\n",
    "    \"5YLHRBO79CT\",\n",
    "    \"WN2NY54F22D\",\n",
    "    \"YVRFKVUOH6Y\",\n",
    "    \"5W8UWJSDCJH\",\n",
    "]\n",
    "\n",
    "hash_table = Hashtable(debug_mode=False)\n",
    "\n",
    "for string in strings:\n",
    "    hash_table.insert(string)\n",
    "\n",
    "hash_table.print()\n",
    "\n",
    "\n",
    
    "#\n",
    "# class Hashtable:\n",
    "#     def __init__(self, size=9) -> None:\n",
    "#         self.size = size\n",
    "#         self.table = [0] * size\n",
    "\n",
    "#     def hashKey(self, string):\n",
    "\n",
    "#         vowels = \"AEIOUaeiou\"\n",
    "#         digits = \"0123456789\"\n",
    "\n",
    "#         total_consonant = 0\n",
    "#         digit_sum = 0\n",
    "\n",
    "#         for char in string:\n",
    "#             # If char is consonant\n",
    "#             if char not in vowels and char not in digits:\n",
    "#                 total_consonant += 1\n",
    "\n",
    "#             elif char.isdigit():\n",
    "#                 digit_sum += int(char)\n",
    "\n",
    "#         hash_key = (total_consonant * 24) + digit_sum\n",
    "#         return hash_key\n",
    "\n",
    "#     def insert(self, string):\n",
    "\n",
    "#         hash_key = self.hashKey(string)\n",
    "#         position = hash_key % self.size\n",
    "\n",
    "#         # Loop start from 1 because we need to add 1\n",
    "#         # with hashkey every iteration\n",
    "#         for index in range(1, self.size):\n",
    "#             if self.table[position] == 0:\n",
    "#                 self.table[position] = string\n",
    "#                 break\n",
    "\n",
    "#             else:\n",
    "#                 position = (hash_key + index) % self.size\n",
    "\n",
    "#     def print(self):\n",
    "#         print(\"Printing Hashtable -> \\n\")\n",
    "\n",
    "#         for string in range(self.size):\n",
    "#             print(self.table[string])\n",
    "\n",
    "\n",
    "# print(\"================ Hashtable & Hashing ================\\n\")\n",
    "\n",
    "# strings = [\n",
    "#     \"ST1E89B8A32\",\n",
    "#     \"ZJO9V49NDOU\",\n",
    "#     \"X9ZAR2JD6F7\",\n",
    "#     \"KD9LNX46TT2\",\n",
    "#     \"G94F5SMC2DG\",\n",
    "#     \"5YLHRBO79CT\",\n",
    "#     \"WN2NY54F22D\",\n",
    "#     \"YVRFKVUOH6Y\",\n",
    "#     \"5W8UWJSDCJH\",\n",
    "# ]\n",
    "\n",
    "# hash_table = Hashtable()\n",
    "\n",
    "\n",
    "# for string in strings:\n",
    "#     hash_table.insert(string)\n",
    "\n",
    "# hash_table.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "================ Searching & Sorting ================\n",
      "\n",
      "Given Array: [-5, 8, 4, 6, 1, -8, -10]\n",
      "\n",
      "Searing for -> 4\n",
      "4 is in the list.\n",
      "\n",
      "Sorted List -> [-10, -8, -5, 1, 4, 6, 8]\n",
      "\n",
      "================ Hashtable & Hashing ================\n",
      "\n",
      "Printing Hashtable -> \n",
      "\n",
      "KD9LNX46TT2\n",
      "5YLHRBO79CT\n",
      "WN2NY54F22D\n",
      "YVRFKVUOH6Y\n",
      "ST1E89B8A32\n",
      "5W8UWJSDCJH\n",
      "X9ZAR2JD6F7\n",
      "ZJO9V49NDOU\n",
      "G94F5SMC2DG\n"
     ]
    }
   ],
   "source": [
    "# ================================ Searching & Sorting ================================\n",
    "\n",
    "\n",
    "def findMaxValue(list):\n",
    "    val = list[0]\n",
    "    for i in list:\n",
    "        if val < abs(i):\n",
    "            val = abs(i)\n",
    "    return val\n",
    "\n",
    "\n",
    "class KeyIndex:\n",
    "    def __init__(self, arr):\n",
    "\n",
    "        self.maxValue = findMaxValue(arr)\n",
    "\n",
    "        self.aux = [0] * ((self.maxValue * 2) + 1)\n",
    "\n",
    "        for i in arr:\n",
    "            if self.aux[self.maxValue + i] == 0:\n",
    "                self.aux[self.maxValue + i] = 1\n",
    "            else:\n",
    "                self.aux[self.maxValue + i] = self.aux[self.maxValue + i] + 1\n",
    "\n",
    "    def search(self, key):\n",
    "        key = int(key)\n",
    "\n",
    "        if key + self.maxValue < 0 or key + self.maxValue >= len(self.aux):\n",
    "            return False\n",
    "        else:\n",
    "            if self.aux[key + self.maxValue] != 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "    def sort(self):\n",
    "        index = 0\n",
    "\n",
    "        arrSize = 0\n",
    "        for item in self.aux:\n",
    "            arrSize += item\n",
    "\n",
    "        arr = [0] * arrSize\n",
    "\n",
    "        for i in range(0, len(self.aux)):\n",
    "            if index >= len(arr):\n",
    "                print(arr)\n",
    "                break\n",
    "\n",
    "            if self.aux[i] >= 1:\n",
    "                for _ in range(0, self.aux[i]):\n",
    "                    arr[index] = i - self.maxValue\n",
    "                    index += 1\n",
    "\n",
    "        return arr\n",
    "\n",
    "\n",
    "# ================================ Searching & Sorting Testing ================================\n",
    "print(\"================ Searching & Sorting ================\\n\")\n",
    "\n",
    "list = [-5, 8, 4, 6, 1, -8, -10]\n",
    "print(f\"Given Array: {list}\")\n",
    "\n",
    "key_indx = KeyIndex(list)\n",
    "print(\"\")\n",
    "\n",
    "# Searching\n",
    "try:\n",
    "    var = 4\n",
    "    # var = int(input(\"Search for : \"))\n",
    "    print(f\"Searing for -> {var}\")\n",
    "except ValueError:\n",
    "    var = 3\n",
    "    print(\n",
    "        \"User didn't manually entered the search value. Searching for default value 3.\\n\"\n",
    "    )\n",
    "\n",
    "if key_indx.search(var):\n",
    "    print(f\"{var} is in the list.\\n\")\n",
    "else:\n",
    "    print(f\"{var} is not in the list.\\n\")\n",
    "\n",
    "# Sorting\n",
    "print(\"Sorted List -> \", end=\"\")\n",
    "key_indx.sort()\n",
    "print()\n",
    "\n",
    
    "\n",
    "\n",
    "class Hashtable:\n",
    "    def __init__(self, size=9, debug_mode=False) -> None:\n",
    "        self.size = size\n",
    "        self.table = [0] * size\n",
    "\n",
    "        # Debug Mode Flag for turning on/off some\n",
    "        # print statements to help debugging\n",
    "        self.debug_mode = debug_mode\n",
    "        if debug_mode:\n",
    "            print(f\"\\n[DEBUG MODE] Created Hashtable with Size - {self.size}\\n\")\n",
    "\n",
    "    def hashKey(self, string):\n",
    "\n",
    "        vowels = \"AEIOUaeiou\"\n",
    "        digits = \"0123456789\"\n",
    "\n",
    "        total_consonant = 0\n",
    "        digit_sum = 0\n",
    "\n",
    "        for char in string:\n",
    "            # If char is consonant\n",
    "            if char not in vowels and char not in digits:\n",
    "                total_consonant += 1\n",
    "\n",
    "            elif char.isdigit():\n",
    "                digit_sum += int(char)\n",
    "\n",
    "        hash_key = (total_consonant * 24) + digit_sum\n",
    "        return hash_key\n",
    "\n",
    "    def insert(self, string):\n",
    "\n",
    "        hash_key = self.hashKey(string)\n",
    "        position = hash_key % self.size\n",
    "\n",
    "        if self.debug_mode:\n",
    "            print(\n",
    "                f\"[DEBUG MODE] String - {string}\\n[DEBUG MODE] HashKey - {hash_key}\\n[DEBUG MODE] Position - {position}\"\n",
    "            )\n",
    "\n",
    "        # Loop start from 1 because we need to add 1\n",
    "        # with hashkey every iteration\n",
    "        for index in range(1, self.size):\n",
    "            if self.table[position] == 0:\n",
    "                self.table[position] = string\n",
    "\n",
    "                if self.debug_mode:\n",
    "                    print(f\"[DEBUG MODE] String inserted in Position - {position}\")\n",
    "                    print(f\"[DEBUG MODE] Current HashTable -> \\n{self.table}\\n\\n\")\n",
    "\n",
    "                break\n",
    "\n",
    "            else:\n",
    "                position = (hash_key + index) % self.size\n",
    "\n",
    "                if self.debug_mode:\n",
    "                    print(\n",
    "                        f\"> Current Position is not empty. New Position -> {position}\"\n",
    "                    )\n",
    "\n",
    "    def print(self):\n",
    "        print(\"Printing Hashtable -> \\n\")\n",
    "\n",
    "        for string in range(self.size):\n",
    "            print(self.table[string])\n",
    "\n",
    "\n",
    "# ================================ Hashtable Testing ================================\n",
    "print(\"================ Hashtable & Hashing ================\\n\")\n",
    "\n",
    "strings = [\n",
    "    \"ST1E89B8A32\",\n",
    "    \"ZJO9V49NDOU\",\n",
    "    \"X9ZAR2JD6F7\",\n",
    "    \"KD9LNX46TT2\",\n",
    "    \"G94F5SMC2DG\",\n",
    "    \"5YLHRBO79CT\",\n",
    "    \"WN2NY54F22D\",\n",
    "    \"YVRFKVUOH6Y\",\n",
    "    \"5W8UWJSDCJH\",\n",
    "]\n",
    "\n",
    "hash_table = Hashtable(debug_mode=False)\n",
    "\n",
    "for string in strings:\n",
    "    hash_table.insert(string)\n",
    "\n",
    "hash_table.print()\n",
    "\n",
    "\n",
    "# =============================== Hashing Without Debug Mode ============================\n",
    "#\n",
    "#\n",
    "# class Hashtable:\n",
    "#     def __init__(self, size=9) -> None:\n",
    "#         self.size = size\n",
    "#         self.table = [0] * size\n",
    "\n",
    "#     def hashKey(self, string):\n",
    "\n",
    "#         vowels = \"AEIOUaeiou\"\n",
    "#         digits = \"0123456789\"\n",
    "\n",
    "#         total_consonant = 0\n",
    "#         digit_sum = 0\n",
    "\n",
    "#         for char in string:\n",
    "#             # If char is consonant\n",
    "#             if char not in vowels and char not in digits:\n",
    "#                 total_consonant += 1\n",
    "\n",
    "#             elif char.isdigit():\n",
    "#                 digit_sum += int(char)\n",
    "\n",
    "#         hash_key = (total_consonant * 24) + digit_sum\n",
    "#         return hash_key\n",
    "\n",
    "#     def insert(self, string):\n",
    "\n",
    "#         hash_key = self.hashKey(string)\n",
    "#         position = hash_key % self.size\n",
    "\n",
    "#         # Loop start from 1 because we need to add 1\n",
    "#         # with hashkey every iteration\n",
    "#         for index in range(1, self.size):\n",
    "#             if self.table[position] == 0:\n",
    "#                 self.table[position] = string\n",
    "#                 break\n",
    "\n",
    "#             else:\n",
    "#                 position = (hash_key + index) % self.size\n",
    "\n",
    "#     def print(self):\n",
    "#         print(\"Printing Hashtable -> \\n\")\n",
    "\n",
    "#         for string in range(self.size):\n",
    "#             print(self.table[string])\n",
    "\n",
    "\n",
    "# print(\"================ Hashtable & Hashing ================\\n\")\n",
    "\n",
    "# strings = [\n",
    "#     \"ST1E89B8A32\",\n",
    "#     \"ZJO9V49NDOU\",\n",
    "#     \"X9ZAR2JD6F7\",\n",
    "#     \"KD9LNX46TT2\",\n",
    "#     \"G94F5SMC2DG\",\n",
    "#     \"5YLHRBO79CT\",\n",
    "#     \"WN2NY54F22D\",\n",
    "#     \"YVRFKVUOH6Y\",\n",
    "#     \"5W8UWJSDCJH\",\n",
    "# ]\n",
    "\n",
    "# hash_table = Hashtable()\n",
    "\n",
    "\n",
    "# for string in strings:\n",
    "#     hash_table.insert(string)\n",
    "\n",
    "# hash_table.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No. 1 -->\n",
      "[1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0]\n",
      "\n",
      "User didnot manually enter the search value. Searching for default value 3.\n",
      "3 is not in the list.\n",
      "\n",
      "Sorted List -> [-10, -8, -5, 1, 4, 6, 8]\n"
     ]
    }
   ],
   "source": [
    "def maxValue(list):\n",
    "    val = list[0]\n",
    "    for i in list:\n",
    "        if val < abs(i):\n",
    "            val = abs(i)\n",
    "    return val\n",
    "\n",
    "\n",
    "class keyIndex:\n",
    "    def __init__(self, k):\n",
    "        self.k = k\n",
    "\n",
    "        global max_val\n",
    "        max_val = maxValue(self.k)\n",
    "        self.temp = [0] * ((max_val * 2) + 1)\n",
    "\n",
    "        for i in self.k:\n",
    "            if 0 == self.temp[max_val + i]:\n",
    "                self.temp[max_val + i] = 1\n",
    "            else:\n",
    "                self.temp[max_val + i] = self.temp[max_val + i] + 1\n",
    "\n",
    "    def search(self, key):\n",
    "        k = int(key)\n",
    "        if k + max_val < 0 or k + max_val >= len(self.temp):\n",
    "            return False\n",
    "        else:\n",
    "            if self.temp[k + max_val] != 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "    def sort(self):\n",
    "        indx = 0\n",
    "        for i in range(0, len(self.temp)):\n",
    "            if len(self.k) <= indx:\n",
    "                print(self.k)\n",
    "                break\n",
    "\n",
    "            if self.temp[i] >= 1:\n",
    "                for _ in range(0, self.temp[i]):\n",
    "                    self.k[indx] = i - max_val\n",
    "                    indx += 1\n",
    "\n",
    "    def printlist(self):\n",
    "        print(self.temp)\n",
    "\n",
    "\n",
    "print(\"No. 1 -->\")\n",
    "list = [-5, 8, 4, 6, 1, -8, -10]\n",
    "key_indx = keyIndex(list)\n",
    "key_indx.printlist()\n",
    "\n",
    "print(\"\")\n",
    "try:\n",
    "    var = int(input(\"Search for : \"))\n",
    "except ValueError:\n",
    "    var = 3\n",
    "    print(\"User didnot manually enter the search value. Searching for default value 3.\")\n",
    "\n",
    "if key_indx.search(var):\n",
    "    print(f\"{var} is in the list.\")\n",
    "else:\n",
    "    print(f\"{var} is not in the list.\")\n",
    "\n",
    "print()\n",
    "print(\"Sorted List -> \", end=\"\")\n",
    "key_indx.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No. 2 -->\n",
      "\n",
      "KD9LNX46TT2\n",
      "5YLHRBO79CT\n",
      "WN2NY54F22D\n",
      "YVRFKVUOH6Y\n",
      "ST1E89B8A32\n",
      "5W8UWJSDCJH\n",
      "X9ZAR2JD6F7\n",
      "ZJO9V49NDOU\n",
      "G94F5SMC2DG\n"
     ]
    }
   ],
   "source": [
    "# Problem -02\n",
    "\n",
    "\n",
    "vowels = [\"A\", \"E\", \"I\", \"O\", \"U\"]\n",
    "consonants = [\n",
    "    \"B\",\n",
    "    \"C\",\n",
    "    \"D\",\n",
    "    \"F\",\n",
    "    \"G\",\n",
    "    \"H\",\n",
    "    \"J\",\n",
    "    \"K\",\n",
    "    \"L\",\n",
    "    \"M\",\n",
    "    \"N\",\n",
    "    \"P\",\n",
    "    \"Q\",\n",
    "    \"R\",\n",
    "    \"S\",\n",
    "    \"T\",\n",
    "    \"V\",\n",
    "    \"W\",\n",
    "    \"X\",\n",
    "    \"Y\",\n",
    "    \"Z\",\n",
    "]\n",
    "\n",
    "\n",
    "class Hashstring:\n",
    "    def __init__(self, str):\n",
    "        self.str = str\n",
    "\n",
    "    def string_get(self):\n",
    "        return self.str\n",
    "\n",
    "    def string_key(self):\n",
    "        val = 0\n",
    "        var = 0\n",
    "\n",
    "        for i in self.str:\n",
    "            if i in consonants:\n",
    "                val = val + 1\n",
    "            if i not in consonants and i not in vowels:\n",
    "                var += int(i)\n",
    "\n",
    "        string_key = (val * 24) + var\n",
    "        return string_key\n",
    "\n",
    "\n",
    "class Hashtable:\n",
    "    def __init__(self, size=9):\n",
    "        self.size = size\n",
    "        self.list = [0] * size\n",
    "\n",
    "    def function(self, string_key):\n",
    "        return string_key % self.size\n",
    "\n",
    "    def add(self, s):\n",
    "        val = s.string_key()\n",
    "        position = self.function(val)\n",
    "        for i in range(1, self.size):\n",
    "            if self.list[position] == 0:\n",
    "                self.list[position] = s.string_get()\n",
    "                break\n",
    "            else:\n",
    "                position = (val + i) % self.size\n",
    "\n",
    "    def print(self):\n",
    "        for i in range(self.size):\n",
    "            print(self.list[i])\n",
    "\n",
    "\n",
    "hash_table = Hashtable()\n",
    "list = [\n",
    "    \"ZJO9V49NDOU\",\n",
    "    \"X9ZAR2JD6F7\",\n",
    "    \"KD9LNX46TT2\",\n",
    "    \"G94F5SMC2DG\",\n",
    "    \"5YLHRBO79CT\",\n",
    "    \"WN2NY54F22D\",\n",
    "    \"YVRFKVUOH6Y\",\n",
    "    \"ST1E89B8A32\",\n",
    "    \"5W8UWJSDCJH\",\n",
    "]\n",
    "\n",
    "print(\"No. 2 -->\\n\")\n",
    "for i in list:\n",
    "    s = Hashstring(i)\n",
    "    hash_table.add(s)\n",
    "\n",
    "hash_table.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "[-3, -3, -2, 0, 3, 5, 9, 9]\n"
     ]
    }
   ],
   "source": [
    "class KeyIndex:\n",
    "    def __init__(self,a):\n",
    "        max = a[0]\n",
    "        min = a[0]\n",
    "        for i in a:\n",
    "            if i>max:\n",
    "                max = i\n",
    "            if i<min:\n",
    "                min = i\n",
    "        if min<0:\n",
    "            self.add = -1*min\n",
    "        else:\n",
    "            self.add = 0\n",
    "        self.k = [0]*(self.add+max+1)\n",
    "        for i in a:\n",
    "            self.k[i+self.add] += 1\n",
    "\n",
    "    def search(self,val):\n",
    "        if len(self.k)+1<val or val<(-1*self.add) or self.k[val+self.add]==0 :\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def sort(self):\n",
    "        leng = 0\n",
    "        for i in self.k:\n",
    "            if i!=0:\n",
    "                for m in range(i):\n",
    "                    leng+=1\n",
    "        z = [0]*(leng)\n",
    "        j = 0\n",
    "        for i in range(len(self.k)):\n",
    "            if self.k[i]!=0:\n",
    "                for l in range(self.k[i]):\n",
    "                    z[j]=i-self.add\n",
    "                    j+=1\n",
    "        return z\n",
    "\n",
    "\n",
    "\n",
    "a=[9,5,3,-3,-2,-3,0,9]\n",
    "p = KeyIndex(a)\n",
    "print(p.search(-3))\n",
    "print(p.search(9))\n",
    "print(p.search(-99))\n",
    "print(p.sort())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 'ST1E89B8A31', 'ST1E89B8A32', 'ST1E89B8A32', 'ST1E89B8A32', 'ST1E89B8A31', 0]\n"
     ]
    }
   ],
   "source": [
    "class hashTable:\n",
    "    def __init__(self,arr):\n",
    "        self.table = [0]*9\n",
    "        for i in arr:\n",
    "            j = self.hashFunction(i)\n",
    "            if self.table[j] == 0:\n",
    "                self.table[j] = i\n",
    "            else:\n",
    "                for q in range(9):\n",
    "                    if self.table[(j+q)%9] == 0:\n",
    "                        self.table[(j + q) % 9] = i\n",
    "                        break\n",
    "\n",
    "    def hashFunction(self,string):\n",
    "        consonant = 0\n",
    "        digits = 0\n",
    "        for i in string:\n",
    "            if i in \"0123456789\":\n",
    "                digits += int(i)\n",
    "            elif i.upper() not in \"AEIOU\":\n",
    "                consonant += 1\n",
    "        func = (consonant * 24 + digits) % 9\n",
    "        return func\n",
    "\n",
    "q = [\"ST1E89B8A32\",\"ST1E89B8A32\",\"ST1E89B8A32\",\"ST1E89B8A31\",\"ST1E89B8A31\"]\n",
    "q = hashTable(q)\n",
    "print(q.table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Continue:  5\n",
      "Continue:  4\n",
      "Continue:  3\n",
      "Continue:  2\n",
      "Stop:  1\n",
      "Finally  15\n"
     ]
    }
   ],
   "source": [
    "class Trace:\n",
    "    def hMB(self,h):\n",
    "        if (h==0):\n",
    "            print(\"Stop: \",h)\n",
    "            return 0\n",
    "        elif(h==1):\n",
    "            print(\"Stop: \",h)\n",
    "            return h\n",
    "        else:\n",
    "            print(\"Continue: \",h)\n",
    "            return h + self.hMB(h-1)\n",
    "#Tester\n",
    "t = Trace()\n",
    "print(\"Finally \",t.hMB(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class KeyIndex:\n",
    "    def __init__(self,array):\n",
    "        self.array = []\n",
    "        for i in array:\n",
    "            self.array.append(i)\n",
    "            \n",
    "    def sort(self):\n",
    "        mx = self.array[-1]\n",
    "        for i in range(len(self.array)):\n",
    "            if self.array[i]>mx:\n",
    "                mx = self.array[i]\n",
    "\n",
    "        na=[0 for _ in range(mx+1)]\n",
    "        \n",
    "        for j in range(len(self.array)):\n",
    "            na[self.array[j]]+=1\n",
    "        i=0\n",
    "        c=0     \n",
    "        while(i<mx+1):\n",
    "            if(na[i]>0):\n",
    "                self.array[c]=i\n",
    "                c+=1\n",
    "                na[i]-=1\n",
    "            else:\n",
    "                i+=1\n",
    "\n",
    "        return self.array   \n",
    "    def search(self,val):\n",
    "        if val in self.array:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    \n",
    "    \n",
    "#Tester    \n",
    "    \n",
    "array = KeyIndex([3,5,2,6,7])    \n",
    "array.sort()\n",
    "lst = array.array\n",
    "print(lst)\n",
    "array.search(5)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}