spanning trees

	from UnionFind import unionfind
	def kruskal(Ge, n):
	# Ge is a list of edges.
	# n is the number of vertices.
	Ge.sort(key=lambda x: x[2])
	Te = []
	uf = unionfind(n)
	for i, edge in enumerate(Ge):
	if not uf.connected(edge[0], edge[1]):
	Te.append(edge)
	uf.union(edge[0], edge[1])
	return Te

view raw kruskal.py hosted with ❤ by GitHub

	"""
	return any spanning tree out of a graph.
	"""
	from collections import deque
	def spanning_tree(graph):
	# graph is a list of lists
	root = 0
	tree = [[] for x in xrange(len(graph))]
	queue = deque([root])
	visited = set()
	while queue:
	node = queue.pop()
	visited.add(node)
	for x in graph[node]:
	if x not in visited:
	queue.appendleft(x)
	tree[node].append(x)
	visited.add(x)
	return tree

view raw spanning_tree_bfs.py hosted with ❤ by GitHub

	import array
	class unionfind:
	def __init__(self, n):
	self._length = n
	self._roots = array.array('L', [x for x in xrange(n)])
	self._weights = array.array('L', [1]*n)
	def __str__(self):
	return str(self._roots)
	def union(self, a, b):
	assert isinstance(a, int) and isinstance(b, int)
	assert a < self._length and b < self._length
	aroot = self.find(a)
	broot = self.find(b)
	if self._weights[aroot] > self._weights[broot]:
	self._roots[broot] = aroot
	self._weights[aroot] += self._weights[broot]
	self._weights[broot] = 0
	else:
	self._roots[aroot] = broot
	self._weights[broot] += self._weights[aroot]
	self._weights[aroot] = 0
	def connected(self, a, b):
	assert isinstance(a, int) and isinstance(b, int)
	assert a < self._length and b < self._length
	return self.find(a) == self.find(b)
	def find(self, a):
	assert isinstance(a, int)
	while self._roots[a] != a:
	self._roots[a] = self._roots[self._roots[a]]
	a = self._roots[a]
	return a

view raw UnionFind.py hosted with ❤ by GitHub

a simple proxy server

well i just tried to implement the basic concept of a proxy server, i.e

1. intercept the request

2. handle the request,(make necessary changes to the request)

3. perform the modified request

4. handle the response,(make necessary changes to the response)

5. send the modified reponse to the user.

	import BaseHTTPServer
	import requests
	class proxy(BaseHTTPServer.BaseHTTPRequestHandler):
	def do_GET(self):
	print self.path
	print self.headers
	print self.server.server_name
	print self.server.server_port
	self.send_header("Content-type", "text/html")
	self.end_headers()
	print self.path.strip('/')
	resp = requests.get('http://' + self.path.strip('/'))
	print resp.status_code
	self.send_response(resp.status_code)
	print resp.content
	self.wfile.write(resp.content)
	def run():
	host = ('', 9999)
	prod = BaseHTTPServer.HTTPServer(host, proxy)
	print 'running server on', host
	prod.serve_forever()
	run()

view raw proxy_server.py hosted with ❤ by GitHub

It’s working great with the curl and httpie, but it is not working well enough when it comes to browsers

I wish that i knew factor.io before nonsenso.

I wish that i knew factor.io before nonsenso.
It was always messy to manage a site using different services.

Red Black Tree coloring bit

in python it’s quite difficult allocate  single bit for coloring a node as every thing in python is reference based. so it’s a nice practice to borrow a bit from the height of the red black tree, i.e just increment the height in 2’s and if the color is black just add one or else leave it. and we can retrieve the bit using height & 1 or height % 2

serializing and deserializing binary search tree

