Category: Python

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()

classy class

This class to represent how classy someone
or something is.”Classy” is interchangable with “fancy”.
If you add fancy-looking items, you will increase
your “classiness”.

class Classy(object):
    def __init__(self):
        self.items = []

    def addItem(self, item):
    	self.items.append(item)
 
    def getclassiness(self):
    	classiness = 0
    	if len(self.items) > 0:
    		for item in self.items:
        		if item == "tophat":
    				classiness += 2
    			elif item == "bowtie":
    				classiness += 4
    			elif item == "monocle":
    				classiness += 5
    		return classiness

notation: expression
():parenthesis

“””input manatees: a list of “manatees”, where one manatee is represented by a dictionary
a single manatee has properties like “name”, “age”, et cetera
n = the number of elements in “manatees”
m = the number of properties per “manatee” (i.e. the number of keys in a manatee dictionary)”””

def example1(manatees):
for manatee in manatees:
print manatee[‘name’]

def example2(manatees):
print manatees[0][‘name’]
print manatees[0][‘age’]

def example3(manatees):
for manatee in manatees:
for manatee_property in manatee:
print manatee_property, “: “, manatee[manatee_property]

def example4(manatees):
oldest_manatee = “No manatees here!”
for manatee1 in manatees:
for manatee2 in manatees:
if manatee1[‘age’] < manatee2['age']: oldest_manatee = manatee2['name'] else: oldest_manatee = manatee1['name'] print oldest_manatee 

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 get_position(self, position):
        counter = 1
        current = self.head
        if position < 1:
            return None
        while current and counter <= position:
            if counter == position:
                return current
            current = current.next
            counter += 1
        return None
    
    def insert(self, new_element, position):
        counter = 1
        current = self.head
        if position > 1:
            while current and counter < position:
                if counter == position -1:
                    new_element.next = current.next
                    current.next = new_element
                current = current.next
                counter += 1
        elif position == 1:
            new_element.next = self.head
            self.head = new_element
    
    def delete(self, value):
        current = self.head
        previous = None
        while current.value != value and current.next:
            previous = current
            current = current.next
        if current.value == value:
            if previous:
                previous.next = current.next
            else:
                self.head = current.next

port:5000 python server

#THIS IS A WEBSERVER FOR DEMONSTRATING THE TYPES OF RESPONSES WE SEE FROM AN API ENDPOINT
from flask import Flask
app = Flask(__name__)

#GET REQUEST

@app.route('/readHello')
def getRequestHello():
	return "Hi, I got your GET Request!"

#POST REQUEST
@app.route('/createHello', methods = ['POST'])
def postRequestHello():
	return "I see you sent a POST message :-)"
#UPDATE REQUEST
@app.route('/updateHello', methods = ['PUT'])
def updateRequestHello():
	return "Sending Hello on an PUT request!"

#DELETE REQUEST
@app.route('/deleteHello', methods = ['DELETE'])
def deleteRequestHello():
	return "Deleting your hard drive.....haha just kidding! I received a DELETE request!"

if __name__ == '__main__':
    app.debug = True
    app.run(host='0.0.0.0', port=5000)

parsing

>>> import urllib2
>>> import urllib
>>> p = urllib2.urlopen("http://www.google.com")
>>> p
>
>>> c = p.read()
>>> dir(p)
['__doc__', '__init__', '__iter__', '__module__', '__repr__', 'close', 'code', 'fileno', 'fp', 'getcode', 'geturl', 'headers', 'info', 'msg', 'next', 'read', 'readline', 'readlines', 'url']
>>> p.url
'http://www.google.co.jp/?gfe_rd=cr&ei=MtZkWNDXDYSL8QeD46cY'
>>> p.headers

>>> p.headers.items()
[('x-xss-protection', '1; mode=block'), ('set-cookie', 'NID=93=O65u9flBWzM92U9MzcezfIXaeG9itO-ala3ogt6T7fipovY5ily4QBNUxbUbsVga_hYeJEKWDq891mFaPgZm2Ya_1gvUZm37K2pNfFpOUVxCptVtOSAn3OXvUHCzKBaC; expires=Fri, 30-Jun-2017 09:24:02 GMT; path=/; domain=.google.co.jp; HttpOnly'), ('accept-ranges', 'none'), ('expires', '-1'), ('vary', 'Accept-Encoding'), ('server', 'gws'), ('connection', 'close'), ('cache-control', 'private, max-age=0'), ('date', 'Thu, 29 Dec 2016 09:24:02 GMT'), ('p3p', 'CP="This is not a P3P policy! See https://www.google.com/support/accounts/answer/151657?hl=en for more info."'), ('content-type', 'text/html; charset=Shift_JIS'), ('x-frame-options', 'SAMEORIGIN')]
>>> p.headers['content-type']
'text/html; charset=Shift_JIS'

