![]() |
Help on adding two lists recursively - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: General Coding Help (https://python-forum.io/forum-8.html) +--- Thread: Help on adding two lists recursively (/thread-12860.html) |
Help on adding two lists recursively - Metalman488 - Sep-16-2018 So I have two lists that are each a large integer that has been split up into nodes. (Example: 123456 => [123,456]) and I need to add two lists like that, so something like [123,456]+[789,654] This is the code I have so far: def recursive_sum(l1, l2, idx = 0): if idx < min(len(l1), len(l2)): return [int(l1[idx]) + int(l2[idx])] + recursive_sum(l1, l2, idx + 1) else: return []The int() is because the elements are strings from when I was splitting the numbers into nodes. This sort of works, but it doesn't handle carryout and it doesn't work correctly if the lists are of different length. It turns ['001', '234', '567'], '+', ['007', '894', '561'] into [8,1128,1128], the answer is 9128128 so it works but it's not doing 8+1 <= 1 <= 128+1 <= 1 <= 128. I'm not exactly sure how to get it to do carryout. RE: Help on adding two lists recursively - gontajones - Sep-16-2018 def recursive_sum(l1, l2, idx=0, carryout=0): if idx < min(len(l1), len(l2)): l1 = l1[::-1] l2 = l2[::-1] n = int(l1[idx]) + int(l2[idx]) + carryout carryout = 0 if n > 999: carryout = int(n/1000) n -= 1000*carryout return recursive_sum(l1, l2, idx + 1, carryout) + [n] else: return [carryout] if carryout else [] l1 = ['001', '234', '567'] l2 = ['007', '894', '561'] # l2 = ['999', '166', '568'] print(recursive_sum(l1, l2)) RE: Help on adding two lists recursively - Metalman488 - Sep-16-2018 (Sep-16-2018, 04:36 PM)gontajones Wrote:def recursive_sum(l1, l2, idx=0, carryout=0): if idx < min(len(l1), len(l2)): l1 = l1[::-1] l2 = l2[::-1] n = int(l1[idx]) + int(l2[idx]) + carryout carryout = 0 if n > 999: carryout = int(n/1000) n -= 1000*carryout return recursive_sum(l1, l2, idx + 1, carryout) + [n] else: return [carryout] if carryout else [] l1 = ['001', '234', '567'] l2 = ['007', '894', '561'] # l2 = ['999', '166', '568'] print(recursive_sum(l1, l2)) That is a lot simpler than what I just came up with, Thank you. The only thing is that I forgot to mention that the number of digits per node can be any positive number (1,2,3,...) so I need to modify it to deal with that. The way I did this involved a few different functions, but here's my carryout function that deals with different node sizes: def carryout(myList, ND, pos, Res = []): strly = str(myList[pos]) if(pos < 0): return [] else: if(len(strly) > ND): myList[pos-1] = myList[pos-1] + int(strly[0]) strly = strly[1:] myList[pos] = int(strly) carryout(myList, ND, pos-1) return myListit takes in the result from my sum function ([8,1128,1128]) and then finds the carryout based on the ND which is the number of digits per node. This is my modified sum function: def Brecursive_sum(l1, l2, idx, ND, carryout = 0): if idx >= 0: print(int(l1[idx]) + int(l2[idx])) n = int(l1[idx]) + int(l2[idx]) + carryout nStr = str(n) if(len(nStr) > ND): carryout = int(nStr[0]) n = int(nStr[1:]) return Brecursive_sum(l1, l2, idx - 1, ND, carryout) + [n] else: return []It seems to work. It also gave me the correct result. I only tested it with my example numbers from above and with ND = 3 though. I'm thinking I don't have to worry about the carryout being more then one digit long since 999+999 = 1998 With that portion solved, now I need to figure out how to do it if the two lists are of different lengths. (l1 = [123, 456, 789] and l2 = [987, 654, 321, 123]) I did this in my overly complicated way by running the two lists through this code before doing the add function: def eqSize(sList, mx): if (len(sList) < mx): sList.insert(0, "0") eqSize(sList, mx) return sList if(len(list1) > len(list2)): list2 = eqSize(list2, len(list1)) elif(len(list1) < len(list2)): list1 = eqSize(list1, len(list2))It works for my earlier solution, so I don't see why it wouldn't work for my newly modified solution. RE: Help on adding two lists recursively - Metalman488 - Sep-16-2018 so I applied my eqSize function and the result I get from adding these two lists: list1 = ["123", "001", "234", "567"] list2 = ["007", "894", "561"] is ['124', '009', '129', '128'] which is almost correct except the first element should be 123 not 124, and I have no clue why it's doing that. My best guess is that there is something wrong with my carryout. All I had to do is add an else statement to the if statement that dealt with carryout in the add function: if(len(nStr) > ND): carryout = int(nStr[0]) n = int(nStr[1:]) else: carryout=0Sorry for all the mini reiplies. I guess I should try to figure it out more before I post. |