solution Algorithm
Algorithm is a step-by-step procedure or a set of well-defined instructions to solve a specific problem or perform a certain task. In the context of computer science and programming, algorithms are essential as they provide a systematic approach to problem-solving and enable computers to process and analyze data, make decisions, and execute tasks efficiently. They are the backbone of software applications and systems, powering various functionalities and enabling automation. Algorithms can be simple, like sorting a list of numbers, or complex, like determining the best route for a self-driving vehicle. They are designed to be efficient, scalable, and adaptable to a wide range of applications and environments.
The effectiveness of an algorithm is often determined by its time and space complexity, which describe the amount of computational resources required to execute the algorithm. Time complexity refers to the number of basic operations or steps needed to complete the algorithm, while space complexity refers to the memory space required to store data during the algorithm's execution. Optimizing an algorithm's performance involves minimizing its time and space complexity, ensuring that it can handle large-scale problems and deliver results in a reasonable amount of time. Algorithm design and analysis play a crucial role in the development of modern computing systems, as they provide the foundation for creating efficient, high-performance software and hardware solutions.
"""
By starting at the top of the triangle below and moving to adjacent numbers on
the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""
import os
def solution():
"""
Finds the maximum total in a triangle as described by the problem statement
above.
>>> solution()
1074
"""
script_dir = os.path.dirname(os.path.realpath(__file__))
triangle = os.path.join(script_dir, "triangle.txt")
with open(triangle, "r") as f:
triangle = f.readlines()
a = [[int(y) for y in x.rstrip("\r\n").split(" ")] for x in triangle]
for i in range(1, len(a)):
for j in range(len(a[i])):
if j != len(a[i - 1]):
number1 = a[i - 1][j]
else:
number1 = 0
if j > 0:
number2 = a[i - 1][j - 1]
else:
number2 = 0
a[i][j] += max(number1, number2)
return max(a[-1])
if __name__ == "__main__":
print(solution())
