Pyramid Transition Matrix in Java

Creating a pyramid block by block is the task given to us in this problem. Each block has a color that corresponds to a letter. The pyramid is built so that each row contains one fewer block than the row below it. To create the pyramid, one block is stacked on top of two nearby blocks that are directly below it, creating a triangle.

There are particular rules that we have to adhere to when stacking the blocks: only specific triangular designs are permitted. A three-letter strings is used to indicate a pattern, with the first two letters representing the colors of the left and right base blocks and the third letter representing the color of the block that is piled on top.

A list of permitted designs is also given to us, along with the base of the pyramid in the form of a string bottom. Finding out if the pyramid can be constructed all the way to the top while ensuring that every triangle pattern it forms is included in the list of permitted patterns is the aim. We return true if it is possible to construct that way; if not, we return false.

Example 1:

Input:

String bottom = "BCD"

String allow = ["BCC", "CDE", "CEA", "FFF"]

Output: true

Explanation:

The triangle patterns that are permitted are displayed on the right.

Building "CE" on level 2 and then "A" on level 1 would allow us to start at the bottom (level 3).

"BCC," "CDE," and "CEA" are the three triangle designs that make up the pyramid. All are allowed.

Example 2:

Input:

String bottom = "AAAA"

String allowed = ["AAB", "AAC", "BCD", "BBE", "DEF"]

Output: false

Explanation:

The triangle patterns that are permitted are displayed on the right.

We can build level 3 in a number of ways, starting from level 4, but if we try every option, we will always end up stranded before we can create level 1.

Approach: Using Recursive Depth First Search

Using a depth-first search, the recursive function dfs builds potential pyramid configurations level by level, starting at the bottom. On the basis of the blocks that are now being analyzed, each dfs invocation attempts to construct the subsequent level.

In the given code, in order to determine whether a pyramid can be constructed from a given base (bottom) and permitted transitions (allow), a Java program creates a pyramid transition matrix utilizing bitwise operations and depth-first search (DFS) with memoization. Bitwise representation is used to store valid transitions in the transition matrix (trans_Matrix). The pyramid is constructed iteratively by the DFS function, which verifies that each level can be created with the provided guidelines. Efficiency is increased by optimizing repeated state computations through the use of memorization (memorization hash map). The base case guarantees that the function returns true when there is just a single block left at the top.

Algorithm:

Step 1: In order to store potential transitions using bitwise representation, create a 2D integer array called trans_Matrix[7][7].

Step 2: To save previously calculated results for optimization, use a memoization HashMap.

Step 3: Go through each allow list transition string one by one.

Step 3.1: Extract the transition's first and second characters as first and second, respectively.

Step 3.2: Take their ASCII values and subtract 'A' from them to convert them to indices.

Step 3.3: To store the transition to the third character, set the matching entry in trans_Matrix using bitwise OR.

Step 4: Use an empty StringBuilder as nextLevel and bottom as curr_Level when calling the dfs(curr_Level, nextLevel) method.

Step 5: Return true if curr_Level has a single block (pyramid is correctly created).

Step 6: If the necessary length (curr_Level.length() - 1) is reached by nextLevel,

Step 6.1: For the following level, recursively call dfs(nextLevel.toString(), new StringBuilder()).

Step 7: Use curr_Level + "." + nextLevel.toString() to create a unique key.

Step 8: Return the key's stored value if it is present in the memoization.

Step 9: Using curr_Level, find the first and second block indices.

Step 10: From trans_Matrix, retrieve potentialTransitions.[first] [second].

Step 11: Repeat with seven different characters ('A' to 'G'):

Step 11.1: If a character 'A' + i transition is feasible, add it to the following level.

Step 11.1.1: Call dfs(curr_Level, nextLevel) recursively.

Step 11.1.2: If successful, return true after storing true in memoization.

Step 11.1.3: If not, retrace and erase the final character that was added.

Step 12: Return false and store false in memoization if there isn't a proper transition.

Step 13: Set the allow list and bottom string to initial values.

Step 14: Invoke pyramidTransition(bottom, allow) after creating an instance of the class.

Step 15: Return the result (false or true).

Implementation:

Output:

 
true   

Complexity Analysis:

The time complexity of the above code is O(7^(N-1)), where 'N' represents the length of the bottom, and the space complexity is O(7^(N-1)) since each recursive step can branch into seven choices per transition.