multivac61

def merge_sort(m, sort_by):
	def merge(left, right):
		result = []
		while left and right:
			# keep on merging/sorting from left/right
			# lists on an element basis 
			if sort_by(left[0], right[0]):
				result.append(left[0])
				left.pop(0)
			else:

multivac61

def heap_sort(m, sort_by):
	def sift_down(m, start, end):
		"""Repair heap whose root element is at index start
		assuming the heaps rooted at its children are valid"""
		root = start

		while 2*root+1 <= end:
			child = 2*root + 1	# left child
			swap = root

multivac61

def quick_sort(m, sort_by):
	def partition(m, lo, hi):
		p = m[hi]	# choose a pivot
		i = lo
		for j in range(lo, hi):
			if sort_by(m[j], p):
				m[i], m[j] = m[j], m[i]
				i += 1
		m[i], m[hi] = m[hi], m[i]
		return i

multivac61

def selection_sort(m, sort_by=(lambda a, b: a < b)):
	def find_next(m):
		next_elem = m[0]
		for i in m:
			if sort_by(i, next_elem):
				next_elem = i
		return next_elem

	if len(m) <= 1:	# if list less than one element return
			return m

multivac61

'This is an example of list comprehension control variables being leaked to their outer scope'

for i in range(10):
    a = [i for i in range(43)]
    print i # will print 42 every time!

multivac61

    def _viterbi(self, observations):
        '''Generate the most likely sequence of words given the observations'''
        transitions = self.transition_prob; emissions = self.emission_prob

        V = {};    V[(0, X0)] = log10(1)    # initial probabilities
        path = {}; path[X0] = [X0]          # path to most likely seq
        
        current_words = [[] for i in range(len(observations)+1)]
        current_words[0] = [X0] # list of words that have an entry in bigram table

multivac61

class NQueensSquare(SearchProblem):
    def __init__(self, N):
        super(NQueensSquare, self).__init__()
        self.N = N
        self.initial_state = tuple([tuple([0 for i in range(N)]) for j in range(N)])
        self._actions      = [(i, j) for i in range(N) for j in range(N)]

    def actions(self, s):
        '''Possible actions from a state.'''
        # generate every possible state then filter out invalid

multivac61

class NQueensSwap(SearchProblem):
    def __init__(self, N):
        self.N = N
        init               = [i for i in range(N)]
        shuffle(init)   # randomize the initial array
        self.initial_state = tuple(init)    # states must me immutable
        self._actions      = [ (i, j) for i in range(N) 
                                      for j in range(i,N) 
                                          if i != j ]

multivac61

class NQueensRow(SearchProblem):
    def __init__(self, N):
        super(NQueensRow, self).__init__()
        self.N             = N
        self.initial_state = ()
        self._actions      = range(N)
        shuffle(self._actions) # randomize actions

    def actions(self, s):
        '''Possible actions from a state.'''

multivac61

class KnightsTour():
    '''Knights Tour using Warnsdorf's rule as heuristics'''

    def __init__(self, N, start_point=(0,0)):
        self.N             = N
        self.initial_state = (start_point, )
        # all relative moves expressed as displacement in 2D
        self._actions      = [(1,2), (1,-2), (2,1), (2,-1),\
                              (-1,2), (-1,-2), (-2,1), (-2,-1)]