#python scripts I written when learning it. #math

README.markdown

Some scripts I've written when learning Python. Most of them are trying to slove math problems.

factor.py

''' find factors of a number
Author: Mike Hanse
URL: http://sage.math.washington.edu/home/mhansen/factor.py
Descriptions: This code shows an efficient method to find all the factors:
find all of the prime factors and then build up all of the factors from that.

'''

def pull_off_factors(n, p, output_list):
    count = 0
    while True:
        if n % p == 0:
            count += 1
            n = n // p
        else:
            if count != 0:
                output_list.append((p, count))
            break
    return n


def prime_factors(n):
    output_list = []
    primes = [2,3,5,7,11,13,17,19,23,29]
    other_primes = [1,7,11,13,17,19,23,29]

    for p in primes:
        n = pull_off_factors(n, p, output_list)

    c = 0
    while True:
        top = n**0.5 + 1

        c += 30
        if c > top:
            if n != 1:
                output_list.append((n,1))
            return output_list
        for p in other_primes:
            n = pull_off_factors(n, c+p, output_list)

def factors(n):
    factors = prime_factors(n)

    all = [1]
    for p,e in factors:
        prev = all[:]
        pn = 1
        for i in range(e):
            pn *= p
            all.extend([a*pn for a in prev])        
    all.sort()
    return all

function_decorators.py

#-------------------------------------------------------------------------------
# File:         function_decorators.py
#
# Description:  Two examples of how to write your own decorators in Python. 
#               Uses Python v3.0.
#
# Associated article: http://programmingbits.pythonblogs.com/27_programmingbits/archive/50_function_decorators.html
#
# (C) 2009 by Ariel Ortiz, Tecnologico de Monterrey, Campus Estado de Mexico.
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
#-------------------------------------------------------------------------------

def memoize(f):
    cache = {}
    def helper(x):
        if x not in cache:            
            cache[x] = f(x)
        return cache[x]
    return helper
    
def trace(f):
    def helper(x):
        call_str = '{0}({1})'.format(f.__name__, x)
        print('Calling {0} ...'.format(call_str))
        result = f(x)
        print('... returning from {0} = {1}'.format(call_str, result))
        return result
    return helper

@memoize
@trace
def fib(n):
    if n in (0, 1):
        return n
    else:
        return fib(n - 1) + fib(n - 2)        
        

isPerfect.py

#!/usr/bin/env python2.5

'''Test whether a number is perfect or in an amicable pair.

by Jakukyo Friel <weakish@gmail.com> under GPL v2

'''

def divisor(n):
    from factor import factors
    return sum(factors(n))

properDivisor = lambda n: divisor(n) - n


isPerfect = lambda n: 1 if properDivisor(n) == n else 0

def isAmicable(n):
    if isPerfect(n):
        return 0
    else:
        pair = properDivisor(n)
        if properDivisor(pair) == n: return 1
        else: return 0

if __name__ == '__main__':
    def testNum(n):
        if isPerfect(n): print '%d is perfect.' % (n,)
        elif isAmicable(n): print '%d is amicable with %d.' %(n, properDivisor(n))
        else: print '%d is neither perfect nor amicable.' %(n,)
    while 1:
        testNum(input('Type an inter: '))
        

poly.py

'''poly
Tested with python 2.5
Constructs cubic polynomials such that the set for natural numbers
where its value is at least 3 is {n belongs to N: n=1 or n>5}

by Jakukyo Friel <weakish@gmail.com> under GPL v2

'''

abs = 10  # hard-coded value of min/max

cubes = lambda: (  # list "all" possiblie polynomials considering n=1 
    (
    lambda n:(a * n ** 3 + b * n ** 2 + c * n + d, [a, b, c, d])
    for a in range(-abs, abs)
    for b in range(-abs, abs)
    for c in range(-abs, abs)
    for d in range(-abs, abs)
    if a != 0  # must be cubic polynomials
    if a + b + c + d >= 3  # n=1
    )
)

slicePre = lambda n: (
    (cube for cube in cubes() if cube(n)[0] < 3)
    if n == 2  # for n in [2,4], the polynomial < 3
    else (cube for cube in slicePre(n-1) if cube(n)[0] < 3)
)

slice = lambda n: (
    (cube for cube in slicePre(4)) 
    if n == 4  # for n>=5, the polynomial >= 3
    else (cube for cube in slice(n-1) if cube(n)[0] >= 3)
)

