Skip to content

Instantly share code, notes, and snippets.

View irachex's full-sized avatar

Huayi Zhang irachex

175 followers · 106 following
View GitHub Profile
@irachex
irachex / h2server.py
Last active October 31, 2016 06:21
import sys
import json
import socket
import h2.connection
import h2.events
def send_response(conn, event):
stream_id = event.stream_id
response_data = json.dumps(dict(event.headers)).encode('utf-8')
@irachex
irachex / minimum_spanning_tree.py
Created February 9, 2014 09:26
"""
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=203
"""
import math
def prim(n, edges):
g = [[] for i in range(n)]
for u, v, w in edges:
@irachex
irachex / test.py
Last active December 13, 2015 19:09
http://www.douban.com/people/mckelvin/status/1100048453/#last
cnt = {}
MAX_DEP = 10
def traverse(dep, i, size):
cnt[i] = cnt.get(i, 0) + 1
if dep >= MAX_DEP: return
for j in range(size):
traverse(dep + 1, i + j + 1, size + 1 - j)
traverse(0, 0, 1)
@irachex
irachex / getDistanceFromLatLon.coffee
Last active December 10, 2015 13:48
calculate distance between two latitude-longitude points. using Haversine formula http://en.wikipedia.org/wiki/Haversine_formula
getDistanceFromLatLonInKm = (lat1, lon1, lat2, lon2)->
R = 6371 # Radius of the earth in km
dLat = deg2rad(lat2 - lat1) # deg2rad below
dLon = deg2rad(lon2 - lon1)
a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) *
Math.sin(dLon/2) * Math.sin(dLon/2)
c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a))
d = R * c # Distance in km
return d
@irachex
irachex / TinyHTTPProxy.py
Created November 9, 2012 02:21
Tiny HTTP Proxy. Usuage: python TinyHTTPProxy.py -p 11028
#!/usr/bin/python
__doc__ = """Tiny HTTP Proxy.
This module implements GET, HEAD, POST, PUT and DELETE methods
on BaseHTTPServer, and behaves as an HTTP proxy. The CONNECT
method is also implemented experimentally, but has not been
tested yet.
Any help will be greatly appreciated. SUZUKI Hisao
@irachex
irachex / Treap.py
Created October 20, 2012 08:43
Treap (tree + heap) in Python
import random
class TreapNode(object):
def __init__(self, key, data):
self.key = key
self.ran = random.random()
self.size = 1
self.cnt = 1
self.data = data
self.left = None
@irachex
irachex / tarjan.py
Created October 20, 2012 08:42
Tarjan (find articulation vertex and bridges in graph) non-recursive (use stack) in Python
def tarjan(N, S, T, edges):
cnt = 0
bridges = []
visit = [0 for i in range(N)]
low = [N + 1 for i in range(N)]
ret = [False for i in range(N)]
q = [0 for i in range(N + 1)]
q[0] = (S, -1, -1)
top = 0
while top >= 0:
@irachex
irachex / dijkstra.py
Created October 20, 2012 08:38
Dijkstra (with Heap optimized) in Python
from heapq import heappush, heappop
def dijkstra(N, S, edges):
d = [INF for i in range(N)]
d[S] = 0
h = []
heappush(h, (0, S))
for i in range(N - 1):
min_dist, k = 0, 0
if not h: break
@irachex
irachex / SegmentTree.py
Created October 20, 2012 08:36
SegmentTree in Python
INF = 999999999999999
class SegTreeNode(object):
def __init__(self, left, right, data):
self.left = left
self.right = right
self.data = data
self.left_child = None
self.right_child = None
@irachex
irachex / PriorityQueue.py
Created October 20, 2012 08:34
PriorityQueue implements in Python
from collections import deque
class PriorityQueueNode(object):
def __init__(self, id, value):
self.id = id
self.value = value
class PriorityQueue(object):
def __init__(self, k):
self.q = deque()