Chapter 4 Exercises.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 4 Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reinforcement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "774\n",
      "8\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'\\nRunning time is O(n)\\n\\nSpace is also O(n)\\n\\n'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#-----------R4-1--------------------\n",
    "def rec_find_max(S,index):\n",
    "    if index == len(S)-1:\n",
    "        return S[index]\n",
    "    return max(S[index], rec_find_max(S, index+1))\n",
    "\n",
    "\n",
    "\n",
    "def find_max(S):\n",
    "    return rec_find_max(S, 0)\n",
    "    \n",
    "\n",
    "print(find_max([1,2,3,4,5,6,7,8]))\n",
    "print(find_max([1,2,774,5,6,7,8]))\n",
    "print(find_max([8,7,6,5,4,3,2,1]))\n",
    "\n",
    "\"\"\"\n",
    "Running time is O(n)  (N calls to recursion, each taking O(1) time\n",
    "\n",
    "Space is also O(n) since you have to call n activations\n",
    "If I had passed in a copy of the subarray, it would have taken O(n^2) space, although if I had just passed\n",
    "in the subarray (S[index:]), it should not have recopied it and still been O(n)\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n"
     ]
    }
   ],
   "source": [
    "#------R4-2----------------------\n",
    "def power(x,n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return x*power(x, n-1)\n",
    "\n",
    "\"\"\"\n",
    "For this implementation (x=2, n=5) , the trace is\n",
    "\n",
    "power(2, 5)    returns 16*2  = 32\n",
    "    power(2,4)       returns 8*2 = 16\n",
    "        power(2,3)     returns 4*2 = 8\n",
    "            power (2,2)     returns 2*2 = 4\n",
    "                power (2,1)   returns 2*1 = 2\n",
    "                    power (2,0) returns 1\n",
    "\n",
    "\n",
    "The arrows would trace downwards for the calls and upwards for the returns as in the textbook\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "print(power(2,5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "262144\n"
     ]
    }
   ],
   "source": [
    "#---------R4-3-------------------\n",
    "def power(x, n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        partial = power(x, n//2)\n",
    "        result = partial*partial\n",
    "        if n%2 == 1:\n",
    "            result *= x\n",
    "        return result\n",
    "\n",
    "\"\"\"\n",
    "For this implementation (x =2, n = 18), the trace is:\n",
    "\n",
    "power(2,18) return 512*512 = 262144\n",
    "    power (2,9) return 2*16*16 = 512\n",
    "        power (2,4)  return 4*4 = 16\n",
    "            power (2,2)  return 2*2 = 4\n",
    "                power (2,1)   return (1*1)*2 = 2\n",
    "                    power (2,0)   return 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "    \n",
    "    \n",
    "    \n",
    "print (power(2,18))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6, 2, 6, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "#-----------R4-4---------------------\n",
    "def reverse(S, start, stop):\n",
    "    if start < stop-1:\n",
    "        S[start], S[stop-1] = S[stop-1], S[start]\n",
    "        reverse(S, start+1, stop-1)\n",
    "        \n",
    "\"\"\"\n",
    "calling reverse on S = [4, 3, 6, 2, 6] (reverse(S, 0, 4) provides:\n",
    "\n",
    "reverse(S, 0, 5)   return None (S is [6, 2, 6, 3, 4] at the return)\n",
    "    produces [6, 3, 6, 2, 4]\n",
    "    recurse(S, 1, 4)    return None (S is [6, 2, 6, 3, 4] at the return)\n",
    "        produces [6, 2, 6, 3, 4]\n",
    "        recurses(S, 2, 3)     return None  (S is [6, 2, 6, 3, 4])\n",
    "            \n",
    "\n",
    "After everything, S is now (S is [6, 2, 6, 3, 4]).  Note that this function changes the original array\n",
    "\n",
    "Note that in this recursion, the swaps happen before the next recursion is called, and the return is none\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "S = [4, 3, 6, 2, 6]\n",
    "reverse(S, 0, 5)\n",
    "print(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'b', 'c']\n",
      "['a', 'b', 'd']\n",
      "['a', 'c', 'b']\n",
      "['a', 'c', 'd']\n",
      "['a', 'd', 'b']\n",
      "['a', 'd', 'c']\n",
      "['b', 'a', 'c']\n",
      "['b', 'a', 'd']\n",
      "['b', 'c', 'a']\n",
      "['b', 'c', 'd']\n",
      "['b', 'd', 'a']\n",
      "['b', 'd', 'c']\n",
      "['c', 'a', 'b']\n",
      "['c', 'a', 'd']\n",
      "['c', 'b', 'a']\n",
      "['c', 'b', 'd']\n",
      "['c', 'd', 'a']\n",
      "['c', 'd', 'b']\n",
      "['d', 'a', 'b']\n",
      "['d', 'a', 'c']\n",
      "['d', 'b', 'a']\n",
      "['d', 'b', 'c']\n",
      "Solution found: ['d', 'b', 'c']\n",
      "['d', 'c', 'a']\n",
      "['d', 'c', 'b']\n"
     ]
    }
   ],
   "source": [
    "#--------------R4-5------------------------\n",
    "#Note that S is our attempt at solving the sequence and U is our set of all possible numbers that are unused\n",
    "def solves(S):\n",
    "    #Note, this is a random solution to the pseudoproblem\n",
    "    return S == ['d','b','c']\n",
    "\n",
    "\n",
    "def PuzzleSolver(k, S, U):\n",
    "    for e in sorted(U).copy():\n",
    "        S.append(e)\n",
    "        U.remove(e)\n",
    "        if k==1:\n",
    "            print(S)\n",
    "            if solves(S):\n",
    "                print( f'Solution found: {S}')\n",
    "        else:\n",
    "            PuzzleSolver(k-1, S, U)\n",
    "        U.add(S.pop())  #removes the last item of an array\n",
    "        \n",
    "        \n",
    "\"\"\"\n",
    "Note: It would be very difficult to draw the entire recursive trace so I'm outputting the order of the calls\n",
    "\n",
    "Also note: a set is unordered, so the order in which you would get these outputs is not guaranteed.\n",
    "I have ordered the set for this example\n",
    "\n",
    "PuzzleSolver(3, [], {'a','b','c','d'})\n",
    "    PuzzleSolver(2, [a], {'b','c','d'})\n",
    "        PuzzleSolver(1, ['a','b'], {'c','d'})\n",
    "            Tests ['a','b','c'] and ['a', 'b', 'd'] and returns None\n",
    "        PuzzleSolver(1, ['a','c'], {'b','d'})\n",
    "            Tests ['a', 'c', 'b'] and ['a','c','d'] then returns None\n",
    "            \n",
    "        .....\n",
    "        \n",
    "        \n",
    "    PuzzleSolver(2, [b], {'a','c','d'})\n",
    "        ....\n",
    "        \n",
    "    PuzzleSolver(2, [c], {'a','b','d'})\n",
    "    \n",
    "        ...\n",
    "    PuzzleSolver(2, [d], {'a','b','c'})\n",
    "        ...\n",
    "        \n",
    "        PuzzleSolver(1, ['d','c'], {'a','b'})\n",
    "            Tests ['d', 'c', 'a'] and ['d','c','b'] then returns None\n",
    "            \n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "PuzzleSolver(3, [], {'a','b','c','d'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.9289682539682538\n"
     ]
    }
   ],
   "source": [
    "#----------R4-6----------------\n",
    "\"\"\"\n",
    "Note, we want 1/1 + 1/2 + 1/3 ... 1/i\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "def harmonic_recursive(n):\n",
    "    if n==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return 1/n + harmonic_recursive(n-1)\n",
    "    \n",
    "\n",
    "\"\"\"\n",
    "This will run in O(n) time and require O(n) space\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "    \n",
    "    \n",
    "    \n",
    "print(harmonic_recursive(10))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12342543 <class 'int'>\n"
     ]
    }
   ],
   "source": [
    "#----------R4-7---------------------\n",
    "\"\"\"\n",
    "Note, we can solve this by knowing that a number can be decomposed into:\n",
    "a*1e0 + a2*1e1 + a3*1e2, etc...\n",
    "\n",
    "So 123 is\n",
    "1*1 + 2*10 + 3*100\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "def str_2_int(string, index = 0):\n",
    "    length = len(string)\n",
    "    if index == length-1:\n",
    "        return int(string[index])\n",
    "    else:\n",
    "        return int(string[index])*10**(length-index-1) + str_2_int(string, index+1)\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "This runs in 0(n) time and space\n",
    "\n",
    "\"\"\" \n",
    "    \n",
    "ans = str_2_int('12342543')\n",
    "print (ans, type(ans))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28\n",
      "Your array must be a length that is a power of 2\n"
     ]
    }
   ],
   "source": [
    "#---------------R4-8---------------------\n",
    "import math\n",
    "\n",
    "def isabel_method(A):\n",
    "    assert math.log(len(A),2)%1 == 0, 'Your array must be a length that is a power of 2'\n",
    "    if len(A) == 1:\n",
    "        return A[0]\n",
    "    else:\n",
    "        B = [None]*(len(A)//2)\n",
    "        for i in range(len(B)):\n",
    "            B[i] = A[2*i] + A[2*i-1]           \n",
    "        return isabel_method(B)\n",
    "\n",
    "\"\"\"\n",
    "The recursion will be called log(n) times, since the array is divided in half each time\n",
    "\n",
    "\n",
    "Each call will require you to access all of the remaining elements, which means it will be\n",
    "n + n/2 + n/4 + ...\n",
    "\n",
    "This is equal to n* Sum(1/2**i), which is <2n\n",
    "\n",
    "Therefore, the running time is O(n), although a much slower implementation than just adding them up element by element\n",
    "\n",
    "\"\"\"\n",
    "    \n",
    "                \n",
    "print(isabel_method([0, 1,2,3,4,5,6,7]))\n",
    "try:\n",
    "    print(isabel_method([1,2,3,4,5,6,7]))\n",
    "except Exception as e:\n",
    "    print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creativity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 8)\n",
      "(-45, 774)\n",
      "(1, 8)\n"
     ]
    }
   ],
   "source": [
    "#----------C4-9------------------------------\n",
    "#Note, this is similar to R4-1\n",
    "\n",
    "def min_max(S, index=0):\n",
    "    if index == len(S)-1:\n",
    "        return S[index], S[index]  #The current min and max values\n",
    "    else:\n",
    "        min_c, max_c = min_max(S, index+1)\n",
    "        return min(S[index], min_c), max(S[index], max_c)\n",
    "    \n",
    "    \n",
    "print(min_max([1,2,3,4,5,6,7,8]))\n",
    "print(min_max([-45,2,774,5,6,7,8]))\n",
    "print(min_max([8,7,6,5,4,3,2,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 6 6.643856189774725\n",
      "5 2 2.321928094887362\n",
      "7 2 2.807354922057604\n",
      "1.9 0 0.925999418556223\n",
      "0.1 0 -3.321928094887362\n",
      "6 2 2.584962500721156\n"
     ]
    }
   ],
   "source": [
    "#------------C4-10------------------------\n",
    "import math\n",
    "def log_2_int(n):\n",
    "    if n<2:\n",
    "        return 0   #If you are less than 2, you don't get to accumulate any more divisions.  Note it isn't <=2\n",
    "    else:\n",
    "        return 1+log_2_int(n//2)\n",
    "     \n",
    "\n",
    "for n in [100, 5, 7, 1.9, 0.1, 6]:\n",
    "    print(n, log_2_int(n), math.log(n, 2))\n",
    "\n",
    "\"\"\"\n",
    "Note, it fails at numbers less than 1. You could detect this and set n = 1/n, but since you can only\n",
    "use integer division, there are some errors (ex. 1//0.1 = 9.0) so it's not worth going into\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#------------C4-11----------------------\n",
    "\"\"\"\n",
    "Note, the easiest way is to use a set or dictionary, but I'm not sure we're allowed to do that for this assignment \n",
    "(Otherwise it's easy to do this in O(n))\n",
    "\n",
    "Based on the hint, we are recommended to check if the first element is different from the rest, which \n",
    "would produce n-1 + n-2 + .... 1 comparisons, which would add up to  (n)(n+1)/2- n = (n-1)(n)/2\n",
    "which is O(n)\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "def unique_no_dictionary(S, index = 0):\n",
    "    if index == len(S)-1:\n",
    "        return True    #The trivial case is true\n",
    "    else:\n",
    "        unique = True\n",
    "        for i in range(index+1, len(S)):\n",
    "            if S[index] == S[i]: unique = False\n",
    "        #Note, this return will short-circuit if unique is False, therefore saving time\n",
    "        return unique and unique_no_dictionary(S, index+1)\n",
    "    \n",
    "for S in [[1,2,3,4,5,6], \n",
    "          [3,4,5,2,3,4,6,7],\n",
    "          [234,654,32,543,652]\n",
    "         ]:\n",
    "    print(unique_no_dictionary(S))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The product of 1 and 2 is 2\n",
      "The product of 3 and 6 is 18\n",
      "The product of 10 and 10 is 100\n"
     ]
    }
   ],
   "source": [
    "#-----------C4-12----------------------\n",
    "#Note, this only works for positive integers since I don't know if we're allowed to use > or asserts\n",
    "\n",
    "def prod(m, n):\n",
    "    if not n: #ie. if n==0\n",
    "        return 0\n",
    "    else:\n",
    "        return m + prod(m, n-1)\n",
    "    \n",
    "for x, y in [(1,2),\n",
    "             (3,6),\n",
    "             (10, 10)\n",
    "            ]:\n",
    "    print (f'The product of {x} and {y} is {prod(x, y)}')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#-------------C4-13--------------------\n",
    "\"\"\"\n",
    "F(0) = 2 + 0 - 2 = 0\n",
    "More base cases (unnecessary):\n",
    "    F(1) = 4 - 1 - 2 = 1\n",
    "    F(2) = 8 - 2 - 2 = 4\n",
    "    \n",
    "\n",
    "When you add 1 to c, you draw 2 iterations of the previous -> 2*F(c-1) and 1 line of length C\n",
    "\n",
    "Therefore F(C) = 2*(2**(c+1-1) - (c-1) -2) + c = 2**(c+1) - 2*(c-1) - 4 + c\n",
    "\n",
    "2**(c+1) - 2*(c-1) - 4 + c \n",
    "= 2**(c+1) - 2c +2 -4 +c\n",
    "= 2**(c+1) -c -2 as required\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t  0\t\t  \t\t  \t\n",
      "\t  1\t\t  \t\t  \t\n",
      "\t  2\t\t  \t\t  \t\n",
      "\t  3\t\t  \t\t  \t\n",
      "\t  4\t\t  \t\t  \t\n",
      "\t_____\t\t_____\t\t_____\t\n",
      "\t  1\t\t  2\t\t  3\t\n",
      "\n",
      "This took a total of 31 moves!\n"
     ]
    }
   ],
   "source": [
    "#---------C4-14-----------------------\n",
    "import time\n",
    "from IPython.display import clear_output\n",
    "\n",
    "class TowerOfHanoi():\n",
    "    def __init__(self, n=4):\n",
    "        self._n = n\n",
    "        self._array = [[], [], list(reversed(range(n)))]\n",
    "        self._lengths = [0, 0, n]\n",
    "        \n",
    "    def draw_towers(self):\n",
    "        rows = []\n",
    "        rows.append(['\\t  1\\t', '\\t  2\\t', '\\t  3\\t'])\n",
    "        rows.append(['\\t_____\\t', '\\t_____\\t', '\\t_____\\t'])\n",
    "        for i in range(max(self._lengths)):\n",
    "            row = []\n",
    "            for j in range(3):\n",
    "                if i<self._lengths[j]:\n",
    "                    row.append('\\t  ' + str(self._array[j][i]) + '\\t')\n",
    "                else:\n",
    "                    row.append('\\t  \\t')\n",
    "            rows.append(row)\n",
    "        \n",
    "        \n",
    "        for r in reversed(rows):\n",
    "            print(''.join(r))\n",
    "            \n",
    "    def __getitem__(self, index):\n",
    "        return self._array[index]\n",
    "    \n",
    "    def pop(self, index):\n",
    "        self._lengths[index] -= 1\n",
    "        return self[index].pop()\n",
    "    \n",
    "    \n",
    "    def getlen(self):\n",
    "        return self._lengths\n",
    "    \n",
    "    \n",
    "    def __setitem__(self, index, value):\n",
    "        if self[index] and self[index][-1] < value:\n",
    "            raise ValueError (f'Illegal move.  Cannot place block with size {value} on block {self[index][-1]}')\n",
    "        else: \n",
    "            self[index].append(value)\n",
    "            self._lengths[index] += 1\n",
    "    \n",
    "    def _move_stack(self, n_disks, start_peg, help_peg, target_peg):\n",
    "        time.sleep(0.5)\n",
    "        clear_output()\n",
    "        self.draw_towers()\n",
    "        \n",
    "        if n_disks == 1:\n",
    "            self._count += 1\n",
    "            value = self.pop(start_peg)\n",
    "            try:\n",
    "                self[target_peg] = value\n",
    "            except Exception as e:\n",
    "                print(e)\n",
    "                self[start_peg]\n",
    "        \n",
    "        else:\n",
    "            #Move the upper stack to the helper peg\n",
    "            self._move_stack(n_disks-1, start_peg, target_peg, help_peg)\n",
    "            #Move the lowest item to the target peg\n",
    "            self._move_stack(1, start_peg, help_peg, target_peg)\n",
    "            #Move the upper stack to the target peg\n",
    "            self._move_stack(n_disks-1, help_peg, start_peg, target_peg)\n",
    "            \n",
    "    \n",
    "    def solve_hanoi(self):\n",
    "        self._count = 0\n",
    "        self._move_stack(self.getlen()[2], 2, 1, 0)\n",
    "        \n",
    "        time.sleep(0.5)\n",
    "        clear_output()\n",
    "        self.draw_towers()\n",
    "        \n",
    "        print(f'\\nThis took a total of {self._count} moves!')\n",
    "        \n",
    "        \n",
    "            \n",
    "t = TowerOfHanoi(5)\n",
    "t.solve_hanoi()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{  }\n",
      "{ 1 }\n",
      "{ 2 }\n",
      "{ 2, 1 }\n",
      "{ 3 }\n",
      "{ 3, 1 }\n",
      "{ 3, 2 }\n",
      "{ 3, 2, 1 }\n",
      "{ 4 }\n",
      "{ 4, 1 }\n",
      "{ 4, 2 }\n",
      "{ 4, 2, 1 }\n",
      "{ 4, 3 }\n",
      "{ 4, 3, 1 }\n",
      "{ 4, 3, 2 }\n",
      "{ 4, 3, 2, 1 }\n",
      "{ 5 }\n",
      "{ 5, 1 }\n",
      "{ 5, 2 }\n",
      "{ 5, 2, 1 }\n",
      "{ 5, 3 }\n",
      "{ 5, 3, 1 }\n",
      "{ 5, 3, 2 }\n",
      "{ 5, 3, 2, 1 }\n",
      "{ 5, 4 }\n",
      "{ 5, 4, 1 }\n",
      "{ 5, 4, 2 }\n",
      "{ 5, 4, 2, 1 }\n",
      "{ 5, 4, 3 }\n",
      "{ 5, 4, 3, 1 }\n",
      "{ 5, 4, 3, 2 }\n",
      "{ 5, 4, 3, 2, 1 }\n"
     ]
    }
   ],
   "source": [
    "#---------------C4-15-----------------------------\n",
    "\"\"\"\n",
    "Here, we want combinations, not permutations\n",
    "\n",
    "\n",
    "We rely on the addition of an empty set value 'UNK'\n",
    "\n",
    "For each stage of the recursion, we add one more value from the sequence\n",
    "and for each current item either add another UNK or that value\n",
    "\n",
    "The final layer of that tree will contain exactly one copy of each unique set\n",
    "\n",
    "\"\"\"\n",
    "UNK = chr(1000)\n",
    "\n",
    "\n",
    "\n",
    "def sub_rec(U, S):\n",
    "    \"\"\"\n",
    "    U is the current set\n",
    "    S is the remaining sequence\n",
    "    \"\"\"\n",
    "    if len(S) == 0:\n",
    "        print('{', str([x for x in U if x!= UNK])[1:-1], '}')\n",
    "        \n",
    "    else:\n",
    "        val = S.pop()\n",
    "        U.append(UNK)\n",
    "        sub_rec(U, S)\n",
    "        U.pop()\n",
    "        \n",
    "        U.append(val)\n",
    "        sub_rec(U, S)\n",
    "        U.pop()\n",
    "        S.append(val)\n",
    "\n",
    "def print_subsets (U):\n",
    "    sub_rec([], list(U))\n",
    "    \n",
    "    \n",
    "print_subsets({1,2,3,4,5})\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'snap&stop'"
      ]
     },
     "execution_count": 255,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#----------C4-16---------------------\n",
    "def reversestring(S, index = 0):\n",
    "    if index == len(S)-1:\n",
    "        return [S[index]]\n",
    "    else:\n",
    "        ans = reversestring(S, index + 1)\n",
    "        ans.append (S[index])\n",
    "        if index == 0:\n",
    "            ans = ''.join(ans)\n",
    "        return ans\n",
    "\n",
    "    \n",
    "reversestring('pots&pans')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 261,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True racecar\n",
      "True gohangasalamiimalasagnahog\n",
      "False notapalindrome\n",
      "True bob\n",
      "True a\n",
      "False hat\n"
     ]
    }
   ],
   "source": [
    "#--------------C4-17------------------\n",
    "\"\"\"\n",
    "Note: if a sequence is a palindrome and has an odd number of characters, the middle character has no duplicate\n",
    "Otherwise, the middle two characters should be identical\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "def palindrome_checker(S, index = 0):\n",
    "    l = len(S)\n",
    "    if l == 1:\n",
    "        return True\n",
    "    \n",
    "    elif index >= l//2:\n",
    "        #You actually want the (last index + 1)//2, but since the last index is l-1, it becomes (l+1-1)//2, or just l//2\n",
    "        return S[index] == S[l//2]   #For odd this will be the same index, for even it will not be\n",
    "      \n",
    "    else:\n",
    "        #Note, you want to put the terms in this order to shortcircuit the recursive check.  If it's going to fail, it's\n",
    "        #likely to fail around the first few indices in most normal cases\n",
    "        return (S[index] == S[l-index-1]) and palindrome_checker(S, index+1)\n",
    "    \n",
    "    \n",
    "    \n",
    "strings_list = ['racecar', 'gohangasalamiimalasagnahog', 'notapalindrome', 'bob', 'a', 'hat']\n",
    "\n",
    "for s in strings_list:\n",
    "    print (palindrome_checker(s), s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 270,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are more consonants by 1 racecar\n",
      "There are more consonants by 2 gohangasalamiimalasagnahog\n",
      "There are more consonants by 2 notapalindrome\n",
      "There are more consonants by 1 bob\n",
      "There are more vowells by -1 a\n",
      "There are more consonants by 1 hat\n"
     ]
    }
   ],
   "source": [
    "#---------------C4-18------------\n",
    "\"\"\"\n",
    "Two approaches:\n",
    "1) Actually count all the vowell and consonants and return two values\n",
    "2) Have a common counter that increments if it sees a consonant and decrements if it sees a vowell\n",
    "    It's sign will tell you which is more.\n",
    "    I'll fo the second because it's more unique\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "VOWELLS = {'a','e','i','o','u'}\n",
    "\n",
    "def c_or_v(S, index = 0):\n",
    "    a = -1 if S[index] in VOWELLS else 1\n",
    "    if index == len(S)-1:\n",
    "        return a\n",
    "    else:\n",
    "        return (a+ c_or_v(S, index +1))\n",
    "    \n",
    "def check_vowells(S):\n",
    "    ans = c_or_v(S)\n",
    "    if ans>0:\n",
    "        return (f'There are more consonants by {ans}')\n",
    "    elif ans<0:\n",
    "        return (f'There are more vowells by {ans}')\n",
    "    else:\n",
    "        return (f'There are an equal number of each {ans}')\n",
    "    \n",
    "    \n",
    "strings_list = ['racecar', 'gohangasalamiimalasagnahog', 'notapalindrome', 'bob', 'a', 'hat', ]\n",
    "\n",
    "for s in strings_list:\n",
    "    print (check_vowells(s), s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 284,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Two lists approach\n",
      "[8, 6, 4, 2, 7, 5, 3, 1]\n",
      "[46, 4, 23, 45, 3, 765, 5, 23, 65, 3]\n",
      "[1]\n",
      "[2, 2]\n",
      "\n",
      "\n",
      "Adding each element approach\n",
      "[2, 4, 6, 8, 7, 5, 3, 1]\n",
      "[4, 46, 23, 45, 3, 765, 5, 23, 65, 3]\n",
      "[1]\n",
      "[2, 2]\n"
     ]
    }
   ],
   "source": [
    "#--------------C4-18-----------------\n",
    "\"\"\"\n",
    "Approaches:\n",
    "1) Two lists that you join at the end\n",
    "2) Add new even numbers to the front and odd ones to the back\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "def evenoddbylists(S, index=0):\n",
    "    if index == len(S)-1:\n",
    "        if len(S) == 1:\n",
    "            return S\n",
    "        elif S[index]%2==0:\n",
    "            return [S[index]], []\n",
    "        else:\n",
    "            return [], [S[index]]  \n",
    "    else:\n",
    "        evens, odds = evenoddbylists(S, index+1)\n",
    "        if S[index] %2 == 0: evens.append(S[index])\n",
    "        else: odds.append(S[index])\n",
    "        if index == 0: return evens+odds\n",
    "        else: return evens, odds\n",
    "        \n",
    "        \n",
    "def evenoddbyappending(S, index=0):\n",
    "    if index == len(S)-1:\n",
    "        return [S[index]]\n",
    "    \n",
    "    else:\n",
    "        if S[index]%2 == 1: #If odd, we want to add it to the end of the list\n",
    "            return evenoddbyappending(S, index+1) + [S[index]]\n",
    "        else:\n",
    "            return [S[index]] + evenoddbyappending(S, index+1)\n",
    "        \n",
    "    \n",
    "    \n",
    "sequences = [[1,2,3,4,5,6,7,8], [4,3,65,23,5,46,765,3,45,23], [1], [2,2]]\n",
    "print('Two lists approach')\n",
    "for s in sequences:\n",
    "    print(evenoddbylists(s))\n",
    "    \n",
    "    \n",
    "print('\\n\\nAdding each element approach')\n",
    "for s in sequences:\n",
    "    print(evenoddbyappending(s))\n",
    "    \n",
    "    \n",
    "\"\"\"\n",
    "Final notes: the second approach is not desirable with lists because it is O(n) due to the fact that\n",
    "appending an entire list of length m to another requires O(m) time.  This could be solved with Linked Lists when \n",
    "we get to that part of the book\n",
    "\n",
    "\n",
    "Note also that both answers are correct, but the numbers are in a different order\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 307,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Splitting by:  0 produces [10, 9, 8, 7, 6, 5, 4, 33, 2, 11]\n",
      "Splitting by:  2 produces [2, 10, 9, 8, 7, 6, 5, 4, 33, 11]\n",
      "Splitting by:  4 produces [2, 4, 10, 9, 8, 7, 6, 5, 33, 11]\n",
      "Splitting by:  6 produces [5, 4, 2, 6, 10, 9, 8, 7, 33, 11]\n",
      "Splitting by:  8 produces [7, 6, 5, 4, 2, 8, 10, 9, 33, 11]\n",
      "Splitting by:  10 produces [9, 8, 7, 6, 5, 4, 2, 10, 33, 11]\n",
      "Splitting by:  12 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  14 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  16 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  18 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  20 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  22 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  24 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  26 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n",
      "Splitting by:  28 produces [10, 9, 8, 7, 6, 5, 4, 2, 11, 33]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\"\\nNote, it's easier to troubleshoot if you output the three lists seperately\\n\\nThis should run in O(n) time.\\nIt relies on O(n) calls to the recursive function, each requiring O(1) time since we're adding at the end\\nThe final concatenation of all the lists uses O(n) time, but this only happens once\\n\\nTherefore O(n)*O(1) + O(n) is O(n)\\n\\n\\n\""
      ]
     },
     "execution_count": 307,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#-------------C4-20--------------------\n",
    "\"\"\"\n",
    "Note: we can use the same approachs as before to do this in either O(n) time or O(n^2) time\n",
    "Let's choose the O(n) approach\n",
    "\n",
    "The major difference is that we need a third list for just k\n",
    "\"\"\"\n",
    "\n",
    "#There are issues adding a [a] + [], so this circumvents the problem\n",
    "def add_lists(a,b):\n",
    "    if a and b:\n",
    "        return a+b\n",
    "    else:\n",
    "        return b or a #if one of them is [], return the other\n",
    "    \n",
    "\n",
    "\n",
    "def split_by_k(S, k, index=0):\n",
    "    if len(S)==1:\n",
    "        return S \n",
    "        \n",
    "    elif index == len(S)-1:    #we use this line for too many of these exercises...\n",
    "        if S[index] <k:\n",
    "            return [S[index]], [], []\n",
    "        elif S[index] >k:\n",
    "            return [], [], [S[index]]\n",
    "        else:\n",
    "            return [], [S[index]], []  #Should return k in the middle list\n",
    "        \n",
    "    else:\n",
    "        low, med, high = split_by_k(S, k, index+1)\n",
    "        if S[index] <k:\n",
    "            low = add_lists(low, [S[index]])\n",
    "        elif S[index] >k:\n",
    "            high = add_lists(high, [S[index]])\n",
    "        else:\n",
    "            med = add_lists(med, [S[index]])\n",
    "            \n",
    "        if index == 0:\n",
    "            return add_lists(low, add_lists(med, high)) #This is not very elegant...\n",
    "        else:\n",
    "            return low, med, high\n",
    "            \n",
    "\n",
    "sequence = [11,2,33,4,5,6,7,8,9,10]\n",
    "\n",
    "for i in range(0, 30, 2):\n",
    "    print('Splitting by: ', i, 'produces', split_by_k(sequence, i))\n",
    "\n",
    "\"\"\"\n",
    "Note, it's easier to troubleshoot if you output the three lists seperately\n",
    "\n",
    "This should run in O(n) time.\n",
    "It relies on O(n) calls to the recursive function, each requiring O(1) time since we're adding at the end\n",
    "The final concatenation of all the lists uses O(n) time, but this only happens once\n",
    "\n",
    "Therefore O(n)*O(1) + O(n) is O(n)\n",
    "\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 315,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For the value 0, the resulting pair is None\n",
      "For the value 1, the resulting pair is None\n",
      "For the value 2, the resulting pair is None\n",
      "For the value 3, the resulting pair is (1, 2)\n",
      "For the value 4, the resulting pair is (1, 3)\n",
      "For the value 5, the resulting pair is (2, 3)\n",
      "For the value 6, the resulting pair is (2, 4)\n",
      "For the value 7, the resulting pair is (3, 4)\n",
      "For the value 8, the resulting pair is (3, 5)\n",
      "For the value 9, the resulting pair is (4, 5)\n",
      "For the value 10, the resulting pair is (4, 6)\n",
      "For the value 11, the resulting pair is (5, 6)\n",
      "For the value 12, the resulting pair is (5, 7)\n",
      "For the value 13, the resulting pair is (6, 7)\n",
      "For the value 14, the resulting pair is (6, 8)\n",
      "For the value 15, the resulting pair is (7, 8)\n",
      "For the value 16, the resulting pair is None\n",
      "For the value 17, the resulting pair is None\n",
      "For the value 18, the resulting pair is None\n",
      "For the value 19, the resulting pair is None\n"
     ]
    }
   ],
   "source": [
    "#----------------C4-21----------------------\n",
    "\"\"\"\n",
    "Note: there is a brute force approach, but we will use the one with dictionaries instead\n",
    "\n",
    "\n",
    "Additional Note: I learned an important thing about using mutable objects as defaults in python\n",
    "Successive calls used the growing key_set, rather than initializing it as set() every time.\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "#The following line is the wrong way to do the initialization...\n",
    "#def find_pair(S, target, key_set = set(), index=0):\n",
    "\n",
    "def find_pair(S, target, key_set = None, index=0):\n",
    "    if key_set is None:\n",
    "        key_set = set()\n",
    "    \n",
    "    \n",
    "    key = target - S[index]\n",
    "    if len(S) <= 1:\n",
    "        return None\n",
    "    \n",
    "    elif index == len(S)-1:\n",
    "        if key in key_set: return (key, S[index])\n",
    "        else: return None\n",
    "        \n",
    "    else:\n",
    "        if key in key_set: return (key, S[index])\n",
    "        else:\n",
    "            key_set.add(S[index])\n",
    "            return find_pair(S, target, key_set, index+1)\n",
    "        \n",
    "    \n",
    "sequence = [1,2,3,4,5,6,7,8]\n",
    "\n",
    "for i in range(20):\n",
    "    print(f'For the value {i}, the resulting pair is {find_pair(sequence, i)}')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 387,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " 8192 8192\n",
      "\n",
      " 32768 32768\n",
      "\n",
      " 14348907 14348907\n",
      "\n",
      " 10000000 10000000\n",
      "\n",
      " 32 32\n"
     ]
    }
   ],
   "source": [
    "#--------------C4-22---------------------\n",
    "\"\"\"\n",
    "Note: this one took me a long time.  The secret is that we want to do the extra odd multiplications in reverse order\n",
    "than you would get using the traditional:\n",
    "\n",
    "    while factor>0:\n",
    "        partial *= partial\n",
    "        if factor%2 == 1:\n",
    "            partial *= x\n",
    "        factor = factor//2\n",
    "    return partial\n",
    "    \n",
    "This will work in many cases, but not all.  Instead, you have to read in the sequence of odds backwards, which \n",
    "you can do using the bitwise notation (thanks to the hint in the book!)\n",
    "\n",
    "Before that, you need to know how many relevant bits there are in your number, so the initial counter loop is for that\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def power_loop(x, n):\n",
    "    factor = n\n",
    "    partial = 1\n",
    "    \n",
    "    counter = 0\n",
    "    while factor:\n",
    "        factor = factor >>1\n",
    "        counter += 1\n",
    "    \n",
    "    while counter+1:\n",
    "        partial *= partial\n",
    "        if n>>counter&1:\n",
    "            partial *= x        \n",
    "        counter -=1\n",
    "    return partial\n",
    "        \n",
    "    \n",
    "    \n",
    "combos = [ (2,13), (2, 15), (3, 15), (10, 7), (2, 5)]\n",
    "for b, p in combos:\n",
    "    print('\\n', power_loop(b, p), b**p)\n",
    "        \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Projects"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 395,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SampleFiles/Ch4FileStructure\\Folder1\\Subfolder\\target.txt\n",
      "SampleFiles/Ch4FileStructure\\Folder2\\target.txt\n"
     ]
    }
   ],
   "source": [
    "#------------P4-23-----------------------\n",
    "import os\n",
    "\"\"\"\n",
    "The os functions that we are given are:\n",
    "os.path.getsize(path)\n",
    "os.path.isdir(path)\n",
    "os.listdir(path)\n",
    "os.path.join(path, filename)\n",
    "\n",
    "\"\"\"\n",
    "def find(path, filename):\n",
    "    if os.path.isdir(path):\n",
    "        for obj in os.listdir(path):\n",
    "            if os.path.isdir(os.path.join(path, obj)):\n",
    "                find(os.path.join(path, obj), filename)\n",
    "            elif obj == filename:\n",
    "                print(os.path.join(path, obj))\n",
    "                \n",
    "                \n",
    "find(r'SampleFiles/Ch4FileStructure', 'target.txt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 429,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "One solution is: 31 + 4986 = 5017.  Check:5017\n",
      "Dictionary is : {'b': 0, 'o': 3, 'y': 1, 'g': 4, 'i': 9, 'r': 8, 'l': 6, 'a': 5, 's': 7}\n",
      "\n",
      "\n",
      "One solution is: 31 + 6984 = 7015.  Check:7015\n",
      "Dictionary is : {'b': 0, 'o': 3, 'y': 1, 'g': 6, 'i': 9, 'r': 8, 'l': 4, 'a': 7, 's': 5}\n",
      "\n",
      "\n",
      "One solution is: 41 + 2975 = 3016.  Check:3016\n",
      "Dictionary is : {'b': 0, 'o': 4, 'y': 1, 'g': 2, 'i': 9, 'r': 7, 'l': 5, 'a': 3, 's': 6}\n",
      "\n",
      "\n",
      "One solution is: 41 + 5972 = 6013.  Check:6013\n",
      "Dictionary is : {'b': 0, 'o': 4, 'y': 1, 'g': 5, 'i': 9, 'r': 7, 'l': 2, 'a': 6, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 42 + 5981 = 6023.  Check:6023\n",
      "Dictionary is : {'b': 0, 'o': 4, 'y': 2, 'g': 5, 'i': 9, 'r': 8, 'l': 1, 'a': 6, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 42 + 6981 = 7023.  Check:7023\n",
      "Dictionary is : {'b': 0, 'o': 4, 'y': 2, 'g': 6, 'i': 9, 'r': 8, 'l': 1, 'a': 7, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 42 + 6983 = 7025.  Check:7025\n",
      "Dictionary is : {'b': 0, 'o': 4, 'y': 2, 'g': 6, 'i': 9, 'r': 8, 'l': 3, 'a': 7, 's': 5}\n",
      "\n",
      "\n",
      "One solution is: 51 + 2967 = 3018.  Check:3018\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 1, 'g': 2, 'i': 9, 'r': 6, 'l': 7, 'a': 3, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 51 + 3967 = 4018.  Check:4018\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 1, 'g': 3, 'i': 9, 'r': 6, 'l': 7, 'a': 4, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 51 + 7962 = 8013.  Check:8013\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 1, 'g': 7, 'i': 9, 'r': 6, 'l': 2, 'a': 8, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 51 + 7963 = 8014.  Check:8014\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 1, 'g': 7, 'i': 9, 'r': 6, 'l': 3, 'a': 8, 's': 4}\n",
      "\n",
      "\n",
      "One solution is: 52 + 3976 = 4028.  Check:4028\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 2, 'g': 3, 'i': 9, 'r': 7, 'l': 6, 'a': 4, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 53 + 1984 = 2037.  Check:2037\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 3, 'g': 1, 'i': 9, 'r': 8, 'l': 4, 'a': 2, 's': 7}\n",
      "\n",
      "\n",
      "One solution is: 53 + 6981 = 7034.  Check:7034\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 3, 'g': 6, 'i': 9, 'r': 8, 'l': 1, 'a': 7, 's': 4}\n",
      "\n",
      "\n",
      "One solution is: 54 + 2987 = 3041.  Check:3041\n",
      "Dictionary is : {'b': 0, 'o': 5, 'y': 4, 'g': 2, 'i': 9, 'r': 8, 'l': 7, 'a': 3, 's': 1}\n",
      "\n",
      "\n",
      "One solution is: 61 + 2957 = 3018.  Check:3018\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 1, 'g': 2, 'i': 9, 'r': 5, 'l': 7, 'a': 3, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 61 + 3957 = 4018.  Check:4018\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 1, 'g': 3, 'i': 9, 'r': 5, 'l': 7, 'a': 4, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 61 + 7952 = 8013.  Check:8013\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 1, 'g': 7, 'i': 9, 'r': 5, 'l': 2, 'a': 8, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 61 + 7953 = 8014.  Check:8014\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 1, 'g': 7, 'i': 9, 'r': 5, 'l': 3, 'a': 8, 's': 4}\n",
      "\n",
      "\n",
      "One solution is: 63 + 1975 = 2038.  Check:2038\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 3, 'g': 1, 'i': 9, 'r': 7, 'l': 5, 'a': 2, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 64 + 1983 = 2047.  Check:2047\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 4, 'g': 1, 'i': 9, 'r': 8, 'l': 3, 'a': 2, 's': 7}\n",
      "\n",
      "\n",
      "One solution is: 64 + 2981 = 3045.  Check:3045\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 4, 'g': 2, 'i': 9, 'r': 8, 'l': 1, 'a': 3, 's': 5}\n",
      "\n",
      "\n",
      "One solution is: 65 + 3987 = 4052.  Check:4052\n",
      "Dictionary is : {'b': 0, 'o': 6, 'y': 5, 'g': 3, 'i': 9, 'r': 8, 'l': 7, 'a': 4, 's': 2}\n",
      "\n",
      "\n",
      "One solution is: 71 + 2945 = 3016.  Check:3016\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 1, 'g': 2, 'i': 9, 'r': 4, 'l': 5, 'a': 3, 's': 6}\n",
      "\n",
      "\n",
      "One solution is: 71 + 5942 = 6013.  Check:6013\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 1, 'g': 5, 'i': 9, 'r': 4, 'l': 2, 'a': 6, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 72 + 3956 = 4028.  Check:4028\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 2, 'g': 3, 'i': 9, 'r': 5, 'l': 6, 'a': 4, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 73 + 1965 = 2038.  Check:2038\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 3, 'g': 1, 'i': 9, 'r': 6, 'l': 5, 'a': 2, 's': 8}\n",
      "\n",
      "\n",
      "One solution is: 75 + 2981 = 3056.  Check:3056\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 5, 'g': 2, 'i': 9, 'r': 8, 'l': 1, 'a': 3, 's': 6}\n",
      "\n",
      "\n",
      "One solution is: 75 + 3981 = 4056.  Check:4056\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 5, 'g': 3, 'i': 9, 'r': 8, 'l': 1, 'a': 4, 's': 6}\n",
      "\n",
      "\n",
      "One solution is: 76 + 2985 = 3061.  Check:3061\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 6, 'g': 2, 'i': 9, 'r': 8, 'l': 5, 'a': 3, 's': 1}\n",
      "\n",
      "\n",
      "One solution is: 76 + 3985 = 4061.  Check:4061\n",
      "Dictionary is : {'b': 0, 'o': 7, 'y': 6, 'g': 3, 'i': 9, 'r': 8, 'l': 5, 'a': 4, 's': 1}\n",
      "\n",
      "\n",
      "One solution is: 81 + 4936 = 5017.  Check:5017\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 1, 'g': 4, 'i': 9, 'r': 3, 'l': 6, 'a': 5, 's': 7}\n",
      "\n",
      "\n",
      "One solution is: 81 + 6934 = 7015.  Check:7015\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 1, 'g': 6, 'i': 9, 'r': 3, 'l': 4, 'a': 7, 's': 5}\n",
      "\n",
      "\n",
      "One solution is: 82 + 5941 = 6023.  Check:6023\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 2, 'g': 5, 'i': 9, 'r': 4, 'l': 1, 'a': 6, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 82 + 6941 = 7023.  Check:7023\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 2, 'g': 6, 'i': 9, 'r': 4, 'l': 1, 'a': 7, 's': 3}\n",
      "\n",
      "\n",
      "One solution is: 82 + 6943 = 7025.  Check:7025\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 2, 'g': 6, 'i': 9, 'r': 4, 'l': 3, 'a': 7, 's': 5}\n",
      "\n",
      "\n",
      "One solution is: 83 + 1954 = 2037.  Check:2037\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 3, 'g': 1, 'i': 9, 'r': 5, 'l': 4, 'a': 2, 's': 7}\n",
      "\n",
      "\n",
      "One solution is: 83 + 6951 = 7034.  Check:7034\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 3, 'g': 6, 'i': 9, 'r': 5, 'l': 1, 'a': 7, 's': 4}\n",
      "\n",
      "\n",
      "One solution is: 84 + 1963 = 2047.  Check:2047\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 4, 'g': 1, 'i': 9, 'r': 6, 'l': 3, 'a': 2, 's': 7}\n",
      "\n",
      "\n",
      "One solution is: 84 + 2957 = 3041.  Check:3041\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 4, 'g': 2, 'i': 9, 'r': 5, 'l': 7, 'a': 3, 's': 1}\n",
      "\n",
      "\n",
      "One solution is: 84 + 2961 = 3045.  Check:3045\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 4, 'g': 2, 'i': 9, 'r': 6, 'l': 1, 'a': 3, 's': 5}\n",
      "\n",
      "\n",
      "One solution is: 85 + 2971 = 3056.  Check:3056\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 5, 'g': 2, 'i': 9, 'r': 7, 'l': 1, 'a': 3, 's': 6}\n",
      "\n",
      "\n",
      "One solution is: 85 + 3967 = 4052.  Check:4052\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 5, 'g': 3, 'i': 9, 'r': 6, 'l': 7, 'a': 4, 's': 2}\n",
      "\n",
      "\n",
      "One solution is: 85 + 3971 = 4056.  Check:4056\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 5, 'g': 3, 'i': 9, 'r': 7, 'l': 1, 'a': 4, 's': 6}\n",
      "\n",
      "\n",
      "One solution is: 86 + 2975 = 3061.  Check:3061\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 6, 'g': 2, 'i': 9, 'r': 7, 'l': 5, 'a': 3, 's': 1}\n",
      "\n",
      "\n",
      "One solution is: 86 + 3975 = 4061.  Check:4061\n",
      "Dictionary is : {'b': 0, 'o': 8, 'y': 6, 'g': 3, 'i': 9, 'r': 7, 'l': 5, 'a': 4, 's': 1}\n",
      "\n",
      "\n",
      "There are a total of 46 solutions\n"
     ]
    }
   ],
   "source": [
    "#------------P4-24------------------\n",
    "\"\"\"The ones we want to ultimately solve are:\n",
    "pot + pan = bib\n",
    "dog + cat = pig\n",
    "boy+ girl = baby\n",
    "\"\"\"\n",
    "\n",
    "class SummationSolver():\n",
    "    def __init__(self, a, b, c):\n",
    "        self._a = a\n",
    "        self._b = b\n",
    "        self._c = c\n",
    "        self._max_len = len(c) #c cannot be shorter than a or b under the rules\n",
    "        self._count = 0\n",
    "        \n",
    "    def _t2i(self, text, lookup): #text to int\n",
    "        total = 0\n",
    "        length = len(text)\n",
    "        for i in range(length):\n",
    "            total += int(lookup[text[i]])*10**(length-i-1)\n",
    "            \n",
    "        return total\n",
    "\n",
    "\n",
    "    def summation_check(self, a, b, c, U):\n",
    "        \"\"\"\n",
    "        a + b = c using the keys, value pairs in U\n",
    "        \"\"\"\n",
    "        if self._t2i(a, U) + self._t2i(b, U) == self._t2i(c, U):\n",
    "            self._count += 1\n",
    "            print(f'One solution is: {self._t2i(a, U)} + {self._t2i(b, U)} = {self._t2i(c, U)}.  Check:{self._t2i(a, U) + self._t2i(b, U)}')\n",
    "            print('Dictionary is :', U)\n",
    "            print('\\n')\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    \n",
    "    def _solver_r(self, a, b, c, S, index, U, nums):\n",
    "        if index >= len(S):  #Note, this means we are past the final index\n",
    "            #print(U)\n",
    "            return self.summation_check(a, b, c, U)\n",
    "        elif S[index] in U:  #If the next letter in the sequence is already in the dictionary, skip it\n",
    "            return self._solver_r(a,b,c,S,index+1, U, nums) \n",
    "        else:\n",
    "            for number in nums.copy():\n",
    "                U[S[index]] = number\n",
    "                nums.remove(number)\n",
    "                ans = self._solver_r(a,b,c,S, index+1, U, nums)\n",
    "                nums.add(number)\n",
    "                del U[S[index]]\n",
    "                \n",
    "        \n",
    "    \n",
    "    def solve(self):\n",
    "        U = {}\n",
    "        nums = set(range(10))\n",
    "        S = list(self._a) + list(self._b) + list(self._c)\n",
    "        self._count = 0\n",
    "        \n",
    "        self._solver_r(self._a, self._b, self._c, S, 0, U, nums)\n",
    "        \n",
    "        if self._count == 0:\n",
    "            print ('Sorry, no solution found! :(')\n",
    "            \n",
    "        else:\n",
    "            print(f'There are a total of {self._count} solutions')\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "#a = SummationSolver('pot', 'pan', 'bib')\n",
    "a = SummationSolver('boy', 'girl', 'babys')\n",
    "#a = SummationSolver('boy', 'girl', 'babysda')\n",
    "a.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 444,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-\n",
      "--\n",
      "-\n",
      "---\n",
      "-\n",
      "--\n",
      "-\n",
      "----\n",
      "-\n",
      "--\n",
      "-\n",
      "---\n",
      "-\n",
      "--\n",
      "-\n",
      "----\n",
      "-\n",
      "--\n",
      "-\n",
      "---\n",
      "-\n",
      "--\n",
      "-\n",
      "----\n",
      "-\n",
      "--\n",
      "-\n",
      "---\n",
      "-\n",
      "--\n",
      "-\n",
      "----\n",
      "-\n",
      "--\n",
      "-\n",
      "---\n",
      "-\n",
      "--\n",
      "-\n",
      "----\n",
      "-\n",
      "--\n",
      "-\n"
     ]
    }
   ],
   "source": [
    "#------------P4-25-------------------\n",
    "\"\"\"\n",
    "The hint is that we should use a loop from 0 to 2**c -2\n",
    "and that the number of ticks should be one more than the number of consecutive 1s.\n",
    "\n",
    "That's a great hint!\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "def english_ruler(n = 3, repeats = 10):\n",
    "    limit = repeats*(2**n -2)\n",
    "    counter = 0\n",
    "    while counter<=limit:\n",
    "        dashes = 1\n",
    "        sub_counter = counter \n",
    "        while sub_counter & 1:\n",
    "            dashes += 1\n",
    "            sub_counter = sub_counter >> 1\n",
    "        dashes = min (dashes, n)\n",
    "        print('-'*dashes)\n",
    "        counter += 1\n",
    "        \n",
    "english_ruler(4, 3)\n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 445,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t  0\t\t  \t\t  \t\n",
      "\t  1\t\t  \t\t  \t\n",
      "\t  2\t\t  \t\t  \t\n",
      "\t  3\t\t  \t\t  \t\n",
      "\t  4\t\t  \t\t  \t\n",
      "\t  5\t\t  \t\t  \t\n",
      "\t_____\t\t_____\t\t_____\t\n",
      "\t  1\t\t  2\t\t  3\t\n",
      "\n",
      "This took a total of 63 moves!\n"
     ]
    }
   ],
   "source": [
    "#----------------P4-26-----------------------\n",
    "\"\"\"\n",
    "Note, this was solved in C4-14\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "t = TowerOfHanoi(6)\n",
    "t.solve_hanoi()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 463,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('SampleFiles', ['Ch4FileStructure', 'Chapter 2 Books'], ['Chapter1 ExampleText2 (Alice in Wonderland).txt', 'Chapter1ExampleText.txt', 'desktop.ini'])\n",
      "('SampleFiles\\\\Ch4FileStructure', ['Folder1', 'Folder2', 'Folder3'], [])\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder1', ['Subfolder'], ['desktop.ini', 'SampleText1.txt', 'SampleText2.txt', 'SampleText3.txt'])\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder1\\\\Subfolder', [], ['desktop.ini', 'target.txt'])\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder2', [], ['target.txt'])\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder3', [], ['desktop.ini'])\n",
      "('SampleFiles\\\\Chapter 2 Books', [], ['Alice in Wonderland.txt', 'Dracula.txt', 'Frankenstein.txt', 'Pride and Prejudice.txt', 'Ulysses.txt'])\n",
      "\n",
      "\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder1\\\\Subfolder', [], ['desktop.ini', 'target.txt'])\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder1', ['Subfolder'], ['desktop.ini', 'SampleText1.txt', 'SampleText2.txt', 'SampleText3.txt'])\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder2', [], ['target.txt'])\n",
      "('SampleFiles\\\\Ch4FileStructure\\\\Folder3', [], ['desktop.ini'])\n",
      "('SampleFiles\\\\Ch4FileStructure', ['Folder1', 'Folder2', 'Folder3'], [])\n",
      "('SampleFiles\\\\Chapter 2 Books', [], ['Alice in Wonderland.txt', 'Dracula.txt', 'Frankenstein.txt', 'Pride and Prejudice.txt', 'Ulysses.txt'])\n",
      "('SampleFiles', ['Ch4FileStructure', 'Chapter 2 Books'], ['Chapter1 ExampleText2 (Alice in Wonderland).txt', 'Chapter1ExampleText.txt', 'desktop.ini'])\n"
     ]
    }
   ],
   "source": [
    "#----------------P4-27-------------------------\n",
    "import os\n",
    "\n",
    "def our_walk(path):\n",
    "    folders = []\n",
    "    files = []\n",
    "    \n",
    "    for obj in os.listdir(path):\n",
    "        new_path = os.path.join(path, obj)\n",
    "        if os.path.isdir(new_path):\n",
    "            folders.append(obj)\n",
    "            yield from our_walk (new_path)  #Note the use of yield from\n",
    "        elif os.path.isfile(new_path):\n",
    "            files.append(obj)\n",
    "        else:\n",
    "            print('Unknown object:', obj)\n",
    "    \n",
    "    yield(path, folders, files)\n",
    "\n",
    "\n",
    "\n",
    "for i in os.walk('SampleFiles'):\n",
    "    print(i)\n",
    "    \n",
    "print('\\n')\n",
    "for i in our_walk('SampleFiles'):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finished Chapter 4!"
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}