# list groups of coefficients
# Don't use a too big value of n. Otherwise, you'll exceed maximum recursion depth.
res = lambda n = 50: [cube(1)[1] for cube in slice(n)]

rm_coin.py

# by Jakukyo Friel <weakish@gmail.com> under GPL v2

''' The Coin-Removal Problem.
Suppose n coins are arranged in a row.  Coins may be heads-up (H) or tails-up (T).  We are allowed the following operation: remove an H and flip the coin or coins in the immediate neighboring position(s), if these are still present.  For which arrangements of heads and tails can we remove all the coins?  (When we remove a coin between two others, the others do NOT become neighbors.)  For example, THHHT succeeds, via THHHT, H.THT, ..THT, ..H.H, ....H, ....., but THTHT fails.

'''

from weakish_fn import seq2dict, genP, dict2str


# Generate all possible permutations for the given number and store them
# in a dictionary for further manipulation.
genRows = lambda n: [seq2dict(row) for row in genP(n,'HT')]

# N stands for an empty position/an nonexsiting coin.
flip = lambda coin: {'H':'T', 'T':'H', 'N':'N'}[coin]

def rmFlip(coin,row):
    ''' The remove and flip operation.'''
    coins = row.copy()
    # remove the coin
    if coins[coin] == 'H':
        coins[coin] = 'N'
        # flip the left/right coin if present
        if coin != 0:
            coins[coin-1] = flip(coins[coin-1])
        if coin != len(coins) - 1:
            coins[coin+1] = flip(coins[coin+1])
    return coins

# Check that if we can continue the operation or not.
checkFin = lambda row: (
# can continue 
    2 if 'H' in row.values()  
# No 'H' remaining, but at least one 'T' is left.  A bad condition.
    else ( 
        0 if 'T' in row.values()   
    # All the coins have been removed.  Congratulations.
        else 1))

def operateCoins(row):
    ''' Operate on rows of coins and report if it's good or bad.  '''

    coins = row.copy()
    while checkFin(coins) == 2:  # can continue

# Note the usage of sorted.  We use the sorted function to make sure
# that we first remove the left-most H-coin, since removing H-coin
# between other H-coins may cause false bad permutations. For example,
# as mentioned in the header, THHHT succeeds.  But if we remove the
# central coin first, that is, TT.TT, it fails.
#
# But if we first remove the left-most H-coin, we can side-step
# these pitfalls.  (This can be proved by induction.)
#
# I guess even if we don't use the sorted function, it will work out.
# This is because Python sort keys internally when storing dictionaries.
# And I guess the internal sorting (i.e. hash ordering) has the same
# effect in this case.  But wrapping it inside a sorted function makes
# me feel safe.

        for coin in sorted(coins):
            coins = rmFlip(coin,coins)
    # return the original row as a string (for eye-candy in output) and
    # whether it's good(1) or bad(0).
    return checkFin(coins), dict2str(row)


# Sort permutations of a given number according to whether it's good or bad. 
collect = lambda n: sorted(map(operateCoins, genRows(n)))

# List all permutations of all numbers.
listCoins = lambda n: [ collect(n) for n in range(1,n+1) ]

twoDice.py

#!/usr/bin/env python2.5
# by Jakukyo Friel <weakish@gmail.com> under GPL v2

# Many games involve rolling two dice, each having six sides numbered 1
# through 6.  Explain why x and 14-x are equally likely to be the sum
# of the numbers facing up on the two side.

sums = [i + j for i in range(1, 7) for j in range(1, 7)]

for x in set(sums):
    result = 0
    if sums.count(x) == sums.count(14 - x):
        result +=0
    else:
        result +=1

print result


# The following problem appeared on a statewide exam for grade 10 in
# California.  "A game involves two cubes with sides numbered 1 through
# 6.  After throwing the two cubes, the smaller number is subtracted from
# the larger number to find the difference.  If a player throws the cubes
# many times, what difference will probably occur most often?  Provide
# a diagram and written explanation that you could use to explain to a
# friend."

difference = [abs(i - j) for i in range(1, 7) for j in range(1, 7)]

print max(difference.count(x) for x in set(difference))

weakish_fn.py

#!/usr/bin/env python2.5
# by Jakukyo Friel <weakish@gmail.com> under GPL v2

'''Some functions written by weakish for fun.'''

import operator

# Sequences and dictionaries conversion
# -----------------------------------------

