compute_power.py

# compute_power O(logn) 
def compute_power(a, p, m):
  result = 1
  p_bin = bin(p)[2:]
  length = len(p_bin)
  for i in range(0, length):
    result = result**2 % m
    if p_bin[i] == '1':
      result = result * a % m
  return result

gistfile1.txt

Four Tricks for Comprehensions in Python
http://tech.pro/tutorial/1554/four-tricks-for-comprehensions-in-python

Creates an iterator (or more precisely: a generator object) that evaluates the expression when it is needed.
A generator object can be iterated over exactly once.

text = "My hovercraft is full of eels."
first_chars = (word[0] for word in text.split())
for char in first_chars:
  print(char)

Loops
combinatorial functions in itertools: permutations(), combinations() and combinations_with_replacement()
http://docs.python.org/2/library/itertools

nucleobases = "GTCA"
results = ["".join(c) for c in product(nucleobases, repeat=4)]

Transpose Matrices
transposed = list(map(list, zip(*matrix)))

monty-hall.py

import random
 
def select():
    return random.randint(0,2) 
 
sum=0.0;change=0;notchange=0;
 
def game():
    global sum,change,notchange
    gift=select()
    choose=select()
    opendoor=select()
    while opendoor==choose or (opendoor!=choose and opendoor==gift):
        #re-select
        opendoor=select()
 
    sum=sum+1
    if choose==gift:
        notchange=notchange+1
    else:
        change=change+1
 
for i in xrange(100000):
    game()
print change/sum,notchange/sum

prime_test_fermat.py

# prime test
# http://blog.codinglabs.org/articles/prime-test.html
# a^(p-1) mod p=1 (p is a prime)
def prime_test_fermat(p):
  if p == 1:
    return False
  if p == 2:
    return True   
  d = compute_power(2, p - 1, p)
  if d == 1:
    return True
  return False
 
# some tests  
print prime_test_fermat(7) #True
print prime_test_fermat(11) #True
print prime_test_fermat(15) #False
print prime_test_fermat(121) #False
print prime_test_fermat(561) #True !wrong!561=3*187

Python code snippets

Python code snippets