Category: Python

fibo

def fibo(n):
	in n <= 2:
		return 1
	else:
		return fibo(n-1)+fibo(n-2)

print fibo(20)
&#91;/python&#93;

&#91;python&#93;
chart = {}

def memofibo(n):
    if n in chart:
    	return chart&#91;n&#93;
    elif n <= 2:
    	chart&#91;n&#93; = 1
    
print memofibo(24)
&#91;/python&#93;

&#91;python&#93;
def t_javascript(token):
	r'<script\ type=\"text\/javascript\"\>'
	token.lexer.code_start = token.lexer.lexpos
	token.lexer.begin("javascript")

def t_javascript_end(token):

def t_javascript(token):
	r'<script\ type=\"text\/javascript\"\>'
	token.lexer.code_start = token.lexer.lexpos
	token.lexer.begin("javascript")

def t_javascript_end(token):
	r'\<\/script\>'
	token.value = token.lexer.lexdata[token.lexer.code_start:
		token.lexer.lexpos-9]
	token.type = 'JAVASCRIPT'
	token.lexer.lineno += token.value.count('\n')
	token.lexer.begin.('INITIAL')
	return token

parthing:構文解析 lexing:字句解析
after regular expression, lexer get token value.

javascript to python

#        function mymin(a, b){
#            if (a < b){
#                return a;
#            } else {
#                return b;
#            };
#        }
#        
#        function square(x){
#            return x * x;
#        }
#        
#        write(mymin(square(-2), square(3)));

def mymin(a, b):
	if (a < b):
		return a
	else:
		return b

def square(x):
	return x * x
print mymin(square(-2), square(3))

[1,2,3,4,5,6,7]

def odds_only(numbers):
	for N in numbers:
		if N % 2 == 1:
			yield N

def small_words(words):
	for word in words:
		if len(word) <= 3:
			yield word

print [w for w in small_words(["The","quick","brown","fox"])]

grammar = [
	("exp",["exp","+","exp"]),
	("exp",["exp","-","exp"]),
	("exp",["(","exp",")"]),
	("exp",["num"]),
]

def expand(tokens, grammar):
	for pos in range(len(tokens)):
		for rule in grammar:

depth = 1
utterances = [["exp"]]

def sublists(big_list, selected_so_far):
	if big_list == []:
		print selected_so_far
	else:
		current_element = big_list[0]
		rest_of_big_list = big_list[1:]
		sublists(rest_of_big_list, selected_so_far + [current_element])
		sublists(rest_of_big_list, selected_so_far )

	dinner_guests = ["LM", "ECS", "SBA"]
	sublists(dinner_guests, [])

def cfgempty(grammar, symbol, visited):
	if symbol in visited:
		return None
	elif not any([rule[0] == symbol for rule in grammar ]):
		return [symbol]
	else:
		new_visited = visited + [symbol]
		for rhs in [r[1] for r in grammar if r[0] == symbol]:
			if all([None] != cfgempty(frammar, r, new_visited) for r in rhs):
				result = []
				for r in rhs:
					result = result + cfgempty(grammar, r, new_visited)
				return result
		return None

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