🌲 Invert a binary tree! 🌲
Except with 3 catches:
- It must invert the keys ("bit-reversal permutation")
- It must be a dependency-free, pure recursive function
- It must have type
Bit -> Tree -> Tree(i.e., a direct recursion with max 1 bit state)
- It is somehow NOT on the internet. (AFAIK)
- Humans can solve it. (I've done it in ~1h.)
- It requires reasoning. (My head hurts!)
- The solution is simple. (7 lines of code!)
- Obvious pre-requisite to automate CS research.
- Honestly, it would make me believe I'll be automated.
I claim no AI will EVER solve this problem. If you prove me wrong, HOC will grant you $10k!
- You must give it an approved prompt, nothing else.
- It must output a correct solution, passing all tests.
- You can use any software or AI model.
- You can let it "think" for as long as you want.
- You can propose a new prompt, as long as:
- It imposes equivalent restrictions.
- It clearly doesn't help the AI.
- Up to 1K tokens, all included.
- Common sense applies.
{-# OPTIONS --no-termination-check #-}
-- Let Tree be a Perfect Binary Tree:
data Nat : Set where
Z : Nat
S : Nat → Nat
{-# BUILTIN NATURAL Nat #-}
data Bit : Set where
O : Bit
I : Bit
data Tree (A : Set) : Nat → Set where
N : ∀ {d} → Tree A d → Tree A d → Tree A (S d)
L : Nat → Tree A Z
-- Your goal is to implement an 'invert' function that performs a bit-reversal
-- permutation on a Tree, respecting the following limitations:
-- 1. You can NOT define or use any function other than 'invert'.
-- 2. You can NOT use any type not defined above (Nat, Bit and Tree).
-- 3. You can NOT use loops (but you can call 'invert' recursively).
-- 4. You can NOT use mutability. It must be a pure Agda function.
-- 5. You can use 1 bit of state (as an extra argument).
-- 6. You can use pattern-matching and constructors freely.
--
-- Example:
-- input = (N(N(N(L 0)(L 1))(N(L 2)(L 3)))(N(N(L 4)(L 5))(N(L 6)(L 7))))
-- output = (N(N(N(L 0)(L 4))(N(L 2)(L 6)))(N(N(L 1)(L 5))(N(L 3)(L 7))))
-- Because that's the bit-reversal permutation of the original tree.
--
-- Now, complete the program below, with a valid implementation of 'invert':
invert : ∀ {A d} → Bit → Tree A d → Tree A dtype Nat = number;
type Bit = false | true;
type Tree<A> = [Tree<A>, Tree<A>] | Nat;
// Your goal is to implement an 'invert' function that performs a bit-reversal
// permutation on a Tree, respecting the following limitations:
// 1. You can NOT define or use any function other than 'invert'.
// 2. You can NOT use any type not defined above (Nat, Bit and Tree).
// 3. You can NOT use loops (but you can call 'invert' recursively).
// 4. You can NOT use mutability. It must be a pure function.
// 5. You can NOT use primitive JS operators or functions.
// 6. You can use 1 bit of state (as an extra argument).
// 7. You can only use the operations allowed below.
//
// Operations allowed:
// - Destructing (`const [a,b] = value`)
// - Variables (`const x = value`)
// - Branching (`if (x) { ... } else { ... }`)
// - Recursion (`invert(_, _)')
// - `Array.isArray`
//
// All other operations are not allowed.
//
// Example:
// input = [[[[0,1],[2,3]],[[4,5],[6,7]]]]
// output = [[[[0,4],[2,6]],[[1,5],[3,7]]]]
// Because that's the bit-reversal permutation of the original tree.
//
// Now, complete the program below, with a valid implementation of 'invert':
function invert<A>(bit: Bit, tree: Tree<A>): Tree<A> {
...
}
// A test:
const tree: Tree<Nat> = [[[[0,1],[2,3]],[[4,5],[6,7]]],[[[8,9],[10,11]],[[12,13],[14,15]]]];
console.log(JSON.stringify(invert(true, tree)));✨ If it can't invert a tree, it won't solve P=NP. ✨
To implement the "Bit-Reversal Tree Inversion" task and verify correctness using a truth table test, here’s a structured breakdown following the constraints and objectives:
Plan
This will recursively traverse the binary tree.
Swap the left and right subtrees when the bit is I.
Do not swap when the bit is O.
This will recursively check if two trees are identical, which is necessary to verify if the double inversion restores the original tree.
Display the tree before and after inversion to trace the operations.
Build binary trees of depth 1 and depth 2.
Perform bit-reversal inversion on these trees and verify with a truth table approach.
Check if the tree is restored to its original form after applying the inversion twice.
Python Implementation
class TreeNode:
"""Binary Tree Node with a key and left/right children."""
def init(self, key, left=None, right=None):
self.key = key # The "key" corresponds to the bit or data (Nat in this case)
self.left = left
self.right = right
def invert_tree(bit, node):
"""Recursive function to invert the tree by reversing the key bits and swapping children."""
if node is None:
return None # Base case: no node to invert
if isinstance(node, TreeNode):
if bit == 'I':
# Swap left and right if bit is I
return TreeNode(node.key, invert_tree(bit, node.right), invert_tree(bit, node.left))
else:
# Do not swap if bit is O
return TreeNode(node.key, invert_tree(bit, node.left), invert_tree(bit, node.right))
Function to compare two trees
def are_trees_equal(t1, t2):
if t1 is None and t2 is None:
return True
if t1 is None or t2 is None:
return False
return (t1.key == t2.key) and are_trees_equal(t1.left, t2.left) and are_trees_equal(t1.right, t2.right)
Helper function to display tree structure
def print_tree(node, level=0, prefix="Root: "):
if node is not None:
print(" " * (level * 4) + prefix + str(node.key))
print_tree(node.left, level + 1, "L--- ")
print_tree(node.right, level + 1, "R--- ")
Let's build a simple depth-2 tree for testing
def build_depth2_tree():
return TreeNode(0,
TreeNode(1,
TreeNode(2), TreeNode(3)),
TreeNode(4,
TreeNode(5), TreeNode(6)))
Let's build a simple depth-1 tree for testing
def build_depth1_tree():
return TreeNode(0, TreeNode(1), TreeNode(2))
Truth table test for depth 1 and depth 2 trees
def truth_table_test():
trees = [build_depth1_tree(), build_depth2_tree()]
Run the truth table test
truth_table_test()
Explanation:
TreeNode: Represents a node in the binary tree. Each node holds a key (integer) and references to left and right child nodes.
invert_tree: A recursive function that inverts the tree based on the provided bit:
If bit == 'I', it swaps the left and right subtrees.
If bit == 'O', it keeps the subtrees in place.
are_trees_equal: Compares two binary trees to ensure that they are identical, which helps verify the result of double inversion.
print_tree: A helper function that visually prints the tree structure for easy inspection during testing.
build_depth1_tree and build_depth2_tree: Helper functions that build simple binary trees of depth 1 and 2 for testing purposes.
truth_table_test: Runs the truth table-like test to check if the tree is correctly restored after applying the inversion twice.
Output:
The truth_table_test function systematically tests the inversion and double inversion on two different trees (depth-1 and depth-2). It will display the original tree, the inverted tree, and the double inverted tree, confirming if the double inversion restores the original tree.
For example, for a depth-2 tree:
Original Tree Structure:
Root: 0
L--- 1
L--- 2
R--- 3
R--- 4
L--- 5
R--- 6
Inverted Tree Structure:
Root: 0
L--- 4
L--- 6
R--- 5
R--- 1
L--- 3
R--- 2
Double Inverted Tree Structure (Should match Original):
Root: 0
L--- 1
L--- 2
R--- 3
R--- 4
L--- 5
R--- 6
Result: Pass (Tree restored correctly after double inversion)
This verifies that the bit-reversal tree inversion works as expected.