just extending the previous binary search tree code

	class BST(object):
	def __init__(self):
	self.root = None
	def insert(self, t):
	"""
	Insert key t into this BST, modifying it in-place.
	"""
	new = BSTnode(t)
	if self.root is None:
	self.root = new
	return new
	# else:
	node = self.root
	while True:
	if t < node.key:
	# Go left
	if node.left is None:
	node.left = new
	new.parent = node
	break
	node = node.left
	else:
	# Go right
	if node.right is None:
	node.right = new
	new.parent = node
	break
	node = node.right
	return new
	def find(self, t):
	"""
	Return the node for key t if is in the tree, or None otherwise.
	"""
	node = self.root
	while node is not None:
	if t == node.key:
	return node
	elif t < node.key:
	node = node.left
	else:
	node = node.right
	return None
	def delete(self, t):
	# TODO: test this thing
	node = self.find(t)
	if node is None:
	return None, None
	if node.left is not None:
	maximum, parent = self.delete_max(node.left)
	elif node.right is not None:
	maximum, parent = self.delete_min(node.right)
	else:
	if node.parent is not None:
	if node.parent.left is node:
	node.parent.left = None
	else:
	node.parent.right = None
	else:
	self.root = None
	node.disconnect()
	return node, None
	maximum.parent = node.parent
	maximum.left = node.left
	maximum.right = node.right
	if maximum.left is not None:
	maximum.left.parent = maximum
	if maximum.right is not None:
	maximum.right.parent = maximum
	if maximum.parent is not None:
	if maximum.parent.left is node:
	maximum.parent.left = maximum
	else:
	maximum.parent.right = maximum
	if node is self.root:
	self.root = maximum
	parent = node.parent
	node.disconnect()
	return node, parent
	def minimum(self):
	# TODO: test this thing
	if self.root is None:
	return None
	node = self.root
	while node.left is not None:
	node = node.left
	return node
	def maximum(self):
	# TODO: test this thing
	if self.root is None:
	return None
	node = self.root
	while node.right is not None:
	node = node.right
	return node
	def delete_max(self, root=None):
	root = root or self.root
	if root is None:
	return None, None
	else:
	maximum = root
	while maximum.right is not None:
	maximum = maximum.right
	if maximum is not root:
	maximum.parent.right = maximum.left
	elif maximum.parent is not None:
	if maximum.parent.left is maximum:
	maximum.parent.left = maximum.left
	else:
	maximum.parent.right = maximum.right
	else:
	self.root = maximum.left
	if maximum.left is not None:
	maximum.left.parent = maximum.parent
	parent = maximum.parent
	maximum.disconnect()
	return maximum, parent
	def delete_min(self, root=None):
	"""
	Delete the minimum key (and return the old node containing it).
	"""
	root = root or self.root
	if root is None:
	return None, None
	else:
	# Walk to leftmost node.
	node = root
	while node.left is not None:
	node = node.left
	# Remove that node and promote its right subtree.
	if node is not root:
	node.parent.left = node.right
	elif node.parent is not None: # The root was smallest.
	if node.parent.left is node:
	node.parent.left = node.right
	else:
	node.parent.right = node.right
	else:
	self.root = node.right
	if node.right is not None:
	node.right.parent = node.parent
	parent = node.parent
	node.disconnect()
	return node, parent
	def __str__(self):
	if self.root is None:
	return '<empty tree>'
	def recurse(node):
	if node is None:
	return [], 0, 0
	label = str(node.key)
	left_lines, left_pos, left_width = recurse(node.left)
	right_lines, right_pos, right_width = recurse(node.right)
	middle = max(right_pos + left_width - left_pos + 1, len(label), 2)
	pos = left_pos + middle // 2
	width = left_pos + middle + right_width - right_pos
	while len(left_lines) < len(right_lines):
	left_lines.append(' ' * left_width)
	while len(right_lines) < len(left_lines):
	right_lines.append(' ' * right_width)
	if (middle - len(label)) % 2 == 1 and node.parent is not None and \
	node is node.parent.left and len(label) < middle:
	label += '.'
	label = label.center(middle, '.')
	if label[0] == '.':
	label = ' ' + label[1:]
	if label[-1] == '.':
	label = label[:-1] + ' '
	lines = [
	' ' * left_pos + label + ' ' * (right_width - right_pos),
	' ' * left_pos + '/' + ' ' * (middle - 2) +
	'\\' + ' ' * (right_width - right_pos)] + \
	[
	left_line + ' ' *
	(width - left_width - right_width) +
	right_line
	for left_line, right_line in zip(left_lines, right_lines)
	]
	return lines, pos, width
	return '\n'.join(recurse(self.root)[0])
	def serialize(self):
	r = self.root
	if not self.root:
	return []
	stack = [r]
	result = []
	while stack:
	node = stack.pop()
	result.append(node)
	if not node.left:
	stack.append(node.left)
	if not node.right:
	stack.append(node.right)
	return '|'.join([str(x) for x in result])
	def deserialize(self, data):
	data = map(int, data.split('|'))
	for x in data:
	self.insert(x)
	class BSTnode(object):
	"""
	Representation of a node in a binary search tree.
	Has a left child, right child, and key value.
	"""
	def __init__(self, t):
	"""
	Create a new leaf with key t.
	"""
	self.key = t
	self.disconnect()
	def disconnect(self):
	self.left = None
	self.right = None
	self.parent = None
	def has_left(self):
	return self.left
	def has_right(self):
	return self.right
	def is_left(self):
	return self.parent and self.parent.left is self
	def is_right(self):
	return self.parent and self.parent.right is self
	def is_root(self):
	return not self.parent
	def has_anychild(self):
	return self.left or self.right
	def has_allchild(self):
	return self.left and self.right
	def test(args=None, BSTtype=BST):
	import random
	import sys
	if not args:
	args = sys.argv[1:]
	if not args:
	print 'usage: %s <number-of-random-items | item item item ...>' % \
	sys.argv[0]
	sys.exit()
	elif len(args) == 1:
	items = [random.randrange(100) for i in xrange(int(args[0]))]
	else:
	items = [int(i) for i in args]
	tree = BSTtype()
	print tree
	for item in items:
	tree.insert(item)
	print
	print tree
	print '-------------------------------------------'
	for item in items:
	tree.delete(item)
	print
	print tree
	if __name__ == '__main__':
	test()