>>> s = = urllib2.urlopen("http://www.example.com")
SyntaxError: invalid syntax
>>> s = urllib2.urlopen("http://www.example.com")
>>> s.url
'http://www.example.com'
>>> s.headers.items()
[('content-length', '1270'), ('x-ec-custom-error', '1'), ('x-cache', 'HIT'), ('expires', 'Thu, 05 Jan 2017 09:28:12 GMT'), ('vary', 'Accept-Encoding'), ('server', 'ECS (rhv/818F)'), ('last-modified', 'Fri, 09 Aug 2013 23:54:35 GMT'), ('connection', 'close'), ('etag', '"359670651+gzip+ident"'), ('cache-control', 'max-age=604800'), ('date', 'Thu, 29 Dec 2016 09:28:12 GMT'), ('content-type', 'text/html')]

parsing xml
from xml.com import minidom

json

>>> import json
>>> j = '{"one": 1, "numbers": [1,2,3.5]}'
>>> json.loads(j)
{u'numbers': [1, 2, 3.5], u'one': 1}

def total_ups():
    j = json.loads(reddit_front)
    sum(c['data']['ups'] for c in j['data']['children'])

host ip info
host ip info

IP_URL = "http://api.hostip.info/?ip="
def get_coords(ip):
    url = IP_URL + ip
    content = None
    content = urllib2.urlopen(url).read()
    except URLError:
        return
    if content:
        d = minidom.parseString(content)
        coords = d.getElementByTagName("gml:coordinates")
        if coords and coords[0].childNodes[0].nodeValue:
            lon, lat = coords[0].childNodes[0].nodeValue.split(',')
            return db.GetPt(lat, lon)

Gmap

GMAPS_URL = ""

def gmap_img(points):
    markers = '&'.join('makers=%s,%s' % (p.lat, p.lon)
        for p in points)
    return GMAPS_URL + markers

print gmaps_img([Point])

Querying

from collections import namedtuple

# make a basic Link class
Link = namedtuple('Link', ['id', 'submitter_id', 'submitted_time', 'votes',
                           'title', 'url'])

# list of Links to work with
links = [
    Link(0, 60398, 1334014208.0, 109,
         "C overtakes Java as the No. 1 programming language in the TIOBE index.",
         "http://pixelstech.net/article/index.php?id=1333969280"),
    Link(1, 60254, 1333962645.0, 891,
         "This explains why technical books are all ridiculously thick and overpriced",
         "http://prog21.dadgum.com/65.html"),
    Link(23, 62945, 1333894106.0, 351,
         "Learn Haskell Fast and Hard",
         "http://yannesposito.com/Scratch/en/blog/Haskell-the-Hard-Way/"),
    Link(2, 6084, 1333996166.0, 81,
         "Announcing Yesod 1.0- a robust, developer friendly, high performance web framework for Haskell",
         "http://www.yesodweb.com/blog/2012/04/announcing-yesod-1-0"),
    Link(3, 30305, 1333968061.0, 270,
         "TIL about the Lisp Curse",
         "http://www.winestockwebdesign.com/Essays/Lisp_Curse.html"),
    Link(4, 59008, 1334016506.0, 19,
         "The Downfall of Imperative Programming. Functional Programming and the Multicore Revolution",
         "http://fpcomplete.com/the-downfall-of-imperative-programming/"),
    Link(5, 8712, 1333993676.0, 26,
         "Open Source - Twitter Stock Market Game - ",
         "http://www.twitstreet.com/"),
    Link(6, 48626, 1333975127.0, 63,
         "First look: Qt 5 makes JavaScript a first-class citizen for app development",
         "http://arstechnica.com/business/news/2012/04/an-in-depth-look-at-qt-5-making-javascript-a-first-class-citizen-for-native-cross-platform-developme.ars"),
    Link(7, 30172, 1334017294.0, 5,
         "Benchmark of Dictionary Structures", "http://lh3lh3.users.sourceforge.net/udb.shtml"),
    Link(8, 678, 1334014446.0, 7,
         "If It's Not on Prod, It Doesn't Count: The Value of Frequent Releases",
         "http://bits.shutterstock.com/?p=165"),
    Link(9, 29168, 1334006443.0, 18,
         "Language proposal: dave",
         "http://davelang.github.com/"),
    Link(17, 48626, 1334020271.0, 1,
         "LispNYC and EmacsNYC meetup Tuesday Night: Large Scale Development with Elisp ",
         "http://www.meetup.com/LispNYC/events/47373722/"),
    Link(101, 62443, 1334018620.0, 4,
         "research!rsc: Zip Files All The Way Down",
         "http://research.swtch.com/zip"),
    Link(12, 10262, 1334018169.0, 5,
         "The Tyranny of the Diff",
         "http://michaelfeathers.typepad.com/michael_feathers_blog/2012/04/the-tyranny-of-the-diff.html"),
    Link(13, 20831, 1333996529.0, 14,
         "Understanding NIO.2 File Channels in Java 7",
         "http://java.dzone.com/articles/understanding-nio2-file"),
    Link(15, 62443, 1333900877.0, 1244,
         "Why vector icons don't work",
         "http://www.pushing-pixels.org/2011/11/04/about-those-vector-icons.html"),
    Link(14, 30650, 1334013659.0, 3,
         "Python - Getting Data Into Graphite - Code Examples",
         "http://coreygoldberg.blogspot.com/2012/04/python-getting-data-into-graphite-code.html"),
    Link(16, 15330, 1333985877.0, 9,
         "Mozilla: The Web as the Platform and The Kilimanjaro Event",
         "https://groups.google.com/forum/?fromgroups#!topic/mozilla.dev.planning/Y9v46wFeejA"),
    Link(18, 62443, 1333939389.0, 104,
         "github is making me feel stupid(er)",
         "http://www.serpentine.com/blog/2012/04/08/github-is-making-me-feel-stupider/"),
    Link(19, 6937, 1333949857.0, 39,
         "BitC Retrospective: The Issues with Type Classes",
         "http://www.bitc-lang.org/pipermail/bitc-dev/2012-April/003315.html"),
    Link(20, 51067, 1333974585.0, 14,
         "Object Oriented C: Class-like Structures",
         "http://cecilsunkure.blogspot.com/2012/04/object-oriented-c-class-like-structures.html"),
    Link(10, 23944, 1333943632.0, 188,
         "The LOVE game framework version 0.8.0 has been released - with GLSL shader support!",
         "https://love2d.org/forums/viewtopic.php?f=3&amp;t=8750"),
    Link(22, 39191, 1334005674.0, 11,
         "An open letter to language designers: Please kill your sacred cows. (megarant)",
         "http://joshondesign.com/2012/03/09/open-letter-language-designers"),
    Link(21, 3777, 1333996565.0, 2,
         "Developers guide to Garage48 hackatron",
         "http://martingryner.com/developers-guide-to-garage48-hackatron/"),
    Link(24, 48626, 1333934004.0, 17,
         "An R programmer looks at Julia",
         "http://www.r-bloggers.com/an-r-programmer-looks-at-julia/")]


