Archive | August 2013

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

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