Minimum Score Triangulation of Polygon

Leetcode Solution: Understand Minimum Score Triangulation of Polygon With Brute Force and Optimal Solution

01 November 2020

This article presents the solution to the problem 1039. Minimum Score Triangulation of Polygon- Leetcode. I’ll break the solution in three connected parts:

Brute force solution - presents the brute force solution
Addition of memoization and caching to make the program faster and then
Implementing the dynamic programming top down approach to solve it efficiently

		
				
Given N, consider a convex N-sided polygon with vertices labelled A[0], A[i], ..., A[N-1]
in clockwise order.
                                                           
Suppose you triangulate the polygon into N-2 triangles.  For each triangle, the value of 
that triangle is the product of the labels of the vertices, and the total score of the 
triangulation is the sum of these values over all N-2 triangles in the triangulation.

Return the smallest possible total score that you can achieve with some triangulation of 
the polygon.

    Example 1:
    
    Input: [1,2,3]
    Output: 6
    Explanation: The polygon is already triangulated, and the score of the only triangle is 6.
    
    Example 2:
    
    Input: [3,7,4,5]
    Output: 144
    Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.  
                 The minimum score is 144.
    
    Example 3:
    
    Input: [1,3,1,4,1,5]
    Output: 13
    Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

Note:

    3 <= A.length <= 50
    1 <= A[i] <= 100

Let’s use this input array as our base example:

input := []int{
    1, 2, 3, 4, 5, 6
}

The length of the input array is 6 and that makes it a Hexagon, and it can be broken down into 4(6 - 2) triangles. If we remove one of those points by creating a triangle using its neighbours, we’ll get a Pentagon and a triangle and similarly we’ll get a quadrilateral and one more triangle if we remove one point from the Pentagon. This image shows the divisions by reduction of polygons point wise.

This way four triangles can be created. To find the triangles having the minimum product we’ll have to select one point at a time and reduce the polygon. So, in the brute force approach, we’ll reduce the polygon in this way:

In this image, you can see that removal of a point creates a new Pentagon and this leads to the creation of 6 pentagons. The pentagons can then be reduced to quadrilaterals like this:

So, here’s the brute force approach that I’ve come up with:

Pick a point at index i
Increment the sum by adding the product of i - 1, i, i + 1 because these three indexes will make the triangle now.
If there are only three elements in the array return the sum
If there are more than 3 elements then remove the element i from the array and go to step 1
Decrement the sum added in step two and increment i

There is recursion in step 4, and the elements of the array will change based on the point we pick. As the removal of the elements from array will require N operations, I’ve created a circular doubly linked list. I can remove or add the element into circular doubly linked list whenever needed.

Here’s the Brute force program for this problem:

type Node struct {
	Val    int
	Index  int
	Length int
	Next   *Node
	Prev   *Node
}

var minSum int

func minScoreTriangulation(A []int) int {
	start := &Node{
		Val:   A[0],
		Index: 0,
	}
	temp := start
	for i := 1; i < len(A); i++ {
		temp.Next = &Node{
			Val:   A[i],
			Prev:  temp,
			Index: i,
		}
		temp = temp.Next
	}
	temp.Next = start
	start.Prev = temp
	minSum = math.MaxInt32
	minScoreTriangulationBruteForce(start, 0, len(A))
	return minSum
}

func minScoreTriangulationBruteForce(start *Node, sum, length int) {
	if length == 3 {
		sum += start.Val * start.Next.Val * start.Next.Next.Val
		if minSum > sum {
			minSum = sum
		}
		return
	}
	temp := start
	for temp != nil {
		remove := temp
		sum += remove.Val * remove.Next.Val * remove.Prev.Val
		remove.Prev.Next = remove.Next
		remove.Next.Prev = remove.Prev
		minScoreTriangulationBruteForce(remove.Next, sum, length-1)
		remove.Prev.Next = remove
		remove.Next.Prev = remove
		sum -= remove.Val * remove.Next.Val * remove.Prev.Val
		if temp.Next == start {
			break
		}
		temp = temp.Next
	}
	return
}

The struct Node represents an element from the linked list. The function minScoreTriangulation creates the linked list from the array and passes it to the minScoreTriangulationBruteForce function along with the length of the list. minScoreTriangulationBruteForce function then loops over each one of the element, removes them and recursively calls itself. Once the recursion is complete, it adds the element back at the same location moves to the next element.

This brute force solution has a time complexity of O(n^{n - 3}) and that is pretty terrible.

As we are converting the polygons with n points to a new polygon with n - 1 points. There will be a number of scenarios in which polygons will be repeated. For example, if the pentagon is 1 → 2 → 3 → 4 → 5 then it’ll be reduced to quadrilaterals 1 → 2 → 3 → 4 and 2 → 3 → 4 → 5. Both these quadrilaterals have triangle 2 → 3 → 4 common which means we can cache the result of previous calculations to use them later.

