hillscottc

// Use Gists to store code you would like to remember later on
console.log(window); // log the "window" object to the console

hillscottc

""" Graph traversal functions. Breadth-first search (BFS) and Depth-first search (DFS).
Adapted from: http://code.activestate.com/recipes/576723-dfs-and-bfs-graph-traversal
"""
import pprint


GRAPH_PIC = """  
+---- A
|   / |
|  B--D--C

hillscottc

fib_vals = {1:1, 2:1}

def fib(n):
    if n <= 2:
        return 1
    if n in fib_vals:
        return fib_vals[n]
    else:
        fib_vals[n] = fib(n - 1) + fib(n - 2)
        return fib_vals[n]

hillscottc

def memoize(func):
    """Decorator for memoization via 'cache' dictionary."""
    cache = {}
    
    def memoed_func(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    
    memoed_func.cache = cache

hillscottc

tree_walk(x):
    if x:
        tree_walk(x:left)
        print x:key
        tree_walk(x:right)


tree_search(x, k):
    """Recursive search."""
    if not x or k == x.key:

hillscottc

from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)

hillscottc

from pythonds.basic.deque import Deque

def palchecker(aString):
    chardeque = Deque()

    for ch in aString:
        chardeque.addRear(ch)

    stillEqual = True

hillscottc

"""Recursive sum of a list of numbers. The basic recursive case. 

Define the base case. 
If base case, return it. 
Else: listSum(numList) = first(numList) + listSum(rest(numList))
"""

def listsum(numList):
   if len(numList) == 1:
        return numList[0]

hillscottc

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False
   
    while first<=last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
            found = True
        else:

hillscottc

"""
Dijkstra's algorithm for shortest paths.
http://code.activestate.com/recipes/577343-dijkstras-algorithm-for-shortest-paths/)

  - dijkstra(G, s) finds all shortest paths from s to each other vertex.
  - shortest_path(G, s, t) uses dijkstra to find the shortest path from s to t.

The input graph G is assumed to have the following representation:

  - A vertex can be any object that can be used as an index into a dictionary.