We are stacking blocks to form a pyramid.  Each block has a color which is a one letter string, like `'Z'`.

For every block of color `C` we place not in the bottom row, we are placing it on top of a left block of color `A` and right block of color `B`.  We are allowed to place the block there only if `(A, B, C)` is an allowed triple.

We start with a bottom row of bottom, represented as a single string.  We also start with a list of allowed triples allowed.  Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.


Example 1:

Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.



Example 2:

Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
Output: false
Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.



Note:

bottom will be a string with length in range [2, 8].
allowed will have length in range [0, 200].
Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Graph traversal

Starter code: class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        

Solutions:
class Solution:

	def pourWater(self, heights, V, K):
		for i in range(V):
			if not self.fallLeft(K, heights):
				if not self.fallRight(K, heights):
					heights[K] += 1
		return heights

	def fallLeft(self, K, heights):
		minBlock = K
		for i in range(K - 1, -1, -1):
			if heights[i] < heights[minBlock]:
				minBlock = i
			elif heights[i] > heights[minBlock]:
				break
		if minBlock == K:
			return False
		heights[minBlock] += 1
		return True

	def fallRight(self, K, heights):
		minBlock = K
		for i in range(K + 1, len(heights)):
			if heights[i] < heights[minBlock]:
				minBlock = i
			elif heights[i] > heights[minBlock]:
				break
		if minBlock == K:
			return False
		heights[minBlock] += 1
		return True


class Solution:

	def pourWater(self, heights, total, index):
		if not heights or total <= 0 or index < 0 or (index >= len(heights)):
			return heights
		for _ in range(total):
			left = -1
			for i in range(index - 1, -1, -1):
				if heights[i] > heights[i + 1]:
					break
				if heights[i] < heights[i + 1]:
					left = i
			if left != -1:
				heights[left] += 1
				continue
			right = -1
			for j in range(index + 1, len(heights)):
				if heights[j] > heights[j - 1]:
					break
				if heights[j] < heights[j - 1]:
					right = j
			if right != -1:
				heights[right] += 1
				continue
			heights[index] += 1
		return heights