Dynamic programmings

ChessKnight.java

public class ChessKnight {
        //Possible moves
        //for each possible way we can move in x, we have a corresponding y
	int[] x ={-2,-2,-1,-1,1,1,2,2}; 
	int[] y = {-1,1,-2,2,-2,2,-1,1};
	double[][][] results;
	private static final int BOARD_SIZE = 8;
	
	public double probAfterNSteps(int x, int y, int n){
		init_memoize(n); //initialize our memoization array
		return probAfterNStepsHelper(x-1,y-1,n);
	}
	
	public void init_memoize(int steps){
		results = new double[BOARD_SIZE][BOARD_SIZE][steps+1];
		for (int i = 0; i < results.length;i++){
			for(int j = 0; j < results[0].length;j++){
				for(int k = 0;k < results[0][0].length;k++){
					results[i][j][k] = -1;
				}
			}
		}
	}
	//start at (x,y) where  0<= x, y <=7 and have n steps left
	public double probAfterNStepsHelper(int x,int y,int n){
		//We are off the board if this happens
		if(x < 0 || y < 0 || x > 7 || y > 7){
			return 0;
		}
		if(n==0){
			return 1;
		}
		//do we have prior results cached?
		if (results[x][y][n] != -1){
			return results[x][y][n];
		}
		double chance = 0.0;
		//for each possible move, add up the probability of staying on the board,
		//then divide by 8
		for (int i = 0; i < this.x.length;i++){
			chance += probAfterNStepsHelper(x+this.x[i], y+this.y[i],n-1);
		}
		chance = chance/8; // 8 different possibilities
		results[x][y][n] = chance;
		return chance;
	}
	
	public static void main (String[] args){
		ChessKnight k = new ChessKnight();
		System.out.println(k.probAfterNSteps(1, 1, 2));
		System.out.println(k.probAfterNSteps(4, 4, 1));
		System.out.println(k.probAfterNSteps(4, 4, 8));
		
	}

}

knapsack.py

@memoize()
def knapsack(weights,values,n,max_weight):
  if n <= 0 or max_weight <= 0:
    return 0
  if max_weight < weights[n-1]: #too much weight! can't include nth item
    return knapsack(weights,values,n-1,max_weight) # look over n-1 items
  elif max_weight >= weights[n-1]:
    #still have room, should we include item? or not?
    #lets say we don't add it (you know to save room for possible more valuable things)
    do_not_include = knapsack(weights,values,n-1,max_weight)
    #ok, now what if we do add it?
    do_include = values[n-1] + knapsack(weights,values,n-1, max_weight-weights[n-1]) #add item, so remove its weight from the weight we have left
    #return the max value between adding next item and not adding it
    return max(do_not_include, do_include)

LongestCommonSubsequence.py

def lcs(x,y,i,j):
  if i < 0 or j < 0:
    #no way there can be a match if one string doesn't exist
    return 0
  if x[i] == y[j]:
    # if the characters in each string are the same, add 1
    # and reduce index by 1 in each - smaller subproblem + 1 for the match
    return 1 + lcs(x,y,i-1,j-1)
  else:
    #not matching, so return the max value we would get if we reduced
    # index in one string by 1, or in the other string by 1
    return max(lcs(x,y,i-1,j),lcs(x,y,i,j-1))

maximize_copypaste_output.py

# Using the keystrokes 'A', 'CTRL + A', 'CTRL + C', 'CTRL + V'
# for a combined N times, what it the largest number of 'A's that you can output?
# CTRL + character counts as 1.

def maximize_copypaste_output(n):
  #no keys, no length
  if n==0:
    return 0
  moves = [0]; #initialize our array of 'best moves' for each N
  # for 1 to 7 key presses, you are best off just pressing 'A' 7 times.
  for i in range(1,7+1):
    moves.append(i)
  #if we are allowed more than 7, we can benefit by using 4+i key-strokes to act as a 2+i
  # multiplier of a value that is n-(4 + i) moves back from current move
  # This is because ctrl a, ctrl c, ctrl v, ctrl v will double what you have, and for each
  # additional ctrl v, the multiplication factor increases by 1. eg. ctrl a, ctrl c, ctrl v,
  #ctrl v, ctrl v will triple
  for i in range(8, n+1):
    moves.append(1)
    for j in range(4,i):
      factor = j-2 #move back 4, we can multiply what we have by 2
      #moves[i-j] is the solution to a smaller subproblem i-j moves back
      potential = factor*moves[i-j]
      if potential > moves[i]: # if more potential, then save as new max
        moves[i] = potential
  #return max amount of chars we can print
  return moves[n]

memoize.py

import functools

def memoize():
  CACHE = {}
  def decorator(f):
    @functools.wraps(f)
    def wrapped(*args, **kwargs):
      key = repr(f.func_name)+"|"+repr(args)+"|"+repr(kwargs)
      if key in CACHE:
        print "Using cache value for "+ key
        return CACHE[key]
      else:
        value = f(*args,**kwargs)
        CACHE[key] = value
        return value
    return wrapped
  return decorator

@memoize()
def lcs(x,y,i,j):
  if i < 0 or j < 0:
    #no way there can be a match if one string doesn't exist
    return 0
  if x[i] == y[j]:
    # if the characters in each string are the same, add 1
    # and reduce index by 1 in each - smaller subproblem + 1 for the match
    return 1 + lcs(x,y,i-1,j-1)
  else:
    #not matching, so return the max value we would get if we reduced
    # index in one string by 1, or in the other string by 1
    return max(lcs(x,y,i-1,j),lcs(x,y,i,j-1))

Memoized LCS Results vs Non-Memoized LCS Results

>>> time_me(lcs,"dude, mit is rich","dmitri cherniak",16,14)
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 1, -1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 2, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 3, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 4, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 6, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 5, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 7, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 8, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 9, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 10, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 14, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 14, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 5)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 2)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 1)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 11, 0)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 12, 3)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 7)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 13, 4)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 14, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 14, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 14, 8)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 14, 6)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 7)|{}
lcs took 5.153 ms
8 # correct, dmitrich

>>> time_me(non_memoized_lcs,"dude, mit is rich","dmitri cherniak",16,14)
non_memoized_lcs took 108760.369 ms
8 # correct, dmitrich


108760.369 / 5.15300 = 21106.2234 times speed up!

time_me.py

def time_me(f,*args,**kwargs):
   start = time.time()
   result = f(*args,**kwargs)
   end = time.time()
   print '%s took %0.3f ms' % (f.func_name, (end-start)*1000.0)
   return result

Truncated Memoized LCS Results vs Non-Memoized LCS Results

>>> time_me(lcs,"dude, mit is rich","dmitri cherniak",16,14)
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 0, 12)|{}
...
...
...
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 13)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 12)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 11)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 10)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 9)|{}
Using cache value for 'lcs'|('dude, mit is rich', 'dmitri cherniak', 15, 7)|{}
lcs took 5.153 ms
8 # correct, dmitrich

>>> time_me(non_memoized_lcs,"dude, mit is rich","dmitri cherniak",16,14)
non_memoized_lcs took 108760.369 ms
8 # correct, dmitrich


108760.369 / 5.15300 = 21106.2234 times speed up!