Category: Python

JS Number

tokens = (
	'IDENTIFIER',
	'NUMBER',
	'STRING'
	)

def t_NUMBER(t):
	r'-?[0-9]+(?:\.[0-9]*)?'
	t.value = float(t.value)
	return t

def t_STRING(t):
	r'([^"\\]|(\\.))*"'
	t.value = t.value[1:-1]
	return t

function gcd(a,b){
	if(a==b){
		return a;
	} else {
		if(a > b){
		return gcd(a-b, b);
		} else {
			return gcd(a, b- a)
		}
	}
}

recursion: function call itself

javascript and python

def uptoten(x):
if x < 10: return x else: return 10 javascriptcode=""" function uptoten(x) { if x < 10 { return x } else { return 10 } } """ [/python]

element

def findmax(f,l):
	best_element_sofar = None
	best_f_value_sofar = None
	for i in range(len(l)-1):
		elt = l[i]
		f_value = f(elt)
		if best_f_value_sofar == None or \
			f_value > best_f_value_sofar:
			best_element_sofar = elt
			best_f_value_sofar = f_value
	return best_element_sofar

Modern programming languages like Python can understand hexadecimal
numbers natively! Try it:

print 0x234 # uncomment me to see 564 printed
print 0xb # uncomment me to see 11 printed

import ply.lex as lex

tokens = ('NUM', 'ID')

def test_lexer(input_string):
	lexer.input(input_string)
	result = [ ]
	while True:
		tok = lexer.token()
		if not tok: break
		result = result + [(tok.type,tok.value)]
	return result

specification

import re
re.findall(needle,haystack)

def t_LANGLESLASH(token):
    r'

def t_NUMBER(token):
	r"[0-9]+"
	token.value = int(token.value)
	return token



def t_STRING(token):
    r'"[^"]*"'
    return token



def t_WORD(token):
    r'[^ <>]+'
    return token



def t_IDENTIFIER(token):
    r'[a-zA-Z][a-zA-Z_]*'
    return token



def t_NUMBER(token):
    r'-?[0-9]+(:?\.[0-9]*)'   
    return token

simulator

edges = {(1,'a'):2,
	(2, 'a'): 2,
	(2, '1'): 3,
	(3, '1'): 3}
	accepting = [ 3 ]

	def fsmsim(string, current, edges, accepting):
		if string == ""
			return current in accepting
		else:
			letter = string[0]
			if (current, letter) in edges:
				destination = edges[(current,letter)]
				remaining_string = string[1:]
				return fsmsim(remaining_string,destination,edges,accepting)
			else:
				return False
	print fsmsim("aaa111",1,edges,accepting)

import re

def umnums(sentence):
	r = r"[0-9]+"
	sum = 0
	for found in re.findall(r,sentence):
		sum = sum + int(found)
	return sum

(?:[a-z]+-[a-z]+)|(?:[a-z]+)

def nfsmsim(string, current edges, accepting):
	if string == "":
		return current in accepting
	else:
		letter = string[0:1]
		if (current, letter) in edges:
			remainder = string[1:]
			newstates = edges[(current, letter)]
			for newstate in newstates:
				if nfsmsim(remainder, newstate, edges, accepting):
					return True

	if current in visited:
		return None
	elif current in accepting:
		return ""
	else:
		newvisited = visited + [current]
		for edge in edges:
			if edge[0] == curent:
				for newstate in edges[edge]:
					foo = nfsmaccepts(nestate, edges, accepting, newvisited)
					if foo != None:
						return edge[1] + foo
		return None

breaking points

Python 2.7.12 (v2.7.12:d33e0cf91556, Jun 27 2016, 15:19:22) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> "Ada Lovelace".find(" ")
3
>>> "Alan Turing".find("n",4)
9

def myfirst_yoursecond(p,q):
	pindex = p.find(" ")
	qindex = q.find(" ")
	return p[ :pindex] == q[qindex+1:]

>>> "Python is fun".split()
['Python', 'is', 'fun']
>>> "July-August 1842".split()
['July-August', '1842']
>>> "6*9==42".split()
['6*9==42']

Regular expression [1-3][4-8][a-b]

>>> r"[0-9][0-9]"
>>> re.findall(r"[0-9][0-9]", "July 28, 1821")
>>> re.findall(r"[0-9][0-9]", "12345")

r”a+”, r”[0-1]+”
regular expression rule is maximum match eat single match
re.findall(r”[0-9][ ][0-9]+”, “a1 2b cc3 44d”)
r”[0-9]+%”
r”[a-z]+|[0-9]+”,”Goothe 1798″

regexp = r”[a-z]+-?[a-z]+”

>>> re.findall(r”[0-9].[0-9]”, “1a1 222 cc3”)
[‘1a1’, ‘222’]

edges = {(1,'a'):2,
	(2, 'a'): 2,
	(2, '1'): 3,
	(3, '1'): 3}

