In [5]:
# Imports
import random
import unittest
from binarytree import Node, bst as generate_bst, stringify
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
In [6]:
# 8.1 - Triple Step - Staircause with n steps. Can hope 1, 2, or 3 steps.
# How many ways can the child run up the stairs?
def memoize(f):
cache = {}
def decorated_function(*args):
if args in cache:
return cache[args]
else:
cache[args] = f(*args)
return cache[args]
return decorated_function
@memoize
def count_hops(numSteps, i=0):
ways = 0
for skip in [x for x in [1, 2, 3] if x <= numSteps]:
if numSteps-skip == 0:
ways += 1
elif numSteps-skip > 0:
ways += count_hops(numSteps-skip, i+1)
return ways
for x in range(10):
print x, count_hops(x)
print ''
def count_hops2(x):
memo = [1, 1, 2, 4]
if x < 3:
return memo[x]
for i in xrange(3, x):
memo[3], memo[2], memo[1], memo[0] = sum(memo[-3:]), memo[3], memo[2], memo[1]
return memo[3]
for x in range(10):
print x, count_hops2(x)
In [27]:
map(sum, zip([3,4],[5,6]))
Out[27]:
In [171]:
# 8.2 - Robot in a Grid - Grid with R rows and C cols. Robot can move in 2 directions: right and down.
# Certain cells are off limits. Design an algorithm to find path from top/left to bottom/right.
import copy
RIGHT = (0, 1)
DOWN = (1, 0)
LEFT = (0, -1)
UP = (-1, 0)
def make_grid(r, c, densityOfOffLimits=0.3):
grid = (np.random.random((r,c)) > densityOfOffLimits).astype(np.int)
grid[0, 0] = 1
grid[-1, -1] = 1
return grid
def is_good_pos(pos, grid):
return pos[0] < grid.shape[0] and pos[1] < grid.shape[1] and grid[pos[0], pos[1]]
def get_result(direction, pos, path):
axis = {UP: 0, DOWN: 0, RIGHT: 1, LEFT: 1}[direction]
newPos = map(sum, zip(pos, direction))
if is_good_pos(newPos, grid):
newPath = copy.copy(path)
newPath.append(pos)
path = find_path(grid, newPos, newPath)
if path:
return path
def find_path(grid, pos=None, path=None):
if pos is None:
pos = [0, 0]
if path is None:
path = []
if pos == map(sum, zip(grid.shape, [-1, -1])):
path.append(pos)
return path
for direction in [RIGHT, DOWN]:
result = get_result(direction, pos, path)
if result:
return result
print 'returning', path, result
path.append(result)
return path
def draw_grid(grid):
for r in grid:
for c in r:
if c == 1:
print '.',
elif c > 1:
print 'o',
else:
print chr(127),
print ''
grid = make_grid(10, 20)
draw_grid(grid)
result = find_path(grid)
print result is not None
if result is not None:
result = np.array(result)
grid[result[:,0], result[:,1]] = 8
draw_grid(grid)