Chapter 8.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chapter 8: Recursion and Dynamic Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.1 Triple Step:** A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3\n",
    "steps at a time. Implement a method to count how many possible ways the child can run up the\n",
    "stairs.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.2 Robot in a Grid:** Imagine a robot sitting on the upper left corner of grid with r rows and c columns.\n",
    "The robot can only move in two directions, right and down, but certain cells are \"off limits\" such that\n",
    "the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to\n",
    "the bottom right.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.3 Magic Index:** A magic index in an array A [ 0••• n -1] is defined to be an index such that A[ i] =\n",
    "i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in\n",
    "array A.\n",
    "\n",
    "FOLLOW UP\n",
    "\n",
    "What if the values are not distinct?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.4 Power Set:** Write a method to return all subsets of a set.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1], [2], [3], [3, 2], [2, 1], [3, 1], [3, 2, 1]]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "case_0 = []\n",
    "case_1 = [1]\n",
    "case_2 = [1,2]\n",
    "case_3 = [1,2,3]\n",
    "case_4 = [1,2,3,4]\n",
    "# is the set guranteed to have no duplicates?\n",
    "# hopefully...\n",
    "\n",
    "# \n",
    "\n",
    "def power_set (my_set):\n",
    "    if len(my_set) <= 1:\n",
    "        return [my_set]\n",
    "    else:\n",
    "        element = my_set[0]\n",
    "        res = power_set(my_set[1:])\n",
    "        return [[element]] + res + ([r + [element] for r in res])\n",
    "    \n",
    "power_set(case_3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.5 Recursive Multiply:** Write a recursive function to multiply two positive integers without using the\n",
    "*operator.You can use addition, subtraction, and bit shifting, but you should minimize the number\n",
    "of those operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.6 Towers of Hanoi:** In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of\n",
    "different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order\n",
    "of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following\n",
    "constraints:\n",
    "\n",
    "(1) Only one disk can be moved at a time.\n",
    "\n",
    "(2) A disk is slid off the top of one tower onto another tower.\n",
    "\n",
    "(3) A disk cannot be placed on top of a smaller disk.\n",
    "\n",
    "Write a program to move the disks from the first tower to the last using stacks.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.7 Permutations without Dups:** Write a method to compute all permutations of a string of unique\n",
    "characters.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['abc', 'bac', 'bca', 'acb', 'cab', 'cba']"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str_a = \"\"\n",
    "str_b = \"a\"\n",
    "str_c = \"ab\"\n",
    "str_d = \"abc\"\n",
    "\n",
    "def permutate(string):\n",
    "    if len(string) <= 1:\n",
    "        return [string]\n",
    "    else:\n",
    "        char = string[0]\n",
    "        rest = permutate(string[1:])\n",
    "        perm = []\n",
    "        for p in rest:\n",
    "            perm = perm + [p[:i] + char + p[i:] for i in range(len(p)+1)]\n",
    "        return perm\n",
    "\n",
    "permutate(str_d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.8 Permutations with Dups:** Write a method to compute all permutations of a string whose characters are not necessarily unique. The list of permutations should not have duplicates.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['cbaa',\n",
       " 'aacb',\n",
       " 'bcaa',\n",
       " 'aabc',\n",
       " 'abca',\n",
       " 'acba',\n",
       " 'acab',\n",
       " 'caba',\n",
       " 'abac',\n",
       " 'caab',\n",
       " 'baca',\n",
       " 'baac']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str_e = \"abca\"\n",
    "\n",
    "def permutate_dups(string):\n",
    "    if len(string) <= 1:\n",
    "        return [string]\n",
    "    else:\n",
    "        char = string[0]\n",
    "        rest = permutate_dups(string[1:])\n",
    "        perm = []\n",
    "        for p in rest:\n",
    "            for i in range(len(p)+1):\n",
    "                perm = perm + [p[:i] + char + p[i:]]\n",
    "        perm = list(set(perm)) # remove duplicates\n",
    "        return perm\n",
    "\n",
    "permutate_dups(str_e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.9 Parens:** Implement an algorithm to print all valid (e.g., properly opened and closed) combinations\n",
    "of n pairs of parentheses.\n",
    "\n",
    "EXAMPLE\n",
    "\n",
    "Input: 3\n",
    "\n",
    "Output: ( (() ) ) , (() () ) , (() ) () , () ( () ) , () () ()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.10 Paint Fill:** Implement the \"paint fill\" function that one might see on many image editing programs.\n",
    "That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color,\n",
    "fill in the surrounding area until the color changes from the original color.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.11 Coins:** Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and\n",
    "pennies (1 cent), write code to calculate the number of ways of representing n cents.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "242"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# we want to build up from the smaller amounts:\n",
    "# eg, if we know all the ways to make 5c, we can build up to larger amounts easily\n",
    "# we only need the number of ways, not the ways themsevles\n",
    "\n",
    "def make_change(cents,denominations=[25,10,5,1]):\n",
    "    if len(denominations) == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        n = 0\n",
    "        for i in range(int(cents / denominations[0])+1):\n",
    "            n += make_change(cents-i*denominations[0],denominations[1:])\n",
    "        return n\n",
    "    \n",
    "make_change(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.12 Eight Queens:** Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board\n",
    "so that none of them share the same row, column, or diagonal. In this case, \"diagonal\" means all\n",
    "diagonals, not just the two that bisect the board.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "92"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# at each state, need to place a queen\n",
    "# grab first available spot\n",
    "\n",
    "# represent the places as (x,y)\n",
    "# a place is available if no queen shares the x or y\n",
    "# or any place on diagonals - so abs((x1-x2)) != abs((y1-y2))\n",
    "\n",
    "# could determine next spot by exhaustive search but smarter to remove unavailable spots at each stage\n",
    "\n",
    "def queens (n):\n",
    "    board = [[i,j] for j in range(n) for i in range(n)]\n",
    "    places = []\n",
    "    return len(place_queen(n,board,places))\n",
    "\n",
    "def place_queen (n,available_spots,places):\n",
    "    if n == 0:\n",
    "        return [places]\n",
    "    elif not available_spots:\n",
    "        return []\n",
    "    else:\n",
    "        placements = []\n",
    "        i = 0\n",
    "        for spot in available_spots:\n",
    "            reduced_spots = []\n",
    "            # placing here eliminates spots\n",
    "            # we should we also eliminate previously considered spots so we don't get duplicates\n",
    "            for a in available_spots[i:]:\n",
    "                if spot[0] != a[0] and spot[1] != a[1] and (abs(spot[0] - a[0]) != abs(spot[1] - a[1])):\n",
    "                    reduced_spots.append(a)\n",
    "            i += 1\n",
    "            placements += place_queen(n-1,reduced_spots,places+[spot])\n",
    "        return placements\n",
    "    \n",
    "queens(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.13 Stack of Boxes:** You have a stack of n boxes, with widths wi, heights h i , and depths d i. The boxes\n",
    "cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly\n",
    "larger than the box above it in width, height, and depth. Implement a method to compute the\n",
    "height of the tallest possible stack. The height of a stack is the sum of the heights of each box.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.14 Boolean Evaluation:** Given a boolean expression consisting of the symbols 0 (false), 1 (true), &\n",
    "(AND), I (OR), and /\\ (XOR), and a desired boolean result value result, implement a function to\n",
    "count the number of ways of parenthesizing the expression such that it evaluates to result.\n",
    "\n",
    "EXAMPLE\n",
    "\n",
    "```countEval(\"l /\\01011\", false) -> 2```\n",
    "\n",
    "```countEval(\"0&0&0&1 /\\ ll0\", true) -> 10```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}