Hello Folks!

Happy New Year! I know I'm late at this point but hey, it's better late than never!

As the year had begun, I got busy with work and I barely found any time to post anything new but that doesn't mean I didn't do anything new.

At the end of December, I decided to get back on solving algorithmic and programming puzzles again (The last time I did was back on 2016) and for starters, I decided to solve Project Euler problems by adding a new programming language to my tech arsenal, Python.

Why solve it using Python?

Previously, I'd solved around 57 problems using C++ and it got paused for a while after I got into internships and work life. But now that I have found the time for it, I thought that this would be the perfect opportunity for me to learn Python. It has a really good community, good documentation and the code looks so clean, simple and readable without those curly brackets!

What is Project Euler?

It's a website that hosts a series of challenging algorithmic and mathematical programming puzzles in which you will have to produce solutions that'd clock in under a minute with decent computer specifications.

By solving these puzzles, you will be experiencing an inductive chain learning i.e. when you solve one problem, you'll be exposed to a completely new concept that allows you to delve into unfamiliar areas of mathematics and programming.

As I'm writing this article, I'm taking it slow and I have solved around 21 problems in 3 weekends. I will be posting a walkthrough for each problem but for now, I will talk about one of my favorite problems: Maximum Path Sum.

Maximum Path Sum

Problem definition of Problem 18:

By starting at the top of the Binary Tree 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. Now, find the maximum total from top to bottom of the Binary Tree 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

Since there are fifteen rows, you can solve this puzzle using Brute Force by trying every route possible but if you're going to use that same technique for Problem 67 that has a Binary Tree containing one hundred rows, it will not be efficient. So this problem forces you to avoid brute force and instead wants you to come up with a clever solution!

Solution

As I had mentioned above, a brute force technique is going to be very inefficient, instead I did a bottom-up approach:

Implementation of the method(s):

# Sum of numbers
def sumOfNumbers(n):
    return (n*(n+1))/2

# Return the maximum path sum in a Binary Tree
# Bottom Up Approach
def maxPathSum(list):
    # the last number of the list
    last = len(list)

    # number of rows in the Binary Tree
    nrow = 1

    # count the number of rows in the Binary Tree
    # use the sum of numbers method to count the number of rows
    while sumOfNumbers(nrow) < last:
        # print (sumOfNumbers(nrow))
        nrow += 1

    last -= 1

    for i in range(nrow, 0, -1):
        # print list[last - i]

        # iterate through each number in each row
        for j in range(2, i+1):
            # pick a number from the row above the current row
            # and pick the 2 numbers from the current row
            # Find the max between the two numbers and add it
            list[last - i] = list[last - i] + max(list[last - 1], list[last])

            # shift to the next number in the row above
            last -= 1

        # shift to the next number in the row above
        last -= 1

    # return the max sum
    return list[0]

Final code:

# Project Euler: Problem 18 and 67 - Maximum Path Sum I and II

#!usr/bin/python
import time, math, pe_lib

num_str = ""

# read text file
f = open("triangle2.txt", "r")
for line in f:
    num_str += line
f.close()

# convert the string numbers to integers in the list
list = map(int, num_str.replace('n', ' ').split(' '))

start = time.time()
print pe_lib.maxPathSum(list)
print "Finished: %f seconds" % (time.time() - start)

The maximum path sum for Problem 67 is 7273 and it compiled in 0.003990 seconds.

Note: This solution and the library named pe_lib.py was built using the Python programming language. The source code for this solution can be found on Github.

Stay tuned for more!