Dynamic Programming

Steps to dynamic programming

  1. Careful brute force- take and exponetial search space and reduce it to a polynomial search space, even though you are still blindly trying all posibilities.
  2. Guessing + recursion + memoization- Pick out some feature to the solution that we don't know but we want to know- and 'guess' the answer (take all the possible answers). Then we use a recursion- you can recurse over anything that has some substructure- we can recurse over the subproblems. In shortest paths, the sub-paths to shortest paths were also shortest paths.
  3. Usuallly the recusrion itself is exponetial time so we add in memoization and it becomes linear time/polynomial time.
  4. Instead of recusrion and memoization there is also the bottom-up approach where you build up a dynamic programming table. They more or less have the same running time
  5. Solve the original problem.

In [19]:
'''
A child is running up a stiarcase with n steps and can hop either 
1 step, 2 steps, or 3 steps at a time. Implement a method to count 
how many possible ways the child can run up the stairs. 
'''
class triple_step():
    def __init__(self):
        self.memo = {}
        
    def triple_step(self, step):
        if step < 0:
            return 0
        
        self.memo[0] = 1
        if step == 0:
            return self.memo[0]
        
        self.memo[1] = 1
        if step == 1:
            return self.memo[1]
        
        result = self.triple_step(step-1) + self.triple_step(step-2) + self.triple_step(step-3)
        self.memo[step] = result
        
        return result
t = triple_step()
t.triple_step(3)

In [23]:
'''
Imagine a robot sitting on the upper left corner of grid with r 
rows and c columns. The robot can only move in two directions, 
right and down, but certain cells are 'off limits' such that the 
robot cannot step on them. Design an algorithim to find a path for 
the robot from the top left to the bottom right. 
'''

class robotPath:
    def __init__(self, maze):
        self.maze = maze
        self.failedPoints = []
        self.path = []

def getPath(row, col):
    if col < 0 or row < 0 or not self.maze[row][col]:
        return False
    
    point = (row, col)
    
    if point in self.failedPoints:
        return False
    
    isAtOrigin = (row == 0) and (col == 0)
    
    if isAtOrigin or self.getPath(row, col-1) or self.getPath(row-1, col):
        self.path.append(point)
        return True
    
    self.failedPoints.append(point)
    return False

In [ ]:
def getPath(self, maze):
    if len(maze) == 0 or len(maze[0]) == 0:
        return None
    path = []
    failedPoints = set()
    if self.pathFinder(maze, len(maze), len(maze[0]), path, failedPoints):
        return path
    return None

def pathFinde(self, maze, row, col, path, failedPoints):
    if col < 0 or row < 0 or not maze[row][col]:
        return False
    p = (row, col)
    if p in failedPoints:
        retuen False
    isAtOrigin = (row == 0) and (col == 0)
    if isAtOrigin or self.pathFinder(maze, row, col-1, path, failedPoints) or self.pathFinder(maze, row-1, col, path, failedPoints):
        path.append(p)
        return True
    failedPoints.append(p)
    return False

In [3]:
'''
In the classic problem of the Towers of Hanoi, you have 3 towers 
and N disks of differnt size. 1. Only one disk can be moved at a 
time. 2. A disk is slid off the top of one tower onto another tower. 
3. A disk cannot ve placed on top of a smaller disk.
'''
def hanoi(height, fromPole, toPole, withPole):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole )
        hanoi(height -1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole, height)
        hanoi(height-1, withPole, toPole, fromPole)

def moveDisk(fp, tp, height):
        print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)

hanoi(3, 'a', 'b', 'c')


 moveTower: 3 a b
     moveTower: 2 a c
         moveTower: 1 a b
             moving disk ~ from a to b
         moving disk ~~ from a to c
         moveTower: 1 b c
             moving disk ~ from b to c
     moving disk ~~~ from a to b
     moveTower: 2 c b
         moveTower: 1 c a
             moving disk ~ from c to a
         moving disk ~~ from c to b
         moveTower: 1 a b
             moving disk ~ from a to b

In [2]:
'''
Take a periodic table of elements names, find the largest word 
that can be formed. The symbols should be regarded as single 
elements. The largest word is determined by the amount of elements, 
not the amount of letters. 
'''


Out[2]:
'\nTake a periodic table of elements names, find the largest word \nthat can be formed. The symbols should be regarded as single \nelements. The largest word is determined by the amount of elements, \nnot the amount of letters. \n'

In [1]:
'''
Given two strings x and y. What is the cheapest way to convert 
x into y. You can insert a character anywhere in the string, 
you can delete a character anywhere in the string, and you can 
replace a character anywhere in a string. Mutation in geneitc 
sequence can also be framed as a type of edit distance problem. 

The edit distance probelm can also be used to solve related issues 
like longest common subsequence. 
'''

