Algorithm Examples

Question 1

Fibonacci - Python

Answer 1

def fib(n):
    """
    >>> [fib(n) for n in range(10)]
    [0, 1, 1,  2, 3, 5, 8, 13, 21, 34]
    """
    if n <= 1:
        return n 
    return fib(n-1) + fib(n-2)

Question 2

Cache decorator - Python

Answer 2

def mem(func):
    cached = dict()
    def inner(n):
        if n not in cached:
            cached[n] = func(n)
        return cached[n]    
    return inner

@mem
def fib(n):
if n < 2:
return 1
return fib(n-2) + fib(n-1)
~~~
~~~

Question 3

Prime number checker - Python

Answer 3

def is_prime(n):
    if n < 2:
        return False

    for i in filter(lambda x: x % 2 != 0, range(2, int(n**0.5))):
        if n % i == 0:
            return False

    return True

print filter(is_prime, range(100))
~~~
~~~

Question 4

Quick sort - Python

Answer 4

def q_sort(a):
    if len(a) in (0, 1):
        return a

    p = a[-1]
    l = [x for x in a[:-1] if x <= p]
    r = [x for x in a[:-1] if x >  p]

return q_sort(l) + [p] + q_sort(r) ~~~ ~~~

Question 5

Bubble sort - Python

Answer 5

def bubble(l_elems, is_sorted, step):
    if step is 1 or is_sorted:
        return l_elems
    else:
        is_swapped = False
        for i in range(len(l_elems) - 1):
            if l_elems[i] > l_elems[i + 1]:
                is_swapped = True
                l_elems[i], l_elems[i + 1] = l_elems[i + 1], l_elems[i]
        return bubble(l_elems, not is_swapped, step - 1)

print(bubble(range(10,0,-1), False, len(range(10,0,-1))))
print(bubble([5,6,5,3,3], False, len([5,6,5,3,3])))

https://gist.github.com/jootse84/3c51a776471a37beebac10d42ba9f42f

Question 6

Depth First Search - Python

Answer 6

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
~~~

dfs(graph, ‘C’) # {‘E’, ‘D’, ‘F’, ‘A’, ‘C’, ‘B’}
~~~

http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

Question 7

Breadth First Search - Python

Answer 7

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
~~~

bfs(graph, ‘A’) # {‘B’, ‘C’, ‘A’, ‘F’, ‘D’, ‘E’}
~~~

http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

Question 8

Binary search - Python

Answer 8

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False

while first<=last and not found:
    midpoint = (first + last)//2
    if alist[midpoint] == item:
        found = True
    else:
        if item < alist[midpoint]:
            last = midpoint-1
        else:
            first = midpoint+1 ~~~

return found ~~~

5.4. The Binary Search — Problem Solving with Algorithms and Data Structures

Question 9

Factorial - Python

Answer 9

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

Question 10

Linear Search - Python

Answer 10

def search(arr, x):

    for i in range(len(arr)):

        if arr[i] == x:
            return i

    return -1

Question 11

Binary tree - Python

Answer 11

class Tree(object):
    def \_\_init\_\_(self):
        self.left = None
        self.right = None
        self.data = None

root = Tree()

root. data = “root”
root. left = Tree()
root. left.data = “left”
root. right = Tree()
root. right.data = “right”

print(root.left.data)

Question 12

Tree data - Python

Answer 12

from collections import defaultdict

def tree():
    return defaultdict(tree)

or

tree = lambda: defaultdict (tree)

https://gist.github.com/hrldcpr/2012250

Question 13

N-queens problem - Python

Answer 13

BOARD_SIZE = 8

def under_attack(col, queens):
return col in queens or \
any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))
~~~

def solve(n):
solutions = [[]]
for row in range(n):
solutions = (solution+[i+1]
for solution in solutions
for i in range(BOARD_SIZE)
if not under_attack(i+1, solution))
return solutions

answers = solve(BOARD_SIZE)
first_answer = next(answers)
print(list(enumerate(first_answer, start=1)))
~~~

https://rosettacode.org/wiki/N-queens_problem#Python