Python Forum
Help on adding two lists recursively
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Help on adding two lists recursively
#1
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.
Reply
#2
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))
Reply
#3
(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 myList
it 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.
Reply
#4
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=0
Sorry for all the mini reiplies. I guess I should try to figure it out more before I post.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  How to return the next page from json recursively? sandson 0 1,104 Apr-01-2022, 11:01 PM
Last Post: sandson
  Help Needed | Read Outlook email Recursively & download attachment Vinci141 1 4,018 Jan-07-2022, 07:38 PM
Last Post: cubangt
Star Recursively convert nested dicts to dict subclass Alfalfa 1 2,840 Jan-22-2021, 05:43 AM
Last Post: buran
  Split dict of lists into smaller dicts of lists. pcs3rd 3 2,312 Sep-19-2020, 09:12 AM
Last Post: ibreeden
  Python script that recursively zips folders WITHOUT nesting the folder inside the zip umkc1 1 2,742 Feb-11-2020, 09:12 PM
Last Post: michael1789
  How to get full path of specified hidden files matching pattern recursively SriRajesh 4 3,842 Jan-18-2020, 07:12 PM
Last Post: SriRajesh
  Adding markers to Folium map only adding last element. tantony 0 2,094 Oct-16-2019, 03:28 PM
Last Post: tantony
  Find a given file recursively inside a directory alinaveed786 1 1,917 Jul-01-2019, 01:53 PM
Last Post: ichabod801
  adding lists to lists? ivinjjunior 5 3,014 Apr-15-2019, 07:41 PM
Last Post: ivinjjunior
  sort lists of lists with multiple criteria: similar values need to be treated equal stillsen 2 3,188 Mar-20-2019, 08:01 PM
Last Post: stillsen

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020