#3 Maximum parimeter triangle:

date posted: 2020-05-05

TMI of the day

1. I've been trying to solve recursion problems however had no idea how to approach it... backing down one step to solve easier problems and hope I can solve them later on.

Solutions

#1 Try

This problem is solved using greedy approach which basically means at each step you find most optimal solution and in the end that will be global optimal solution. But we know that obtaining global optimal solution is not always true.

So this is my approach:

• sort list of sticks in ascending order.
• start from first three sticks, goto next three, and so on... Check if they are valid triangles, if yes insert into triangles list.
• If there is no valid triangle, return [-1]
• If we only have one valid triangle, return that one triangles[0]
• If we have more than one valid triange since we had them sorted in ascending order, last triangle would be valid and have greatest perimeter

def check_valid_tri(triangle):
    """if sum of two sides > another side then it is valid triangle"""
    a = triangle[0]
    b = triangle[1]
    c = triangle[2]
    
    if (a + b > c) & (a + c > b) & (b + c > a):
        return True
    else:
        return False

def maximumPerimeterTriangle(sticks):
    sticks.sort()
    triangles = []
    for i, st in enumerate(sticks):
        triangle = sticks[i:3+i]
        if len(triangle) < 3: 
            continue  
        if check_valid_tri(triangle):
            triangles.append(triangle)
              
    if len(triangles) == 0:
        return [-1]
    
    elif len(triangles) == 1:
        return triangles[0]
    else:
        return triangles[-1]

This problem was pretty easy to solve, I just needed to search for ways to check whether a triangle was valid (I'm a math major).

This works perfectly, going over every three sticks (do not need to try all combinations since it is ordered and if it doens't creates valid triangle at last three it means there won't be any sticks that can be replaced to create valid triangle since a + b < c will become a + b << c)

Every three sticks can be seen as feasible solution, and we update our triangles with more feasible ones finally picking the latest feasible one which would be our most optimal solution. This is very simple greedy approach and I believe my code has done a pretty good job! :)