To create the cache I’ll first create a hash from the elements by setting the bits in an unsigned int64 variable. Here’s the code for creating the hash:

func createHash(start *Node) uint64 {
	var hash uint64
	temp := start
	for temp != nil {
		hash |= 1 << temp.Index
		if temp.Next == start {
			break
		}
		temp = temp.Next
	}
	return hash
}

The variable hash has the bit set at only those indexes for which there’s an element at the same index in the array. If the elements are removed then the hash is also updated by this function:

func updateHash(currentHash uint64, indexToBeRemoved int) uint64 {
	return currentHash ^ (1 << indexToBeRemoved)
}

The index, at which the element removed, is unset from the hash.

Here’s the updated program:

var cache map[uint64]int
var minSum int

func minScoreTriangulation(A []int) int {
	start := &Node{
		Val:   A[0],
		Index: 0,
	}
	temp := start
	for i := 1; i < len(A); i++ {
		temp.Next = &Node{
			Val:   A[i],
			Prev:  temp,
			Index: i,
		}
		temp = temp.Next
	}
	temp.Next = start
	start.Prev = temp
	minSum = math.MaxInt32
	cache = make(map[uint64]int)
	hash := createHash(start)
	minScoreTriangulationLLC(start, 0, len(A), hash)
	return minSum
}

func minScoreTriangulationLLC(start *Node, sum, length int, hash uint64) int {
	if cacheSum, ok := cache[hash]; ok {
		sum += cacheSum
		if minSum > sum {
			minSum = sum
		}
		return sum
	}
	if length == 3 {
		sum += start.Val * start.Next.Val * start.Next.Next.Val
		if minSum > sum {
			minSum = sum
		}
		return sum
	}
	currentSum := math.MaxInt32
	temp := start
	for temp != nil {
		remove := temp
		sum += remove.Val * remove.Next.Val * remove.Prev.Val
		remove.Prev.Next = remove.Next
		remove.Next.Prev = remove.Prev
		newHash := updateHash(hash, remove.Index)
		tempSum := minScoreTriangulationLLC(remove.Next, sum, length-1, newHash)
		if tempSum-sum+(remove.Val*remove.Next.Val*remove.Prev.Val) < currentSum {
			currentSum = tempSum - sum + (remove.Val * remove.Next.Val * remove.Prev.Val)
		}
		remove.Prev.Next = remove
		remove.Next.Prev = remove
		sum -= remove.Val * remove.Next.Val * remove.Prev.Val
		if temp.Next == start {
			break
		}
		temp = temp.Next
	}
	cache[hash] = currentSum
	return currentSum + sum
}

This program contains the code for hashing and caching along with the previous brute force program. The cache will contain the sum for all the different polygons that will be created.

Here we’ve reduced the time complexity to O(2ⁿ) but still it can be further improved. One problem that you’ll find here is high cache cardinality. Since we’re removing one point at a time, there can be multiple combinations that are possible. For example, between 2 and 5, there can be 2,3,5 or 2,3,4,5 or 2,4,5. So, to cache the result, we had to create the hash of the entire elements that were part of the polygon. Let’s quickly move on to a better solution that will be very similar to this solution only, but we’ll break the problem into 2 sub problems instead of 1 that we’ve doing earlier. This will help in efficient caching.

In this image you can see that I’ve started from the first and the last element, 1 and 6, and then I’m creating a triangle using the points between 1 and 6. Then each triangle creation job is creating two polygons on the either sides of the triangle. These two new polygons will become the new subproblems that we’ll solve recursively. Here’s the program for that:

var cache [][]int

func minScoreTriangulation(A []int) int {
	cache = make([][]int, len(A))
	for i := range cache {
		cache[i] = make([]int, len(A))
	}
	minScoreTriangulationR(A, 0, len(A)-1)
	return cache[0][len(A)-1]
}

func minScoreTriangulationR(A []int, start, end int) int {
	if math.Abs(float64(start-end)) == 1 {
		return 0
	}
	if cache[start][end] > 0 {
		return cache[start][end]
	}
	sum := math.MaxInt32
	for i := start + 1; i < end; i++ {
		tempSum := minScoreTriangulationR(A, start, i) + 
                   minScoreTriangulationR(A, i, end) + 
                   (A[start] * A[end] * A[i])
		if tempSum < sum {
			sum = tempSum
		}
	}
	cache[start][end] = sum
	return sum
}

This program looks simplest of all the three programs we’ve seen today. Here, I’ve made triangles for all the elements between start and end and then calculated the sum. The minimum sum is stored in the 2D cache array. The 2D cache array helps in limiting the number of recursion. Since we’re using the start and the end indexes for the cache, it becomes easy to look up into it unlike the previous solution.

Here’s the GitHub link for all the programs:

Loading Comments... Disqus Loader

Minimum Score Triangulation of Polygon

Leetcode Solution: Understand Minimum Score Triangulation of Polygon With Brute Force and Optimal Solution

Related Pages: