Code that is commonly used in programming contest problems

util.py

# C-Snake's Ruby
# Commonly used contest code
# 
# Last updated: 3-1-2010
import math

def fib(n):
 '''Returns the nth fibonacci number O(n)'''
 a, b = 0, 1
 i = 1
 while i < n:
   a, b = b, a + b
   i += 1
 return b

def factorial(n):
 '''Python 2.6 has this but oh well'''
 result = 1
 for i in xrange(1, n + 1):
   result *= i
 return result

def ffib(n):
 '''Returns the nth fibonacci number O(log n)'''
 i = h = 1
 j = k = 0
 while n > 0:
   if n % 2 == 1:
     t = j * h
     j = (i * h) + (j * k) + t
     i = (i * k) + t

   t = h * h
   h = (2 * k * h) + t
   k = (k * k) + t
   n /= 2

 return j

def maxSum_1D(seq):
 '''1-D max subsequence'''
 maxsofar = 0
 maxendinghere = 0
 for s in seq:
   maxendinghere = max(maxendinghere + s, 0)
   maxsofar = max(maxsofar, maxendinghere)
 return maxsofar

def prime_sieve(ceiling=None):
 '''Prime number sieve of eratosthenes'''
 if ceiling is not None:
   if ceiling % 2 == 0:
     ceiling -= 1
   highest_prime = math.ceil(math.sqrt(ceiling))
 last_val = 1
 found_primes = []
 yield 2
 while ceiling is None or ceiling > last_val:
   current_val = None
   while current_val is None:
     current_val = last_val = last_val + 2
     for prime, square in found_primes:
       if current_val < square: 
         break
       if current_val % prime == 0:
         current_val = None
         break
   yield current_val
   if ceiling is None or highest_prime > last_val:
     found_primes.append((current_val, current_val ** 2))

def is_prime(n):
 '''Determines if a number is prime using the sieve'''
 for fac in prime_sieve(int(math.ceil(math.sqrt(n)))):
   if n % fac == 0 and n != fac:
     return False
 return True if n > 1 else False

def gcd(a, b):
 '''Finds the GCD of a and b using the euclidian algorithm'''
 while (b > 0):
   a = a % b
   a ^= b
   b ^= a
   a ^= b

 return a

def extended_gcd(a, b):
 '''Finds x, y and GCD in ax + by = gcd(a, b)'''
 x = 0
 lastX = 1
 y = 1
 lastY = 0
 while (b != 0):
   q = a / b

   temp = b
   b = a % b
   a = temp

   temp = x
   x = lastX - (q * x)
   lastx = temp

   temp = y
   y = lastY - (q * y)
   lastY = temp
 return (lastX, lastY, a)

def extended_gcd_recursive(a, b):
 '''Finds x and y in ax + by = gcd(a, b)'''
 if a % b == 0:
   return (0, 1)
 else:
   x, y = extended_gcd_recursive(b, a % b)
   return (y, x - y * (a / b))