Logic Problem -> Programming

Discussion in 'OT Technology' started by 5Gen_Prelude, Sep 21, 2006.

  1. 5Gen_Prelude

    5Gen_Prelude There might not be an "I" in the word "Team", but

    Joined:
    Mar 14, 2000
    Messages:
    14,519
    Likes Received:
    1
    Location:
    Vancouver, BC, CANADA
    So here's the deal. We have a series of numbers on one side and we need to match them with a series of numbers on the other side. It isn't a straight match though - a combination of 1 or more numbers on the right side add up the the number on the left side. I need a systematic way of identifying which numbers on the right add up to the numbers on the left. For example:

    Code:
    75 1
       23
       25
       10
       17
       30
       90
       15
       8
    
    I can visually see that 25, 10, 17, 15, 8 add up to 75 but I want the computer to figure it out. The only way I can think of doing it is calculating each possible combination:

    1
    1 + 23
    1 + 25
    1 + 10
    1 + 17
    1 + 30
    1 + 90
    1 + 15
    1 + 8
    1 + 23 + 25
    1 + 23 + 10
    1 + 23 + 17
    ...

    And then comparing the totals to the left side (75). After it's all said and done, I should end up with no sequences that match, or 1 or more that match. But I'm still trying to figure out the code to systematically calculate every single column.

    Any ideas?
     
  2. Nocera

    Nocera ...

    Joined:
    Aug 9, 2000
    Messages:
    1,307
    Likes Received:
    0
    Location:
    Long Island, NY
    I would first put the list in descending order and then do some recursive calls to a search function that will avoid numbers that obviously wouldn't work (in your case, numbers like 90 that are > the target sum).

    The following code returns [25, 23, 17, 10].

    Code:
    def search_for_sum(target_sum, current_sum, number_list, current_list):
    	count = 0
    	for num in number_list:
    		count += 1
    		if (num + current_sum == target_sum):
    			current_list.append(num)
    			return current_list
    		elif (num + current_sum < target_sum):
    			current_list.append(num)
    			result = search_for_sum(target_sum, num + current_sum, number_list[count:], current_list)
    			if len(result) > 0:
    				return result
    			else:
    				current_list.pop()
    	return []
    
    if __name__ == '__main__':
    	## sort the list in descending order
    	numbers = [90, 30, 25, 23, 17, 15, 10, 8, 1]
    
    	target_sum = 75
    
    	sum_components = search_for_sum(target_sum, 0, numbers, [])
    
    	print sum_components
    
     
  3. Nocera

    Nocera ...

    Joined:
    Aug 9, 2000
    Messages:
    1,307
    Likes Received:
    0
    Location:
    Long Island, NY
    Given 5Gen_Prelude's reputation, I'm pretty sure he's beyond "homework."
     
  4. 5Gen_Prelude

    5Gen_Prelude There might not be an "I" in the word "Team", but

    Joined:
    Mar 14, 2000
    Messages:
    14,519
    Likes Received:
    1
    Location:
    Vancouver, BC, CANADA
    Lol - the fact that I didn't state which language I needed it in would kind of tip you off that it isn't homework related. It is work related though.

    I had thought of using recursion but I've never been able to wrap my head around the programming and even worse the debugging of a recursive function. I'm going to have to look at this a bit more but thx a bunch for putting me in the right direction.
     
  5. 5Gen_Prelude

    5Gen_Prelude There might not be an "I" in the word "Team", but

    Joined:
    Mar 14, 2000
    Messages:
    14,519
    Likes Received:
    1
    Location:
    Vancouver, BC, CANADA
    I could throw :May2006: up as well but you know - just search my name if you really want to know how long I've been around.
     

Share This Page