Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
Chemistry
Biology and Medical
Earth Sciences
Computer Science
Computing and Technology
DIY Projects
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
Chemistry
Biology and Medical
Earth Sciences
Computer Science
Computing and Technology
DIY Projects
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Other Sciences
Programming and Computer Science
Algorithm Optimization [Python]
Reply to thread
Message
[QUOTE="Jamison Lahman, post: 5780991, member: 599086"] [h2]Homework Statement [/h2] Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum. [code=Python]sum_pairs([11, 3, 7, 5], 10) # ^--^ 3 + 7 = 10 == [3, 7] sum_pairs([4, 3, 2, 3, 4], 6) # ^-----^ 4 + 2 = 6, indices: 0, 2 * # ^-----^ 3 + 3 = 6, indices: 1, 3 # ^-----^ 2 + 4 = 6, indices: 2, 4 # * entire pair is earlier, and therefore is the correct answer == [4, 2] sum_pairs([0, 0, -2, 3], 2) # there are no pairs of values that can be added to produce 2. == None/nil/undefined (Based on the language) sum_pairs([10, 5, 2, 3, 7, 5], 10) # ^-----------^ 5 + 5 = 10, indices: 1, 5 # ^--^ 3 + 7 = 10, indices: 3, 4 * # * entire pair is earlier, and therefore is the correct answer == [3, 7][/code] Negative numbers and duplicate numbers can and will appear. [B]NOTE:[/B] There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn't time out.This is a problem off of codewars.com. I have made two versions that satisfy the eight examples but there is a 12000ms time restraint that I need to overcome. I am not versed in CS so I don't know much about algorithms or how to optimize them. [B] 2. Homework Equations [/B] The examples are: [code=Python]l1= [1, 4, 8, 7, 3, 15] l2= [1, -2, 3, 0, -6, 1] l3= [20, -13, 40] l4= [1, 2, 3, 4, 1, 0] l5= [10, 5, 2, 3, 7, 5] l6= [4, -2, 3, 3, 4] l7= [0, 2, 0] l8= [5, 9, 13, -3] print(sum_pairs(l1, 8) == [1, 7]) #"Basic: %s should return [1, 7] for sum = 8" % l1) print(sum_pairs(l2, -6) == [0, -6]) #"Negatives: %s should return [0, -6] for sum = -6" % l2) print(sum_pairs(l3, -7) == None) #"No Match: %s should return None for sum = -7" % l3) print(sum_pairs(l4, 2) == [1, 1]) #"First Match From Left: %s should return [1, 1] for sum = 2 " % l4) print(sum_pairs(l5, 10) == [3, 7]) #"First Match From Left REDUX!: %s should return [3, 7] for sum = 10 " % l5) print(sum_pairs(l6, 8) == [4, 4]) #"Duplicates: %s should return [4, 4] for sum = 8" % l6) print(sum_pairs(l7, 0) == [0, 0]) #"Zeroes: %s should return [0, 0] for sum = 0" % l7) print(sum_pairs(l8, 10) == [13, -3]) #"Subtraction: %s should return [13, -3] for sum = 10" % l8) [/code] They should all return True [h2]The Attempt at a Solution[/h2] My first attempt is simple and straight forward: [code=Python]def sum_pairs(ints, s): prev_list = [] for num in ints: for test in prev_list: if num+test == s: return ([test, num]) prev_list += [num][/code] My second attempt is the same structure however I store and organize previous test numbers by either positive or negative: [code=Python]def sum_pairs(ints, s): neg_list = [] pos_list = [] for num in ints: if num > s: for neg in neg_list: if neg == s - num: return [neg,num] else: for pos in pos_list: if pos == s - num: return [pos,num] if num < 0: neg_list += [num] else: pos_list += [num][/code] With this new method, I went from 50 total possible returns to 31. I am not sure if this is the right direction to go. It very well may be I'm doing more work by organizing than I am saving. From here, my plan was to make four lists: two negatives with one where abs(number) >= abs(s) and the other abs(number) < abs(s) with a similar pattern for positive numbers. I think it might be helpful to find the sign of 's' at the very beginning but I haven't figured out how to use that to my advantage.. [/QUOTE]
Insert quotes…
Post reply
Forums
Other Sciences
Programming and Computer Science
Algorithm Optimization [Python]
Back
Top