OPPE/Week-2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2024/08/07"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "8\n",
      "8\n",
      "8\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "# external code (avoid this 💀)\n",
    "def findLargest(L):\n",
    "  low = 0\n",
    "  high = len(L)\n",
    "\n",
    "  while low < high:\n",
    "    mid = (low+high)//2\n",
    "    if L[mid] > L[low]:\n",
    "      low = mid  # go R\n",
    "    else:\n",
    "      high = mid  # go L\n",
    "  return L[low]\n",
    "\n",
    "\n",
    "print(findLargest([2, 4, 5, 7, 8]))\n",
    "print(findLargest([8, 2, 4, 5, 7]))\n",
    "print(findLargest([7, 8, 2, 4, 5]))\n",
    "print(findLargest([5, 7, 8, 2, 4]))\n",
    "print(findLargest([4, 5, 7, 8, 2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 1, 2, 3, 4, 5, 6, 7, 8, 9] 10\n",
      "[9, 10, 1, 2, 3, 4, 5, 6, 7, 8] 10\n",
      "[8, 9, 10, 1, 2, 3, 4, 5, 6, 7] 10\n",
      "[7, 8, 9, 10, 1, 2, 3, 4, 5, 6] 10\n",
      "[6, 7, 8, 9, 10, 1, 2, 3, 4, 5] 10\n",
      "[5, 6, 7, 8, 9, 10, 1, 2, 3, 4] 10\n",
      "[4, 5, 6, 7, 8, 9, 10, 1, 2, 3] 10\n",
      "[3, 4, 5, 6, 7, 8, 9, 10, 1, 2] 10\n",
      "[2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 10\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 10\n"
     ]
    }
   ],
   "source": [
    "# our own code, based on standard BS\n",
    "def findLargest(L):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "\n",
    "    # possibility 1: mid is max\n",
    "    if L[mid-1] < L[mid] > L[mid+1]:  # 5, 7, 8, 2, 4 👉 [7, 8, 2]\n",
    "      return L[mid]\n",
    "\n",
    "    # possibility 2: only two numbers in domain\n",
    "    if high - low == 1:  # 2, 4, 5, 7, 8 👉 [7, 8]\n",
    "      if L[low] > L[high]:\n",
    "        return L[low]\n",
    "      else:\n",
    "        return L[high]\n",
    "\n",
    "    # possibility 3: change dir (chose L/R)\n",
    "    if L[low] < L[mid]:\n",
    "      low = mid+1  # chose R\n",
    "    else:\n",
    "      high = mid-1  # chose L\n",
    "\n",
    "\n",
    "# primary test cases\n",
    "# print(findLargest([2, 4, 5, 7, 8]))\n",
    "# print(findLargest([8, 2, 4, 5, 7]))\n",
    "# print(findLargest([7, 8, 2, 4, 5]))\n",
    "# print(findLargest([5, 7, 8, 2, 4]))\n",
    "# print(findLargest([4, 5, 7, 8, 2]))\n",
    "\n",
    "# possibility 1: mid is max\n",
    "# possibility 2: only two numbers in domain\n",
    "# possibility 3: change dir (chose L/R)\n",
    "\n",
    "# ultimate test code\n",
    "n = 10\n",
    "L = list(range(1, n+1))\n",
    "for i in range(1, n+1):\n",
    "  test = L[n-i:] + L[:n-i]\n",
    "  print(test, findLargest(test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "99967"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = open('./input.txt')\n",
    "txt = f.read()\n",
    "\n",
    "findLargest(list(map(int, [x for x in txt.strip().split(',') if x])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, 3)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def binarySearchIndexAndComparisons(L, v):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  count = 0\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "    count += 1\n",
    "    if L[mid] < v:\n",
    "      low = mid+1\n",
    "    elif L[mid] > v:\n",
    "      high = mid-1\n",
    "    else:  # L[mid] == v:\n",
    "      return (True, count)\n",
    "  return (False, count)\n",
    "\n",
    "\n",
    "binarySearchIndexAndComparisons([2, 6, 8, 11, 17, 23, 33, 44, 46, 50, 65], 11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3]\n"
     ]
    }
   ],
   "source": [
    "# In function, no need to return any list, just sort input list `lst` in place.\n",
    "def sortInRange(lst, r):\n",
    "  lst.sort()\n",
    "\n",
    "\n",
    "lst = [2, 0, 1, 1, 2, 3, 0, 2, 1, 0, 2, 3, 1, 2]\n",
    "sortInRange(lst, 4)\n",
    "print(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans: None\n",
      "original list: [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3]\n"
     ]
    }
   ],
   "source": [
    "# In function, no need to return any list, just sort input list `lst` in place.\n",
    "def sortInRange(lst, r):\n",
    "  count = {}\n",
    "\n",
    "  for num in lst:  # n\n",
    "    if num not in count:\n",
    "      count[num] = 0\n",
    "    count[num] += 1\n",
    "\n",
    "  lst.clear()\n",
    "  for i in range(r):\n",
    "    lst += [i]*count[i]\n",
    "\n",
    "  # not in-place sorting ☠️\n",
    "  # my_list = []\n",
    "  # for i in range(r):\n",
    "    # my_list += [i]*count[i]\n",
    "  # return my_list\n",
    "\n",
    "\n",
    "lst = [2, 0, 1, 1, 2, 3, 0, 2, 1, 0, 2, 3, 1, 2]\n",
    "print(f'ans: {sortInRange(lst, 4)}')\n",
    "print(f'original list: {lst}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# python built-in sort respects order of appearances of EQUAL elem (sort is stable)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(['b87', 'c65', 'd34', 'd12', 'd77', 'g54', 'g1', 'g40', 'g5'],\n",
       " ['b87', 'c65', 'd77', 'd34', 'd12', 'g54', 'g40', 'g5', 'g1'])"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def combinationSort(L):\n",
    "  l1 = sorted(L, key=lambda string: string[0])\n",
    "  l2 = sorted(L, key=lambda string: int(string[1:]), reverse=True)\n",
    "  l2 = sorted(l2, key=lambda string: string[0])\n",
    "  return l1, l2\n",
    "\n",
    "\n",
    "combinationSort(['d34', 'g54', 'd12', 'b87', 'g1', 'c65', 'g40', 'g5', 'd77',])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "8\n",
      "8\n",
      "8\n",
      "8\n",
      "[10, 1, 2, 3, 4, 5, 6, 7, 8, 9] 10\n",
      "[9, 10, 1, 2, 3, 4, 5, 6, 7, 8] 10\n",
      "[8, 9, 10, 1, 2, 3, 4, 5, 6, 7] 10\n",
      "[7, 8, 9, 10, 1, 2, 3, 4, 5, 6] 10\n",
      "[6, 7, 8, 9, 10, 1, 2, 3, 4, 5] 10\n",
      "[5, 6, 7, 8, 9, 10, 1, 2, 3, 4] 10\n",
      "[4, 5, 6, 7, 8, 9, 10, 1, 2, 3] 10\n",
      "[3, 4, 5, 6, 7, 8, 9, 10, 1, 2] 10\n",
      "[2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 10\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 10\n"
     ]
    }
   ],
   "source": [
    "def findLargest(L):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "\n",
    "    # mid is max\n",
    "    if L[mid-1] < L[mid] > L[mid+1]:\n",
    "      return L[mid]\n",
    "\n",
    "    # domain has only 2 elems\n",
    "    if high-low == 1:\n",
    "      if L[low] > L[high]:\n",
    "        return L[low]\n",
    "      else:\n",
    "        return L[high]\n",
    "\n",
    "    # chose L/R\n",
    "    if L[low] < L[mid]:\n",
    "      low = mid+1  # chose R\n",
    "    else:\n",
    "      high = mid-1  # chose L\n",
    "\n",
    "\n",
    "print(findLargest([2, 4, 5, 7, 8]))\n",
    "print(findLargest([8, 2, 4, 5, 7]))\n",
    "print(findLargest([7, 8, 2, 4, 5]))\n",
    "print(findLargest([5, 7, 8, 2, 4]))\n",
    "print(findLargest([4, 5, 7, 8, 2]))\n",
    "\n",
    "# ultimate test code\n",
    "n = 10\n",
    "L = list(range(1, n+1))\n",
    "for i in range(1, n+1):\n",
    "  test = L[n-i:] + L[:n-i]\n",
    "  print(test, findLargest(test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A\n",
    "# B\n",
    "# A, B (both together must be sorted)\n",
    "\n",
    "# swap(1st_index, source, 2nd_index)\n",
    "# A.swap(0, B, 5): A[0] <> B[5]\n",
    "# A.swap(0, A, 3): A[0] <> A[3]\n",
    "\n",
    "# before merge\n",
    "# A: 2 4 6 9 13 15\n",
    "# B: 1 3 5 10\n",
    "\n",
    "# after merge\n",
    "# A: 1 2 3 4 5 6\n",
    "# B: 9 10 13 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# before merge\n",
    "# A: 2 4 6 9 13 15\n",
    "# B: 1 3 5 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6]\n",
      "[9, 10, 13, 15]\n"
     ]
    }
   ],
   "source": [
    "def findMinIndex(lst):  # O(n)\n",
    "  # find index of min elem in lst\n",
    "  lst_min = lst[0]\n",
    "  lst_min_index = 0\n",
    "  for i in range(len(lst)):\n",
    "    if lst[i] < lst_min:\n",
    "      lst_min = lst[i]\n",
    "      lst_min_index = i\n",
    "  return lst_min_index\n",
    "\n",
    "\n",
    "def mergeInPlace(A, B):  # O(n^2)\n",
    "  # sort A list (ensure i-th pos is min of both A,B)\n",
    "  # O(n^2)\n",
    "  for i in range(len(A)):  # O(n)\n",
    "    b_min_index = findMinIndex(B)  # O(n)\n",
    "    if B[b_min_index] < A[i]:\n",
    "      A[i], B[b_min_index] = B[b_min_index], A[i]  # this won't work in IITM submission\n",
    "      # A.swap(i, B, b_min_index) 👈 do this on submission\n",
    "\n",
    "  # fix order in B list (standard bubble sort: why? bcz max value bubbles at right end)\n",
    "  # O(n^2)\n",
    "  for i in range(len(B)):\n",
    "    for j in range(len(B)-i-1):\n",
    "      if B[j] > B[j+1]:\n",
    "        B[j], B[j+1] = B[j+1], B[j]\n",
    "        # B.swap(j, B, j+1)\n",
    "\n",
    "\n",
    "A = [2, 4, 6, 9, 13, 15]\n",
    "B = [1, 3, 5, 10]\n",
    "mergeInPlace(A, B)\n",
    "\n",
    "print(A)\n",
    "print(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def find_min_number(lst):\n",
    "  lst_min = lst[0]\n",
    "  for num in lst:\n",
    "    if num < lst_min:\n",
    "      lst_min = num\n",
    "  return lst_min\n",
    "\n",
    "\n",
    "find_min_number([19, 17, 5, 15, 21, 3, 20])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def find_min_index(lst):\n",
    "  lst_min = lst[0]\n",
    "  lst_min_index = 0\n",
    "  for i in range(len(lst)):\n",
    "    if lst[i] < lst_min:\n",
    "      lst_min = lst[i]\n",
    "      lst_min_index = i\n",
    "  return lst_min_index\n",
    "\n",
    "\n",
    "find_min_index([3, 19, 17, 5, 15, 21, 13, 20])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = [1, 2, 3]\n",
    "l2 = [1, 2, 3]\n",
    "abc = l1\n",
    "\n",
    "l1 == l2  # elem by elem check\n",
    "\n",
    "l1 is l2  # check if both vars are same (by reference)\n",
    "abc is l1  # abc and l1 reference to same data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "97"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('a')\n",
    "chr(97) # NEW 😲"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "hello Vidu\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "  print(i)\n",
    "else:  # this runs after loop finishes\n",
    "  print('hello Vidu')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 'hi']"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1, 0, 0, 2, 'hi', []]\n",
    "list(filter(bool, l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(bool('hi'))\n",
    "print(bool(''))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(bool(0))\n",
    "print(bool(-4))\n",
    "print(bool(1))\n",
    "print(bool(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(bool([]))\n",
    "print(bool([1, 2, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 'hi']"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1, 0, 0, 2, 'hi', '', []]\n",
    "list(filter(bool, l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['cat', 'bat', 'jam']"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_good(word):\n",
    "  return len(word) == 3\n",
    "\n",
    "\n",
    "l = ['cat', 'bat', 'hello', 'jam', 'world']\n",
    "list(filter(is_good, l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '2', '3']"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# str.split(separator) -> list of items\n",
    "'1 2 3'.split(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 17]"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [1, 2, 2, 3, 3, 3, 3, 17]\n",
    "list(set(lst))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 17]\n"
     ]
    }
   ],
   "source": [
    "lst = [1, 2, 2, 3, 3, 3, 3, 17]\n",
    "found = {}\n",
    "\n",
    "for num in lst:\n",
    "  found[num] = True\n",
    "\n",
    "my_list = []\n",
    "for key in found:\n",
    "  my_list.append(key)\n",
    "\n",
    "print(my_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 17]\n",
      "[18, 81, 19, 5]\n",
      "[24, 26]\n"
     ]
    }
   ],
   "source": [
    "lst = [1, 2, 2, 3, 3, 3, 3, 17]\n",
    "found = {}\n",
    "\n",
    "for num in lst:\n",
    "  found[num] = True\n",
    "\n",
    "my_list = []\n",
    "for key in found:\n",
    "  my_list.append(key)\n",
    "\n",
    "print(my_list)\n",
    "\n",
    "\n",
    "lst = [18, 81, 19, 19, 18, 5, 5, 5]\n",
    "found = {}\n",
    "\n",
    "for num in lst:\n",
    "  found[num] = True\n",
    "\n",
    "my_list = []\n",
    "for key in found:\n",
    "  my_list.append(key)\n",
    "\n",
    "print(my_list)\n",
    "\n",
    "\n",
    "lst = [24, 24, 24, 26]\n",
    "found = {}\n",
    "\n",
    "for num in lst:\n",
    "  found[num] = True\n",
    "\n",
    "my_list = []\n",
    "for key in found:\n",
    "  my_list.append(key)\n",
    "\n",
    "print(my_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 17]"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[18, 81, 19, 5]"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[24, 26]"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def remove_duplicates(lst):\n",
    "  found = {}\n",
    "\n",
    "  for num in lst:\n",
    "    found[num] = True\n",
    "\n",
    "  my_list = []\n",
    "  for key in found:\n",
    "    my_list.append(key)\n",
    "  return my_list\n",
    "\n",
    "\n",
    "lst = [1, 2, 2, 3, 3, 3, 3, 17]\n",
    "remove_duplicates(lst)\n",
    "\n",
    "lst = [18, 81, 19, 19, 18, 5, 5, 5]\n",
    "remove_duplicates(lst)\n",
    "\n",
    "lst = [24, 24, 24, 26]\n",
    "remove_duplicates(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hello Vidu, u are so very awesome\\ngood morning\\nu r the best'"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "f = open('./ABC.txt')\n",
    "data = f.read()\n",
    "\n",
    "display(data)  # \\n is newline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total chars are 59\n"
     ]
    }
   ],
   "source": [
    "print(f'total chars are {len(data)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total lines are: 3\n"
     ]
    }
   ],
   "source": [
    "data = data.split('\\n')\n",
    "print(f'total lines are: {len(data)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total words are: 13\n"
     ]
    }
   ],
   "source": [
    "word_count = 0\n",
    "for line in data:\n",
    "  line = line.split(' ')\n",
    "  word_count += len(line)\n",
    "print(f'total words are: {word_count}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):  # limits of iteration\n",
    "  print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "i = 0\n",
    "while i < 5:  # u just know when to stop, u dont the exact range\n",
    "  print(i)\n",
    "  i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "42\n",
      "84\n",
      "126\n",
      "168\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "210"
      ]
     },
     "execution_count": 168,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def lcm(a, b):\n",
    "  a, b = max(a, b), min(a, b)\n",
    "  lcm = a\n",
    "  while lcm % b != 0:\n",
    "    lcm += a\n",
    "  return lcm\n",
    "\n",
    "\n",
    "lcm(10, 42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a, b\n",
    "# 10 42\n",
    "\n",
    "# lcm, b\n",
    "# 42 10\n",
    "# 84 10\n",
    "# 126 10\n",
    "# 168 10\n",
    "# 210 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'H', 'a'}"
      ]
     },
     "execution_count": 185,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str1 = 'Hari'\n",
    "str2 = 'Hale'\n",
    "set(str1) & set(str2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['H', 'a']\n"
     ]
    }
   ],
   "source": [
    "str1 = 'Hari'\n",
    "str2 = 'Hale'\n",
    "\n",
    "found1 = {}\n",
    "found2 = {}\n",
    "\n",
    "for char in str1:\n",
    "  found1[char] = True\n",
    "\n",
    "for char in str2:\n",
    "  found2[char] = True\n",
    "\n",
    "common = []\n",
    "for key in found1:\n",
    "  if key in found2:\n",
    "    common.append(key)\n",
    "\n",
    "print(common)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "879\n"
     ]
    }
   ],
   "source": [
    "data = {\n",
    "    'A': 100,\n",
    "    'B': 540,\n",
    "    'C': 239\n",
    "}\n",
    "\n",
    "total = 0\n",
    "for key in data:\n",
    "  total += data[key]\n",
    "\n",
    "print(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{2, 3, 4}\n"
     ]
    }
   ],
   "source": [
    "lst = [2, 3, 3, 4, 4, 4, 2]\n",
    "\n",
    "print(set(lst))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{3, 4}"
      ]
     },
     "execution_count": 200,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set([1, 2, 3, 4]) & set([3, 4])  # intersection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4, 5, 9, 10}"
      ]
     },
     "execution_count": 201,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set([1, 2, 3, 4]) | set([3, 4, 5, 9, 10])  # union"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[32.0, 68.0, 77.0, 98.6, 212.0]\n"
     ]
    }
   ],
   "source": [
    "def cel_to_fah(cel):\n",
    "  return cel * 9/5 + 32\n",
    "\n",
    "\n",
    "temperatures = [0, 20, 25, 37, 100]\n",
    "converted = [cel_to_fah(cel) for cel in temperatures]\n",
    "print(converted)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[32.0, 68.0, 77.0, 98.6, 212.0]\n"
     ]
    }
   ],
   "source": [
    "# autopep8: off\n",
    "\n",
    "temperatures = [0, 20, 25, 37, 100]\n",
    "cel_to_fah = lambda cel: cel * 9/5 + 32\n",
    "converted = [cel_to_fah(cel) for cel in temperatures]\n",
    "print(converted)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "212.0"
      ]
     },
     "execution_count": 218,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# autopep8: off\n",
    "def cel_to_fah(cel): return cel * 9/5 + 32\n",
    "cel_to_fah(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "212.0"
      ]
     },
     "execution_count": 219,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# autopep8: off\n",
    "cel_to_fah = lambda cel: cel * 9/5 + 32\n",
    "cel_to_fah(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "metadata": {},
   "outputs": [],
   "source": [
    "# lambda param: what to return (must be a single expression)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2024/08/08"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30\n",
      "55\n",
      "100\n"
     ]
    }
   ],
   "source": [
    "# IITM provided sol code ☠️\n",
    "# AT FIRST GLANCE:\n",
    "# This is horrible code and it doesn't even work for a general list when finding peak\n",
    "# This can be used with some imposed restrictions (??) on list\n",
    "\n",
    "# AFTER DEEP OBSERVATION:\n",
    "# This code is valid for specific list inputs ✅\n",
    "# These are the observations that you've to find 👇\n",
    "\n",
    "# peak at corner\n",
    "# (peak) decr series;\n",
    "# eg. (30), 25, 12, 7, 5, 3\n",
    "\n",
    "# peak at corner\n",
    "# incr series (peak);\n",
    "# eg. 12, 16, 24, 29, 45, (55)\n",
    "\n",
    "# peak in middle\n",
    "# incr series (peak); decr series;\n",
    "# eg. 15, 17, 21, 25, 61, (100), 99, 65, 59, 1\n",
    "\n",
    "def findPeakUtil(arr, low, high, n):\n",
    "  mid = low + (high - low)/2\n",
    "  mid = int(mid)\n",
    "  if ((mid == 0 or arr[mid - 1] < arr[mid]) and (mid == n - 1 or arr[mid + 1] < arr[mid])):\n",
    "    return arr[mid]\n",
    "  elif (mid > 0 and arr[mid - 1] > arr[mid]):\n",
    "    return findPeakUtil(arr, low, (mid - 1), n)\n",
    "  else:\n",
    "    return findPeakUtil(arr, (mid + 1), high, n)\n",
    "\n",
    "\n",
    "def Findpeak(L):\n",
    "  n = len(L)\n",
    "  return findPeakUtil(L, 0, n-1, n)\n",
    "\n",
    "\n",
    "# print(Findpeak([5, 20, 4, (6), 11, 15, 17]))  # wrong answer (bcz invalid input 🤷) ☠️\n",
    "# print(Findpeak([15, 30, 9, (10), 17, 21, 28]))  # wrong answer (bcz invalid input 🤷) ☠️\n",
    "# print(Findpeak([30, 7, (9), 11, 24, 29]))  # wrong answer (bcz invalid input 🤷) ☠️\n",
    "\n",
    "print(Findpeak([(30), 25, 12, 7, 5, 3]))  # correct answer ✅\n",
    "print(Findpeak([12, 16, 24, 29, 45, (55)]))  # correct answer ✅\n",
    "print(Findpeak([15, 17, 21, 25, 61, (100), 99, 65, 59, 1]))  # correct answer ✅"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30\n",
      "55\n",
      "100\n"
     ]
    }
   ],
   "source": [
    "def Findpeak(L):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "    # peak at corners\n",
    "    if mid == 0 or mid == len(L)-1:\n",
    "      return L[mid]\n",
    "\n",
    "    # peak at mid (mid-1 < mid > mid+1)\n",
    "    if L[mid-1] < L[mid] > L[mid+1]:\n",
    "      return L[mid]\n",
    "\n",
    "    # chose L/R (chose L if mid-1 > mid, else R)\n",
    "    if L[mid-1] > L[mid]:\n",
    "      high = mid-1\n",
    "    else:\n",
    "      low = mid+1\n",
    "\n",
    "\n",
    "# Findpeak([5, 10, 20, 15])\n",
    "# print(Findpeak([5, 20, 4, (6), 11, 15, 17]))  # wrong answer (bcz invalid input 🤷) ☠️\n",
    "# print(Findpeak([15, 30, 9, (10), 17, 21, 28]))  # wrong answer (bcz invalid input 🤷) ☠️\n",
    "# print(Findpeak([30, 7, (9), 11, 24, 29]))  # wrong answer (bcz invalid input 🤷) ☠️\n",
    "\n",
    "print(Findpeak([(30), 25, 12, 7, 5, 3]))  # correct answer ✅\n",
    "print(Findpeak([12, 16, 24, 29, 45, (55)]))  # correct answer ✅\n",
    "print(Findpeak([15, 17, 21, 25, 61, (100), 99, 65, 59, 1]))  # correct answer ✅"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# These are the observations that you've to find 👇\n",
    "\n",
    "# peak at corner\n",
    "# (peak) decr series;\n",
    "# eg. (30), 25, 12, 7, 5, 3\n",
    "\n",
    "# peak at corner\n",
    "# incr series (peak);\n",
    "# eg. 12, 16, 24, 29, 45, (55)\n",
    "\n",
    "# peak in middle\n",
    "# incr series (peak); decr series;\n",
    "# eg. 15, 17, 21, 25, 61, (100), 99, 65, 59, 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 21, 22, 23, 24]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCommonElements(l1, l2):  # O(N)\n",
    "  return list(set(l1) & set(l2))  # N + &(N) + N\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23, 24, 22, 20, 21]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCommonElements(l1, l2):  # O(N)\n",
    "  found1 = {}\n",
    "  found2 = {}\n",
    "\n",
    "  for num in l1:  # N\n",
    "    found1[num] = True\n",
    "\n",
    "  for num in l2:  # N\n",
    "    found2[num] = True\n",
    "\n",
    "  commons = []\n",
    "  for key in found1:  # N\n",
    "    if key in found2:  # 1\n",
    "      commons.append(key)  # 1\n",
    "\n",
    "  return commons\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23, 24, 22, 20, 21]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCommonElements(l1, l2):  # O(N^2)\n",
    "  commons = []\n",
    "  # O(N^2)\n",
    "  for num1 in l1:  # N\n",
    "    for num2 in l2:  # N (is num1 present in l2?)\n",
    "      if num1 == num2:\n",
    "        commons.append(num1)\n",
    "\n",
    "  return commons\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23, 24, 22, 20, 21]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bs(lst, target):  # check is target is present in lst in O(logN) time\n",
    "  low = 0\n",
    "  high = len(lst)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "    if lst[mid] < target:\n",
    "      low = mid+1\n",
    "    elif lst[mid] > target:\n",
    "      high = mid-1\n",
    "    else:\n",
    "      return True\n",
    "  return False\n",
    "\n",
    "\n",
    "def findCommonElements(l1, l2):  # O(NlogN)\n",
    "  l2 = sorted(l2)  # NlogN\n",
    "  commons = []\n",
    "  # NlogN\n",
    "  for num in l1:  # N\n",
    "    if bs(l2, num):  # logN (is num present in l2?)\n",
    "      commons.append(num)\n",
    "  return commons\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1 (constant)\n",
    "# eg. 1000 > 1\n",
    "\n",
    "# logN (logarithmic)\n",
    "# eg. 1000 > 10\n",
    "\n",
    "# N (linear)\n",
    "# eg. 1000 > 1000\n",
    "\n",
    "# N * logN (linearithmic)\n",
    "# eg. 1000 > 1000 * 10\n",
    "\n",
    "# N^2 (squared, poly family)\n",
    "# eg. 1000 > 1000 * 1000\n",
    "\n",
    "# N^3 (cubic, poly family)\n",
    "# eg. 1000 > 1000 * 1000 * 1000\n",
    "\n",
    "# 2^N (exponential)\n",
    "# eg. 1000 > 2^1000\n",
    "\n",
    "# N! (factorial)\n",
    "# eg. 1000 > 1000! ~ 10^2567"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([44, 69, 98, 103, 103, 150, 151, 194], 7)"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "([1, 2, 3, 5], 3)"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "([0, 1, 2, 3, 5], 5)"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def merge(A, B):\n",
    "  m, n = len(A), len(B)\n",
    "  i, j = 0, 0\n",
    "  result = []\n",
    "\n",
    "  # pair-wise companions\n",
    "  while i < m and j < n:\n",
    "    if A[i] < B[j]:\n",
    "      result.append(A[i])\n",
    "      i += 1\n",
    "    else:\n",
    "      result.append(B[j])\n",
    "      j += 1\n",
    "\n",
    "  # add remaining elems\n",
    "  result += A[i:]\n",
    "  result += B[j:]\n",
    "\n",
    "  return result\n",
    "\n",
    "\n",
    "# print(merge([2, 5, 7, 16], [0, 1]))\n",
    "# print(merge([0, 6], [2, 5, 7, 8]))\n",
    "\n",
    "\n",
    "def merge_sort(L, count):  # 1 person\n",
    "  count += 1\n",
    "\n",
    "  n = len(L)\n",
    "  if n == 1:\n",
    "    return L, count\n",
    "  if n == 2:\n",
    "    return [min(L), max(L)], count\n",
    "\n",
    "  mid = n//2\n",
    "  left = L[:mid]\n",
    "  right = L[mid:]\n",
    "\n",
    "  left, count = merge_sort(left, count)  # 1st subordinate\n",
    "  right, count = merge_sort(right, count)  # 2nd subordinate\n",
    "  merged = merge(left, right)\n",
    "  return merged, count\n",
    "\n",
    "\n",
    "def subordinates(L):\n",
    "  return merge_sort(L, 0)  # just 1 line\n",
    "\n",
    "\n",
    "subordinates([194, 69, 103, 150, 151, 44, 103, 98])\n",
    "subordinates([1, 3, 5, 2])\n",
    "subordinates([3, 1, 2, 0, 5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findPair(L, pairSum):  # O(N^2)\n",
    "  # O(N^2)\n",
    "  for i in range(len(L)-1):  # N\n",
    "    for j in range(i+1, len(L)):  # N\n",
    "      if L[i]+L[j] == pairSum:\n",
    "        return True\n",
    "  return False\n",
    "\n",
    "\n",
    "findPair([10, 4, 11, 5, 1, 8, 7], 22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bs(L, target):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "    if L[mid] < target:\n",
    "      low = mid+1\n",
    "    elif L[mid] > target:\n",
    "      high = mid-1\n",
    "    else:\n",
    "      return True\n",
    "  return False\n",
    "\n",
    "\n",
    "def findPair(L, pairSum):  # O(NlogN)\n",
    "  L.sort()  # NlogN\n",
    "\n",
    "  # NlogN\n",
    "  for num1 in L:  # N\n",
    "    num2 = pairSum-num1\n",
    "    if bs(L, num2):  # logN\n",
    "      return True\n",
    "  return False\n",
    "\n",
    "\n",
    "findPair([10, 4, 11, 5, 1, 8, 7], 13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Findpeak(L):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "\n",
    "    # mid at corner\n",
    "    if mid == 0 or mid == len(L)-1:\n",
    "      return L[mid]\n",
    "\n",
    "    # mid is peak (mid-1 < mid > mid+1)\n",
    "    if L[mid-1] < L[mid] > L[mid+1]:\n",
    "      return L[mid]\n",
    "\n",
    "    # chose L/R (chose L if mid-1 > mid, else R)\n",
    "    if L[mid-1] > L[mid]:\n",
    "      high = mid-1\n",
    "    else:\n",
    "      low = mid+1\n",
    "\n",
    "\n",
    "Findpeak([1, 2, 3, 4, 5, 6, 7, 8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 21, 22, 23, 24]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCommonElements(l1, l2):  # O(N)\n",
    "  return list(set(l1) & set(l2))  # N + &(N) + N\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23, 24, 22, 20, 21]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCommonElements(l1, l2):  # O(N)\n",
    "  found1 = {}\n",
    "  found2 = {}\n",
    "\n",
    "  for num in l1:  # N\n",
    "    found1[num] = True\n",
    "  for num in l2:  # N\n",
    "    found2[num] = True\n",
    "\n",
    "  commons = []\n",
    "  # N\n",
    "  for key in found1:  # N\n",
    "    if key in found2:  # key existence check O(1)\n",
    "      commons.append(key)  # 1\n",
    "  return commons\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23, 24, 22, 20, 21]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findCommonElements(l1, l2):  # O(N^2)\n",
    "  commons = []\n",
    "  # N^2\n",
    "  for num1 in l1:  # N\n",
    "    for num2 in l2:  # N\n",
    "      if num1 == num2:\n",
    "        commons.append(num1)\n",
    "  return commons\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23, 24, 22, 20, 21]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bs(L, target):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "    if L[mid] == target:\n",
    "      return True\n",
    "    if L[mid] < target:\n",
    "      low = mid+1\n",
    "    else:\n",
    "      high = mid-1\n",
    "\n",
    "\n",
    "def findCommonElements(l1, l2):  # O(NlogN)\n",
    "  l2.sort()  # NlogN\n",
    "\n",
    "  commons = []\n",
    "  # NlogN\n",
    "  for num in l1:  # N\n",
    "    if bs(l2, num):  # logN\n",
    "      commons.append(num)\n",
    "  return commons\n",
    "\n",
    "\n",
    "findCommonElements([23, 24, 18, 22, 20, 10, 17, 12, 16, 19, 21, 15, 14, 11, 13],\n",
    "                   [23, 22, 33, 24, 31, 21, 20, 26, 30, 29, 25, 27, 28, 34, 32])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([44, 69, 98, 103, 103, 150, 151, 194], 7)"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def merge(A, B):\n",
    "  m, n = len(A), len(B)\n",
    "  result, i, j = [], 0, 0\n",
    "\n",
    "  # pair-wise comparisons\n",
    "  while i < m and j < n:\n",
    "    if A[i] < B[j]:\n",
    "      result.append(A[i])\n",
    "      i += 1\n",
    "    else:\n",
    "      result.append(B[j])\n",
    "      j += 1\n",
    "\n",
    "  # add remaining elems\n",
    "  result += A[i:]\n",
    "  result += B[j:]\n",
    "  return result\n",
    "\n",
    "\n",
    "# print(merge([0, 6], [1, 3, 4, 5, 8, 9, 10]))\n",
    "# print(merge([1, 3, 4, 5, 8, 9, 10], [0, 6]))\n",
    "\n",
    "\n",
    "def merge_sort(lst, count):\n",
    "  count += 1\n",
    "\n",
    "  n = len(lst)\n",
    "  if n <= 1:\n",
    "    return lst, count\n",
    "  if n == 2:\n",
    "    return [min(lst), max(lst)], count\n",
    "\n",
    "  left = lst[:n//2]\n",
    "  right = lst[n//2:]\n",
    "  left, count = merge_sort(left, count)\n",
    "  right, count = merge_sort(right, count)\n",
    "  merged = merge(left, right)\n",
    "  return merged, count\n",
    "\n",
    "\n",
    "def subordinates(lst):\n",
    "  return merge_sort(lst, 0)\n",
    "\n",
    "\n",
    "subordinates([194, 69, 103, 150, 151, 44, 103, 98])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findPair(L, pairSum):  # O(N^2)\n",
    "  # N^2\n",
    "  for i in range(len(L)):  # N\n",
    "    for j in range(i+1, len(L)):  # N\n",
    "      if L[i]+L[j] == pairSum:\n",
    "        return True\n",
    "  return False\n",
    "\n",
    "\n",
    "findPair([10, 4, 11, 5, 1, 8, 7], 50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bs(L, target):\n",
    "  low = 0\n",
    "  high = len(L)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "    if L[mid] < target:\n",
    "      low = mid+1\n",
    "    elif L[mid] > target:\n",
    "      high = mid-1\n",
    "    else:\n",
    "      return True\n",
    "  return False\n",
    "\n",
    "\n",
    "def findPair(L, pairSum):  # O(NlogN)\n",
    "  L.sort()  # NlogN\n",
    "\n",
    "  # NlogN\n",
    "  for num1 in L:  # N\n",
    "    num2 = pairSum-num1\n",
    "    # if num2 also present: YES\n",
    "    if bs(L, num2):  # logN\n",
    "      return True\n",
    "\n",
    "  return False\n",
    "\n",
    "\n",
    "findPair([10, 4, 11, 5, 1, 8, 7], 16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "# lex order: dict order in strings\n",
    "# numeric order: numeric order in numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(['b87', 'c65', 'd34', 'd12', 'd77', 'g54', 'g1', 'g40', 'g5'],\n",
       " ['b87', 'c65', 'd77', 'd34', 'd12', 'g54', 'g40', 'g5', 'g1'])"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def combinationSort(L):\n",
    "  l1 = sorted(L, key=lambda string: string[0])  # respect order of appearance for eq elems\n",
    "  l2 = sorted(L, key=lambda string: int(string[1:]), reverse=True)\n",
    "  l2 = sorted(l2, key=lambda string: string[0])\n",
    "  return l1, l2\n",
    "\n",
    "\n",
    "combinationSort(['d34', 'g54', 'd12', 'b87', 'g1', 'c65', 'g40', 'g5', 'd77',])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "8\n",
      "8\n",
      "8\n",
      "8\n",
      "[10, 1, 2, 3, 4, 5, 6, 7, 8, 9] 10\n",
      "[9, 10, 1, 2, 3, 4, 5, 6, 7, 8] 10\n",
      "[8, 9, 10, 1, 2, 3, 4, 5, 6, 7] 10\n",
      "[7, 8, 9, 10, 1, 2, 3, 4, 5, 6] 10\n",
      "[6, 7, 8, 9, 10, 1, 2, 3, 4, 5] 10\n",
      "[5, 6, 7, 8, 9, 10, 1, 2, 3, 4] 10\n",
      "[4, 5, 6, 7, 8, 9, 10, 1, 2, 3] 10\n",
      "[3, 4, 5, 6, 7, 8, 9, 10, 1, 2] 10\n",
      "[2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 10\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "99967"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findLargest(lst):  # modified (std) BS\n",
    "  low = 0\n",
    "  high = len(lst)-1\n",
    "  while low <= high:\n",
    "    mid = (low+high)//2\n",
    "\n",
    "    # mid is max\n",
    "    if lst[mid-1] < lst[mid] > lst[mid+1]:\n",
    "      return lst[mid]\n",
    "\n",
    "    # domain has only 2 elems\n",
    "    if high - low == 1:\n",
    "      if lst[low] > lst[high]:\n",
    "        return lst[low]\n",
    "      else:\n",
    "        return lst[high]\n",
    "\n",
    "    # chose L/R\n",
    "    if lst[low] < lst[mid]:\n",
    "      low = mid+1\n",
    "    else:\n",
    "      high = mid-1\n",
    "\n",
    "\n",
    "# primary test cases\n",
    "print(findLargest([2, 4, 5, 7, 8]))\n",
    "print(findLargest([8, 2, 4, 5, 7]))\n",
    "print(findLargest([7, 8, 2, 4, 5]))\n",
    "print(findLargest([5, 7, 8, 2, 4]))\n",
    "print(findLargest([4, 5, 7, 8, 2]))\n",
    "\n",
    "# ultimate test code\n",
    "n = 10\n",
    "L = list(range(1, n+1))\n",
    "for i in range(1, n+1):\n",
    "  test = L[n-i:] + L[:n-i]\n",
    "  print(test, findLargest(test))\n",
    "\n",
    "# god level test\n",
    "f = open('./input.txt')\n",
    "txt = f.read()\n",
    "\n",
    "findLargest(list(map(int, [x for x in txt.strip().split(',') if x])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# swap(index1, source, index2)\n",
    "\n",
    "# A.swap(4, B, 0): A[4] <> B[0]\n",
    "# A.swap(4, A, 0): A[4] <> A[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6]\n",
      "[9, 10, 13, 15]\n",
      "[1, 3]\n",
      "[4, 6, 6, 10]\n"
     ]
    }
   ],
   "source": [
    "def findMinIndex(lst):\n",
    "  lst_min = lst[0]\n",
    "  lst_min_index = 0\n",
    "  for i in range(len(lst)):\n",
    "    if lst[i] < lst_min:\n",
    "      lst_min = lst[i]\n",
    "      lst_min_index = i\n",
    "  return lst_min_index\n",
    "\n",
    "\n",
    "def mergeInPlace(A, B):\n",
    "  # sort A list (ensure i-th of A is min of A,B)\n",
    "  for i in range(len(A)):\n",
    "    b_min_index = findMinIndex(B)\n",
    "    if B[b_min_index] < A[i]:\n",
    "      A[i], B[b_min_index] = B[b_min_index], A[i]\n",
    "      # A.swap(i, B, b_min_index): do this in submissions\n",
    "\n",
    "  # sort B list (bubble sort)\n",
    "  for i in range(len(B)):\n",
    "    for j in range(len(B)-i-1):\n",
    "      if B[j] > B[j+1]:\n",
    "        B[j], B[j+1] = B[j+1], B[j]\n",
    "        # B.swap(j, B, j+1): do this in submissions\n",
    "\n",
    "\n",
    "A = [2, 4, 6, 9, 13, 15]\n",
    "B = [1, 3, 5, 10]\n",
    "mergeInPlace(A, B, )\n",
    "print(A)\n",
    "print(B)\n",
    "\n",
    "A = [4, 6]\n",
    "B = [1, 3, 6, 10]\n",
    "mergeInPlace(A, B, )\n",
    "print(A)\n",
    "print(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [],
   "source": [
    "# not this 😵\n",
    "# 0 0 1\n",
    "# 0 1 2\n",
    "# 0 2 3\n",
    "# 1 1 2\n",
    "# 1 2 3\n",
    "# 2 2 3\n",
    "\n",
    "# we do this in bubble sort ✅\n",
    "# 0 0 1\n",
    "# 0 1 2\n",
    "# 0 2 3\n",
    "# 1 0 1\n",
    "# 1 1 2\n",
    "# 2 0 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[25, 27, 75, 77, 157, 210, 221, 234, 240, 241, 316, 396, 435, 467, 557, 643, 643, 716, 720, 798, 824, 893, 929, 979, 1054, 1067, 1260, 1322, 1391, 1393, 1540, 1580, 1770, 1794, 1824, 1835, 1915, 1983, 1996, 2034, 2036, 2086, 2184, 2311, 2327, 2354, 2367, 2372, 2390, 2401, 2489, 2490, 2500, 2523, 2528, 2582, 2697, 2732, 2763, 2779, 2838, 2976, 2985, 2990, 3007, 3098, 3115, 3163, 3191, 3269, 3306, 3439, 3502, 3505, 3536, 3573, 3590, 3645, 3702, 3705, 3861, 3913, 4144, 4238, 4244, 4363, 4407, 4667, 4689, 4767, 4854, 4894, 4985, 5000, 5001, 5068, 5119, 5309, 5339, 5398, 5496, 5533, 5562, 5575, 5589, 5661, 5704, 5786, 5829, 5924, 5957, 6015, 6103, 6133, 6214, 6226, 6244, 6258, 6276, 6306, 6318, 6327, 6363, 6388, 6406, 6436, 6454, 6572, 6735, 6881, 6952, 6966, 6971, 7041, 7070, 7093, 7248, 7275, 7283, 7307, 7308, 7330, 7352, 7365, 7390, 7436, 7516, 7531, 7585, 7600, 7626, 7660, 7731, 7742, 7758, 7791, 7848, 7871, 7872, 7898, 7932, 7972, 8017, 8033, 8089, 8127, 8280, 8324, 8390, 8425, 8471, 8485, 8553, 8636, 8713, 8781, 8931, 8990, 8999, 9024, 9087, 9107, 9107, 9188, 9213, 9218, 9228, 9285, 9372, 9456, 9556, 9568, 9574, 9574, 9678, 9816, 9848, 9954, 9968, 9985]\n",
      "[45, 53, 71, 79, 98, 112, 119, 131, 164, 173, 184, 210, 245, 286, 359, 391, 398, 418, 446, 449, 460, 462, 467, 472, 499, 509, 511, 525, 527, 547, 570, 575, 579, 634, 641, 655, 661, 679, 692, 715, 719, 757, 771, 806, 808, 854, 873, 919, 922, 961, 1051, 1052, 1060, 1121, 1165, 1187, 1221, 1245, 1251, 1252, 1287, 1343, 1362, 1363, 1384, 1460, 1471, 1533, 1555, 1587, 1594, 1608, 1612, 1638, 1730, 1730, 1766, 1766, 1767, 1774, 1843, 1865, 1872, 1874, 1925, 1982, 2010, 2113, 2114, 2121, 2132, 2148, 2175, 2191, 2228, 2274, 2279, 2280, 2326, 2337, 2443, 2455, 2464, 2467, 2494, 2502, 2567, 2570, 2584, 2586, 2587, 2595, 2597, 2617, 2659, 2689, 2712, 2722, 2724, 2725, 2733, 2751, 2752, 2757, 2813, 2878, 2914, 2940, 2943, 2946, 2955, 2965, 2987, 2998, 3050, 3068, 3108, 3129, 3154, 3171, 3225, 3274, 3281, 3298, 3309, 3318, 3329, 3335, 3351, 3354, 3357, 3405, 3413, 3440, 3486, 3490, 3495, 3505, 3518, 3521, 3541, 3543, 3548, 3560, 3588, 3605, 3612, 3614, 3655, 3683, 3689, 3709, 3734, 3745, 3770, 3778, 3783, 3787, 3788, 3811, 3825, 3828, 3838, 3850, 3858, 3863, 3871, 3884, 3887, 3896, 3907, 3920, 3969, 3995, 4030, 4037, 4077, 4089, 4115, 4139, 4159, 4169, 4178, 4204, 4220, 4253, 4258, 4267, 4279, 4280, 4290, 4343, 4373, 4385, 4403, 4414, 4433, 4446, 4466, 4480, 4493, 4521, 4533, 4538, 4563, 4588, 4622, 4641, 4645, 4656, 4715, 4726, 4749, 4783, 4797, 4799, 4866, 4877, 4881, 4911, 4916, 4961, 4970, 4990, 5005, 5019, 5030, 5039, 5045, 5054, 5076, 5077, 5093, 5102, 5119, 5131, 5135, 5154, 5166, 5178, 5179, 5204, 5252, 5259, 5276, 5316, 5326, 5345, 5374, 5375, 5397, 5406, 5410, 5416, 5418, 5433, 5442, 5492, 5500, 5531, 5565, 5568, 5571, 5714, 5719, 5757, 5768, 5813, 5822, 5832, 5839, 5865, 5877, 5905, 5925, 5926, 5958, 5967, 5968, 5988, 6008, 6027, 6029, 6033, 6055, 6077, 6086, 6087, 6088, 6111, 6128, 6133, 6146, 6159, 6199, 6218, 6237, 6260, 6316, 6354, 6377, 6420, 6420, 6457, 6468, 6473, 6550, 6553, 6564, 6570, 6573, 6590, 6645, 6645, 6682, 6694, 6697, 6698, 6728, 6747, 6751, 6760, 6762, 6765, 6778, 6779, 6788, 6794, 6818, 6821, 6824, 6844, 6844, 6892, 6906, 6938, 6968, 7029, 7040, 7041, 7063, 7095, 7101, 7102, 7119, 7142, 7200, 7222, 7225, 7231, 7233, 7243, 7253, 7254, 7297, 7303, 7315, 7317, 7328, 7365, 7372, 7389, 7391, 7410, 7439, 7445, 7458, 7464, 7476, 7540, 7571, 7585, 7628, 7628, 7631, 7642, 7643, 7711, 7728, 7734, 7749, 7750, 7755, 7759, 7768, 7826, 7836, 7881, 7902, 7950, 7997, 8000, 8004, 8026, 8037, 8042, 8077, 8096, 8116, 8127, 8135, 8148, 8170, 8189, 8191, 8223, 8223, 8236, 8258, 8278, 8285, 8296, 8315, 8319, 8322, 8331, 8358, 8373, 8404, 8423, 8435, 8466, 8489, 8490, 8494, 8531, 8543, 8548, 8585, 8613, 8639, 8698, 8703, 8706, 8708, 8735, 8740, 8743, 8754, 8756]\n"
     ]
    }
   ],
   "source": [
    "f = open('./w2-grpa3-in.txt')\n",
    "data = f.read().strip().split('\\n')\n",
    "in_A = list(map(int, data[0].split()))\n",
    "in_B = list(map(int, data[1].split()))\n",
    "print(in_A)\n",
    "print(in_B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[25, 27, 45, 53, 71, 75, 77, 79, 98, 112, 119, 131, 157, 164, 173, 184, 210, 210, 221, 234, 240, 241, 245, 286, 316, 359, 391, 396, 398, 418, 435, 446, 449, 460, 462, 467, 467, 472, 499, 509, 511, 525, 527, 547, 557, 570, 575, 579, 634, 641, 643, 643, 655, 661, 679, 692, 715, 716, 719, 720, 757, 771, 798, 806, 808, 824, 854, 873, 893, 919, 922, 929, 961, 979, 1051, 1052, 1054, 1060, 1067, 1121, 1165, 1187, 1221, 1245, 1251, 1252, 1260, 1287, 1322, 1343, 1362, 1363, 1384, 1391, 1393, 1460, 1471, 1533, 1540, 1555, 1580, 1587, 1594, 1608, 1612, 1638, 1730, 1730, 1766, 1766, 1767, 1770, 1774, 1794, 1824, 1835, 1843, 1865, 1872, 1874, 1915, 1925, 1982, 1983, 1996, 2010, 2034, 2036, 2086, 2113, 2114, 2121, 2132, 2148, 2175, 2184, 2191, 2228, 2274, 2279, 2280, 2311, 2326, 2327, 2337, 2354, 2367, 2372, 2390, 2401, 2443, 2455, 2464, 2467, 2489, 2490, 2494, 2500, 2502, 2523, 2528, 2567, 2570, 2582, 2584, 2586, 2587, 2595, 2597, 2617, 2659, 2689, 2697, 2712, 2722, 2724, 2725, 2732, 2733, 2751, 2752, 2757, 2763, 2779, 2813, 2838, 2878, 2914, 2940, 2943, 2946, 2955, 2965, 2976, 2985, 2987, 2990, 2998, 3007, 3050]\n",
      "[3068, 3098, 3108, 3115, 3129, 3154, 3163, 3171, 3191, 3225, 3269, 3274, 3281, 3298, 3306, 3309, 3318, 3329, 3335, 3351, 3354, 3357, 3405, 3413, 3439, 3440, 3486, 3490, 3495, 3502, 3505, 3505, 3518, 3521, 3536, 3541, 3543, 3548, 3560, 3573, 3588, 3590, 3605, 3612, 3614, 3645, 3655, 3683, 3689, 3702, 3705, 3709, 3734, 3745, 3770, 3778, 3783, 3787, 3788, 3811, 3825, 3828, 3838, 3850, 3858, 3861, 3863, 3871, 3884, 3887, 3896, 3907, 3913, 3920, 3969, 3995, 4030, 4037, 4077, 4089, 4115, 4139, 4144, 4159, 4169, 4178, 4204, 4220, 4238, 4244, 4253, 4258, 4267, 4279, 4280, 4290, 4343, 4363, 4373, 4385, 4403, 4407, 4414, 4433, 4446, 4466, 4480, 4493, 4521, 4533, 4538, 4563, 4588, 4622, 4641, 4645, 4656, 4667, 4689, 4715, 4726, 4749, 4767, 4783, 4797, 4799, 4854, 4866, 4877, 4881, 4894, 4911, 4916, 4961, 4970, 4985, 4990, 5000, 5001, 5005, 5019, 5030, 5039, 5045, 5054, 5068, 5076, 5077, 5093, 5102, 5119, 5119, 5131, 5135, 5154, 5166, 5178, 5179, 5204, 5252, 5259, 5276, 5309, 5316, 5326, 5339, 5345, 5374, 5375, 5397, 5398, 5406, 5410, 5416, 5418, 5433, 5442, 5492, 5496, 5500, 5531, 5533, 5562, 5565, 5568, 5571, 5575, 5589, 5661, 5704, 5714, 5719, 5757, 5768, 5786, 5813, 5822, 5829, 5832, 5839, 5865, 5877, 5905, 5924, 5925, 5926, 5957, 5958, 5967, 5968, 5988, 6008, 6015, 6027, 6029, 6033, 6055, 6077, 6086, 6087, 6088, 6103, 6111, 6128, 6133, 6133, 6146, 6159, 6199, 6214, 6218, 6226, 6237, 6244, 6258, 6260, 6276, 6306, 6316, 6318, 6327, 6354, 6363, 6377, 6388, 6406, 6420, 6420, 6436, 6454, 6457, 6468, 6473, 6550, 6553, 6564, 6570, 6572, 6573, 6590, 6645, 6645, 6682, 6694, 6697, 6698, 6728, 6735, 6747, 6751, 6760, 6762, 6765, 6778, 6779, 6788, 6794, 6818, 6821, 6824, 6844, 6844, 6881, 6892, 6906, 6938, 6952, 6966, 6968, 6971, 7029, 7040, 7041, 7041, 7063, 7070, 7093, 7095, 7101, 7102, 7119, 7142, 7200, 7222, 7225, 7231, 7233, 7243, 7248, 7253, 7254, 7275, 7283, 7297, 7303, 7307, 7308, 7315, 7317, 7328, 7330, 7352, 7365, 7365, 7372, 7389, 7390, 7391, 7410, 7436, 7439, 7445, 7458, 7464, 7476, 7516, 7531, 7540, 7571, 7585, 7585, 7600, 7626, 7628, 7628, 7631, 7642, 7643, 7660, 7711, 7728, 7731, 7734, 7742, 7749, 7750, 7755, 7758, 7759, 7768, 7791, 7826, 7836, 7848, 7871, 7872, 7881, 7898, 7902, 7932, 7950, 7972, 7997, 8000, 8004, 8017, 8026, 8033, 8037, 8042, 8077, 8089, 8096, 8116, 8127, 8127, 8135, 8148, 8170, 8189, 8191, 8223, 8223, 8236, 8258, 8278, 8280, 8285, 8296, 8315, 8319, 8322, 8324, 8331, 8358, 8373, 8390, 8404, 8423, 8425, 8435, 8466, 8471, 8485, 8489, 8490, 8494, 8531, 8543, 8548, 8553, 8585, 8613, 8636, 8639, 8698, 8703, 8706, 8708, 8713, 8735, 8740, 8743, 8754, 8756, 8781, 8931, 8990, 8999, 9024, 9087, 9107, 9107, 9188, 9213, 9218, 9228, 9285, 9372, 9456, 9556, 9568, 9574, 9574, 9678, 9816, 9848, 9954, 9968, 9985]\n"
     ]
    }
   ],
   "source": [
    "f = open('./w2-grpa3-out.txt')\n",
    "data = f.read().strip().split('\\n')\n",
    "out_A = list(map(int, data[0].split()))\n",
    "out_B = list(map(int, data[1].split()))\n",
    "print(out_A)\n",
    "print(out_B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 171,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 171,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mergeInPlace(in_A, in_B)\n",
    "in_A == out_A\n",
    "in_B == out_B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[25, 27, 45, 53, 71, 75, 77, 79, 98, 112, 119, 131, 157, 164, 173, 184, 210, 210, 221, 234, 240, 241, 245, 286, 316, 359, 391, 396, 398, 418, 435, 446, 449, 460, 462, 467, 467, 472, 499, 509, 511, 525, 527, 547, 557, 570, 575, 579, 634, 641, 643, 643, 655, 661, 679, 692, 715, 716, 719, 720, 757, 771, 798, 806, 808, 824, 854, 873, 893, 919, 922, 929, 961, 979, 1051, 1052, 1054, 1060, 1067, 1121, 1165, 1187, 1221, 1245, 1251, 1252, 1260, 1287, 1322, 1343, 1362, 1363, 1384, 1391, 1393, 1460, 1471, 1533, 1540, 1555, 1580, 1587, 1594, 1608, 1612, 1638, 1730, 1730, 1766, 1766, 1767, 1770, 1774, 1794, 1824, 1835, 1843, 1865, 1872, 1874, 1915, 1925, 1982, 1983, 1996, 2010, 2034, 2036, 2086, 2113, 2114, 2121, 2132, 2148, 2175, 2184, 2191, 2228, 2274, 2279, 2280, 2311, 2326, 2327, 2337, 2354, 2367, 2372, 2390, 2401, 2443, 2455, 2464, 2467, 2489, 2490, 2494, 2500, 2502, 2523, 2528, 2567, 2570, 2582, 2584, 2586, 2587, 2595, 2597, 2617, 2659, 2689, 2697, 2712, 2722, 2724, 2725, 2732, 2733, 2751, 2752, 2757, 2763, 2779, 2813, 2838, 2878, 2914, 2940, 2943, 2946, 2955, 2965, 2976, 2985, 2987, 2990, 2998, 3007, 3050]\n",
      "[25, 27, 45, 53, 71, 75, 77, 79, 98, 112, 119, 131, 157, 164, 173, 184, 210, 210, 221, 234, 240, 241, 245, 286, 316, 359, 391, 396, 398, 418, 435, 446, 449, 460, 462, 467, 467, 472, 499, 509, 511, 525, 527, 547, 557, 570, 575, 579, 634, 641, 643, 643, 655, 661, 679, 692, 715, 716, 719, 720, 757, 771, 798, 806, 808, 824, 854, 873, 893, 919, 922, 929, 961, 979, 1051, 1052, 1054, 1060, 1067, 1121, 1165, 1187, 1221, 1245, 1251, 1252, 1260, 1287, 1322, 1343, 1362, 1363, 1384, 1391, 1393, 1460, 1471, 1533, 1540, 1555, 1580, 1587, 1594, 1608, 1612, 1638, 1730, 1730, 1766, 1766, 1767, 1770, 1774, 1794, 1824, 1835, 1843, 1865, 1872, 1874, 1915, 1925, 1982, 1983, 1996, 2010, 2034, 2036, 2086, 2113, 2114, 2121, 2132, 2148, 2175, 2184, 2191, 2228, 2274, 2279, 2280, 2311, 2326, 2327, 2337, 2354, 2367, 2372, 2390, 2401, 2443, 2455, 2464, 2467, 2489, 2490, 2494, 2500, 2502, 2523, 2528, 2567, 2570, 2582, 2584, 2586, 2587, 2595, 2597, 2617, 2659, 2689, 2697, 2712, 2722, 2724, 2725, 2732, 2733, 2751, 2752, 2757, 2763, 2779, 2813, 2838, 2878, 2914, 2940, 2943, 2946, 2955, 2965, 2976, 2985, 2987, 2990, 2998, 3007, 3050]\n"
     ]
    }
   ],
   "source": [
    "print(in_A)\n",
    "print(out_A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3068, 3098, 3108, 3115, 3129, 3154, 3163, 3171, 3191, 3225, 3269, 3274, 3281, 3298, 3306, 3309, 3318, 3329, 3335, 3351, 3354, 3357, 3405, 3413, 3439, 3440, 3486, 3490, 3495, 3502, 3505, 3505, 3518, 3521, 3536, 3541, 3543, 3548, 3560, 3573, 3588, 3590, 3605, 3612, 3614, 3645, 3655, 3683, 3689, 3702, 3705, 3709, 3734, 3745, 3770, 3778, 3783, 3787, 3788, 3811, 3825, 3828, 3838, 3850, 3858, 3861, 3863, 3871, 3884, 3887, 3896, 3907, 3913, 3920, 3969, 3995, 4030, 4037, 4077, 4089, 4115, 4139, 4144, 4159, 4169, 4178, 4204, 4220, 4238, 4244, 4253, 4258, 4267, 4279, 4280, 4290, 4343, 4363, 4373, 4385, 4403, 4407, 4414, 4433, 4446, 4466, 4480, 4493, 4521, 4533, 4538, 4563, 4588, 4622, 4641, 4645, 4656, 4667, 4689, 4715, 4726, 4749, 4767, 4783, 4797, 4799, 4854, 4866, 4877, 4881, 4894, 4911, 4916, 4961, 4970, 4985, 4990, 5000, 5001, 5005, 5019, 5030, 5039, 5045, 5054, 5068, 5076, 5077, 5093, 5102, 5119, 5119, 5131, 5135, 5154, 5166, 5178, 5179, 5204, 5252, 5259, 5276, 5309, 5316, 5326, 5339, 5345, 5374, 5375, 5397, 5398, 5406, 5410, 5416, 5418, 5433, 5442, 5492, 5496, 5500, 5531, 5533, 5562, 5565, 5568, 5571, 5575, 5589, 5661, 5704, 5714, 5719, 5757, 5768, 5786, 5813, 5822, 5829, 5832, 5839, 5865, 5877, 5905, 5924, 5925, 5926, 5957, 5958, 5967, 5968, 5988, 6008, 6015, 6027, 6029, 6033, 6055, 6077, 6086, 6087, 6088, 6103, 6111, 6128, 6133, 6133, 6146, 6159, 6199, 6214, 6218, 6226, 6237, 6244, 6258, 6260, 6276, 6306, 6316, 6318, 6327, 6354, 6363, 6377, 6388, 6406, 6420, 6420, 6436, 6454, 6457, 6468, 6473, 6550, 6553, 6564, 6570, 6572, 6573, 6590, 6645, 6645, 6682, 6694, 6697, 6698, 6728, 6735, 6747, 6751, 6760, 6762, 6765, 6778, 6779, 6788, 6794, 6818, 6821, 6824, 6844, 6844, 6881, 6892, 6906, 6938, 6952, 6966, 6968, 6971, 7029, 7040, 7041, 7041, 7063, 7070, 7093, 7095, 7101, 7102, 7119, 7142, 7200, 7222, 7225, 7231, 7233, 7243, 7248, 7253, 7254, 7275, 7283, 7297, 7303, 7307, 7308, 7315, 7317, 7328, 7330, 7352, 7365, 7365, 7372, 7389, 7390, 7391, 7410, 7436, 7439, 7445, 7458, 7464, 7476, 7516, 7531, 7540, 7571, 7585, 7585, 7600, 7626, 7628, 7628, 7631, 7642, 7643, 7660, 7711, 7728, 7731, 7734, 7742, 7749, 7750, 7755, 7758, 7759, 7768, 7791, 7826, 7836, 7848, 7871, 7872, 7881, 7898, 7902, 7932, 7950, 7972, 7997, 8000, 8004, 8017, 8026, 8033, 8037, 8042, 8077, 8089, 8096, 8116, 8127, 8127, 8135, 8148, 8170, 8189, 8191, 8223, 8223, 8236, 8258, 8278, 8280, 8285, 8296, 8315, 8319, 8322, 8324, 8331, 8358, 8373, 8390, 8404, 8423, 8425, 8435, 8466, 8471, 8485, 8489, 8490, 8494, 8531, 8543, 8548, 8553, 8585, 8613, 8636, 8639, 8698, 8703, 8706, 8708, 8713, 8735, 8740, 8743, 8754, 8756, 8781, 8931, 8990, 8999, 9024, 9087, 9107, 9107, 9188, 9213, 9218, 9228, 9285, 9372, 9456, 9556, 9568, 9574, 9574, 9678, 9816, 9848, 9954, 9968, 9985]\n",
      "[3068, 3098, 3108, 3115, 3129, 3154, 3163, 3171, 3191, 3225, 3269, 3274, 3281, 3298, 3306, 3309, 3318, 3329, 3335, 3351, 3354, 3357, 3405, 3413, 3439, 3440, 3486, 3490, 3495, 3502, 3505, 3505, 3518, 3521, 3536, 3541, 3543, 3548, 3560, 3573, 3588, 3590, 3605, 3612, 3614, 3645, 3655, 3683, 3689, 3702, 3705, 3709, 3734, 3745, 3770, 3778, 3783, 3787, 3788, 3811, 3825, 3828, 3838, 3850, 3858, 3861, 3863, 3871, 3884, 3887, 3896, 3907, 3913, 3920, 3969, 3995, 4030, 4037, 4077, 4089, 4115, 4139, 4144, 4159, 4169, 4178, 4204, 4220, 4238, 4244, 4253, 4258, 4267, 4279, 4280, 4290, 4343, 4363, 4373, 4385, 4403, 4407, 4414, 4433, 4446, 4466, 4480, 4493, 4521, 4533, 4538, 4563, 4588, 4622, 4641, 4645, 4656, 4667, 4689, 4715, 4726, 4749, 4767, 4783, 4797, 4799, 4854, 4866, 4877, 4881, 4894, 4911, 4916, 4961, 4970, 4985, 4990, 5000, 5001, 5005, 5019, 5030, 5039, 5045, 5054, 5068, 5076, 5077, 5093, 5102, 5119, 5119, 5131, 5135, 5154, 5166, 5178, 5179, 5204, 5252, 5259, 5276, 5309, 5316, 5326, 5339, 5345, 5374, 5375, 5397, 5398, 5406, 5410, 5416, 5418, 5433, 5442, 5492, 5496, 5500, 5531, 5533, 5562, 5565, 5568, 5571, 5575, 5589, 5661, 5704, 5714, 5719, 5757, 5768, 5786, 5813, 5822, 5829, 5832, 5839, 5865, 5877, 5905, 5924, 5925, 5926, 5957, 5958, 5967, 5968, 5988, 6008, 6015, 6027, 6029, 6033, 6055, 6077, 6086, 6087, 6088, 6103, 6111, 6128, 6133, 6133, 6146, 6159, 6199, 6214, 6218, 6226, 6237, 6244, 6258, 6260, 6276, 6306, 6316, 6318, 6327, 6354, 6363, 6377, 6388, 6406, 6420, 6420, 6436, 6454, 6457, 6468, 6473, 6550, 6553, 6564, 6570, 6572, 6573, 6590, 6645, 6645, 6682, 6694, 6697, 6698, 6728, 6735, 6747, 6751, 6760, 6762, 6765, 6778, 6779, 6788, 6794, 6818, 6821, 6824, 6844, 6844, 6881, 6892, 6906, 6938, 6952, 6966, 6968, 6971, 7029, 7040, 7041, 7041, 7063, 7070, 7093, 7095, 7101, 7102, 7119, 7142, 7200, 7222, 7225, 7231, 7233, 7243, 7248, 7253, 7254, 7275, 7283, 7297, 7303, 7307, 7308, 7315, 7317, 7328, 7330, 7352, 7365, 7365, 7372, 7389, 7390, 7391, 7410, 7436, 7439, 7445, 7458, 7464, 7476, 7516, 7531, 7540, 7571, 7585, 7585, 7600, 7626, 7628, 7628, 7631, 7642, 7643, 7660, 7711, 7728, 7731, 7734, 7742, 7749, 7750, 7755, 7758, 7759, 7768, 7791, 7826, 7836, 7848, 7871, 7872, 7881, 7898, 7902, 7932, 7950, 7972, 7997, 8000, 8004, 8017, 8026, 8033, 8037, 8042, 8077, 8089, 8096, 8116, 8127, 8127, 8135, 8148, 8170, 8189, 8191, 8223, 8223, 8236, 8258, 8278, 8280, 8285, 8296, 8315, 8319, 8322, 8324, 8331, 8358, 8373, 8390, 8404, 8423, 8425, 8435, 8466, 8471, 8485, 8489, 8490, 8494, 8531, 8543, 8548, 8553, 8585, 8613, 8636, 8639, 8698, 8703, 8706, 8708, 8713, 8735, 8740, 8743, 8754, 8756, 8781, 8931, 8990, 8999, 9024, 9087, 9107, 9107, 9188, 9213, 9218, 9228, 9285, 9372, 9456, 9556, 9568, 9574, 9574, 9678, 9816, 9848, 9954, 9968, 9985]\n"
     ]
    }
   ],
   "source": [
    "print(in_B)\n",
    "print(out_B)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}