Pyramid Transition Matrix
Problem
Given a bottom row of blocks and allowed triples (two-block base producing a top block), determine whether a pyramid can be built up to a single block by stacking valid triples.
bottom='BCD', allowed=['BCC','CDE','CEA','FFF']truedef pyramidTransition(bottom, allowed):
m = {}
for s in allowed:
m.setdefault(s[:2], []).append(s[2])
def dfs(row):
if len(row) == 1: return True
def build(i, nxt):
if i+1 == len(row):
return dfs(nxt)
for c in m.get(row[i]+row[i+1], []):
if build(i+1, nxt+c): return True
return False
return build(0, "")
return dfs(bottom)function pyramidTransition(bottom, allowed) {
const m = {};
for (const s of allowed) (m[s.slice(0,2)] ||= []).push(s[2]);
function dfs(row) {
if (row.length === 1) return true;
function build(i, nxt) {
if (i+1 === row.length) return dfs(nxt);
for (const c of (m[row[i]+row[i+1]] || []))
if (build(i+1, nxt+c)) return true;
return false;
}
return build(0, "");
}
return dfs(bottom);
}Map<String,List<Character>> m = new HashMap<>();
boolean pyramidTransition(String bottom, List<String> allowed) {
for (String s : allowed) m.computeIfAbsent(s.substring(0,2), k -> new ArrayList<>()).add(s.charAt(2));
return dfs(bottom);
}
boolean dfs(String row) {
if (row.length() == 1) return true;
return build(row, 0, new StringBuilder());
}
boolean build(String row, int i, StringBuilder nxt) {
if (i+1 == row.length()) return dfs(nxt.toString());
for (char c : m.getOrDefault(row.substring(i,i+2), List.of())) {
nxt.append(c);
if (build(row, i+1, nxt)) return true;
nxt.deleteCharAt(nxt.length()-1);
}
return false;
}unordered_map<string,string> m;
bool dfs(const string& row);
bool build(const string& row, int i, string& nxt) {
if (i+1 == (int)row.size()) return dfs(nxt);
for (char c : m[row.substr(i,2)]) {
nxt.push_back(c);
if (build(row, i+1, nxt)) return true;
nxt.pop_back();
}
return false;
}
bool dfs(const string& row) {
if (row.size() == 1) return true;
string nxt; return build(row, 0, nxt);
}
bool pyramidTransition(string bottom, vector<string>& allowed) {
for (auto& s : allowed) m[s.substr(0,2)] += s[2];
return dfs(bottom);
}Explanation
We are stacking a pyramid: each block sits on a pair of blocks below it, and only certain triples (two-block base plus the top it produces) are allowed. The question is whether we can keep stacking until a single block remains.
First we turn the allowed triples into a lookup table m: for each two-letter base we store the list of letters that can sit on top. So 'CE' might map to ['A'].
The function dfs(row) tries to build the row directly above the current one. The helper build(i, nxt) walks the row left to right, and for the pair at position i it tries every allowed top letter, appending it to nxt. When the next row is fully built it calls dfs(nxt) to go up another level. This is recursion with backtracking: if a choice leads nowhere, it backs up and tries a different top letter.
If we ever reach a row of length 1, the pyramid is complete and we return true. If no combination works, every branch returns false.
Example: bottom='BCD' with allowed ['BCC','CDE','CEA','FFF']. From BC we get C and from CD we get E, building row CE; then CE gives A, a single block — so the answer is true.