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')
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]:
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
'''