# links is a list of Link objects. Links have a handful of properties. For
# example, a Link's number of votes can be accessed by link.votes if "link" is a
# Link.

# make the function query() return the number of votes for the link whose ID is
# 15

def query():
    submissions = []
    for l in links:
        if submitter_id = 62443:
            submissions.append(l)
    submissions.sort(key = lambda x: x.submitted_time)
    return submissions
print query()

template

import os
import webapp2

form_html = """
<form>
<h2>Add a Food</h2>
<input type="text" name="food">
%s 
<button>Add</button>
</form>
"""
hidden_html = """
<input type="hidden" name="food" value="%s">
"""

shopping_list_html = """
<br>
<br>
<h2>Shopping List</h2>
<ul>
%s
</ul>
"""

class Handler(webapp2.RequestHandler):
    def write(self, *a, **kw):
        self.response.out.write(*a, **kw)

class MainPage(Handler):
    def get(self):
        output = form_html
        hidden_html = ""

        items = self.request.get_all("food")
        if items:
        output_items = ""
        for item in items:
            output_hidden += hidden_html % item
            output_items += item_html % item

        output_shopping = shopping_list_html % output_items
        output += output_shopping

        output = output % output_hidden
            
        self.write(output)

app = webapp2.WSGIApplication([('/', MainPage),
                    ],
                    debug=True)

application:template-lesson
version: 1
runtime: python27
api_version: 1
threadsafe: True

handlers:
  - url: /.*
    script: templates.app

python template

<!DOCTYPE html>

<html>
  <head>
    <title>templates!</title>
  </head>

  <body style="margin: 0">
    <h1 style="background-color: #ddd: color: #888; margin: 0, height: 50px">
      Templates
    </h1>
    {% block content %}
    {% endblock %}
  </body>
</html>

{% extends "base.html" %}

{% block content %}
<form>
      <h2>Add a Food</h2>
      <input type="text" name="food">
      {% if items %}
        {% for item in items %}
          <input type="hidden" name="food" value="{{item}}">
        {% endfor %}
      <button>Add</button>

      {% if items %}
      <br>
      <br>

      <h2>Shopping List</h2>
      <ul>
        {% for item in items %}
        <li>{{ item | escape }}</li>
      </ul>
      {% endif %}
</form>
{% endblock %}