# Convert sequences(list/tuple/string) to dictionaries, using index as key.
seq2dict = lambda seq: dict(enumerate(seq)) 

# convert back
dict2list = lambda dict: [dict[key] for key in sorted(dict)]
dict2str = lambda dict: ''.join(dict2list(dict))
dict2tuple = lambda dict: tuple(dict2list(dict))

# Thus we have:
#
# list == dict2list(seq2dict(list))
# str == dict2str(seq2dict(str))
# tuple == dict2tuple(seq2dict(tuple))

# Dictionaries addition
#
# Add two dictionaries.  If values conflict, first dictionary wins.

dictAddition = lambda dictX, dictY: dict((key, dictX[key] if key in dictX else dictY[key]) for key in set(dictX)|set(dictY))

class myDict(dict):
    __add__ = lambda self, other: dictAddition(self, other)

# Permutations generation
# --------------------------
#
# Generates permutations of elements in a given set.
genP = lambda n, iter: eval(_genListStr(n,set(iter))) 


_genListStr = lambda m, set: (

# Note that we use m instead of n as the parameter.  This is because in
# Python 2.X, list comprehension is implemented like a simple for loop.  
# Thus if we use n, we need to use range(n+1) in the second list
# comprehension, since the value of the n has been changed to n-1 by
# runing the first list comprehension (remains the last state in it).
# In Python 3.x, we can use n as the parameter, though, because in 3.x,
# list comprehension has its own function space "under the hood".
# Another solution is use list(generator expression).

    '[ [' + ''.join(['a' + str(n) + ', ' for n in range(m)]) + '] ' +    
    ''.join(['for a' + str(n) + ' in ' + `set` + ' ' for n in range(m)]) + ']')


# Find occurrences of list items
# In fact, I reinvented list.count(item) poorly.  I really should go fuck
# myself.

def occurr(item, list):
    if item in list: 
        sortedList = sorted(list)
        occurrences = 0
        index = sortedList.index(item)
        while sortedList[index]== item:
            occurrences += 1
            index += 1
        return occurrences
    else:
        return 0

# a less stupid version:

occurr = lambda item, list:
  len([a for a in list if a == item])

# Weakish unit test
# ---------------------
#
# A weakish unit test implement.

_test = lambda caller, output: 1 if eval(caller) == output else 0


def Ts(listOfTuple):
    '''weakish unit test

    Simple unit test function.  Only tests functions' output (return value)
    and does nothing with side-effects.  Thus it'd better used for
    functional programing style

    Examples usage: (Note that you need to enclose callers in string.)
        import weakish_fn
        tests = [
            ('f(0)', 0,),
            ('f(1)', 2,),
            ('g(1,2,3)', (3,2,1)),
            ]
        weakish_fn.Ts(test)
    
    Example output:
        Testing f(0) ... O.K.
        TEST OF f(1) FAILED!
        Result:
        1
        Expect:
        2
        Testing g(1,2,3) ... O.K.
        1 out of 3 test(s) failed!
    '''
    totalNum = str(len(listOfTuple))
    failedNum = 0
    def T(caller, output, failedNum):
        if _test(caller, output):
            print 'Testing ' + caller + ' ... O.K.'
            return failedNum
        else:
            print 'TEST OF ' + caller + ' FAILED!'
            print 'Result:\n'
            print eval('caller')
            print 'Expect:\n'
            print output
            return failedNum + 1
    for tuple in listOfTuple:
        failedNum = T(tuple[0], tuple[1], failedNum)
    if failedNum == 0:
        print 'Congratulations!  All ' +  totalNum + ' test(s) passed.'
    else:
        print str(failedNum) + ' out of ' + totalNum + ' test(s) failed!'



# Unit test

if __name__ == '__main__':
    list = ['spam', 'foo', 'bar']
    string = 'spam'
    pair = (2008, 2009)
    
    permutation = [
[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 0], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 0], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 0], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 0], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 0], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]]

    dictA = {'a':1, 'b':2}
    dictB = {'a':0, 'c':'bar'}
    dictAplusB = {'a': 1, 'c': 'bar', 'b': 2}

    tests = [
        ('dict2list(seq2dict(list))', list),
        ('dict2str(seq2dict(string))', string),
        ('dict2tuple(seq2dict(pair))', pair),
        ('genP(2, range(9))', permutation),
        ('dictAddition(dictA, dictB)', dictAplusB), 
        ]

    Ts(tests)