Bottom Page

• 3 Vote(s) - 2.67 Average
• 1
• 2
• 3
• 4
• 5
 Triangle: max path sum Mateoo Unladen Swallow Posts: 2 Threads: 2 Joined: Jan 2019 Reputation: 0 Likes received: 0 #1 Jan-10-2019, 07:39 PM In my task I have to find the maximum path sum in a triangle of numbers - .txt file (maximum total from top to bottom). For example in a triangle: 4 34 126 maxpathsum is 10 This is my program: ```def maxSum(triangle, l, n): for i in range(l-1, -1, -1): for j in range(i+1): if (triangle[i+1][j] > triangle[i+1][j+1]): triangle[i][j] += triangle[i+1][j] else: triangle[i][j] += triangle[i+1][j+1] return triangle[0][0] with open("triangle.txt") as fp: total = 0 for count, line in enumerate(fp): triangle = [int(num) for num in line.split()] tri1 = open('triangle.txt', 'r') tri2 = tri1.read() x= len(tri2.splitlines()) y=x-1 #print(triangle) print(maxSum(triangle, y, y)) ```I don't know how to fix this error: ``````Error:Traceback (most recent call last): File "C:\Users\Mateo\Desktop\course-0\Task1.py", line 27, in print(maxSum(triangle, y, y)) File "C:\Users\Mateo\Desktop\course-0\Task1.py", line 6, in maxSum if (triangle[i+1][j] > triangle[i+1][j+1]): IndexError: list index out of range`````` stullis Spam, spam, eggs, and spam Posts: 221 Threads: 0 Joined: Sep 2018 Reputation: 22 Likes received: 40 #2 Jan-10-2019, 09:16 PM The inherent issue is with maxSum(). To fix it, I recommend structuring the variable triangle differently. Right now, the code is opening the file twice to get different metadata about the data. It looks like triangle would be a list of individual numbers as it currently is. As I understand the max sum problem, you need to find the greatest value on each line of the triangle and sum those values. Now, Python has a built-in function called max() that can help so you don't have to do the indexing. To make that happen, pass in a list of lists that represents the triangle: Quote:5 2 3 1 2 1 becomes triangle = [[5], [2,3], [1,2,1]] The code is fairly close to what is needed to make that possible. It only requires a little refactoring and a more complex list comprehension: ```triangle = [ [ int(num) for num in line.split() ] for line in fp.read().splitlines() ] ```Then, in maxSum() you can iterate over triangle list to get the max values of each one. Then, add them all together and you're done. If you are required to do the indexing or are not permitted to use max(), the indexing should be done differently. With the list structure above, you can simply iterate over each item. To ensure that the indices don't exceed the length of the lists, you will have to check the index of the current item against the length: ```for each in tri: if len(each) == 1: break for num in each: if each.index(name) + 1 < len(each): # compare current index value to next index value ``` « Next Oldest | Next Newest »

Top Page

 Possibly Related Threads... Thread Author Replies Views Last Post Printing out a triangle using nested for loops MrGoat 12 241 Jan-16-2019, 07:21 PM Last Post: ichabod801 Problem with reading a path gkiller007 30 490 Jan-05-2019, 10:09 PM Last Post: snippsat Beautiful soup won't find value even with CSS path copied. AdequatelyChilled 4 128 Jan-01-2019, 12:12 PM Last Post: snippsat os.path.isdir() returns always True Fabrizio 3 150 Dec-04-2018, 04:28 PM Last Post: nilamo Directory path EOF Graham 8 224 Nov-28-2018, 10:13 PM Last Post: Graham Anaconda problem about path Leloup 1 211 Nov-23-2018, 05:14 PM Last Post: Larz60+ How to print a File Path ? Astrikor 3 322 Sep-24-2018, 10:18 AM Last Post: Astrikor rtlsdr depenancy path on windows 10 kiyoshi7 2 366 Sep-12-2018, 07:26 PM Last Post: kiyoshi7 pathlib: resolving a path that does not exist Skaperen 6 344 Sep-08-2018, 12:25 AM Last Post: Skaperen makin hardlinks with pathlib.Path Skaperen 2 322 Sep-06-2018, 07:53 AM Last Post: scidam

Forum Jump:

Users browsing this thread: 1 Guest(s)