A new code-generating tool is given only one input - n, the size of an input array. The tool should then generate a simple decision tree program that contains 2 kinds of nodes:
The decision node compares two elements from an input array using 1 of 3 operators - <, =, >. Combinations of these operators are NOT allowed. Using extra Boolean operators like NOT, AND, OR is also not allowed.
An output node specifies what elements to return from the input array. Those elements should all have the same value and this value is the minimum of the entire input array.
So far, I have tried to use a stack-based approach that generates correct code for input array of length 2 but fails for every higher length. The output looks like this:
if input[0] < input[1]:
return input[0]
else:
if input[0] == input[1]:
return input[0, 1]
else:
return input[1]
Here is my code:
Node.kt
import ComparisonOperator.*
enum class ComparisonOperator {
LESS_THAN, EQUALS, GREATER_THAN
}
class Node (
val trueBranch: Node? = null,
val falseBranch: Node? = null,
val operator: ComparisonOperator = LESS_THAN,
val indices: IntArray = intArrayOf()
)
print.kt
import TaskType.*
enum class TaskType {
PROCESS_NODE,
PROCESS_ELSE
}
data class StackEntry(val node: Node, val indent: Int, val taskType: TaskType)
fun generatePythonCode(root: Node): String {
val builder = StringBuilder()
val stack = ArrayDeque<StackEntry>()
stack.addLast(StackEntry(root, 0, PROCESS_NODE))
while (stack.isNotEmpty()) {
val entry = stack.removeLast()
val node = entry.node
val indent = entry.indent
val indentStr = " ".repeat(indent)
when (entry.taskType) {
PROCESS_NODE -> {
if (node.trueBranch == null) {
// Leaf node: output the return statement.
val indices = node.indices.joinToString(", ")
builder.append(indentStr).append("return input[").append(indices).append("]\n")
} else {
// Decision node: output an if statement.
val left = "input[${node.indices[0]}]"
val right = "input[${node.indices[1]}]"
val op = when (node.operator) {
ComparisonOperator.LESS_THAN -> "<"
ComparisonOperator.EQUALS -> "=="
ComparisonOperator.GREATER_THAN -> ">"
}
builder.append(indentStr).append("if ").append(left).append(" $op ").append(right).append(":\n")
// Push the false branch as an else task (it will add the "else:" line).
stack.addLast(StackEntry(node.falseBranch!!, indent, PROCESS_ELSE))
// Then push the true branch for processing with increased indent.
stack.addLast(StackEntry(node.trueBranch, indent + 1, PROCESS_NODE))
}
}
PROCESS_ELSE -> {
// For an else task, output the "else:" line and then process the node.
builder.append(indentStr).append("else:\n")
stack.addLast(StackEntry(node, indent + 1, PROCESS_NODE))
}
}
}
return builder.toString().trimEnd()
}
codegen.kt
import ComparisonOperator.*
enum class FrameType {
EQUALITY,
MERGE
}
// Each frame holds the current candidate groups (each a List<Int>).
// When the number of candidate groups is 1, a leaf (output) node is produced.
// Otherwise, two candidate groups are extracted and processed.
data class Frame(
val candidates: List<List<Int>>,
val type: FrameType,
var step: Int = 0,
var group1: List<Int>? = null,
var group2: List<Int>? = null,
var rest: List<List<Int>> = emptyList(),
// For a MERGE frame, we need:
// branchTrue: result for candidate list [group1] + rest.
// branchEquality (i.e. the nested equality decision) will be built from two subbranches.
// For an EQUALITY frame, we only need branchTrue and branchFalse.
var branchTrue: Node? = null,
var branchFalse: Node? = null,
// Temporary field to hold a generated child result.
var tempResult: Node? = null
)
// The function generateMinProgram builds the decision tree (as Node objects) that, when interpreted,
// returns the indices of all occurrences of the minimum element from the input array.
// It uses a brute-force backtracking strategy based on a stack.
fun generateMinProgram(n: Int): Node {
// Assume n >= 2. Initially, each candidate group is a single index.
val initialCandidates = (0 until n).map { listOf(it) }
val stack = ArrayDeque<Frame>()
// The outermost decision is always a MERGE.
stack.add(Frame(candidates = initialCandidates, type = FrameType.MERGE))
// The iterative DFS: process the frames until the root decision is built.
var result: Node? = null
while (stack.isNotEmpty()) {
val current = stack.last()
// If the candidate list has only one candidate group, create a leaf (output) node.
if (current.candidates.size == 1) {
// This candidate group represents the indices that are equal to the minimum.
result = Node(
trueBranch = null,
falseBranch = null,
// For output nodes the operator value is not used.
operator = LESS_THAN,
indices = current.candidates.first().toIntArray()
)
stack.removeLast()
if (stack.isNotEmpty()) {
// Propagate the result to the parent frame.
stack.last().tempResult = result
} else {
// No parent exists; this would happen if n==1 (but we assume n>=2).
return result
}
continue
}
// Otherwise, there is at least a decision to be made.
when (current.type) {
FrameType.MERGE -> {
// MERGE frame has three main phases.
when (current.step) {
0 -> {
// Initialize: pick the first two candidate groups.
current.group1 = current.candidates[0]
current.group2 = current.candidates[1]
current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
// Process the "true" branch for the primary decision:
// if input[group1[0]] < input[group2[0]] then the winner is group1.
val trueCandidates = listOf(current.group1!!) + current.rest
// New frame for processing the "true" branch.
stack.add(Frame(candidates = trueCandidates, type = FrameType.MERGE))
current.step = 1
}
1 -> {
// Coming back from the "true" branch.
current.branchTrue = current.tempResult
current.tempResult = null
// Next, process the nested equality decision.
// Create a new EQUALITY frame.
// For equality: if input[group1[0]] == input[group2[0]], then we merge group1 and group2.
// The candidate list becomes [group1 U group2] + rest.
val merged = current.group1!! + current.group2!!
val eqCandidates = listOf(merged) + current.rest
stack.add(Frame(candidates = eqCandidates, type = FrameType.EQUALITY))
current.step = 2
}
2 -> {
// Returning from the equality branch's "true" part (for the equality decision).
// In a MERGE frame, we now go to process the "false" branch of the nested equality:
current.branchTrue = current.branchTrue // holds nothing new; we now reuse the equality structure.
// For the "false" branch of the equality decision (i.e. when input[group1[0]] is not equal to input[group2[0]])
// we take group2 as the winner. Candidate list becomes [group2] + rest.
val falseCandidates = listOf(current.group2!!) + current.rest
stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
current.step = 3
}
3 -> {
// Coming back from the equality frame "false" branch.
current.branchFalse = current.tempResult
current.tempResult = null
// Build the nested equality decision node.
// This node has operator EQUALS and compares the same indices from group1 and group2.
val eqNode = Node(
trueBranch = current.tempResult ?: run {
// The true branch result is already stored in branch from the equality frame "true",
// which was set when processing the equality frame. In this MERGE frame, we expect the equality
// decision to have been constructed by processing the two equality branches.
// Here we use current.branchTrue that was computed in step 2.
current.branchTrue
},
falseBranch = current.branchFalse,
operator = EQUALS,
indices = intArrayOf(current.group1!![0], current.group2!![0])
)
// Build the primary decision node.
val mergeNode = Node(
trueBranch = current.branchTrue,
falseBranch = eqNode,
operator = LESS_THAN,
indices = intArrayOf(current.group1!![0], current.group2!![0])
)
stack.removeLast() // Done with current MERGE frame.
if (stack.isNotEmpty()) {
stack.last().tempResult = mergeNode
} else {
return mergeNode
}
}
}
}
FrameType.EQUALITY -> {
// EQUALITY frame has two phases.
when (current.step) {
0 -> {
// In an EQUALITY frame the comparison is always on the two groups that formed the candidate list.
// Since we always pass a candidate list with at least one candidate, if there are at least two,
// then we perform a decision test.
current.group1 = current.candidates[0]
current.group2 = current.candidates[0] // In an equality frame candidate list is built from either merged groups or single group2.
// For an EQUALITY frame, if there is more than one candidate group then we consider the first two.
// However, in our usages we've built the candidate list so that its size should be 1.
// To support a generic approach we check:
if (current.candidates.size >= 2) {
current.group2 = current.candidates[1]
current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
} else {
// If candidate list size is 1, then we are at a leaf even in an equality frame.
val leaf = Node(
trueBranch = null,
falseBranch = null,
operator = EQUALS,
indices = current.candidates.first().toIntArray()
)
stack.removeLast()
if (stack.isNotEmpty()) {
stack.last().tempResult = leaf
} else {
return leaf
}
continue
}
// Process the "true" branch of the equality decision:
// If input[group1[0]] == input[group2[0]], then the result candidate list remains as-is.
// (In our usage, for the equality branch, candidate list is already merged.)
val trueCandidates = current.candidates
stack.add(Frame(candidates = trueCandidates, type = FrameType.EQUALITY))
current.step = 1
}
1 -> {
// Return from the "true" branch.
current.branchTrue = current.tempResult
current.tempResult = null
// Process the "false" branch:
// In our usage, the "false" branch for an EQUALITY decision comes from a candidate list built for group2.
// We expect that candidate list to have a single candidate group.
val falseCandidates = if (current.candidates.size >= 2) {
// Use the second candidate alone alongside any remaining candidates.
listOf(current.candidates[1]) + current.rest
} else {
current.candidates
}
stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
current.step = 2
}
2 -> {
// Return from the "false" branch.
current.branchFalse = current.tempResult
current.tempResult = null
// Build the equality decision node.
val eqNode = Node(
trueBranch = current.branchTrue,
falseBranch = current.branchFalse,
operator = EQUALS,
indices = intArrayOf(current.candidates[0][0], if (current.candidates.size >= 2) current.candidates[1][0] else current.candidates[0][0])
)
stack.removeLast()
if (stack.isNotEmpty()) {
stack.last().tempResult = eqNode
} else {
return eqNode
}
}
}
}
}
}
// Should never reach here.
return result!!
}
main.kt
fun main() {
val root = generateMinProgram(2)
val code = generatePythonCode(root)
println(code)
}
I don't ask you to fix my code. Instead what I am searching is a description of a high-level algorithm and its data structures. Maybe a backtracking solution is sufficient?
It's also a XY problem because what I really need is an answer to the question How can we derive the formula for the minimal strict decision nodes in array Minimum-Finding? which didn't get many views so I am trying to find out the formula by brute-forcing the code-generating step.
All you need is a recursive procedure that compares the elements from left to right going through the array and keeps track of mins, although the output size will be growing exponentially:
generateTree(n) {
root = new Node(LESS_THAN, [0, 1])
root.trueBranch = generateSubtree([0], 2, n)
root.falseBranch = new Node(EQUALS, [0, 1])
root.falseBranch.falseBranch = generateSubtree([1], 2, n)
root.falseBranch.trueBranch = generateSubtree([0, 1], 2, n)
}
generateSubtree(mins, next, n) {
if (next == n)
return new Node(null, mins.clone())
node = new Node(LESS_THAN, [next, mins[0]])
node.trueBranch = generateSubtree([next], next + 1, n)
node.falseBranch = new Node(EQUALS, [next, mins[0]])
mins.add(next)
node.falseBranch.trueBranch = generateSubtree(mins, next + 1, n)
mins.removeLast()
node.falseBranch.falseBranch = generateSubtree(mins, next + 1, n)
return node
}