<file_sep>pitchup
=======

REQUIREMENT:

Write a program to find a pitch based on this clue: 

"Join us at pitch x. x is a number between 1 and 553 such that the sum of x's divisors 
(not including x) is greater than x but no subset of x's divisors add up to exactly x."*


IMPLEMENTATION NOTES:

This project is implemented using Python 2.7

There have been few rafactoring iterations - that gradually improved program's performance, 
ultimately leading to the given, quite well performing implementation.

If interested in details (to see how each refactoring iteration led to performance improvements) -
contact developer at <EMAIL>. Notes below correspond to the latest (most current)
implementation:

1. Number class (number.py) is used as helper. It implements methods that load number's divisors
	set (__loadDivisors()) and a generator method powerset() that returns POWERSET of number's 
	divisors. 

2. Main program (pitchup.py) uses "threading" to evaluate all individual numbers (in the range
	1 .. 553) in parallel. This is very primitive use of threading - as this program does not
	involve resource sharing that would require use of locking (Lock or RLock), notifications, etc.

3. All "heavy lifting" is done within number._powerset() procedure - which implements GENERATOR
	design pattern. Instead of loading entire POWERSET (a set of all subsets) of number's divisors
	into memory (which proved to be highly resource-bound and time consuming process), this procedure
	allows getting POWERSET items iteratively, one at a time. This results in really *huge* 
	performance improvements - due to the fact that instead of generating entire POWERSET (as I had 
	in previous iterations) and evaluating individual subsets after that, we now evaluate each 
	individual subset as it gets fetched by generator, and stop processing as soon as we find one 
	subset that does not pass validation. This saves time, memory, and avoids generating 
	(potentially large number of) subsets that are not needed for our evaluation   

	
RESULT:

Program (pitchup.py) finds (quite quickly) following solution to the given problem: 70
<file_sep>'''
Created on May 3, 2012

@author: valeriy
'''

import time
import threading
from number import Number

pitches = []

def checkNum( num ):
    """Check if given <num.value> satisfies following requirements:
        1. sum(num.divisors) > num.value
        2. No subset from powerset of <num.divisors> adds up to exactly <num.value>
    """
    global pitches

    num = Number( num )

    isOfInterest = True

    if sum( num.divisors ) > num.value:
        subsets = num.powerset()
        for subset in subsets:
            if sum( subset ) == num.value:
                isOfInterest = False
                break
    else:
        isOfInterest = False

    if isOfInterest:
        pitches.append( num.value )

def pitchup():
    "Find all numbers in the range 1 .. 553 that pass requirements"

    # Start all the threads - one for each number in range 1 ... 553
    for num in range( 1, 553 ):
        thread = threading.Thread( target = checkNum, name = "checkNum_%i" % num, args = ( num, ) )
        thread.start()

    # Wait for all threads to terminate
    while threading.activeCount() > 1:
        time.sleep( 1 )

    return

if __name__ == '__main__':
    pitchup()
    if pitches != []:
        for pitch in pitches:
            print "Selected pitch: %i" % pitch
    else:
        print "No pitch selected"
<file_sep>'''
Created on May 3, 2012

@author: valeriy
'''

def _powerset( seq ):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len( seq ) <= 1:
        yield seq
        yield []
    else:
        for item in _powerset( seq[1:] ):
            yield [seq[0]] + item
            yield item

class Number:
    def __init__( self, value ):
        self.value = value
        self.divisors = None
        self.__loadDivisors()

    def __loadDivisors( self ):
        "Get a list of all divisors of <self.value> - excluding <self.value> itself"
        self.divisors = [1]
        for num in range( 2, ( self.value / 2 + 1 ) ):
            if ( self.value % num ) == 0:
                if num in self.divisors:
                    break
                i = self.value / num
                if i == num:
                    self.divisors.append( num )
                else:
                    self.divisors.extend( [num, self.value / num] )

    def powerset( self ):
        """
        Returns all the subsets of this set. This is a generator.
        """
        return _powerset( self.divisors )