Binary Tree

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)

    def search(self, find_val):
        return self.preorder_serach(tree.root, find_val)

    def print_tree(self):
        return self.preorder_print(tree.root, "")[:-1]

    def preorder_search(self, start, find_val):
        if start:
            if start.value == find_val:
                return True
            else
                return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
            return False                

    def preorder_print(self, start, traversal):
        if start:
            traversal += (str(start.value) + "-")
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
        return traversal

Binary Search Tree

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST(object):
    def __init__(self, root):
        self.root = Node(root)

    def insert(self, new_val):
        self.insert_helper(self.root, new_val)

    def insert_helper(self, current, new_val):
        if current_value < new_val:
            if current.right:
                self.insert_helper(current.right, new_val)
            else:
                current.right = Node(new_val)

        else:
            if current.left:
                self.insert_helper(current.left, new_val)
            else:
                current.left = Node(new_val)

    def search(self, find_val):
        return self.search_helper(self.root, find_val)

    def search_helper(self, current, find_val):
        if current:
            if current.value == find_val:
                return True
            elif current.value < find_val:
                return self.search_helper(current.right, find_val)
            else:
                return self.search_helper(current.left, find_val)
        return False

graph(network): how things is connect one another which is similar to tree.

0[0, 1, 0, 0]
1[1, 0, 1, 1]
2[0, 1, 0, 1]
3[0, 1, 1, 0]

Dictionary

In Python, the map concept appears as a built-in data type called a dictionary. A dictionary contains key-value pairs. Dictionaries is extremely easy to use and useful. Here’s a sample of setting up a dictionary.

locations = {'North America': {'USA': ['Mountain View']}}
locations['North America']['USA'].append('Atranta')
locations['Asia'] = {'India': ['Bangalore']}
locations['Asia']['China'].append = ['Shanghai']
locations['Africa'] = {'Egypt': ['Cairo']}

usa_sorted = sorted(locations['North America']['USA'])
for city in usa_sorted
    print city

asia_cities = []
for countries, cities in location['Asia'].iteritems():
    city_country = cities[0] + " - " + countries
    asia_cities.append(city_country)
asia_sorted = sorted(asia_cities)
for city in asia_sorted:
    print city

When hash table collision, bucket store data.

Hash Value = (ASCII Value of First Letter * 100) + ASCII Value of Second Letter

hash table

class HashTable(object):
    def __init__(self):
        self.table = [None]*10000

    def store(self, string):
        hv = self.calculate_hash_value(string)
        if hv != -1:
            if self.table[hv] != None:
                self.table[hv].append(string)
            else
                self.table[hv] = [string]

    def lookup(self, string):
        hv = slef.calculate_hash_value(string)
        if hv != -1:
            if self.table[hv] != None:
                if string in self.table[hv]:
                    return hv
        return -1

    def calculate_hash_value(self, string):
        value = ord(string[0])* 100 + ord(string[1])
        return -1

Tree DFS, In-order

binary search

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:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
        return found

recursion

function recursive(input):
    if input <= 0
        return input
    else
        output = recursive(input - 1)
        return output

fib

function getFib(position){
    if (position == 0) { return 0; }
    if (position == 1) { return 1; }
    var first = 0,
        second = 1,
        next = first + second;
    for (var i = 2; i < position; i++){
        first = second;
        second = next;
        next = first + second;
    }
    return next;
}

def get_fib(position):
    if position == 0 or position == 1:
        return position
    return get_fib(position -1) + get_fib(position -2)

margin sort efficiency
log(n)
1, 4(log n1),8(log n3), 16(log n4)

ease yourself by commic
https://xkcd.com/1185/

margin sort text
http://algs4.cs.princeton.edu/22mergesort/

quick sort

def quicksort(array):
    if len(array) < 1:
        return array
    pivot = array[0]
    left = []
    right = []
    for x in range(1, len(array)):
        if array[x] <= pivot:
            left.append(array[x])
        else:
            right.append(array[x])
        left = quicksort(left)
        right = quicksort(right)
        foo = [pivot]
        return left + foo + right

list: A B C
set: C A B

quee, enqueue, dequeue

class Queue:
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        self.storage.append(new_element)

    def peek(self):
        return self.storage[0]

    def dequeue(self):
        return self.storage.pop(0)

stack

def delete_first(self):
    deleted = self.head
    if self.head:
        self.head = self.head.next
        deleted.next = None
    return deleted

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None
        
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
        
    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def insert_first(self, new_element):
        new_element.next = self.head
        self.head = new_element

    def delete_first(self):
        if self.head:
            deleted_element = self.head
            temp = deleted_element.next
            self.head = temp
            return deleted_element
        else:
            return None

class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)

    def push(self, new_element):
        self.ll.insert_first(new_element)

    def pop(self):
        return self.ll.delete_first()