Archive | Programming RSS for this section

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

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()

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)

Binary search – Python implementation

def binarySearch(array,item):
    if len(array) == 0: return False
    else:
        mid = len(array)//2
        if array[mid] == item:
            return True
        else:
            if item < array[mid]:
                return binarySearch(array[:mid],item)
            else:
                return binarySearch(array[mid+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))