view raw bst.py hosted with ❤ by GitHub

maximum sub array sum

the beauty of python

	def maximum_subarray_sum(a):
	maximumsum = tmpsum = -float('inf')
	for x in a:
	tmpsum = max(x, tmpsum + x)
	maximumsum = max(maximumsum, tmpsum)
	return maximumsum

view raw maximum_subarray_sum.py hosted with ❤ by GitHub

pyjs is real magic

finally using powerline in ipython in its full power !

after some edits in my unicode.json powerline.json and my default ipython theme, i finally made it!

So INVCNT can’t be solved using python

neither the merge sort routine nor the BIT implementation was able to solve it in 1S using python.

	#include <stdio.h>
	long long int temp_array[200005];
	long long int split_inversions(long long int a[], long long int lo, long long int hi)
	{
	if(hi - lo <= 1)
	return 0;
	long long int mid = lo + (hi - lo) / 2;
	long long int i = lo;
	long long int j = mid;
	long long int inv = 0;
	long long int k = lo;
	while(i < mid && j < hi)
	{
	if (a[i] > a[j])
	{
	inv += mid - i;
	temp_array[k++] = a[j++];
	}
	else
	{
	temp_array[k++] = a[i++];
	}
	}
	while(i < mid)
	{
	temp_array[k++] = a[i++];
	}
	while(j < hi)
	{
	temp_array[k++] = a[j++];
	}
	for(i = lo; i < hi; i++)
	a[i] = temp_array[i];
	return inv;
	}
	long long int inversions(long long int a[], long long int lo, long long int hi)
	{
	if (hi - lo <= 1)
	return 0;
	long long int inv;
	inv = inversions(a, lo, lo + (hi - lo) / 2);
	inv += inversions(a, lo + (hi - lo) / 2, hi);
	inv += split_inversions(a, lo, hi);
	return inv;
	}
	long long int get_int(long long int n)
	{
	int sign=1;
	char c=0;
	while(c<33)
	c=getchar_unlocked();
	if (c=='-')
	{
	sign=-1;
	c=getchar_unlocked();
	}
	while(c>='0'&&c<='9')
	{
	n=(n<<3)+(n<<1)+(c-'0');
	c=getchar_unlocked();
	}
	return n*sign;
	}
	int main(int argc, const char *argv[])
	{
	long long int tests, n, i;
	tests = get_int(0);
	while (tests--)
	{
	n = get_int(0);
	long long int a[n];
	for (i = 0; i < n; i++)
	a[i] = get_int(0);
	printf("%lld\n", inversions(a, 0, n));
	}
	return 0;
	}

view raw invcnt.c hosted with ❤ by GitHub

	from bisect import bisect
	def inversions(a):
	t = []
	count = 0
	for x in xrange(len(a)):
	i = bisect(t, a[x])
	t.insert(i, a[x])
	count += x - i
	return count
	temp_array = [0]*200000
	def split_inversions(a, lo, hi):
	if hi - lo <= 1:
	return 0
	mid = lo + (hi - lo) // 2
	i = lo
	j = mid
	inv = 0
	k = lo
	while i < mid and j < hi:
	if a[i] > a[j]:
	inv += mid - i
	temp_array[k] = a[j]
	j += 1
	k += 1
	else:
	temp_array[k] = a[i]
	i += 1
	k += 1
	while i < mid:
	temp_array[k] = a[i]
	i += 1
	k += 1
	while j < hi:
	temp_array[k] = a[j]
	j += 1
	k += 1
	for x in xrange(lo, hi):
	a[x] = temp_array[x]
	return inv
	def count_inversions(a, l, h):
	if h - l <= 1:
	return 0
	inv = count_inversions(a, l, l + (h - l) // 2)
	inv += count_inversions(a, l + (h - l) // 2, h)
	inv += split_inversions(a, l, h)
	return inv
	class Bit:
	def __init__(self, n):
	sz = 1
	while n > sz:
	sz *= 2
	self.size = sz
	self.data = [0]*sz
	def sum(self, i):
	s = 0
	while i > 0:
	s += self.data[i]
	i -= i & -i
	return s
	def add(self, i, x):
	while i < self.size:
	self.data[i] += x
	i += i & -i
	def count_inversion_using_BIT(a):
	res = 0
	bit = Bit(max(a)+1)
	for i, v in enumerate(a):
	res += i - bit.sum(v)
	bit.add(v, 1)
	return res
	for tests in xrange(int(raw_input())):
	raw_input()
	n = int(raw_input())
	a = []
	append = a.append
	for x in xrange(n):
	append(int(raw_input()))
	print count_inversion_using_BIT(a)

view raw invcnt.py hosted with ❤ by GitHub

complete spoj database using Beautiful Soup

https://gist.github.com/9bca355f38444a161ef8