Gere um programa simples de árvore de decisão para encontrar mínimos

Uma nova ferramenta de geração de código recebe apenas uma entrada - n, o tamanho de um array de entrada. A ferramenta deve então gerar um programa de árvore de decisão simples que contém 2 tipos de nós:

• nó de decisão com comparação estrita
• nó de saída (folha)

O nó de decisão compara dois elementos de uma matriz de entrada usando 1 de 3 operadores - <, =, >. Combinações desses operadores NÃO são permitidas. Usar operadores booleanos extras como NOT, AND, OR também não é permitido.

Um nó de saída especifica quais elementos retornar do array de entrada. Esses elementos devem ter todos o mesmo valor e esse valor é o mínimo de todo o array de entrada.

Até agora, tentei usar uma abordagem baseada em pilha que gera código correto para array de entrada de comprimento 2, mas falha para cada comprimento maior. A saída se parece com isso:

if input[0] < input[1]:
    return input[0]
else:
    if input[0] == input[1]:
        return input[0, 1]
    else:
        return input[1]

Aqui está meu código:

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()
)

imprimir.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!!
}

principal.kt

fun main() {
    val root = generateMinProgram(2)
    val code = generatePythonCode(root)
    println(code)
}

Não estou pedindo para você consertar meu código. Em vez disso, o que estou procurando é uma descrição de um algoritmo de alto nível e suas estruturas de dados. Talvez uma solução de backtracking seja suficiente?

Também é um problema XY porque o que eu realmente preciso é de uma resposta para a pergunta Como podemos derivar a fórmula para os nós de decisão estrita mínima na matriz Minimum-Finding? que não teve muitas visualizações, então estou tentando descobrir a fórmula forçando brutamente a etapa de geração de código.