Python_The_early_days_of_learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python: The early days of Learning\n",
    "\n",
    "The codes included here comes from various problems that I solved when learning Python for the first time. Just like the codes in [\"Beginning Python\"](https://github.com/muktoakash/Python_Practice/blob/master/Beginning_Python.ipynb), these programs and functions are fairly straight-forward, and are uploaded here for my reference. Once again, there may be a bit of conflicting styles in the way the code is commented."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Membership Check\n",
    "\n",
    "Your local university's Raptors fan club maintains a register of its active members on a .txt document. Every month they update the file by removing the members who are not active. You have been tasked with automating this with your python skills. <br>\n",
    "Given the file currentMem, Remove each member with a 'no' in their inactive coloumn. Keep track of each of the removed members and append them to the exMem file. Make sure the format of the original files in preserved. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "## My solution to the problem.\n",
    "import os\n",
    "\n",
    "def cleanFiles(currentMem,exMem):\n",
    "    '''\n",
    "    currentMem: File containing list of current members\n",
    "    exMem: File containing list of old members\n",
    "    \n",
    "    Removes all rows from currentMem containing 'no' and appends them to exMem\n",
    "    '''\n",
    "    \n",
    "    with open(currentMem, 'r') as cMem:\n",
    "        with open(exMem, 'a+') as xMem:\n",
    "            with open('temp.txt', 'w') as temp: #Use temp.txt to copy active members\n",
    "                cMem.seek(0,0) #get to the beginning of currentMem\n",
    "                cpyline = cMem.readline() #the first line is just headings\n",
    "                temp.write(cpyline)\n",
    "                \n",
    "                cpyline = cMem.readline() #membership info starts here\n",
    "                while cpyline:\n",
    "                    lineVec = cpyline.split(' ')\n",
    "                    if 'no' in lineVec: #not active member\n",
    "                        xMem.write(cpyline)\n",
    "                    else:\n",
    "                        temp.write(cpyline)\n",
    "                    cpyline = cMem.readline()\n",
    "    \n",
    "    # Now transfer all active members back to currentMem\n",
    "    with open('temp.txt', 'r') as temp:\n",
    "        with open(currentMem, 'w') as cMem:\n",
    "            for line in temp:\n",
    "                cMem.write(line)\n",
    "    \n",
    "    os.remove(\"temp.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test Passed\n"
     ]
    }
   ],
   "source": [
    "## Test for the above code, this part of the code was provided to me, so I don't take any credit:\n",
    "from random import randint as rnd\n",
    "\n",
    "memReg = 'members.txt'\n",
    "exReg = 'inactive.txt'\n",
    "fee =('yes','no')\n",
    "\n",
    "def genFiles(current,old):\n",
    "    with open(current,'w+') as writefile: \n",
    "        writefile.write('Membership No  Date Joined  Active  \\n')\n",
    "        data = \"{:^13}  {:<11}  {:<6}\\n\"\n",
    "\n",
    "        for rowno in range(20):\n",
    "            date = str(rnd(2015,2020))+ '-' + str(rnd(1,12))+'-'+str(rnd(1,25))\n",
    "            writefile.write(data.format(rnd(10000,99999),date,fee[rnd(0,1)]))\n",
    "\n",
    "\n",
    "    with open(old,'w+') as writefile: \n",
    "        writefile.write('Membership No  Date Joined  Active  \\n')\n",
    "        data = \"{:^13}  {:<11}  {:<6}\\n\"\n",
    "        for rowno in range(3):\n",
    "            date = str(rnd(2015,2020))+ '-' + str(rnd(1,12))+'-'+str(rnd(1,25))\n",
    "            writefile.write(data.format(rnd(10000,99999),date,fee[1]))\n",
    "\n",
    "\n",
    "genFiles(memReg,exReg)\n",
    "\n",
    "def testMsg(passed):\n",
    "    if passed:\n",
    "       return 'Test Passed'\n",
    "    else :\n",
    "       return 'Test Failed'\n",
    "\n",
    "testWrite = \"testWrite.txt\"\n",
    "testAppend = \"testAppend.txt\" \n",
    "passed = True\n",
    "\n",
    "genFiles(testWrite,testAppend)\n",
    "\n",
    "with open(testWrite,'r') as file:\n",
    "    ogWrite = file.readlines()\n",
    "\n",
    "with open(testAppend,'r') as file:\n",
    "    ogAppend = file.readlines()\n",
    "\n",
    "try:\n",
    "    cleanFiles(testWrite,testAppend)\n",
    "except:\n",
    "    print('Error')\n",
    "\n",
    "with open(testWrite,'r') as file:\n",
    "    clWrite = file.readlines()\n",
    "\n",
    "with open(testAppend,'r') as file:\n",
    "    clAppend = file.readlines()\n",
    "        \n",
    "# checking if total no of rows is same, including headers\n",
    "\n",
    "if (len(ogWrite) + len(ogAppend) != len(clWrite) + len(clAppend)):\n",
    "    print(\"The number of rows do not add up. Make sure your final files have the same header and format.\")\n",
    "    passed = False\n",
    "    \n",
    "for line in clWrite:\n",
    "    if  'no' in line:\n",
    "        passed = False\n",
    "        print(\"Inactive members in file\")\n",
    "        break\n",
    "    else:\n",
    "        if line not in ogWrite:\n",
    "            print(\"Data in file does not match original file\")\n",
    "            passed = False\n",
    "print (\"{}\".format(testMsg(passed)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Active Members: \n",
      "\n",
      "\n",
      "Membership No  Date Joined  Active  \n",
      "    36275      2017-4-25    yes   \n",
      "    55976      2018-1-24    yes   \n",
      "    25852      2020-11-23   yes   \n",
      "    51081      2016-7-2     yes   \n",
      "    48329      2015-12-21   yes   \n",
      "    35948      2018-4-9     yes   \n",
      "    70911      2017-9-17    yes   \n",
      "    24605      2019-9-10    yes   \n",
      "\n",
      "Inactive Members: \n",
      "\n",
      "\n",
      "Membership No  Date Joined  Active  \n",
      "    49580      2016-9-22    no    \n",
      "    50584      2020-4-13    no    \n",
      "    30828      2016-3-5     no    \n",
      "    93209      2017-8-20    no    \n",
      "    55770      2018-2-18    no    \n",
      "    53562      2020-9-1     no    \n",
      "    92404      2018-3-2     no    \n",
      "    62500      2019-8-5     no    \n",
      "    64344      2016-12-10   no    \n",
      "    96178      2018-6-1     no    \n",
      "    83090      2015-5-2     no    \n",
      "    77414      2016-5-3     no    \n",
      "    61415      2018-2-11    no    \n",
      "    70502      2019-11-10   no    \n",
      "    41073      2017-12-14   no    \n",
      "\n"
     ]
    }
   ],
   "source": [
    "## Alternate solution that was provided to me, again, I take no credit\n",
    "def cleanFiles(currentMem,exMem):\n",
    "    with open(currentMem,'r+') as writeFile: \n",
    "        with open(exMem,'a+') as appendFile:\n",
    "            #get the data\n",
    "            writeFile.seek(0)\n",
    "            members = writeFile.readlines()\n",
    "            #remove header\n",
    "            header = members[0]\n",
    "            members.pop(0)\n",
    "\n",
    "            inactive = [member for member in members if ('no' in member)]\n",
    "            '''\n",
    "            The above is the same as \n",
    "\n",
    "            for member in active:\n",
    "            if 'no' in member:\n",
    "                inactive.append(member)\n",
    "            '''\n",
    "            #go to the beginning of the write file\n",
    "            writeFile.seek(0) \n",
    "            writeFile.write(header)\n",
    "            for member in members:\n",
    "                if (member in inactive):\n",
    "                    appendFile.write(member)\n",
    "                else:\n",
    "                    writeFile.write(member)      \n",
    "            writeFile.truncate()\n",
    "\n",
    "memReg = 'members.txt'\n",
    "exReg = 'inactive.txt'\n",
    "cleanFiles(memReg,exReg)\n",
    "\n",
    "# code to help you see the files\n",
    "\n",
    "headers = \"Membership No  Date Joined  Active  \\n\"\n",
    "\n",
    "with open(memReg,'r') as readFile:\n",
    "    print(\"Active Members: \\n\\n\")\n",
    "    print(readFile.read())\n",
    "\n",
    "with open(exReg,'r') as readFile:\n",
    "    print(\"Inactive Members: \\n\\n\")\n",
    "    print(readFile.read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iterator: Fibonacci Sequence\n",
    "\n",
    "Use the concept of an iterator to iterate through the Fibonacci sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Fibonacci.py creates an iterator for the Fibonacci sequence\"\"\"\n",
    "\n",
    "class Fibonacci():\n",
    "    \"\"\"Iterator class for Fibonacci sequence\"\"\"\n",
    "\n",
    "    def __init__(self, num) -> None:\n",
    "        if not isinstance(num, int):\n",
    "            raise ValueError\n",
    "        self.num = num\n",
    "        self.index = 0\n",
    "        self.current_value = 0\n",
    "        self.previous_value = 0\n",
    "\n",
    "    def __iter__(self):\n",
    "        \"\"\"Returns the Fibonacci sequence\"\"\"\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        \"\"\"Defines the next number in the sequence\"\"\"\n",
    "\n",
    "        if self.index > self.num:\n",
    "            raise StopIteration\n",
    "\n",
    "        current_value = self.current_value\n",
    "\n",
    "        if self.index == 0:\n",
    "            self.current_value = 0\n",
    "        elif self.index == 1:\n",
    "            self.current_value = 1\n",
    "        else:\n",
    "            self.current_value += self.previous_value\n",
    "            self.previous_value = current_value\n",
    "\n",
    "        current_value = self.current_value\n",
    "\n",
    "        self.index += 1\n",
    "\n",
    "        return current_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Test suite for fibonacci.py\"\"\"\n",
    "\n",
    "# import pytest\n",
    "# from fibonacci import Fibonacci\n",
    "\n",
    "def test_fib_constructor():\n",
    "    \"\"\"If constructed with a value other than an integer, \n",
    "    the Fibonacci constructor should raise a ValueError.\n",
    "    \"\"\"\n",
    "    with pytest.raises(ValueError):\n",
    "        Fibonacci('A')\n",
    "\n",
    "def test_fib_n_is_zero():\n",
    "    \"\"\"Given a constructor value of 0,\n",
    "     the iterator should produce the values [0] if cast as a list.\n",
    "     \"\"\"\n",
    "    assert list(Fibonacci(0))==[0]\n",
    "\n",
    "def test__fib_n_is_one():\n",
    "    \"\"\"Given a constructor value of 1,\n",
    "    the iterator should produce the values [0, 1] if cast as a list.\n",
    "    \"\"\"\n",
    "    assert list(Fibonacci(1))==[0,1]\n",
    "\n",
    "def test_fib_n_is_two():\n",
    "    \"\"\"Given a constructor value of 2,\n",
    "     the iterator should produce the values [0, 1, 1].\n",
    "    \"\"\"\n",
    "    assert list(Fibonacci(2))==[0, 1, 1]\n",
    "\n",
    "def test_fib_n_is_four():\n",
    "    \"\"\"Given a value of 4,\n",
    "    the iterator should produce [0, 1, 1, 2, 3]\n",
    "    \"\"\"\n",
    "    assert list(Fibonacci(4))==[0, 1, 1, 2, 3]\n",
    "\n",
    "def test_fib_n_is_ten():\n",
    "    \"\"\"Given a value of 10,\n",
    "     the iterator should produce [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n",
    "    \"\"\"\n",
    "    assert list(Fibonacci(10))==[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n",
    "\n",
    "def test_fib_n_is_neg():\n",
    "    \"\"\"Given a negative value,\n",
    "    the iterator should produce an empty list.\n",
    "    \"\"\"\n",
    "    assert not list(Fibonacci(-1))\n",
    "\n",
    "def test_fib_thorough():\n",
    "    \"\"\"Test fibonacci recurrence for n =3 .. 20\"\"\"\n",
    "    for index in range(3, 20):\n",
    "        l_fib_n_plus_one = list(Fibonacci(index))\n",
    "        l_fib_n_plus_one.append(l_fib_n_plus_one[-1]+l_fib_n_plus_one[-2])\n",
    "        assert list(Fibonacci(index+1))==l_fib_n_plus_one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run the tests\n",
    "# test_fib_constructor() # skipped, needs pytest\n",
    "test_fib_n_is_zero()\n",
    "test__fib_n_is_one()\n",
    "test_fib_n_is_two()\n",
    "test_fib_n_is_four()\n",
    "test_fib_n_is_ten()\n",
    "test_fib_n_is_neg()\n",
    "test_fib_thorough()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A recent thought: playing with Linked Lists\n",
    "\n",
    "On November 1st 2023, while having lunch at work, I was watching a Youtube video emulating a Google Interview. The question was to reverse a linked-list.\n",
    "\n",
    "Watching the mock interviewee work through the problem, I was thinking to myself that this cannot be too difficult!? I know about linked-lists from my C programming (2020 Summer), so I should be able to solve it. Then lunchtime was over.\n",
    "\n",
    "On my drive home, I decided to solve the problem in my head (probably not advisable while driving), and it tool me longer than I thought it would. After about 10 minutes of debating the code with myself, I felt that I had a solution, and decided to write it up. Here is that write up - using python. I am doing this from memory, so please excuse mistakes.\n",
    "\n",
    "This code isn't really from the early days, but the simplicity of the code encourages me to put it here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Setting up a (forward) linked list class. A linked list should be a sequence of\n",
    "# nodes, starting with a head node, and ending with None or Null pointer.\n",
    "# In abstract notation, a linked-list (LL) is\n",
    "# either None (empty)\n",
    "# or head -> LL*\n",
    "# A node is an ADT that is either None/Null pointer, i.e., empty, or a class\n",
    "# containing a data field and a next field. The next field acts as a pointer\n",
    "# to the next node in the data field.\n",
    "\n",
    "class Node():\n",
    "    \"\"\"The structure of a non-empty node.\n",
    "    Fields: data, next\n",
    "    data is type object\n",
    "    next is type Node or None\"\"\"\n",
    "\n",
    "    def __init__(self, data, next=None):\n",
    "        \"\"\"Constructor\"\"\"\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "    \n",
    "    def __str__(self):\n",
    "        return f'{self.data} -> '\n",
    "    \n",
    "    def pop_data(self):\n",
    "        return self.data\n",
    "    \n",
    "    def next_node(self):\n",
    "        return self.next\n",
    "    \n",
    "    def __eq__(self, other):\n",
    "        \"\"\"Equating two nodes, could get expensive for long linked lists.\n",
    "        A better way to do this would be to use memory address of the next\n",
    "        pointer rather than the recursive equality done here.\"\"\"\n",
    "        return self.data == other.data and self.next==other.next\n",
    "    \n",
    "class LinkedList():\n",
    "    \"\"\"A linked list can be empty, i.e., head=None, or a sequence of nodes,\n",
    "    starting with a head node, where each node points to the subsequent node\n",
    "    until the last node, which then points to None.\n",
    "    \n",
    "    Linked lists can be initiated in various ways. Here, I am using a very\n",
    "    simple construction from a list of numbers (obviously not a good choice).\"\"\"\n",
    "    \n",
    "    head = None\n",
    "\n",
    "    def __init__(self, loN):\n",
    "        \"\"\"loN is a list of numbers that is then converted to a linked list\"\"\"\n",
    "        n = len(loN) # not very python-y, more like a C approach :p\n",
    "\n",
    "        self.head = None # if empty\n",
    "\n",
    "        for i in range(n): #loop only runs if loN is non-empty\n",
    "            if i==0:\n",
    "                self.head = Node(loN[i], None) #set up head\n",
    "                current = self.head\n",
    "            else:\n",
    "                next = Node(loN[i], None) #create next node to insert\n",
    "                current.next = next #point\n",
    "                current = next #update\n",
    "    \n",
    "    def __str__(self):\n",
    "        current = self.head\n",
    "        ret_str = 'head: '\n",
    "        while current: # loops until current is None\n",
    "            ret_str += str(current)\n",
    "            current = current.next\n",
    "\n",
    "        if self.head: #non-empty\n",
    "            ret_str += 'None'\n",
    "        else:\n",
    "            ret_str = 'empty'\n",
    "        \n",
    "        return ret_str\n",
    "    \n",
    "    def __repr__(self):\n",
    "        if self.head:\n",
    "            loN = []\n",
    "            current = self.head\n",
    "            while current:\n",
    "                loN.append(current.data)\n",
    "                current = current.next\n",
    "            return f'LinkedList({loN})'\n",
    "        else:\n",
    "            return 'LinkedList([])'\n",
    "        \n",
    "    def __eq__(self, other):\n",
    "        return self.head == other.head\n",
    "\n",
    "\n",
    "    # The following is the main problem that I am looking to solve:\n",
    "    # given the head node of a linked list, mutate the list to reverse it\n",
    "    def reverse(self):\n",
    "        \"\"\"reverses the linkied list\n",
    "        Side-effect: linked list is mutated\"\"\"\n",
    "\n",
    "        def help_reverse(head_node):\n",
    "            \"does the actual reversing from a head node\"\n",
    "            \n",
    "            current = head_node\n",
    "            if head_node: # for non-empty\n",
    "                next = head_node.next\n",
    "                current.next = None # A little trickery to reverse head right-away\n",
    "\n",
    "            while current and next:\n",
    "                # Loop until next is None, only when self is non-empty\n",
    "                previous = current\n",
    "                current = next\n",
    "                next = current.next\n",
    "                current.next = previous\n",
    "            \n",
    "            head_node = current # reset head, thust mutating list\n",
    "            return head_node\n",
    "        \n",
    "        self.head = help_reverse(self.head)\n",
    "        return self\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tests for LinkedList() and revsered linked-list\n",
    "\n",
    "# import pytest\n",
    "# from linked_list import LinkedList, Node\n",
    "\n",
    "def test_node_constructor():\n",
    "    node = Node('')\n",
    "    assert isinstance(node, Node) == True\n",
    "\n",
    "def test_node_functions():\n",
    "    node1 = Node(1)\n",
    "    node2 = Node(2, node1)\n",
    "    test_str = (str(node2) == '2 -> ')\n",
    "    test_data = (node2.pop_data() == 2)\n",
    "    test_next = (node1.next_node() == None)\n",
    "    test_eq12 = (node2 != node1)\n",
    "    test_eq22 = (node2 == Node(2, node1))\n",
    "    assert test_data and test_str and test_next and test_eq12 and test_eq22\n",
    "\n",
    "def test_empty_linked_list_constructor():\n",
    "    linkedL = LinkedList([])\n",
    "    assert isinstance(linkedL, LinkedList) == True\n",
    "\n",
    "def test_nonempty_linked_list_constructor():\n",
    "    linkedL = LinkedList([1, 2])\n",
    "    assert isinstance(linkedL, LinkedList) == True\n",
    "\n",
    "def test_linked_list_str():\n",
    "    linkedL_empty = LinkedList([])\n",
    "    linkedL_nonempty = LinkedList([1, 2])\n",
    "    test_empty = (str(linkedL_empty) == 'empty')\n",
    "    test_nonempty = (str(linkedL_nonempty) == 'head: 1 -> 2 -> None')\n",
    "    assert test_empty and test_nonempty\n",
    "\n",
    "def test_linked_list_repr():\n",
    "    linkedL = LinkedList([1, 2])\n",
    "    linkedL_repr = repr(linkedL)\n",
    "    assert isinstance(eval(linkedL_repr), LinkedList) == True\n",
    "\n",
    "def test_empty_linked_list_eq():\n",
    "    linkedL = LinkedList([])\n",
    "    assert linkedL ==  LinkedList([])\n",
    "\n",
    "def test_non_empty_linked_list_eq():\n",
    "    linkedL = LinkedList([1, 2])\n",
    "    assert linkedL == LinkedList([1, 2])\n",
    "\n",
    "def test_reverse_empty_linked_list():\n",
    "    loN = []\n",
    "    linkedL = LinkedList(loN)\n",
    "    assert linkedL.reverse() == LinkedList(loN)\n",
    "\n",
    "def test_reverse_non_empty_linked_list():\n",
    "    loN = [1, 2, 3, 4]\n",
    "    linkedL = LinkedList(loN)\n",
    "    loN.reverse()\n",
    "    assert linkedL.reverse() == LinkedList(loN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_node_constructor()\n",
    "test_node_functions()\n",
    "test_empty_linked_list_constructor()\n",
    "test_nonempty_linked_list_constructor()\n",
    "test_linked_list_str()\n",
    "test_linked_list_repr()\n",
    "test_empty_linked_list_eq()\n",
    "test_non_empty_linked_list_eq()\n",
    "test_reverse_empty_linked_list()\n",
    "test_reverse_non_empty_linked_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Setting up MineSweeper\n",
    "\n",
    "In this script, I set up a grid for the game minesweeper. The location of mines are assigned through a given list (which could be randomized). Then the mines are detected in order to place \"safe\" numbers on the board according to how many mines are in the neighborhood (3x3 grid with the safe square in the middle). The grid is created in two different ways - using recursion, and then functionally without recursion.\n",
    "\n",
    "This code was written in November 2020"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def row_creator(w, content, lst):\n",
    "  \"\"\"Creates a row\"\"\"\n",
    "  if w == 0:\n",
    "    return \n",
    "  lst.append(content) \n",
    "  row_creator(w-1, content, lst)\n",
    "\n",
    "def grid_creator(h, lst, retlst):\n",
    "  \"\"\"Creates the grid using recursion.\n",
    "    Mutates retlst\n",
    "    \"\"\"\n",
    "  if h == 0:\n",
    "    return\n",
    "  cpylst = lst.copy()\n",
    "  retlst.append(cpylst)\n",
    "  grid_creator(h-1, lst, retlst)\n",
    "  \n",
    "def create_grid_recur(width, height, content):\n",
    "    \"\"\" create_grid(width, height, content)\n",
    "        consumes two positive natural numbers, width and height, \n",
    "        and a third value of any type, content.\n",
    "\n",
    "        The function returns a width times height two dimensional list\n",
    "        whose cells all contain content. Uses recursion.\n",
    "    \"\"\"\n",
    "    lst = []\n",
    "    row_creator(width, content, lst)\n",
    "    retlst = [] \n",
    "    grid_creator(height, lst, retlst)\n",
    "    return retlst\n",
    "\n",
    "\n",
    "assert create_grid_recur(3, 2, None) ==  [[None, None, None],\n",
    "                                    [None, None, None]]\n",
    "\n",
    "def create_grid(width, height, content):\n",
    "  \"\"\"the function create_grid again, this time without using recursion.\"\"\"\n",
    "  lst = list(range(width))\n",
    "  lst = list(map(lambda x: content, lst))\n",
    "  retlst = list(range(height))\n",
    "  retlst = list(map(lambda x: lst.copy(), retlst))\n",
    "  return retlst\n",
    "\n",
    "assert create_grid(3, 2, None) ==  [[None, None, None],\n",
    "                                    [None, None, None]]\n",
    "\n",
    "def place_mines(lst, width, height, mine_coordinates):\n",
    "  \"\"\"Places mines at the given mine coordinates\"\"\"\n",
    "  if mine_coordinates == []:\n",
    "    return\n",
    "  else:\n",
    "    assert mine_coordinates[0][0] < width\n",
    "    assert mine_coordinates[0][1] < height\n",
    "    x = mine_coordinates[0][0]\n",
    "    y = mine_coordinates[0][1]\n",
    "    lst[x][y] = \"X\"\n",
    "    #print(lst)\n",
    "    place_mines(lst, width, height, mine_coordinates[1:])\n",
    " \n",
    "def check_for_mines(lst, xcoord, ycoord, width, height):\n",
    "  if xcoord >= width or ycoord >= height or xcoord <0 or ycoord < 0:\n",
    "    return False\n",
    "  #elif lst[xcoord][ycoord] == \"X\":\n",
    "   # print([xcoord, ycoord])\n",
    "   # return True\n",
    "  else:\n",
    "    #print([xcoord, ycoord])\n",
    "    if lst[ycoord][xcoord] == \"X\":\n",
    "      return True\n",
    "    return False\n",
    "\n",
    "def check_neighbors(lst, x, y, width, height):\n",
    "  \"\"\"At a given coordinate, checks all 3x3 neighbors for mines and adjusts cournt\"\"\"\n",
    "  check_x1 = x + 1\n",
    "  check_x2 = x - 1\n",
    "  check_y1 = y + 1\n",
    "  check_y2 = y - 1\n",
    "  \n",
    "  count = 0\n",
    "  if check_for_mines(lst, check_x1, check_y1, width, height):\n",
    "    count += 1\n",
    "  if check_for_mines(lst, check_x1, y, width, height):\n",
    "    count += 1\n",
    "  if check_for_mines(lst, check_x1, check_y2, width, height):\n",
    "    count += 1\n",
    "  if check_for_mines(lst, x, check_y1, width, height):\n",
    "    count += 1\n",
    "  if check_for_mines(lst, x, check_y2, width, height):\n",
    "    count += 1 \n",
    "  if check_for_mines(lst, check_x2, check_y1, width, height):\n",
    "    count += 1\n",
    "  if check_for_mines(lst, check_x2, y, width, height):\n",
    "    count += 1\n",
    "  if check_for_mines(lst, check_x2, check_y2, width, height):\n",
    "    count += 1  \n",
    "  return count\n",
    "\n",
    "def place_count(lst, x, y, width, height):\n",
    "  \"\"\"Calculates the safe number for each coordinate as it goes through the grid\"\"\"\n",
    "  if x >= width and y >= height:\n",
    "    return\n",
    "  elif x >= width:\n",
    "    if y + 1 >= height:\n",
    "      return\n",
    "    else:\n",
    "      place_count(lst, 0, y+1, width, height)\n",
    "  #elif lst[y][x] == \"X\":\n",
    "  #  place_count(lst, x+1, y, width, height)\n",
    "  else:\n",
    "    #print([x, y])\n",
    "    if lst[y][x] == \"X\":\n",
    "      place_count(lst, x+1, y, width, height)\n",
    "    else:\n",
    "      count = check_neighbors(lst, x, y, width, height)\n",
    "      if not(count == 0):\n",
    "        lst[y][x] = str(count)\n",
    "      place_count(lst, x+1, y, width, height)\n",
    "  \n",
    "def create_minesweeper_grid(width, height, mine_coordinates):\n",
    "    \"\"\"    create_minesweeper_grid(width, height, mine_coordinates)\n",
    "        that consumes width and height, two positive integers, and mine_coordinates,\n",
    "        a list of lists of two natural numbers \n",
    "        containing the coordinates of the mines. \n",
    "\n",
    "        The function create_minesweeper_grid returns a list of list of strings\n",
    "        representing the minesweeper grid:\n",
    "\n",
    "        Each cell representing a mine contains the string \"X\".\n",
    "        Each cell that is not in the vicinity of any mine contains the empty string.\n",
    "        Each other cells contain a string representing the number of mines\n",
    "        in the adjacent cells (including diagonals).\n",
    "        The mine coordinates in mine_coordinates must be within grid.\n",
    "    \"\"\"\n",
    " \n",
    "    lst = create_grid(width, height, \"\")\n",
    "    place_mines(lst, width, height, mine_coordinates)\n",
    "    place_count(lst, 0, 0, width, height)\n",
    "    return lst\n",
    "\n",
    "assert create_minesweeper_grid(5, 3, [[1,1], [2,2], [1,2]]) == \\\n",
    "       [[\"1\", \"2\", \"2\", \"1\", \"\"],\\\n",
    "       [\"1\", \"X\", \"X\", \"2\", \"\"], \\\n",
    "       [\"1\", \"3\", \"X\", \"2\", \"\"]]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Splitting Arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "## split_list(source, partition_size)\n",
    "## consumes a list of integers source and \n",
    "## a positive integer partition_size, and\n",
    "## returns a list of lists of integers containing all elements of source \n",
    "## split amongst lists of partition_size elements \n",
    "## (except the last one that might be smaller).\n",
    "\n",
    "def split_list(source, partition_size):\n",
    "  if source == []:\n",
    "    return []\n",
    "  \n",
    "  source_length = len(source)\n",
    "  number_of_partitions = source_length // partition_size\n",
    "  \n",
    "  retlst = list(range(number_of_partitions))\n",
    "  \n",
    "  offset = partition_size\n",
    "  \n",
    "  for n in range(number_of_partitions):\n",
    "    retlst[n] = source[n * offset : (n + 1) * offset]\n",
    "  \n",
    "  if not(source_length % partition_size == 0):\n",
    "    retlst.append(source[(n + 1)* offset: ])\n",
    "  \n",
    "  return retlst\n",
    "\n",
    "\n",
    "assert split_list([1, 2, 3, 4, 5, 6, 7, 8, 9], 4) \\\n",
    "       == [[1, 2, 3, 4], [5, 6, 7, 8], [9]]\n",
    "\n",
    "assert split_list([], 1375) == []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A virtual vending machine\n",
    "\n",
    "This is a small project in object oriented programming that simulates a vending machine which takes coins (Canadian denomination: nickels, dimes, quarters, loonies and toonies only -no pennies) and dispenses drinks, chips and candies. The products have different prices. The main purpose of this project is to learn about dataclasses.\n",
    "\n",
    "## Classes and Methods\n",
    "- ### Vending Machine\n",
    "#### Fields:\n",
    "- inserted_coins\n",
    "- purchases\n",
    "#### Methods:\n",
    "- insert_coin(coin)\n",
    "- buy_product(product)\n",
    "- return_change()\n",
    "- ### InsufficientFunds\n",
    "Exception Class\n",
    "- ### Product\n",
    "#### Fields:\n",
    "- name\n",
    "- price\n",
    "#### Methods:\n",
    "- str\n",
    "#### Subclasses inherited from Product:\n",
    "- Chips\n",
    "- Drink\n",
    "- Candy\n",
    "- ### Coin\n",
    "#### Fields:\n",
    "None\n",
    "#### Methods:\n",
    "- constructor and str\n",
    "#### Subclasses Inherited from Coin\n",
    "- Nickel\n",
    "- Dime\n",
    "- Quarter\n",
    "- Loonie\n",
    "- Toonie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass, field\n",
    "\n",
    "\"\"\"coins.py defines Coins() class, and Nickel(), Dime(), Quarter()\n",
    "    Loonie() and Toonie() classes that inherit from Coin()\n",
    "\"\"\"\n",
    "\n",
    "@dataclass()\n",
    "class Coin():\n",
    "    \"\"\"Coin() is the parent class that describes coins\"\"\"\n",
    "   \n",
    "    def __init__(self, val, lab):\n",
    "        self.value = val\n",
    "        self.label = lab\n",
    "\n",
    "    def __str__(self):\n",
    "        return self.label\n",
    "\n",
    "@dataclass()\n",
    "class Nickel(Coin):\n",
    "    def __init__(self):\n",
    "        super().__init__(5, '5¢')\n",
    "    # value: int = 5\n",
    "    # label: str = '5¢'\n",
    "\n",
    "\n",
    "@dataclass()\n",
    "class Dime(Coin):\n",
    "    value: int = 10\n",
    "    label: str = '10¢'\n",
    "\n",
    "\n",
    "@dataclass()\n",
    "class Quarter(Coin):\n",
    "    value: int = 25\n",
    "    label: str = '25¢'\n",
    "\n",
    "\n",
    "@dataclass()\n",
    "class Loonie(Coin):\n",
    "    value: int = 100\n",
    "    label: str = '$1'\n",
    "\n",
    "\n",
    "@dataclass()\n",
    "class Toonie(Coin):\n",
    "    value: int = 200\n",
    "    label: str = '$2'\n",
    "\n",
    "\"\"\"product.py contains the Product() class and it's subclasses\"\"\"\n",
    "@dataclass()\n",
    "class Product:\n",
    "    name : str =''\n",
    "    price : int = 0\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        return f'{self.name}: ${self.price / 100}'\n",
    "\n",
    "@dataclass()\n",
    "class Chips(Product):\n",
    "    name: str = 'Chips'\n",
    "    price: int = 225\n",
    "\n",
    "\n",
    "@dataclass()\n",
    "class Drink(Product):\n",
    "    name: str = 'Drink'\n",
    "    price: int = 275\n",
    "\n",
    "\n",
    "@dataclass()\n",
    "class Candy(Product):\n",
    "    name: str = 'Candy'\n",
    "    price: int = 315\n",
    "\n",
    "\"\"\"\n",
    "A virtual vending machine.\n",
    "\"\"\"\n",
    "\n",
    "@dataclass\n",
    "class VendingMachine():\n",
    "    \"\"\"Represents an vending machine that takes coins as input and allows purchase\n",
    "        of product and returns change\n",
    "\n",
    "        Functions:\n",
    "        insert_coin(coin)\n",
    "        buy_product(product, balance) -> Product  \n",
    "        get_balance() -> int\n",
    "        get_change() -> List[Coin]  \n",
    "    \"\"\"\n",
    "\n",
    "    inserted_coins: list = field(default_factory=list)\n",
    "    purchases: list = field(default_factory=list)\n",
    "\n",
    "\n",
    "##\n",
    "# insert_coin takes two arguments: one called \"coin\" and another called \"inserted_coins\".\n",
    "#The \"coin\" parameter will accept the values any of the following values: 5, 10, 25, 100, 200.\n",
    "# These values represent cents. Any other value should raise a ValueError exception.\n",
    "#The \"inserted_coins\" parameter is a list\n",
    "#When the function insert_coin() is called, the \"coin\" value is appended to the insert_coins parameter.\n",
    "##\n",
    "    def insert_coin(self, coin):\n",
    "        # if not isinstance(coin, coins.Coin):\n",
    "        if not isinstance(coin, Coin):\n",
    "            raise ValueError\n",
    "        \n",
    "        self.inserted_coins.append(coin)\n",
    "\n",
    "##\n",
    "# buy_product takes two arguments: one called \"product\" and the other is called \"balance\".\n",
    "# The product argument may be one of the following values: \"drink\", \"candy\", \"chips\".\n",
    "# Any other value should raise a ValueError exception.\n",
    "# balance is an integer representing the current balance of funds available\n",
    "# When the buy_product function is called, the price of the chosen product is compared to the balance.\n",
    "# If the balance of the inserted coins is less than the cost of the product, a custom exception called\n",
    "# InsufficientFunds should be raised.\n",
    "# If the balance equals or exceeds the cost of the product, then the function\n",
    "# will return the balance minus the cost of the purchased product.\n",
    "\n",
    "# Drink: $2.75\n",
    "# Chips: $2.25\n",
    "# Candy: $3.15\n",
    "##\n",
    "    def buy_product(self, prod):\n",
    "        # if not isinstance(prod, product.Product):\n",
    "        if not isinstance(prod(), Product):\n",
    "            raise ValueError\n",
    "        \n",
    "        balance = self.get_balance()\n",
    "        if balance < prod.price:\n",
    "            raise InsufficientFunds\n",
    "        \n",
    "        purchased = prod()\n",
    "        self.purchases.append(purchased)\n",
    "        \n",
    "        return purchased\n",
    "\n",
    "##\n",
    "# return_change takes a single argument called \"balance\".\n",
    "# If the balance is greater than zero, return a list of coins (can be any of 5, 10, 25, 100, 200)\n",
    "# which will sum up to the balance.\n",
    "# If for whatever reason the balance is not a multiple of 5,\n",
    "# then the sum of coins returned should be rounded down to the nearest multiple of 5, and not exceed the balance.\n",
    "# The coins returned should be the largest first, then the smallest.\n",
    "##\n",
    "    def return_change(self):\n",
    "        balance = self.get_balance()\n",
    "        ret_list = []\n",
    "\n",
    "        if balance > 0:\n",
    "            # possible_coins = list(coins.Nickel(), coins.Dime(),\n",
    "            #                       coins.Quarter, coins.Loonie,\n",
    "            #                       coins.Toonie)\n",
    "            possible_coins = list(Nickel(), Dime(),\n",
    "                                  Quarter, Loonie,\n",
    "                                  Toonie)\n",
    "            for coin in possible_coins:\n",
    "                while balance >= coin.get_value():\n",
    "                    ret_lst.append(coin)\n",
    "                    balance -= coin.get_value()\n",
    "        \n",
    "        self.inserted_coins = []\n",
    "        self.purchases = []\n",
    "        \n",
    "        return ret_list\n",
    "\n",
    "    def get_balance(self):\n",
    "        balance = 0\n",
    "        for coin in self.inserted_coins:\n",
    "            balance += coin.value\n",
    "\n",
    "        for product in self.purchases:\n",
    "            balance -= product.price\n",
    "\n",
    "        return balance\n",
    "    \n",
    "class InsufficientFunds(Exception):\n",
    "    \"\"\"\n",
    "    Exception used to indicate that there isn't\n",
    "    enough money to make a purchase.\n",
    "    \"\"\"\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test Functions\n",
    "\n",
    "These unit test functions were developed as part of TDD and is meant to run using pytest. To keep things clean, here I have modified the code slightly to test in the Notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pytest\n",
    "\n",
    "def test_nickel_value():\n",
    "    # coin = coins.Nickel()\n",
    "    coin = Nickel()\n",
    "    assert coin.value == 5\n",
    "\n",
    "\n",
    "def test_nickel_str():\n",
    "    # coin = coins.Nickel()\n",
    "    coin = Nickel()\n",
    "    assert str(coin) == '5¢'\n",
    "\n",
    "\n",
    "def test_dime_value():\n",
    "    # coin = coins.Dime()\n",
    "    coin = Dime()\n",
    "    assert coin.value == 10\n",
    "\n",
    "\n",
    "def test_dime_str():\n",
    "    # coin = coins.Dime()\n",
    "    coin = Dime()\n",
    "    assert str(coin) == '10¢'\n",
    "\n",
    "\n",
    "def test_quarter_value():\n",
    "    # coin = coins.Quarter()\n",
    "    coin = Quarter()\n",
    "    assert coin.value == 25\n",
    "\n",
    "\n",
    "def test_quarter_str():\n",
    "    # coin = coins.Quarter()\n",
    "    coin = Quarter()\n",
    "    assert str(coin) == '25¢'\n",
    "\n",
    "\n",
    "def test_loonie_value():\n",
    "    # coin = coins.Loonie()\n",
    "    coin = Loonie()\n",
    "    assert coin.value == 100\n",
    "\n",
    "\n",
    "def test_loonie_str():\n",
    "    # coin = coins.Loonie()\n",
    "    coin = Loonie()\n",
    "    assert str(coin) == '$1'\n",
    "\n",
    "\n",
    "def test_toonie_value():\n",
    "    # coin = coins.Toonie()\n",
    "    coin = Toonie()\n",
    "    assert coin.value == 200\n",
    "\n",
    "\n",
    "def test_toonie_str():\n",
    "    # coin = coins.Toonie()\n",
    "    coin = Toonie()\n",
    "    assert str(coin) == '$2'\n",
    "\n",
    "\n",
    "def test_the_coin_constructor_takes_no_arguments():\n",
    "    \"\"\"\n",
    "    Ensure that a developer does not accidentally overwrite the\n",
    "    coin `value` by providing an argument.\n",
    "\n",
    "    In other words, we must ensure that __init__ accepts no\n",
    "    arguments.\n",
    "    \"\"\"\n",
    "    with pytest.raises(TypeError):\n",
    "        # coins.Coin(100)  # Ensure that this isn't possible\n",
    "        Coin(100)\n",
    "\n",
    "def test_insert_coin_rejects_integer():\n",
    "    machine = VendingMachine()\n",
    "    with pytest.raises(ValueError):\n",
    "        machine.insert_coin(25)\n",
    "\n",
    "\n",
    "def test_insert_coin_accepts_quarter():\n",
    "    machine = VendingMachine()\n",
    "    # quarter = coins.Quarter()\n",
    "    quarter = Quarter()\n",
    "    machine.insert_coin(quarter)\n",
    "\n",
    "\n",
    "def test_insert_coin_accepts_dime():\n",
    "    machine = VendingMachine()\n",
    "    # dime = coins.Dime()\n",
    "    dime = Dime()\n",
    "    machine.insert_coin(dime)\n",
    "\n",
    "\n",
    "def test_inserted_coins_are_appended_to_coin_list():\n",
    "    machine = VendingMachine()\n",
    "    # machine.insert_coin(coins.Loonie())\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.insert_coin(coins.Quarter())\n",
    "    machine.insert_coin(Loonie())\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.insert_coin(Quarter())\n",
    "\n",
    "    assert machine.inserted_coins == [\n",
    "        # coins.Loonie(),\n",
    "        # coins.Toonie(),\n",
    "        # coins.Quarter()\n",
    "        Loonie(), Toonie(), Quarter()\n",
    "    ]\n",
    "\n",
    "\n",
    "def test_buy_product_rejects_strings():\n",
    "    machine = VendingMachine()\n",
    "\n",
    "    with pytest.raises(ValueError):\n",
    "        machine.buy_product(str)\n",
    "\n",
    "\n",
    "def test_buy_product_accepts_chips_with_sufficient_balance():\n",
    "    machine = VendingMachine()\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.insert_coin(coins.Quarter())\n",
    "    # machine.buy_product(product.Chips)\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.insert_coin(Quarter())\n",
    "    machine.buy_product(Chips)\n",
    "\n",
    "\n",
    "def test_buy_product_accepts_drink():\n",
    "    machine = VendingMachine()\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.insert_coin(coins.Loonie())\n",
    "    # machine.buy_product(product.Drink)\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.insert_coin(Loonie())\n",
    "    machine.buy_product(Drink)\n",
    "\n",
    "\n",
    "def test_buy_product_accepts_candy():\n",
    "    machine = VendingMachine()\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.buy_product(product.Candy)\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.buy_product(Candy)\n",
    "\n",
    "\n",
    "\n",
    "def test_get_balance_returns_zero_when_no_coins():\n",
    "    machine = VendingMachine()\n",
    "    assert machine.get_balance() == 0\n",
    "\n",
    "\n",
    "def test_get_balance_returns_sum_value_of_coins():\n",
    "    machine = VendingMachine()\n",
    "    # machine.insert_coin(coins.Quarter())\n",
    "    # machine.insert_coin(coins.Loonie())\n",
    "    machine.insert_coin(Quarter())\n",
    "    machine.insert_coin(Loonie())\n",
    "\n",
    "    assert machine.get_balance() == 125\n",
    "\n",
    "\n",
    "def test_buy_drink_with_insufficient_funds():\n",
    "    machine = VendingMachine()\n",
    "    with pytest.raises(InsufficientFunds):\n",
    "        # machine.buy_product(product.Drink)\n",
    "        machine.buy_product(Drink)\n",
    "\n",
    "\n",
    "def test_buy_product_returns_instance_when_valid():\n",
    "    machine = VendingMachine()\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # result = machine.buy_product(product.Drink)\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.insert_coin(Toonie())\n",
    "    result = machine.buy_product(Drink)\n",
    "\n",
    "    # assert isinstance(result, product.Drink)\n",
    "    assert isinstance(result, Drink)\n",
    "\n",
    "\n",
    "def test_get_balance_returns_sum_of_coins_minus_purchases():\n",
    "    machine = VendingMachine()\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.insert_coin(coins.Toonie())\n",
    "    # machine.buy_product(product.Candy)\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.insert_coin(Toonie())\n",
    "    machine.buy_product(Candy)\n",
    "\n",
    "    assert machine.get_balance() == 85\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_nickel_value()\n",
    "   \n",
    "test_nickel_str() \n",
    "\n",
    "test_dime_value()\n",
    "   \n",
    "test_dime_str()\n",
    "   \n",
    "test_quarter_value()\n",
    "\n",
    "test_quarter_str()\n",
    "\n",
    "test_loonie_value()\n",
    "\n",
    "test_loonie_str()\n",
    "\n",
    "test_toonie_value()\n",
    "\n",
    "test_toonie_str()\n",
    "\n",
    "test_the_coin_constructor_takes_no_arguments()\n",
    "    \n",
    "test_insert_coin_rejects_integer()\n",
    "\n",
    "test_insert_coin_accepts_quarter()\n",
    "\n",
    "test_insert_coin_accepts_dime()\n",
    "\n",
    "test_inserted_coins_are_appended_to_coin_list()\n",
    "\n",
    "test_buy_product_rejects_strings()\n",
    "\n",
    "test_buy_product_accepts_chips_with_sufficient_balance()\n",
    "\n",
    "test_buy_product_accepts_drink()\n",
    "\n",
    "test_buy_product_accepts_candy()\n",
    "\n",
    "test_get_balance_returns_zero_when_no_coins()\n",
    "\n",
    "test_get_balance_returns_sum_value_of_coins()\n",
    "\n",
    "test_buy_drink_with_insufficient_funds()\n",
    "\n",
    "test_buy_product_returns_instance_when_valid()\n",
    "\n",
    "test_get_balance_returns_sum_of_coins_minus_purchases()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting Algorithms\n",
    "Here is a collection of a few sorting algorithms, starting with bubble sort, with specified restriction on run-times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def swap(L, p1, p2):\n",
    "  \"\"\"Swap items from indices p1 and p2 in list L\"\"\"\n",
    "  temp = L[p1]\n",
    "  L[p1] = L[p2]\n",
    "  L[p2] = temp\n",
    "  \n",
    "def bubble_sort(L):\n",
    "  \"\"\"bubble_sort(L)\n",
    "  consumes L a list of integers,\n",
    "  returns None and sorts L via mutation using the bubble sort algorithm.\"\"\"\n",
    "  n = len(L)\n",
    "  end = n  - 1\n",
    "  swapped = True\n",
    "  \n",
    "  while swapped == True:\n",
    "    swapped = False\n",
    "    for pos in range(end):\n",
    "      if L[pos] > L[pos + 1]:\n",
    "        swap(L, pos, pos + 1)\n",
    "        swapped = True\n",
    "    end = end - 1\n",
    "\n",
    "L = [6, 1, 5, 3]\n",
    "bubble_sort(L)\n",
    "assert L == [1, 3, 5, 6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersect(L, M): # O(n) where n is the combined length of the two parameters\n",
    "  \"\"\"intersect(L, M)\n",
    "  consumes two sorted lists of distinct integers L and M, \n",
    "  and returns a sorted list that contains only elements common to both lists.\n",
    "  \"\"\"\n",
    "  retlst = [] # O(1)\n",
    "  posL = 0 # O(1)\n",
    "  posM = 0 # O(1)\n",
    "  \n",
    "  while (posL < len(L)) and (posM < len(M)): # loops at most n times\n",
    "    itemL = L[posL] # O(1)\n",
    "    itemM = M[posM] # O(1)\n",
    "    \n",
    "    if itemL > itemM: # O(1)\n",
    "      posM += 1 # O(1)\n",
    "    elif itemM > itemL: # O(1)\n",
    "      posL += 1 # O(1)\n",
    "    else:\n",
    "      retlst.append(itemL) # O(1)\n",
    "      posL += 1 # O(1)\n",
    "      posM += 1 # O(1)\n",
    "    \n",
    "  return retlst # O(1)\n",
    "\n",
    "assert intersect([3, 7, 9, 12, 14], [1, 2, 5, 7, 10, 11, 12]) == [7, 12]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lst_sum(s, r):\n",
    "  for x in s:\n",
    "    if type(x) == list:\n",
    "      r = r + lst_sum(x, r)\n",
    "    else:\n",
    "      r = r + x\n",
    "  return r  \n",
    "  \n",
    "def nest_sort_helper(s):\n",
    "  ret = 0\n",
    "  \n",
    "  if type(s) == list:\n",
    "    if s == []:\n",
    "      return ret\n",
    "    else:\n",
    "      nest_sort(s)\n",
    "      return lst_sum(s, 0)\n",
    "    \n",
    "    return ret + nest_sort_helper(s)\n",
    "    \n",
    "  else:\n",
    "    return ret + s\n",
    "\n",
    "def nest_sort(N):\n",
    "  \"\"\"nest_sort(N)\n",
    "    consumes N, a (nestof Int), returns None, \n",
    "    and mutates N to be in sorted order in according to the following rules:\n",
    "\n",
    "    A nest should come before a sibling nest if the sum of all the integers\n",
    "    it contains is smaller than the sum of the integers the other nest contains;\n",
    "    for example [2, 5] should come before [9].\n",
    "\n",
    "    If the sum of the integers contained in two sibling nests are equal, \n",
    "    they keep the order they had.\n",
    "\n",
    "    An integer should come before a sibling nest if it is smaller than the sum \n",
    "    of all the integers the nest contains; \n",
    "    for example 9 should come before [4, 3, 3]\n",
    "\n",
    "    If an integer is equal to the sum of the integers contained \n",
    "    in a sibling nest, they keep the order they had.\n",
    "\n",
    "    If two integers are equal... It does not matter, they are the same anyway.\n",
    "\n",
    "    The function nest_sort must run in  O(n log n)\n",
    "    where n is the number of individual integers across all nests.\n",
    "\"\"\"\n",
    "  N.sort(key = nest_sort_helper)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_first_help(corpus, prefix, start, end): # O(log n)\n",
    "  if start >= end: # O (1)\n",
    "    return\n",
    "  \n",
    "  prefix_len = len(prefix) # O (1)\n",
    "  string_to_match = corpus[start][:prefix_len] # O(k)\n",
    "  if string_to_match == prefix: # O(k)\n",
    "    return corpus[start]  # O(1)\n",
    "  \n",
    "  mid = (start + end)//2 # O(1)\n",
    "  \n",
    "  if corpus[mid][:prefix_len] <= prefix : # O(k)\n",
    "    start = start + 1 # O(1)\n",
    "    end = mid + 1 # O(1)\n",
    "  else:\n",
    "    start = mid + 1 # O(1)\n",
    "  \n",
    "  return find_first_help(corpus, prefix, start, end) # T(n/2)\n",
    "\n",
    "def find_first(corpus, prefix):   # O(log n)\n",
    "  \"\"\"find_first(corpus, prefix)\n",
    "    consumes corpus, a sorted list of unique strings and prefix a string, \n",
    "    and and returns the first string in corpus that starts with prefix or \n",
    "    None if no such string exists. Must run in O(log n) time.\"\"\"\n",
    "  return find_first_help(corpus, prefix, 0, len(corpus)) # O(log n) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Date and Time\n",
    "Here a class for \"Dates\" has been modified to match the expected behavior of dates. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Below is the Date class.\n",
    "\n",
    "Dates should be equal (__eq__) if and only if they represent \n",
    "exactly the same date (year, month, and day).\n",
    "\n",
    "A date when printed should display Date(day,month,year) where day, \n",
    "month and year are the respective fields of the Date object.\n",
    "\n",
    "The add_day method consumes a positive integer number of days, and \n",
    "returns the Date that is exactly that many days after self.\n",
    "\n",
    "The day_of_week method returns the day of the week as a capitalized string \n",
    "\"Sunday\", \"Monday\", \"Tuesday\", \"Wednesday\", \"Thursday\", \"Friday\", \n",
    "or \"Saturday\"\n",
    "\"\"\"\n",
    "REF_YEAR = 1900\n",
    "REF_MONTH = 1\n",
    "REF_DAY = 1\n",
    "YEAR_PER_LEAP =  4\n",
    "LEAP_YEAR_COND1 = 100\n",
    "LEAP_YEAR_COND2 = 400\n",
    "DAYS_PER_YEAR = 365\n",
    "MONTHS_PER_YEAR = 12\n",
    "DAYS_IN_MONTH = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)\n",
    "MAX_DAYS_IN_MONTH = 31\n",
    "DAYS_OF_WEEK = (\"Monday\", \"Tuesday\", \"Wednesday\", \"Thursday\", \"Friday\",\\\n",
    "                \"Saturday\", \"Sunday\")\n",
    "DAYS_PER_WEEK = 7\n",
    "OFFSET = 1\n",
    "\n",
    "def is_leap_year(year):\n",
    "  return year % 4 == 0 and \\\n",
    "         (year % 100 != 0 or year % 400 == 0)\n",
    "\n",
    "class Date:\n",
    "   '''Fields: \n",
    "         day (Nat)\n",
    "         month (Nat)\n",
    "         year (Nat)\n",
    "   '''\n",
    "   \n",
    "   def __init__(self, day, month, year):\n",
    "     '''\n",
    "     Initializes a Date object\n",
    "     \n",
    "     __init__: Date Nat Nat Nat -> None\n",
    "     Requires: \n",
    "        (day, month, year) is a valid day \n",
    "        year >= 1800\n",
    "     '''\n",
    "     self.day = day\n",
    "     self.month = month\n",
    "     self.year = year\n",
    "\t \n",
    "   def __repr__(self):\n",
    "     s = \"Date({0.day},{0.month},{0.year})\"\n",
    "     return s.format(self)\n",
    "\t \n",
    "   def __eq__(self, other):\n",
    "     return isinstance(other, Date) and \\\n",
    "            self.day == other.day and \\\n",
    "            self.month == other.month and \\\n",
    "            self.year == other.year\n",
    "\t  \n",
    "   def day_of_week(self):\n",
    "    num_days = 0\n",
    "    if self.year >= REF_YEAR:\n",
    "      num_years = self.year - REF_YEAR\n",
    "      num_days = num_years * DAYS_PER_YEAR\n",
    "      for x in range(self.month - REF_MONTH):\n",
    "        num_days += DAYS_IN_MONTH[x]\n",
    "      num_days += self.day - REF_DAY\n",
    "      num_days = num_days + ((num_years - OFFSET + 300) // LEAP_YEAR_COND2)\n",
    "      if is_leap_year(self.year) and self.month > 2:\n",
    "        num_days += OFFSET \n",
    "      sgn = 1  \n",
    "    else:\n",
    "      num_years = REF_YEAR - self.year\n",
    "      num_days = (num_years - OFFSET) * DAYS_PER_YEAR\n",
    "      num_days = num_days + ((num_years - OFFSET + 100) // LEAP_YEAR_COND2)\n",
    "      for x in range(self.month, MONTHS_PER_YEAR):\n",
    "        num_days += DAYS_IN_MONTH[x]\n",
    "      num_days += (DAYS_IN_MONTH[self.month - OFFSET] - self.day + REF_DAY)\n",
    "      if is_leap_year(self.year) and self.month <= 2:\n",
    "        num_days += OFFSET      \n",
    "      sgn = -1\n",
    "      \n",
    "    num_days = num_days + (num_years - 1) // YEAR_PER_LEAP\n",
    "    num_days = num_days - (num_years - 1) // LEAP_YEAR_COND1\n",
    "      \n",
    "    return DAYS_OF_WEEK[sgn * (num_days % 7)]\n",
    "  \n",
    "   def days_curr_year(year):\n",
    "     if is_leap_year(year):\n",
    "       return DAYS_PER_YEAR + 1\n",
    "     else:\n",
    "       return DAYS_PER_YEAR\n",
    "\n",
    "   def add_days(self, n):\n",
    "     curr_year = self.year\n",
    "     curr_month = self.month\n",
    "     curr_day = self.day\n",
    "     while n > 0:\n",
    "       leap = is_leap_year(curr_year)\n",
    "       while curr_month <= 12:\n",
    "         if leap and curr_month == 2:\n",
    "           curr_month_days = 29\n",
    "         else:\n",
    "           curr_month_days = DAYS_IN_MONTH[curr_month - OFFSET]\n",
    "         while curr_day < curr_month_days:\n",
    "           curr_day += 1\n",
    "           n -= 1\n",
    "           if n <= 0:\n",
    "             return Date(curr_day, curr_month, curr_year)\n",
    "         curr_day = 1\n",
    "         curr_month += 1\n",
    "         if n - 1<= 0 and curr_month < 13:\n",
    "           return Date(curr_day, curr_month, curr_year)\n",
    "         elif curr_month < 13:\n",
    "           n -= 1\n",
    "         \n",
    "       curr_day = 1\n",
    "       curr_month = 1\n",
    "       curr_year += 1\n",
    "       n -= 1\n",
    "     return Date(curr_day, curr_month, curr_year)\n",
    "\n",
    "assert str(Date(1,1,2000)) == \"Date(1,1,2000)\"\n",
    "assert (Date(1,1,2000) == Date(1,1,2000)) == True\n",
    "assert (Date(1,1,2000) == Date(1,2,2000)) == False\n",
    "assert Date(6,7,2020).day_of_week() == \"Monday\"\n",
    "assert Date(6,7,2020).add_days(30) == Date(5,8,2020)      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulating Term Grades\n",
    "An object oriented approach at computing term grades for a student."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Course:\n",
    "  ''' \n",
    "   Represents a course attempt by a particular student\n",
    "\n",
    "   Fields: \n",
    "      code (Str)\n",
    "      term (Nat)\n",
    "      grade ((anyof Nat Str))\n",
    "\t\t\t          \n",
    "   Requires: \n",
    "      term is 4 digits (e.g. ths term is 1205)\n",
    "      if grade is a nat, 0 <= grade <= 100\n",
    "\t    if grade is a str, it is one of\n",
    "\t    \"WD\", \"WF\", \"DNW\", \"INC\", \"CR\", \"NCR\"\n",
    "  '''\n",
    "\t  \n",
    "  def __init__(self, code, term, grade):\n",
    "    self.code = code \n",
    "    self.term = term\n",
    "    self.grade = grade\n",
    "\t  \n",
    "  def __repr__(self):\n",
    "    return \"Course({0!r}, {1!r}, {2!r})\".format(\n",
    "              self.code, self.term, self.grade)\n",
    "  \n",
    "  def __eq__(self,other):\n",
    "\t  return isinstance(other,Course) and \\\n",
    "\t           self.code == other.code and \\\n",
    "\t           self.term == other.term and \\\n",
    "\t           self.grade == other.grade\n",
    "\t           \n",
    "def course_list_by_term(courses):\n",
    "  \"\"\" course_list_by_term() that consumes a list of Course and\n",
    "    returns a dictionary where the keys are terms covered by the listed courses,\n",
    "    and the values are lists of courses the student took that term. \n",
    "    The list of courses should be in the same relative order\n",
    "    they were in the consumed list.\n",
    "    \"\"\"\n",
    "  ret = {}\n",
    "  for course in courses:\n",
    "    if course.term in ret:\n",
    "      ret[course.term].append(course)\n",
    "    else:\n",
    "      ret[course.term] = [course]\n",
    "  return ret\n",
    "\n",
    "def is_numeric(course):\n",
    "  if course.grade in [\"WF\", \"INC\", \"CR\", \"NCR\"]:\n",
    "    return False\n",
    "  elif course.grade in [\"WF\", \"DNW\"]:\n",
    "    return 32\n",
    "  else:\n",
    "    return course.grade\n",
    "  \n",
    "def term_average(courses):\n",
    "  \"\"\" term_average() that consumes a list of courses and returns a dictionary \n",
    "  where the keys are all of the terms covered by the listed courses,\n",
    "  and the values are the student's average grade that term,\n",
    "  or None if no courses that term count toward the average.\n",
    "\n",
    "  For non-numerical grades:\n",
    "\n",
    "  WD, INC, CR, NCR do not count toward your average\n",
    "  WF and DNW count as a 32\n",
    "  \"\"\"\n",
    "  ret = {}\n",
    "  by_term = course_list_by_term(courses)\n",
    "  for key in by_term.keys():\n",
    "    n = 0\n",
    "    total = 0\n",
    "    for x in range(len(by_term[key])):\n",
    "      num_score = is_numeric(by_term[key][x])\n",
    "      if num_score:\n",
    "        total += num_score\n",
    "        n += 1\n",
    "      elif by_term[key][x].grade == 0:\n",
    "        n += 1\n",
    "    if n == 0:\n",
    "      ret[key] = None\n",
    "    else:\n",
    "      ret[key] = total / n\n",
    "  return ret\n",
    "        \n",
    "\n",
    "def highest_grade(courses):\n",
    "  \"\"\"highest_grade() that consumes a list of courses, and \n",
    "  returns a dictionary where the keys are course codes, \n",
    "  and the values are the highest numerical grade achieved.\n",
    "  If a course has no numerical grades recorded, \n",
    "  it is excluded from the dictionary.\n",
    "  \"\"\"\n",
    "  ret = {}\n",
    "  for course in courses:\n",
    "    num_score = is_numeric(course)\n",
    "    if num_score:\n",
    "      if course.code in ret.keys():\n",
    "        ret[course.code] = max(ret[course.code], num_score)\n",
    "      else:\n",
    "        ret[course.code] = num_score\n",
    "    elif course.grade == 0:\n",
    "      if course.code in ret.keys():\n",
    "        ret[course.code] = max(ret[course.code], course.grade)\n",
    "      else:\n",
    "        ret[course.code] = course.grade      \n",
    "      \n",
    "  return ret\n",
    "\n",
    "CS115 = Course(\"CS115\", 1199, 75)\n",
    "MATH135 = Course(\"MATH135\", 1199, 80)\n",
    "CS116a = Course(\"CS116\", 1201, \"NCR\")\n",
    "MATH136 = Course(\"MATH136\", 1201, \"CR\")\n",
    "CS116b = Course(\"CS116\",1205, 80)\n",
    "example_list = [CS115, MATH135, CS116a, MATH136, CS116b]\n",
    "\n",
    "assert course_list_by_term(example_list) ==\\\n",
    "  {1199:[CS115, MATH135],\\\n",
    "   1201:[CS116a, MATH136],\\\n",
    "   1205:[CS116b]}\n",
    "\n",
    "assert term_average(example_list) ==\\\n",
    "  {1199:77.5, 1201:None, 1205:80.0}\n",
    "\n",
    "assert highest_grade(example_list) ==\\\n",
    "  {\"CS115\":75,\\\n",
    "   \"MATH135\":80,\\\n",
    "   \"CS116\":80}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SixNimmt\n",
    "\n",
    "[6 Nimmt!](https://boardgamegeek.com/boardgame/432/take-5) is a card game.\n",
    "\n",
    "To play the game, you shuffle a number cards, lay out four cards face-up to start the four rows, then deal cards to each player. Each turn, players simultaneously choose and reveal a card from their hand, then add the cards to the rows, with cards being placed in ascending order based on their number; specifically, each card is placed in the row that ends with the highest number that's below the card's number. When the sixth card is placed in a row, the owner of that card claims the other five cards and the sixth card becomes the first card in a new row.\n",
    "\n",
    "In addition to a number, each card has a point value. After finishing ten rounds, players tally their score and see whether the game ends. (6 nimmt! ends when someone tops 66.) When this happens, the player with the fewest points wins!\n",
    "\n",
    "Coded here is a variant on the game using object oriented programming."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Player:\n",
    "  \"\"\" An instance of Player has three members:\n",
    "      name : The name of the player\n",
    "      hand : A list of numbers representing the card the player has in hand.\n",
    "      score : The current score of the player\n",
    "  \"\"\"\n",
    "  def __init__(self, name):\n",
    "    \"\"\"A Player is initialized with a name, but no cards in hand,\n",
    "    and a score of zero. \"\"\" \n",
    "    self.name = name\n",
    "    self.hand = []\n",
    "    self.score = 0\n",
    "  \n",
    "  def __repr__(self):\n",
    "    return \"<Player {name} score: {score}, hand: {hand}>\".format(\\\n",
    "      name = self.name, score = self.score, hand = self.hand)\n",
    "  \n",
    "  def __eq__(self, other):\n",
    "    \"\"\"equality operator returns true if two player objects have\n",
    "    the same name, score and hand.\"\"\"\n",
    "    return isinstance(other, Player) and\\\n",
    "           self.name == other.name and\\\n",
    "           self.hand == other.hand and\\\n",
    "           self.score == other.score\n",
    "  \n",
    "class SixNimmt:\n",
    "  \"\"\" An instance of SixNimmt has two members:\n",
    "      players : The list of players.\n",
    "      board : A list of list of numbers, \n",
    "              each inner list representing one row of cards on the board.\n",
    "  \"\"\"\n",
    "  def __init__(self, players):\n",
    "    \"\"\"SixNimmt should be initialized with a list of player names.\n",
    "    Player should be initialized without cards, and score at 0.\n",
    "    The board should be empty.\"\"\"\n",
    "    self.players = [Player(name) for name in players]\n",
    "    self.board = [[],[],[],[]]\n",
    "\n",
    "  def __eq__(self, other):\n",
    "    \"\"\"equality operator returns True when comparing two SixNimmt instances \n",
    "    with the same board and players.\"\"\"\n",
    "    return isinstance(other, SixNimmt) and \\\n",
    "           self.players == other.players and \\\n",
    "           self.board == other.board\n",
    "  \n",
    "  def clear(self):\n",
    "    \"\"\"clear SixNimmt method clear the board and the hands of the players.\"\"\"\n",
    "    for player in self.players:\n",
    "      player.hand = []\n",
    "    self.board = [[],[],[],[]]\n",
    "  \n",
    "  def deal(self, deck):\n",
    "    \"\"\"deal consumes deck, a list of numbers \n",
    "    representing the card in random order. \n",
    "    deal first deals cards to each player,\n",
    "    in player order and one card at a time from the start of deck, \n",
    "    then uncover four more cards for the board. \n",
    "    It removes any dealt card from deck.\"\"\"\n",
    "    NUM_TO_DEAL = 10\n",
    "    idx = 0\n",
    "    for i in range(NUM_TO_DEAL):\n",
    "      for player in self.players:\n",
    "        player.hand.append(deck[idx])\n",
    "        idx += 1\n",
    "    self.board = [[deck[idx + j]] for j in range(4)]\n",
    "    del deck[:idx + 4]\n",
    "  \n",
    "  \n",
    "  def turn(self):\n",
    "    \"\"\"The turn SixNimmt method implements a turn of card. \n",
    "    It consumes nothing and returns nothing.\n",
    "  \n",
    "    It\n",
    "    Asks each player which card they planned to play,\n",
    "    Verify their input is correct, and asks again if needed,\n",
    "    Places each players' cards where they should be in the board,\n",
    "    If a player must chose a row, asks this player what row,\n",
    "    Updates the scores and hands,\"\"\"\n",
    "\n",
    "    ## --------------------- CHECK_VALID-------------------------------------\n",
    "    def check_valid(player, card):\n",
    "      \"\"\"1 <= card <= 104 must be an integer and in players hand\"\"\"\n",
    "      if card.isnumeric() == False:\n",
    "        print(\"This is not a card. Please enter a number.\")\n",
    "        return False\n",
    "      elif float(card).is_integer == False:\n",
    "        print(\"This is not a card. Please enter a number.\")\n",
    "        return False        \n",
    "      elif not (1 <= int(card) <= 104):\n",
    "        print(\"This is not a card. Please enter a number.\")\n",
    "        return False        \n",
    "      elif int(card) not in player.hand:\n",
    "        print(\"This card is not in your hand. Which card did you choose?\")\n",
    "        return False\n",
    "      else:\n",
    "        return True\n",
    "    ## --------------------- CHECK_VALID-------------------------------------\n",
    "    \n",
    "    ## --------------------- ROW_TO_USE-------------------------------------\n",
    "    def row_to_use(card, board):\n",
    "      \"\"\"The card must be put on a row where the latest (end) card is lower \n",
    "      in value than the card that is about to be played.\n",
    "    \n",
    "      The card must be put on the row where the latest (end) card\n",
    "      is the closest in value to the card that is about to be played \n",
    "    \n",
    "      If the row where the played card must be placed already contains 5 cards\n",
    "      (the player's card is the 6th), the player must gather the 5 cards\n",
    "    \n",
    "      If the played card is lower than all the latest cards \n",
    "      present on the four rows, the player must choose a row and\n",
    "      gather the cards on that row    \n",
    "      \"\"\"\n",
    "      FULL = 5\n",
    "      collect_row = False\n",
    "      curr_row = len(board)\n",
    "      running_val = 0\n",
    "      for i in range(len(board)):\n",
    "        if running_val < board[i][-1] < card:\n",
    "          curr_row = i\n",
    "      if curr_row == len(board):\n",
    "        print(\"{pl}, your {cd} cannot be placed at the \"\\\n",
    "              .format(pl = doC[card].name, cd = card)\\\n",
    "        +\"end of any row. What row do you want to gather?\"\\\n",
    "              )\n",
    "        curr_row = int(input())\n",
    "        OK = False\n",
    "        if (1 <= curr_row <= 4):\n",
    "          OK = True\n",
    "          curr_row = curr_row - 1\n",
    "        while (not OK):\n",
    "          print(\"This is not a row. Please enter a number between 1 and 4.\")\n",
    "          curr_row = int(input())\n",
    "          if (1 <= curr_row <= 4):\n",
    "            OK = True\n",
    "            curr_row = curr_row - 1\n",
    "        collect_row = True\n",
    "      elif len(board[curr_row]) == FULL:\n",
    "        collect_row = True       \n",
    "      return [curr_row, collect_row]\n",
    "    ## --------------------- ROW_TO_USE-------------------------------------\n",
    "    \n",
    "    ## --------------------- CARD_VALUE_LOOKUP------------------------------ \n",
    "    def card_value_lookup(card):\n",
    "      \"\"\"In the deck there are:\n",
    "    \n",
    "      1 card with 7 cattle heads�number 55\n",
    "    \n",
    "      8 cards with 5 cattle heads�multiples of 11 (except 55): \n",
    "      11, 22, 33, 44, 66, 77, 88, 99\n",
    "    \n",
    "      10 cards with 3 cattle heads�multiples of ten: \n",
    "      10, 20, 30, 40, 50, 60, 70, 80, 90, 100\n",
    "    \n",
    "      9 cards with 2 cattle heads�multiples of five that are \n",
    "      not multiples of ten (except 55): 5, 15, 25, 35, 45, 65, 75, 85, 95\n",
    "    \n",
    "      76 cards with 1 cattle head�the rest of the cards from 1 through 104    \"\"\"\n",
    "      assert 1 <= card <= 104\n",
    "      if card == 55:\n",
    "        return 7\n",
    "      elif card % 11 == 0:\n",
    "        return 5\n",
    "      elif card % 10 == 0:\n",
    "        return 3\n",
    "      elif card % 5 == 0:\n",
    "        return 2\n",
    "      else:\n",
    "        return 1\n",
    "    ## --------------------- CARD_VALUE_LOOKUP---------------------    --------- \n",
    "    \n",
    "    ## --------------------- UPDATE_BOARD-------------------------------------     \n",
    "    def update_board(doC, board):\n",
    "      \"\"\"When all the players have selected a card, the cards are uncovered.\n",
    "    \n",
    "      Starting with the lowest valued card, and continuing in increasing order,\n",
    "      each player must put their card at the end of one of the four rows    \n",
    "      \n",
    "      If the row where the played card must be placed already contains 5 cards\n",
    "      (the player's card is the 6th), the player must gather the 5 cards\n",
    "      leaving only the 6th card in their place to start a new row. \n",
    "      The gathered cards must be taken separated and\n",
    "      never mixed with the hand cards. The sum of the number of cattle head\n",
    "      on the gathered cards will be calculated at the end of the round.\n",
    "      \n",
    "      If the played card is lower than all the latest cards \n",
    "      present on the four rows, the player must choose a row and\n",
    "      gather the cards on that row \n",
    "      leaving only the played card on the row.\"\"\"\n",
    "      cards = list(sorted(doC.keys()))  \n",
    "      for card in cards:\n",
    "        cards_to_sum = []\n",
    "        row, collect_row  = row_to_use(card, board)\n",
    "        ## Now we have a valid row for the given card\n",
    "        if collect_row:\n",
    "          cards_to_sum = board[row].copy()\n",
    "          board[row].clear()\n",
    "          board[row].append(card)\n",
    "          print(\"{pl} gathers row {r}, and replaces it with their {c}.\"\\\n",
    "                .format(pl = doC[card].name, r = row + 1, c = card))\n",
    "        else:\n",
    "          board[row].append(card)\n",
    "          print(\"{pl}'s {c} goes in row {r}.\"\\\n",
    "                .format(pl = doC[card].name, r = row + 1, c = card))\n",
    "        doC[card].score += sum(map(card_value_lookup, cards_to_sum))\n",
    "    ## --------------------- UPDATE_BOARD-------------------------------------   \n",
    "    \n",
    "    ## --------------------- MAIN: TURN -------------------------------------\n",
    "    doC = {} # deck of cards\n",
    "    for player in self.players:\n",
    "      print(\"{0}, which card did you choose?\".format(player.name))\n",
    "      curr_card = input()\n",
    "      while (check_valid(player, curr_card) == False):\n",
    "        curr_card = input()\n",
    "      curr_card = int(curr_card)\n",
    "      player.hand.remove(curr_card)\n",
    "      doC[curr_card] = player\n",
    "    update_board(doC, self.board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TimeZone Mechanics\n",
    "\n",
    "Here is an OOP approach to different time-zones across the world. We start with a Time class that can call it's methods to adjust a given time from one timezone to another."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_timezones(filename):\n",
    "  \"\"\"load_timezones function that consumes a filename, \n",
    "  reads time zones from that file, and returns a (dictof Str Int)\n",
    "  which maps time zone identifiers (e.g. \"EST\") to time zone offsets in minutes\n",
    "  (e.g. \"EST\" has an offset of -300 minutes,\n",
    "  or 5 hours behind Greenwich Mean Time)\"\"\"\n",
    "  \n",
    "  ret_dict = {}\n",
    "  \n",
    "  def str_tz(s):\n",
    "    tzlist = s.split()\n",
    "    return [tzlist[0], tzlist[1]]\n",
    "  \n",
    "  fin = open(filename)\n",
    "  time_zones = fin.readlines()\n",
    "  tzlist = list(map(str_tz, time_zones))\n",
    "  \n",
    "  for x in tzlist:\n",
    "    ret_dict[x[0]] = int(x[1])\n",
    "    \n",
    "  fin.close()\n",
    "  return ret_dict\n",
    "\n",
    "class Time:\n",
    "  ''' \n",
    "  An Object that represents a specific time (with timezone)\n",
    "  Fields: \n",
    "     hour [Nat], \n",
    "     minute [Nat], \n",
    "     second [Nat], \n",
    "     timezone [Str], \n",
    "     day [Int] \n",
    "  \n",
    "  Requires: \n",
    "     0 <= hour < 24\n",
    "\t   0 <= minute < 60\n",
    "\t\t 0 <= second < 60\n",
    "\t\t timezone is a valid timezone identifier\n",
    "  '''\n",
    "\n",
    "  def __init__(self, hour, minute, second, timezone, day):\n",
    "    '''\n",
    "    Initializes self as a Time object with the given hour,\n",
    "    minute, second, and timezone field,\n",
    "\t  and with the day offset equal to day\n",
    "\t  '''\n",
    "    self.hour = hour\n",
    "    self.minute = minute\n",
    "    self.second = second\n",
    "    self.timezone = timezone\n",
    "    self.day = day\n",
    "\n",
    "\n",
    "  def __repr__(self):\n",
    "    ''' returns self in string form \n",
    "    This method should return the time in 24 hour format: \n",
    "    \"HH:MM:SS [TZ-OFFSET]\".\n",
    "    If the day offset is non-zero, it should end with 'DAY-OFFSET day(s)'. \n",
    "    The [TZ-OFFSET] component is the string '[GMT�H:MM]' \n",
    "    (where � is either + or - as appropriate. \n",
    "    If the offset is 0 hours and 0 minutes, use +).\n",
    "    '''\n",
    "    if timezone_table[self.timezone] < 0:\n",
    "      sgn = \"\"\n",
    "    else:\n",
    "      sgn = \"+\"\n",
    "    if self.day > 0:\n",
    "      s = \"{HH:02d}:{MM:02d}:{SS:02d} [GMT{TZH}:{TZM:02d}] +{DD} day(s)\"\n",
    "      return s.format(HH = self.hour, MM = self.minute, SS = self.second,\\\n",
    "                      TZH = sgn + str(timezone_table[self.timezone] // 60),\\\n",
    "                      TZM =  (timezone_table[self.timezone] % 60),\\\n",
    "                      DD = self.day)\n",
    "    elif self.day < 0:\n",
    "      s = \"{HH:02d}:{MM:02d}:{SS:02d} [GMT{TZH}:{TZM:02d}] -{DD} day(s)\"\n",
    "      return s.format(HH = self.hour, MM = self.minute, SS = self.second,\\\n",
    "                      TZH = sgn + str(timezone_table[self.timezone] // 60),\\\n",
    "                      TZM =  (timezone_table[self.timezone] % 60), \\\n",
    "                      DD = self.day)    \n",
    "    s = \"{HH:02d}:{MM:02d}:{SS:02d} [GMT{TZH}:{TZM:02d}]\"\n",
    "    return s.format(HH = self.hour, MM = self.minute, SS = self.second,\\\n",
    "                    TZH = sgn + str(timezone_table[self.timezone] // 60),\\\n",
    "                    TZM =  (timezone_table[self.timezone] % 60))\n",
    "\t   \n",
    "  def __eq__(self, other):\n",
    "    \"\"\"self is equal to other if and only if other is also a Time,\n",
    "    and represents the same time (however, it may represent the same time\n",
    "    in a different time zone!)\"\"\"\n",
    "\n",
    "    def minutes_from_GMT(time):\n",
    "      return time.hour * 60 + time.minute + timezone_table[time.timezone] \n",
    "    \n",
    "    return isinstance(other, Time) and \\\n",
    "           minutes_from_GMT(self) == minutes_from_GMT(other) and \\\n",
    "           self.second == other.second\n",
    "\t\n",
    "    ## NEW MAGIC METHODS! \n",
    "  \n",
    "  def __lt__(self, other):\n",
    "    \"\"\"This method returns True when self < other should be True.\n",
    "    We will say that this occurs only when other is also a Time, and \n",
    "    self represents an earlier time (you will need to consider their \n",
    "    time zones, and now also their day-offsets). \"\"\"\n",
    "\n",
    "    def minutes_from_GMT_day(time):\n",
    "      return time.hour * 60 + time.minute + timezone_table[time.timezone] +\\\n",
    "             time.day * 24 * 60\n",
    "    \n",
    "    ret = False\n",
    "    if minutes_from_GMT_day(self) < minutes_from_GMT_day(other):\n",
    "      ret = True\n",
    "    elif minutes_from_GMT_day(self) == minutes_from_GMT_day(other):\n",
    "      ret = (self.second < other.second)\n",
    "    return isinstance(other, Time) and ret\n",
    "   \n",
    "  def __gt__(self, other):\n",
    "    return not (self < other or self == other)\n",
    "\t \n",
    "  def __le__(self, other):\n",
    "    return self == other or self < other\n",
    "\t  \n",
    "  def __ge__(self, other):\n",
    "    return not (self < other)\n",
    "      \n",
    "  def __add__(self, amount):\n",
    "    \"\"\"self + other should return a new Time based on self,\n",
    "    but with other seconds added (or removed, if it's negative). \n",
    "    The time zone will not change (but the day offset might,\n",
    "    if you add enough seconds).\t\"\"\"\n",
    "    new_sec = self.second + amount\n",
    "    new_min = self.minute + new_sec // 60\n",
    "    new_sec = new_sec % 60\n",
    "    new_hour = self.hour + new_min // 60\n",
    "    new_min = new_min % 60\n",
    "    new_day = self.day + new_hour // 24\n",
    "    new_hour = new_hour % 24\n",
    "    return Time(new_hour, new_min, new_sec, self.timezone, new_day)\n",
    " \n",
    "  def __sub__(self, other):\n",
    "    \"\"\" For Time t, t - o should do the same thing as t + (-o) if o is an integer. \n",
    "    If o is another Time object, then it should return \n",
    "    the number of seconds apart that t and o are.\"\"\"\n",
    "\n",
    "    def seconds_from_GMT_day(time):\n",
    "      return time.hour * 60 * 60 + time.minute * 60 +\\\n",
    "             timezone_table[time.timezone] * 60 +\\\n",
    "             time.day * 24 * 60\n",
    "        \n",
    "    if type(other) == int:\n",
    "      return self + (-1)*other\n",
    "    elif isinstance(other, Time):\n",
    "      return seconds_from_GMT_day(self) - seconds_from_GMT_day(other)\n",
    "  \n",
    "  def __iadd__(self, amount):\n",
    "    \"\"\"For Time, this should do the same thing as __add__ except that instead \n",
    "    of returning a new Time, it should mutate self and then return self.\"\"\"\n",
    "    self = self + amount\n",
    "    return self\n",
    "  \t  \n",
    "  def set_timezone(self, new_zone):\n",
    "    \"\"\"This method consumes a time zone string and mutates \n",
    "    self to use this new time zone (without changing the time represented)\"\"\"\n",
    "    self.minute = self.minute +\\\n",
    "      timezone_table[new_zone] - timezone_table[self.timezone]\n",
    "    self.hour = self.hour + self.minute // 60\n",
    "    self.minute = self.minute % 60\n",
    "    self.day = self.day + self.hour // 24\n",
    "    self.hour = self.hour % 24\n",
    "    self.timezone = new_zone\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Tests:\n",
    "assert load_timezones(\"some_tz.txt\") ==\\\n",
    "       {'EDT':-240, 'EST':-300, 'PST':-480, 'RND':-1375}\n",
    "\n",
    "fout = open(\"my-test1.txt\", 'w')\n",
    "fout.write(\"EDT -240\\n\")\n",
    "fout.write(\"EST -300\\n\")\n",
    "fout.close()\n",
    "\n",
    "assert load_timezones(\"my-test1.txt\") ==\\\n",
    "       {'EDT':-240, 'EST':-300}\n",
    "\n",
    "timezone_table = load_timezones('tz.txt') \n",
    "\n",
    "assert repr(Time(1,2,3,\"EST\",0)) == \"01:02:03 [GMT-5:00]\"\n",
    "assert repr(Time(1,2,3,\"CET\",1)) == \"01:02:03 [GMT+1:00] +1 day(s)\"\n",
    "\n",
    "assert (Time(4,2,3,\"EDT\",1) == Time(5,2,3,\"EST\",1)) == True\n",
    "assert (Time(1,2,3,\"CET\",1) == Time(1,2,3,\"CET\",0)) == True\n",
    "assert (Time(1,2,3,\"CET\",1) == Time(1,2,3,\"EST\",1)) == False\n",
    "assert (Time(1,2,3,\"CET\",1) == Time(1,3,3,\"CET\",1)) == False\n",
    "assert (Time(1,2,3,\"CET\",1) == Time(1,2,4,\"CET\",1)) == False\n",
    "assert (Time(1,2,3,\"CET\",1) == Time(1,2,3,\"CET\",1)) == True\n",
    "\n",
    "assert (Time(4,2,3,\"EDT\",1) < Time(5,2,3,\"EST\",1)) == False\n",
    "assert (Time(4,1,3,\"EDT\",1) < Time(5,2,3,\"EST\",1)) == True\n",
    "assert (Time(4,2,3,\"EST\",1) < Time(5,2,3,\"EST\",1)) == True\n",
    "assert (Time(6,2,3,\"EST\",1) < Time(5,2,3,\"EST\",1)) == False\n",
    "assert (Time(4,1,3,\"EDT\",1) < Time(5,2,3,\"EST\",0)) == False\n",
    "\n",
    "assert Time(1,2,3,\"EST\",0) + 57 == Time(1,3,0, \"EST\", 0) \n",
    "\n",
    "assert Time(1,2,3,\"EST\",0) - 3 == Time(1,2,0,\"EST\", 0)\n",
    "assert Time(23,59,0, \"EST\", 0) - Time(12,0,0, \"EST\", 0) == 43140\n",
    "\n",
    "T = Time(14,0,0,\"EST\",0)\n",
    "assert T.set_timezone(\"EDT\") == None\n",
    "assert T == Time(15,0,0,\"EDT\", 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# n-Grams\n",
    "\n",
    "From [Wikipedia](https://en.wikipedia.org/wiki/N-gram): \"n-gram is a series of n adjacent letters (including punctuation marks and blanks), syllables, or rarely whole words found in a language dataset; or adjacent phonemes extracted from a speech-recording dataset, or adjacent base pairs extracted from a genome.\"\n",
    "\n",
    "In other words. n-grams are sequences of words of length n in a text that is often used to analyze the text. They are very useful in text mining and natural language processing. Often probabilites of n=grams are used to build word-association, autocompletion, and FAQs. Below is an approach to work with n-grams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "## we will be detecting plagiarism in English essays. \n",
    "\n",
    "## ------------------------ MAIN : PREPROCESS_TEXT------------------------------\n",
    "\n",
    "def preprocess_text(text): # O(n)\n",
    "    \"\"\"preprocess_text(s)\n",
    "    consumes a string s and returns the processed string. \n",
    "    \"\"\"\n",
    "    \n",
    "    def is_to_keep(index, start, end): # O(1)\n",
    "        \"\"\"Use the following rules:\n",
    "    \n",
    "        All letters are replaced with their lower case equivalent.\n",
    "    \n",
    "        Numbers, dashes ('-'), and slashes ('/') are left as-is\n",
    "    \n",
    "        Apostrophes are only kept if they are in between two letters \n",
    "    \n",
    "        All consecutive whitespace characters (meaning, ' ' and '\\n' characters)\n",
    "        are replaced with a single space character.\n",
    "    \n",
    "        All other characters not mentioned above are removed (e.g. '+' and '!')\"\"\"\n",
    "\n",
    "        space = False\n",
    "        to_keep = False\n",
    "        if text[index].isalnum():\n",
    "            to_keep = True\n",
    "        elif text[index] == \"-\" or text[index] == \"/\":\n",
    "            to_keep = True\n",
    "        elif text[index] == \"'\":\n",
    "            if index == start or index == end - 1:\n",
    "                to_keep = False\n",
    "            elif text[index - 1].isalpha() and text[index + 1].isalpha():\n",
    "                to_keep = True\n",
    "            else:\n",
    "                to_keep = False\n",
    "        elif text[index] == \" \" or text[index] == \"\\n\":\n",
    "            if text[index - 1] == \" \" or text[index - 1] == \"\\n\":\n",
    "                to_keep = False\n",
    "            else:\n",
    "                to_keep = True\n",
    "                space = True\n",
    "        else:\n",
    "            to_keep = False\n",
    "        return [to_keep, space]\n",
    "    \n",
    "    retlst = []\n",
    "    text_len = len(text)\n",
    "    for index in range(text_len): # iterated n times\n",
    "        to_keep, space = is_to_keep(index, 0, text_len)\n",
    "        if to_keep:\n",
    "            if space:\n",
    "                retlst.append(\" \")\n",
    "            else:\n",
    "                retlst.append(text[index].lower())\n",
    "    return \"\".join(retlst)\n",
    "\n",
    "## ---------------------------- PREPROCESS_TEXT------------------------------\n",
    "\n",
    "## ------------------------ MAIN: GET_NGRAMS----------------------------------\n",
    "def get_ngrams(s, n): # O(nm) where n is the value of parameter , \n",
    "                      #and m is the length of the string\n",
    "    \"\"\"get_ngrams(s, n)\n",
    "    that consumes a string s and a positive integer n and \n",
    "    returns the n-gram dictionary\n",
    "    (where the n parameter is the length of the n-grams to extract).\n",
    "    An n-gram is a length n substring.\"\"\"\n",
    "\n",
    "    d = {}\n",
    "    s_end = len(s) - (n - 1)\n",
    "    for idx in range(s_end): # iterated m - n times\n",
    "        key_lst = list(s[x + idx] for x in range(n)) # O(n)\n",
    "        key = \"\".join(key_lst) # O(n)\n",
    "        if key in d.keys():\n",
    "            d[key] += 1\n",
    "        else:\n",
    "            d[key] = 1\n",
    "    return d\n",
    "         \n",
    "## ------------------------------ GET_NGRAMS----------------------------------\n",
    "\n",
    "## ---------------------------MAIN: JACCARD_NGRAM-----------------------------\n",
    "\n",
    "\n",
    "def jaccard_ngram(ngram1, ngram2):\n",
    "    \"\"\"jaccard_ngram(ngram1, ngram2)\n",
    "    that consumes two n-gram dictionaries in ngram1 and ngram2 and \n",
    "    returns the Jaccard similarity score.\n",
    "\n",
    "    The Jaccard similarity of two sets A and B is\n",
    "    jaccard(A,B) = size(A intersect B) / size(A union B)\n",
    "    \"\"\"\n",
    "\n",
    "    \n",
    "    def size(d):\n",
    "        \"\"\" The size of an n-gram dictionary is the sum\n",
    "        of the counts of all elements.\n",
    "        \"\"\" \n",
    "        return sum(d.values())\n",
    "    \n",
    "    # Test size:\n",
    "    assert size({\"ba\":1, \"an\":2, \"na\":2}) == 5.\n",
    "    ## ---------------------------SIZE----------------------------------------\n",
    "    \n",
    "    ## ---------------------------UNION---------------------------------------- \n",
    "    def union(d1, d2):\n",
    "        \"\"\"The union of n-gram dictionaries A and B will contain all n-grams \n",
    "        that are in either A or B (just like a set union) and \n",
    "        the count will be the maximum count for that key.       \n",
    "        \"\"\"\n",
    "\n",
    "        s1 = set(d1.keys())\n",
    "        s2 = set(d2.keys())\n",
    "        s = s1.union(s2)\n",
    "        d = {}\n",
    "        for key in s:\n",
    "            if key in d1.keys() and key in d2.keys():\n",
    "                d[key] = max(d1[key], d2[key])\n",
    "            elif key in d1.keys():\n",
    "                d[key] = d1[key]\n",
    "            else:\n",
    "                d[key] = d2[key]\n",
    "        return d\n",
    "    \n",
    "    # Test union:\n",
    "    assert union({'a':1, 'b':2, 'c':2}, {'a':2, 'c':1}) == {'a':2, 'b':2, 'c':2}\n",
    "    ## ---------------------------UNION----------------------------------------\n",
    "    \n",
    "    ##------------------------INTERSECTION-------------------------------------\n",
    "    def intersection(d1, d2):\n",
    "        \"\"\"The intersection of n-gram dictionaries A and B will contain all keys\n",
    "        that are in both A and B (just like a set intersection) and the count \n",
    "        will be the minimum count for that key.    \n",
    "        \"\"\"\n",
    "\n",
    "        s1 = set(d1.keys())\n",
    "        s2 = set(d2.keys())\n",
    "        s = s1.intersection(s2)\n",
    "        d = {}\n",
    "        for key in s:\n",
    "            d[key] = min(d1[key], d2[key])\n",
    "        return d        \n",
    "    \n",
    "    # Test intersection:\n",
    "    assert intersection({'a':1, 'b':2, 'c':2}, {'a':2, 'c':1}) == {'a':1, 'c':1}\n",
    "    ##------------------------INTERSECTION-------------------------------------    \n",
    "    \n",
    "    if ngram1 or ngram2:\n",
    "        return size(intersection(ngram1, ngram2)) / size(union(ngram1, ngram2))\n",
    "    else:\n",
    "        return 1.0\n",
    "\n",
    "## ------------------------------ JACCARD_NGRAM-------------------------------\n",
    "\n",
    "## ---------------------------MAIN : DOCUMENT_SIMILARITY-----------------------\n",
    "def document_similarity(filename1, filename2, n):\n",
    "    \"\"\"document_similarity(filename1, filename2, n)\n",
    "    consumes two strings (file names), and n, a positive integer value.\n",
    "    The function returns a floating point value equal to the \n",
    "    Jaccard multi-set score for the n-grams extracted from the two named files.\n",
    "    \"\"\"\n",
    "\n",
    "    fin1 = open(filename1)\n",
    "    fin2 = open(filename2)\n",
    "    \n",
    "    text1 = fin1.read()\n",
    "    text2 = fin2.read()\n",
    "    \n",
    "    fin1.close()\n",
    "    fin2.close()\n",
    "    \n",
    "    s1 = preprocess_text(text1)\n",
    "    s2 = preprocess_text(text2)\n",
    "    \n",
    "    ngram1 = get_ngrams(s1, n)\n",
    "    ngram2 = get_ngrams(s2, n)\n",
    "    \n",
    "    return jaccard_ngram(ngram1, ngram2)\n",
    "    \n",
    "##----------------------------- DOCUMENT_SIMILARITY-----------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Tests:\n",
    "assert preprocess_text(\"This is a 'test'!\\n Try with  2-4-grams.\")\\\n",
    "      == \"this is a test try with 2-4-grams\"\n",
    "\n",
    "assert get_ngrams(\"banana\", 2) == {\"ba\":1, \"an\":2, \"na\":2}\n",
    "assert get_ngrams(\"dross\", 5) == {\"dross\":1}\n",
    "\n",
    "assert jaccard_ngram({'ba':1,'na':2, 'an':2}, {'ba':1, 'na':1, 'an':1}) == 0.6\n",
    "assert jaccard_ngram({}, {}) == 1.0\n",
    "\n",
    "assert document_similarity(\"sim_test1.txt\", \"sim_test1.txt\", 3) == 1.0\n",
    "assert document_similarity(\"sim_test1.txt\", \"sim_test2.txt\", 2) == 0.6\n",
    "assert document_similarity(\"turn_input.txt\", \"sim_test2.txt\", 2) == 0.0"
   ]
  }
 ],
 "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}