def editDistDP(str1, str2, m, n):
    # Create a table to store results of subproblems
    dp = [[0 for x in range(n+1)] for x in range(m+1)]
 
    # Fill d[][] in bottom up manner
    for i in range(m+1):
        for j in range(n+1):
 
            # If first string is empty, only option is to
            # isnert all characters of second string
            if i == 0:
                dp[i][j] = j    # Min. operations = j
 
            # If second string is empty, only option is to
            # remove all characters of second string
            elif j == 0:
                dp[i][j] = i    # Min. operations = i
 
            # If last characters are same, ignore last char
            # and recur for remaining string
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
 
            # If last character are different, consider all
            # possibilities and find minimum
            else:
                dp[i][j] = 1 + min(dp[i][j-1],        # Insert
                                   dp[i-1][j],        # Remove
                                   dp[i-1][j-1])    # Replace
 
    return dp[m][n]

In [ ]:
'''
Fibonacci
'''

class Fibber:
    def __init__(self):
        self.memo = {}
    
    def fib(self, n):
        if n < 0:
            raise Exception('Index was negative. No such thing as a negative index in a series')
        
        elif n < 2:
            return n
        
        if n in self.memo:
            return self.memo[n]
       
        result = self.fib(n-1) + self.fib(n-2)
        self.memo[n] = result
        
        return result

In [ ]:
'''
Parenthesization
You are given an associative expression and you want to evavlutate 
it in some order:

1. Subproblem- Optimal evaluation of substrings. 
2. Guess- Consider all possible partitions for the parentheses. 
The parts in parenthesization are substrings, they are not prefixes
or suffixes. 
3. Recurese - 

The crux to parenthesization is that we are given an array of True
and False values and a series of operator s. We then have to 
construct an expression with those operators and operands with 
parentheses such that we creat e the proper otuput, True or False- 
depending on the situation. 
'''

In [ ]:
'''
Text Justification
Split a string into 'good' lines. 
Define badness in a string `[i, j]` as infiniti if it doesn't fit 
and otherwise as `(page widht - total width)^3` 
The point of the cube is that is strongly discourages wide gaps.

We have n subproblems. We can treat this as a fold. Where we are 
passing the suffix of the document string. If we approach the text 
as a series of subproblems-say we want to take the first part of 
the document string and decide to format it, the rest of the 
document string is called the suffix, `words[i:]` in python notation. 
These suffix words determine our subproblems. 
'''

In [ ]:
'''
Blackjack
Lets say that a deck is a series of cards. And we are one player 
versus the dealer. For a dollar bet per hand without being able to 
double or split- should I hit or should I stand. 
1. Subproblems: suffix, cards after i. The number of subproblems 
is - n, there are n choices. 
2. Guess - How many times should I hit? 
3. BJ(i) = max(outcome{-1, 0, 1}, BJ(i))

I think the muddied idea here is that you play through all the 
options with a for loop that checks if there is a valid play and 
then looks for the max outcome. 
'''

In [2]:
'''
8.5 Recursive Multiply
Write a recursive function to multiply two positive integers 
without using the operator. You can use addition, subtraction, 
and bit shifiting, but you should minimize the number of those 
operations.
'''

class operation:
    def __init__():
        self.memo = {}
    
    def multiply(self, n, m):
        if n == 1:
            return m
        
        if m == 1: 
            return n
        
        if self.memo[(n,m)]:
            return self.memo[(n, m)]
        
        result = self.multiply(n-1, m) + m
        
        self.memo[(n,m)] = result
        
        return result
        
        # I fucked this up somehow, it looks wrong
        #some addition of previous results should happen

In [ ]:
'''
8.4 Power set. 
Write a method to return all subsets of a set. 
'''

In [ ]:
'''
8.7 Permutations without Dups. 
Write a method to compute all permutaitons of a sting of unique 
characters. 
'''

In [ ]:
'''
8.8 Permutations with Dups. Write a method to compute all permutations of a string whose characters are ont necessarily unique. The list of permutations should not have duplicates.
'''

In [ ]:
'''
8.9 Parens. 
Implement an algorithm to print all valid combinations 
of n pairs of parenthesis
'''

In [ ]:
'''
8.10 Paint fill. 
Implement the paint fill function tha tone might see on many image 
editing programs. That is, given a screen(represented by a 
two-dimensional array of colors) a point, a new color, fill in the 
surrounding area until the color changes from the original color.
'''

In [ ]:
'''
8.11 Coins
Given an infinite number of quarters, dimes, nickels, and pennies, 
write code to calculate the number of ways of representing them.
'''

In [ ]:
'''
8.12 Eight queens
Write an algorithim to print all ways of arranging eight queens on 
an 8x8 board so that none of them share the same row, column, or 
diagonal. In the case, 'diagonal' means all diagonals, not just 
the two that bisect the board.
'''

In [ ]:
'''
8.13 Stack of boxes. 
You have a stack of n boxes, with widths w, heights h, and d. The 
boxes cannot be rotatedand can only be stacked on top of one 
another if each box in the stack is strcitly larger than the box 
above it in width, height, and depth. Implement a method to compute 
the height of the talest possible stack. The height of a stack is 
the sum of the heights of each box. 
'''

In [ ]:
'''
8.14 Boolean Evaluation. 
Given a boolean expression consisting of the symbols 0 (false), 
1 (true), and , or , and xor, and a desired boolean result value 
resutl, implement a function to count the number of ways of 
parenthesizing the expression such that it evaluates to result. 
The epression should be fully parenthesized but not extraneously
'''