Python Tutorial

Tuesday, December 11, 2012

Problem solving using python: Count on Cantor


Count on Cantor: https://www.spoj.com/problems/CANTON/
All source code available on github

import math

def solution(n):
    t = float(math.sqrt(1+8*(n-1)))
    k = int((t+1)/2)
    a = int((k*(k-1))/2)
    b = n - a
    if k%2==0:
        return b,(k+1)-b
    return (k+1)-b, b

case = input()
while case>0:
    n=input()
    case = case -1
    a, b = solution(n)
    print "TERM %d IS %d/%d" % (n,a,b)

Problem solving using python: Adding Reversed Numbers


Adding Reversed Numbers: http://www.spoj.com/problems/ADDREV/


All source code available on github

# python 2.7
n=input()
while n>0:
    a, b = [int(x) for x in raw_input().split()]
    sa, sb=str(a)[::-1],str(b)[::-1]
    sr =str( int(sa)+int(sb) )
    sr = sr[::-1]
    print int(sr)
    n=n-1

Wednesday, December 5, 2012

Problem solving using python: Small factorials


Small factorials: https://www.spoj.pl/problems/FCTRL2/

All source code available on github

# python 2.7
def fact(n):
    if n==0:
        return 1
    return n*fact(n-1)

n = input()
while n>0:
    n=n-1
    k=input()
    print fact(k)

Problem solving using python


Currently I am starting to solve online programming problems using python. Spoj support python as well as other's language. Here I post some of my solved problems code of Spoj site, so that you can find how to solve programming problems in python. Lets have fun ....
Life, the Universe, and Everything :
https://www.spoj.pl/problems/TEST/
All source code available on github

# python 2.7
num=input()
while num!=42:
    print num
    num=input()


Tuesday, December 4, 2012

Django-piston REST API


REST API using django and django-piston.
Piston lets you develop API for your site. From my experience in piston you can write API very fast. Lets have a small drive ...
A sample API code with readme available on github.

Monday, December 3, 2012

DFS Algorithm in Python


Depth-first search (DFS) is very usefull for traversing or searching a tree, tree structure, or graph. Here python implementation of DFS .
All source code available on github

 # DA_DFS.py
class DFS:
    def __init__(self, node,edges):
        self.node = node
        self.edges = edges
        self.color=['W' for i in range(0,node)] # W for White
        self.graph =color=[[False for i in range(0,node)] for j in range(0,node)]
        self.parent =[-1 for u in range(0,node)]

        # Start DFS
        self.construct_graph()
        self.dfs_traversal()

    def construct_graph(self):
        for u,v in self.edges:
            self.graph[u][v], self.graph[v][u] = True, True

    def dfs_visit(self, u):
        self.color[u]='G' # G for Gray
        for i in range(0, self.node):
            if self.graph[u][i]==True and self.color[i]=='W':
                self.parent[i]=u
                self.dfs_visit(i)
        self.color[u]='B' # B for black

    def dfs_traversal(self):
        for i in range(0,self.node):
            if self.color[i]=='W': # W for white
                self.dfs_visit(i)

    def print_path(self, source, destination):
        if destination==source:
            print destination,
        elif self.parent[destination] == -1:
            print "No Path"
        else:
            self.print_path(source, self.parent[destination])
            print "-> ",destination,

node = 8 # 8 nodes from 0 to 7
edges =[(0,1),(0,3),(1,2),(1,5),(2,7),(3,4),(3,6),(4,5),(5,7)] # bi-directional edge

dfs = DFS(node, edges)
dfs.print_path(0, 7)
print ""
dfs.print_path(2, 5)
print ""
dfs.print_path(0, 4)


Output:
0 ->  1 ->  2 ->  7 
2 ->  7 ->  5 
0 ->  1 ->  2 ->  7 ->  5 ->  4

BFS Algorithm in Python


Breadth-first search(BFS) is one of the most widely used graph algorithm for single source shortest path. Here I shown python implemenation of this beautiful algorithm.
All source code available on github

#DA_BFS.py
from collections import deque

class BFS:
    def __init__(self, node,edges, source):
        self.node = node
        self.edges = edges
        self.source = source
        self.color=['W' for i in range(0,node)] # W for White
        self.graph =color=[[False for i in range(0,node)] for j in range(0,node)]
        self.queue = deque()
        self.parent =[-1 for u in range(0,node)]

        # Start BFS algorithm
        self.construct_graph()
        self.bfs_traversal()

    def construct_graph(self):
        for u,v in self.edges:
            self.graph[u][v], self.graph[v][u] = True, True

    def bfs_traversal(self):

        self.queue.append(self.source)
        self.color[self.source] = 'B' # B for Black

        while len(self.queue):
            u =  self.queue.popleft()
            for v in range(0,self.node):
                if self.graph[u][v] == True and self.color[v]=='W':
                    self.color[v]='B'
                    self.queue.append(v)
                    self.parent[v]=u

    def print_shortest_path(self, destination):
        if destination==self.source:
            print destination,
        elif self.parent[destination] == -1:
            print "No Path"
        else:
            self.print_shortest_path(self.parent[destination])
            print "-> ",destination,



node = 8 # 8 nodes from 0 to 7
edges =[(0,1),(0,3),(1,2),(1,5),(2,7),(3,4),(3,6),(4,5),(5,7)] # bi-directional edge
source = 0 # set fist node (0) as source

bfs = BFS(node,edges,source)
bfs.print_shortest_path(5) # shortest path from 0 to 5
print
bfs.print_shortest_path(7) # shortest path from 0 to 7


Output:
0 ->  1 ->  5
0 ->  1 ->  2 ->  7

python dequeue data structure


Double-ended queue(dequeue) in python.
All source code available on github

#DA_Dequeue.py

from collections import deque

myDequeue = deque()

myDequeue.append(5) # insert element at back
myDequeue.appendleft(9) # insert element at front
myDequeue.append(55)
myDequeue.appendleft(99)
print myDequeue

print myDequeue.pop() # remove last element
print myDequeue
print myDequeue.popleft() # remove first element
print myDequeue
print myDequeue[-1] # last element
print myDequeue[0] # fist element



Output:
deque([99, 9, 5, 55])
55
deque([99, 9, 5])
99
deque([9, 5])
5
9