Problem Description

You need to build a pyramid of blocks where each block has a color represented by a single letter. The pyramid follows these rules:

1. Pyramid Structure: Each row has one less block than the row below it, and each row is centered on top of the previous row.

2. Allowed Patterns: You can only stack blocks according to specific triangular patterns. Each pattern consists of three blocks - two bottom blocks and one top block. These patterns are given as three-letter strings in the allowed list:

   • The first character represents the left bottom block
   • The second character represents the right bottom block
   • The third character represents the top block that can be placed on them
   • For example, "ABC" means you can place block 'C' on top of blocks 'A' (left) and 'B' (right)

3. Starting Point: You begin with a bottom row given as the string bottom, which must be used as the base of your pyramid.

4. Goal: Determine if it's possible to build a complete pyramid all the way to the top (single block) using only the allowed triangular patterns.

Example: If bottom = "AABA" and you have certain allowed patterns, you would need to:

• Build the second row (3 blocks) by applying allowed patterns to each adjacent pair in "AABA"
• Build the third row (2 blocks) from the second row
• Build the top (1 block) from the third row

The function should return true if you can successfully build the entire pyramid following the allowed patterns, or false if it's impossible.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While not explicitly a traditional graph problem, we can model this as a graph where each possible state of a pyramid row is a node, and edges represent valid transitions from one row to the next row based on allowed patterns.

Is it a tree?

• No: The problem is not a tree structure. Multiple different paths (combinations of blocks) can lead to the same result, and we may revisit states.

Is the problem related to directed acyclic graphs?

• No: This isn't a typical DAG problem involving dependencies or ordering.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path. We need to determine if ANY valid path exists to build the complete pyramid.

Does the problem involve connectivity?

• No: We're not checking if components are connected or finding connected components.

Does the problem have small constraints?

• Yes: The pyramid naturally gets smaller as we go up (each row has one less block), and we need to explore different combinations of allowed patterns. The constraint space is manageable for recursive exploration.

Brute force / Backtracking?

• Yes: We need to try different combinations of allowed patterns at each level and backtrack if a path doesn't lead to a valid complete pyramid. This is essentially DFS with backtracking.

Conclusion: The flowchart suggests using DFS/backtracking approach. We recursively try to build each level of the pyramid by exploring all valid combinations of blocks that can be formed using the allowed patterns, and backtrack when we hit a dead end.

Intuition

The key insight is that building a pyramid is a recursive process where each level depends on the level below it. When we look at any row in the pyramid, we need to figure out what the next row above it could be.

Consider how a pyramid is built: for a bottom row like "AABA", we need to process each adjacent pair ("AA", "AB", "BA") and find valid blocks that can go on top of each pair according to our allowed patterns. This creates the next level up.

Here's where it gets interesting - there might be multiple valid blocks for each pair. For instance, if both "AAC" and "AAD" are allowed patterns, then either 'C' or 'D' can go on top of the "AA" pair. This creates a branching decision tree where we need to explore all possible combinations.

The recursive nature becomes clear when we realize that:

1. Once we build a new row, it becomes the "bottom" for building the next row
2. We repeat this process until we reach a single block (the pyramid's peak)
3. If at any point we can't find valid blocks for a pair, we know this path won't work

The challenge is that different combinations at lower levels might lead to success or failure at higher levels. For example, choosing 'C' for the first pair might work perfectly with later choices, while choosing 'D' might lead to a dead end three levels up. This is why we need to try all possibilities - we can't know which choice is correct until we've built the entire pyramid.

Using DFS with memoization is natural here because:

• We might encounter the same intermediate row through different paths (e.g., different choices at the bottom might converge to the same middle row)
• Caching results for each row string prevents redundant computation
• The state space is manageable since each row is smaller than the previous one

The approach essentially asks: "Given this current row, can I build a complete pyramid on top of it?" We answer this by trying all valid ways to build the next row and recursively checking if any of them leads to success.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution implements a DFS with memoization approach using the following key components:

1. Pre-processing the Allowed Patterns

First, we build a dictionary d that maps each pair of blocks to all possible blocks that can be placed on top:

d = defaultdict(list)
for a, b, c in allowed:
    d[a, b].append(c)

For example, if allowed = ["ABC", "ABD"], then d["A", "B"] would contain ['C', 'D'].

2. Recursive DFS Function

The core logic is in the dfs(s) function where s represents the current row:

• Base Case: If the row has only 1 block (len(s) == 1), we've successfully reached the pyramid's peak, so return True.

• Recursive Case: For the current row, we:

  1. Use pairwise(s) to get all adjacent pairs of blocks
  2. For each pair (a, b), look up all valid blocks that can go on top using d[a, b]
  3. If any pair has no valid blocks (not cs), this path is impossible, return False
  4. Collect all possible blocks for each position in the next row

3. Exploring All Combinations

The trickiest part is handling multiple valid choices for each position:

t.append(cs)  # t contains lists of possible blocks for each position
return any(dfs(''.join(nxt)) for nxt in product(*t))

Here, product(*t) generates all possible combinations. For example, if:

• Position 0 can have blocks ['C', 'D']
• Position 1 can have blocks ['E']
• Position 2 can have blocks ['F', 'G']

Then product(*t) generates: ('C','E','F'), ('C','E','G'), ('D','E','F'), ('D','E','G')

We try each combination by:

1. Joining the characters to form the next row string
2. Recursively calling dfs on that row
3. Using any() to return True if at least one path succeeds

4. Memoization with @cache

The @cache decorator automatically memoizes the function results. If we encounter the same row string again (through different paths), we immediately return the cached result instead of recomputing. This is crucial for efficiency since different bottom-row combinations might converge to identical middle rows.

Example Walkthrough

For bottom = "ABC" with appropriate allowed patterns:

1. Call dfs("ABC")
2. Process pairs: ("A","B") and ("B","C")
3. Find valid blocks for each pair from dictionary d
4. Generate all combinations for the next row (2 blocks)
5. Recursively call dfs on each 2-block combination
6. Each of those calls will create 1-block rows
7. When we reach 1 block, return True
8. Propagate success/failure back up the recursion chain

The algorithm effectively explores all valid pyramid configurations using DFS, pruning impossible paths early and avoiding redundant computation through memoization.

Example Walkthrough

Let's walk through a concrete example with bottom = "AABA" and allowed = ["AAB", "AAC", "ABA", "ABB", "BAC"].

Step 1: Build the lookup dictionary

d = {
    ("A","A"): ["B", "C"],  # from "AAB" and "AAC"
    ("A","B"): ["A", "B"],  # from "ABA" and "ABB"  
    ("B","A"): ["C"]        # from "BAC"
}

Step 2: Start DFS with bottom row "AABA"

Call dfs("AABA"):

• Length is 4, not base case
• Process adjacent pairs: ("A","A"), ("A","B"), ("B","A")
• Look up valid blocks:
  • ("A","A") → ["B", "C"]
  • ("A","B") → ["A", "B"]
  • ("B","A") → ["C"]

Step 3: Generate all combinations for the 3-block row

Using product(["B","C"], ["A","B"], ["C"]):

• Combination 1: "BAC"
• Combination 2: "BBC"
• Combination 3: "CAC"
• Combination 4: "CBC"

Step 4: Try each combination recursively

Let's follow "BAC":

Call dfs("BAC"):

• Process pairs: ("B","A"), ("A","C")
• Look up valid blocks:
  • ("B","A") → ["C"]
  • ("A","C") → [] (no valid block!)
• Since ("A","C") has no valid blocks, return False

Let's try "BBC":

Call dfs("BBC"):

• Process pairs: ("B","B"), ("B","C")
• Assume we have no patterns for these pairs
• Return False

Continue this process for "CAC" and "CBC". If none work, we'd return False.

Step 5: Successful path (hypothetical)

Suppose we had additional patterns and "CAC" worked:

Call dfs("CAC"):

• Process pairs: ("C","A"), ("A","C")
• Assume both pairs have valid blocks that lead to row "XY"

Call dfs("XY"):

• Process pair: ("X","Y")
• Assume this gives us block "Z" for the top

Call dfs("Z"):

• Length is 1 - we've reached the peak!
• Return True

This True propagates back through all the recursive calls, ultimately returning True for the original pyramidTransition(bottom, allowed) call.

Key Observations:

• We explored multiple branches (different 3-block combinations)
• Some branches failed early when no valid blocks existed for a pair
• Memoization would help if we reached the same intermediate row through different paths
• The algorithm exhaustively tries all possibilities until finding a valid pyramid or confirming none exists

Solution Implementation

Time and Space Complexity

Time Complexity: O(b^n * n) where b is the branching factor (maximum number of possible characters for any pair) and n is the length of the bottom string.

• The pyramid has n levels (from bottom to top).
• At each level i, we have n - i + 1 positions.
• For each pair of adjacent characters, we might have up to b choices (where b ≤ 7 since we have at most 7 different characters A-G).
• In the worst case, at level i, we explore up to b^(n-i) different strings.
• The total number of states explored is bounded by Σ(i=1 to n) b^(n-i) = b^(n-1) + b^(n-2) + ... + b^0 = (b^n - 1)/(b - 1) = O(b^n).
• For each state, we perform O(n) work to process the string and generate the next level.
• Therefore, the overall time complexity is O(b^n * n).

Space Complexity: O(b^n * n) for the memoization cache plus O(n) for the recursion stack depth.

• The @cache decorator memoizes all unique strings that appear during recursion.
• In the worst case, we might cache O(b^n) different strings across all levels.
• Each cached string has maximum length n.
• The recursion depth is at most n (height of the pyramid).
• The dictionary d stores the allowed transitions, which takes O(|allowed|) space where |allowed| ≤ 500.
• Therefore, the total space complexity is O(b^n * n + n + |allowed|) = O(b^n * n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Multiple Valid Transitions for the Same Pair

A critical pitfall is assuming each pair of blocks can only produce one block above it. In reality, the same pair might have multiple valid transitions.

Incorrect Approach:

# Wrong: Only considering one possible block per pair
transitions_map = {}  # Using regular dict instead of defaultdict(list)
for transition in allowed:
    left, right, top = transition[0], transition[1], transition[2]
    transitions_map[left, right] = top  # Overwrites previous values!

Why it fails: If allowed = ["ABC", "ABD"], the second pattern overwrites the first, losing valid pyramid paths.

Correct Solution:

transitions_map = defaultdict(list)
for transition in allowed:
    left, right, top = transition[0], transition[1], transition[2]
    transitions_map[left, right].append(top)  # Keeps all possibilities

2. Forgetting to Use Memoization

Without memoization, the algorithm becomes exponentially slow due to recomputing the same intermediate levels multiple times.

Incorrect Approach:

def can_build_pyramid(current_level: str) -> bool:
    # No @cache decorator - recalculates everything!
    if len(current_level) == 1:
        return True
    # ... rest of logic

Why it fails: Different bottom configurations can converge to the same middle levels. For example, both "ABCD" and "EFGH" might produce "XY" as an intermediate level. Without caching, we'd rebuild from "XY" multiple times.

Correct Solution: Always use @cache or implement manual memoization with a dictionary.

3. Incorrect Iteration Over Adjacent Pairs

A subtle bug occurs when manually iterating over pairs instead of using pairwise.

Incorrect Approach:

# Wrong: Off-by-one error or incorrect pairing
for i in range(len(current_level)):  # Goes too far!
    left = current_level[i]
    right = current_level[i + 1]  # IndexError when i == len-1

Or:

# Wrong: Creates wrong number of pairs
for i in range(len(current_level) - 2):  # Should be -1, not -2
    left = current_level[i]
    right = current_level[i + 1]

Correct Solution: Use itertools.pairwise() or carefully implement the loop:

# Option 1: Using pairwise (Python 3.10+)
for left, right in pairwise(current_level):
    # Process pair

# Option 2: Manual implementation
for i in range(len(current_level) - 1):
    left = current_level[i]
    right = current_level[i + 1]

4. Not Exploring All Combinations with Cartesian Product

A common mistake is trying only one possible configuration for the next level instead of exploring all combinations.

Incorrect Approach:

# Wrong: Only tries first valid option for each position
next_level = []
for left, right in pairwise(current_level):
    possible = transitions_map[left, right]
    if not possible:
        return False
    next_level.append(possible[0])  # Only uses first option!

return can_build_pyramid(''.join(next_level))

Why it fails: This greedy approach misses valid pyramid configurations where the first choice leads to a dead end but other choices succeed.

Correct Solution: Use itertools.product() to generate all combinations:

for next_level_combination in product(*next_level_options):
    if can_build_pyramid(''.join(next_level_combination)):
        return True

5. Using Tuples as Dictionary Keys Without Converting

When using pairs as dictionary keys, forgetting to maintain consistent key types causes lookup failures.

Incorrect Approach:

# Building the map with string concatenation
transitions_map[left + right] = top  # Key is string "AB"

# But looking up with tuple
for left, right in pairwise(current_level):
    possible = transitions_map[(left, right)]  # Key is tuple ('A', 'B')
    # KeyError!

Correct Solution: Be consistent with key types:

# Either use tuples consistently:
transitions_map[(left, right)].append(top)
# ...
possible = transitions_map[(left, right)]

# Or use strings consistently:
transitions_map[left + right].append(top)
# ...
possible = transitions_map[left + right]