InfiniteCoder01 · August 15, 2025 14:55 · Aug 15, 2025
diff --git a/challenge.cpp b/challenge.cpp
@@ -0,0 +1,361 @@
+#include <assert.h>
+#include <stddef.h>
+#include <string>
+
+// Option
+template<typename T>
+struct Option {
+    bool tag;
+    T value;
+
+    static Option<T> some(T value) {
+        return Option {
+            .tag = true,
+            .value = value,
+        };
+    }
+
+    static Option<T> none() {
+        return Option {
+            .tag = false,
+        };
+    }
+};
+
+template<typename T>
+T option_unwrap(Option<T> self) {
+    assert(self.tag);
+    return self.value;
+}
+
+// Box
+template<typename T>
+struct Box {
+    T *value;
+};
+
+template<typename T>
+Box<T> box_new(T value) {
+    return Box<T> {
+        .value = new T(value),
+    };
+}
+
+template<typename T>
+void box_drop(Box<T> self) {
+    delete self.value;
+}
+
+template<typename Self>
+struct Display {
+    void (*fmt)(const Self *self, std::string *f);
+};
+
+// iterate on previous program
+namespace iota {
+    // SimpleIterator
+    template<typename T, typename I>
+    struct Peekable;
+
+    template<typename Self, typename Item>
+    Peekable<Self, Item> peekable_default(Self self);
+
+    template<typename Self, typename Item>
+    struct SimpleIterator {
+        Option<Item> (*next)(Self *self);
+        Peekable<Self, Item> (*peekable)(Self self) = peekable_default<Self, Item>;
+    };
+
+    // Peekable
+    template<typename T, typename I>
+    struct Peekable {
+        T iter;
+        Option<I> peeked;
+
+        static SimpleIterator<Peekable<T, I>, I> simple_iterator_impl;
+    };
+
+    template<typename Self, typename Item>
+    Peekable<Self, Item> peekable_default(Self self) {
+        return Peekable<Self, Item> {
+            .iter = self,
+            .peeked = Option<Item>::none(),
+        };
+    }
+
+    template<typename I, typename T>
+    Option<I> peekable_peek(Peekable<T, I> *self) {
+        if (!self->peeked.tag) {
+            self->peeked = T::simple_iterator_impl.next(&self->iter);
+        }
+        return self->peeked;
+    }
+
+    template<typename I, typename T>
+    Option<I> peekable_next(Peekable<T, I> *self) {
+        if (self->peeked.tag) {
+            const auto tmp = self->peeked;
+            self->peeked = Option<I>::none();
+            return tmp;
+        } else return T::simple_iterator_impl.next(&self->iter);
+    }
+
+    template<typename T, typename I>
+    SimpleIterator<Peekable<T, I>, I> Peekable<T, I>::simple_iterator_impl = {
+        .next = peekable_next,
+    };
+
+    // Iota
+    struct Iota {
+        size_t field0;
+
+        static SimpleIterator<Iota, size_t> simple_iterator_impl;
+    };
+
+    Iota iota_new() {
+        return Iota {
+            .field0 = 0,
+        };
+    }
+
+    Option<size_t> iota_next(Iota *self) {
+        const auto prev = self->field0;
+        self->field0 = prev + 1;
+        return Option<size_t>::some(prev);
+    }
+
+    SimpleIterator<Iota, size_t> Iota::simple_iterator_impl = {
+        .next = iota_next,
+    };
+}
+
+namespace peano {
+    struct Nat;
+    Nat nat_add(Nat self, Nat rhs);
+
+    /// Peano Natural Number
+    struct Nat {
+        enum {
+            Zero,
+            Succ,
+        } tag;
+        Box<Nat> field0;
+
+        static Nat zero() {
+            return Nat {
+                .tag = Zero,
+            };
+        }
+
+        static Nat succ(Box<Nat> field0) {
+            return Nat {
+                .tag = Succ,
+                .field0 = field0,
+            };
+        }
+
+        Nat operator+(Nat rhs) {
+            return nat_add(*this, rhs);
+        }
+    };
+
+    Nat nat_one() {
+        return Nat::succ(box_new(Nat::zero()));
+    }
+
+    void nat_drop(Nat self) {
+        if (self.tag == Nat::Succ) {
+            nat_drop(*self.field0.value);
+            box_drop(self.field0);
+        }
+    }
+
+    Nat nat_add(Nat self, Nat rhs) {
+        if (self.tag == Nat::Zero) {
+            nat_drop(self);
+            return rhs;
+        } else {
+            return Nat::succ(box_new(nat_add(*self.field0.value, rhs)));
+        }
+    }
+
+    size_t from_nat(Nat value) {
+        if (value.tag == Nat::Zero) {
+            return 0;
+        } else {
+            return from_nat(*value.field0.value) + 1;
+        }
+    }
+
+    Nat into_nat(size_t value) {
+        if (value == 0) {
+            return Nat::zero();
+        } else {
+            return Nat::succ(box_new(into_nat(value - 1)));
+        }
+    }
+}
+
+namespace bin_tree {
+    template<typename D>
+    struct Node;
+
+    template<typename D>
+    void node_drop(Node<D> self);
+
+    /// Self-Balancing Binary Tree with 0, 1 or 2 children per nodes
+    template<typename D>
+    struct BinTree {
+        enum {
+            Leaf,
+            Left,
+            LeftRight,
+        } tag;
+        Box<Node<D>> left;
+        Box<Node<D>> right;
+
+        static BinTree<D> leaf() {
+            return BinTree<D> {
+                .tag = Leaf,
+            };
+        }
+
+        static BinTree<D> left_(Box<Node<D>> left) {
+            return BinTree<D> {
+                .tag = Left,
+                .left = left,
+            };
+        }
+
+        static BinTree<D> left_right(Box<Node<D>> left, Box<Node<D>> right) {
+            return BinTree<D> {
+                .tag = LeftRight,
+                .left = left,
+                .right = right,
+            };
+        }
+    };
+
+    template<typename D>
+    void bin_tree_drop(BinTree<D> self) {
+        if (self.tag != BinTree<D>::Leaf) {
+            node_drop(*self.left.value);
+            box_drop(self.left);
+        }
+        if (self.tag == BinTree<D>::LeftRight) {
+            node_drop(*self.right.value);
+            box_drop(self.right);
+        }
+    }
+
+    template<typename D>
+    struct Node {
+        D data;
+        BinTree<D> shape;
+
+        static Display<Node<D>> display_impl;
+    };
+
+    template<typename D>
+    void node_fmt(const Node<D> *self, std::string *f) {
+        *f += std::to_string(self->data);
+        *f += ":";
+        if (self->shape.tag == BinTree<D>::Leaf) *f += "()";
+        else if (self->shape.tag == BinTree<D>::Left) {
+            *f += "( ";
+            node_fmt(self->shape.left.value, f);
+            *f += " )";
+        } else if (self->shape.tag == BinTree<D>::LeftRight) {
+            *f += "( ";
+            node_fmt(self->shape.left.value, f);
+            *f += ", ";
+            node_fmt(self->shape.right.value, f);
+            *f += " )";
+        }
+    }
+
+    template<typename D>
+    Display<Node<D>> Node<D>::display_impl = {
+        .fmt = node_fmt<D>,
+    };
+
+    template<typename D>
+    Node<D> node_root(D data) {
+        return Node<D> {
+            .data = data,
+            .shape = BinTree<D>::leaf(),
+        };
+    }
+
+    template<typename D>
+    void node_drop(Node<D> self) {
+        bin_tree_drop(self.shape);
+    }
+
+    template<typename D, typename N>
+    N node_weight(const Node<D> *self) {
+        using namespace peano;
+
+        auto subtree = Nat::zero();
+        if (self->shape.tag != BinTree<D>::Leaf) subtree = into_nat(node_weight<D, N>(self->shape.left.value));
+        if (self->shape.tag == BinTree<D>::LeftRight) subtree = subtree + into_nat(node_weight<D, N>(self->shape.right.value));
+        const auto nat = /*this node*/nat_one() + subtree;
+        return from_nat(nat);
+    }
+
+    template<typename D>
+    Node<D> node_add(Node<D> self, Node<D> rhs) {
+        const auto data = self.data;
+        const auto shape = self.shape;
+
+        BinTree<D> new_shape;
+        if (shape.tag == BinTree<D>::Leaf) new_shape = BinTree<D>::left_(box_new(rhs));
+        else if (shape.tag == BinTree<D>::Left) {
+            new_shape = BinTree<D>::left_right(shape.left, box_new(rhs));
+        } else if (shape.tag == BinTree<D>::LeftRight && node_weight<D, size_t>(shape.left.value) < node_weight<D, size_t>(shape.right.value)) {
+            new_shape = BinTree<D>::left_right(box_new(node_add(*shape.left.value, rhs)), shape.right);
+        } else if (shape.tag == BinTree<D>::LeftRight) {
+            new_shape = BinTree<D>::left_right(shape.left, box_new(node_add(*shape.right.value, rhs)));
+        }
+
+        return Node<D> {
+            .data = data,
+            .shape = new_shape,
+        };
+    }
+}
+
+#include <iostream>
+int main() {
+    {
+        auto iota = iota::iota_new();
+        assert(option_unwrap(iota::iota_next(&iota)) == 0);
+        assert(option_unwrap(iota::iota_next(&iota)) == 1);
+        assert(option_unwrap(iota::iota_next(&iota)) == 2);
+        assert(option_unwrap(iota::iota_next(&iota)) == 3);
+
+        auto peekable_iota = iota::Iota::simple_iterator_impl.peekable(iota);
+        assert(option_unwrap(iota::peekable_peek(&peekable_iota)) == 4);
+        assert(option_unwrap(iota::peekable_peek(&peekable_iota)) == 4);
+        assert(option_unwrap(iota::peekable_peek(&peekable_iota)) == 4);
+
+        assert(option_unwrap(iota::peekable_next(&peekable_iota)) == 4);
+        assert(option_unwrap(iota::peekable_next(&peekable_iota)) == 5);
+        assert(option_unwrap(iota::peekable_next(&peekable_iota)) == 6);
+    }
+
+    auto iota = iota::iota_new();
+    auto b = bin_tree::node_root(option_unwrap(iota::iota_next(&iota)));
+    for (size_t i = 0; i < 100; i++) {
+        const auto new_ = bin_tree::node_root(option_unwrap(iota::iota_next(&iota)));
+        b = bin_tree::node_add(b, new_);
+    }
+
+    std::string f;
+    bin_tree::Node<size_t>::display_impl.fmt(&b, &f);
+    // std::cout << f;
+    assert(f == "0:( 1:( 4:( 10:( 22:( 46:( 94:() ), 62:( 78:() ) ), 30:( 38:( 86:() ), 54:( 70:() ) ) ), 14:( 18:( 42:( 90:() ), 58:( 74:() ) ), 26:( 34:( 82:() ), 50:( 66:(), 98:() ) ) ) ), 6:( 8:( 20:( 44:( 92:() ), 60:( 76:() ) ), 28:( 36:( 84:() ), 52:( 68:(), 100:() ) ) ), 12:( 16:( 40:( 88:() ), 56:( 72:() ) ), 24:( 32:( 80:() ), 48:( 64:(), 96:() ) ) ) ) ), 2:( 3:( 9:( 21:( 45:( 93:() ), 61:( 77:() ) ), 29:( 37:( 85:() ), 53:( 69:() ) ) ), 13:( 17:( 41:( 89:() ), 57:( 73:() ) ), 25:( 33:( 81:() ), 49:( 65:(), 97:() ) ) ) ), 5:( 7:( 19:( 43:( 91:() ), 59:( 75:() ) ), 27:( 35:( 83:() ), 51:( 67:(), 99:() ) ) ), 11:( 15:( 39:( 87:() ), 55:( 71:() ) ), 23:( 31:( 79:() ), 47:( 63:(), 95:() ) ) ) ) ) )");
+
+    bin_tree::node_drop(b);
+    return 0;
+}
diff --git a/challenge.rs b/challenge.rs
@@ -0,0 +1,204 @@
+// iterate on previous program
+mod iota {
+    #[allow(dead_code)]
+    pub trait SimpleIterator {
+        type Item;
+        fn next(&mut self) -> Option<Self::Item>;
+        fn peekable(self) -> Peekable<Self, Self::Item>
+        where
+            Self: Sized,
+        {
+            Peekable {
+                iter: self,
+                peeked: None,
+            }
+        }
+    }
+
+    pub struct Peekable<T, I> {
+        iter: T,
+        peeked: Option<I>,
+    }
+
+    impl<I: Clone, T: SimpleIterator<Item = I>> Peekable<T, I> {
+        #[allow(dead_code)]
+        pub fn peek(&mut self) -> Option<I> {
+            if self.peeked.is_none() {
+                self.peeked = self.iter.next();
+            }
+            self.peeked.clone()
+        }
+    }
+
+    impl<I, T: SimpleIterator<Item = I>> SimpleIterator for Peekable<T, I> {
+        type Item = T::Item;
+        fn next(&mut self) -> Option<T::Item> {
+            match &self.peeked {
+                Some(_) => std::mem::replace(&mut self.peeked, None),
+                None => self.iter.next(),
+            }
+        }
+    }
+
+    pub struct Iota(usize);
+
+    impl Iota {
+        pub fn new() -> Self {
+            Iota(0)
+        }
+    }
+
+    impl SimpleIterator for Iota {
+        type Item = usize;
+        fn next(&mut self) -> Option<usize> {
+            let prev = self.0;
+            self.0 = prev + 1;
+            Some(prev)
+        }
+    }
+}
+
+mod bin_tree {
+    use std::{fmt, ops};
+
+    pub struct Node<D> {
+        pub data: D,
+        shape: BinTree<D>,
+    }
+
+    /// Self-Balancing Binary Tree with 0, 1 or 2 children per nodes
+    enum BinTree<D> {
+        Leaf,
+        Left(Box<Node<D>>),
+        LeftRight {
+            left: Box<Node<D>>,
+            right: Box<Node<D>>,
+        },
+    }
+    use BinTree::*;
+
+    impl<D: fmt::Display> fmt::Display for Node<D> {
+        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+            write!(f, "{}:", self.data)?;
+            match &self.shape {
+                Leaf => write!(f, "()"),
+                Left(left) => write!(f, "( {} )", *left),
+                LeftRight { left, right } => write!(f, "( {}, {} )", *left, *right),
+            }
+        }
+    }
+
+    impl<D> Node<D> {
+        pub fn root(data: D) -> Self {
+            Node {
+                data,
+                shape: BinTree::Leaf,
+            }
+        }
+
+        fn weight<N: super::peano::FromNat + super::peano::IntoNat>(&self) -> N {
+            use super::peano::*;
+
+            let nat = /*this node*/Nat::one() + match &self.shape {
+                Leaf => Nat::Zero,
+                Left(left) => left.weight::<N>().into_nat(),
+                LeftRight { left, right } => left.weight::<N>().into_nat() + right.weight::<N>().into_nat(),
+            };
+            N::from_nat(nat)
+        }
+    }
+
+    impl<D> ops::Add for Node<D> {
+        type Output = Node<D>;
+
+        fn add(self, rhs: Self) -> Self {
+            let Self { data, shape } = self;
+
+            let new_shape = match shape {
+                Leaf => BinTree::Left(Box::new(rhs)),
+                Left(left) => BinTree::LeftRight {
+                    left,
+                    right: Box::new(rhs),
+                },
+                LeftRight { left, right } if left.weight::<usize>() < right.weight::<usize>() => {
+                    LeftRight {
+                        left: Box::new(*left + rhs),
+                        right,
+                    }
+                }
+                LeftRight { left, right } => LeftRight {
+                    left,
+                    right: Box::new(*right + rhs),
+                },
+            };
+
+            Self {
+                data,
+                shape: new_shape,
+            }
+        }
+    }
+}
+
+mod peano {
+    /// Peano Natural Number
+    #[derive(PartialEq)]
+    pub enum Nat {
+        Zero,
+        Succ(Box<Nat>),
+    }
+
+    impl Nat {
+        pub fn one() -> Self {
+            Nat::Succ(Box::new(Nat::Zero))
+        }
+    }
+
+    impl std::ops::Add for Nat {
+        type Output = Nat;
+        fn add(self, rhs: Self) -> Self {
+            match self {
+                Nat::Zero => rhs,
+                Nat::Succ(n) => Nat::Succ(Box::new(*n + rhs)),
+            }
+        }
+    }
+
+    pub trait FromNat: Sized {
+        fn from_nat(value: Nat) -> Self;
+    }
+
+    pub trait IntoNat {
+        fn into_nat(self) -> Nat;
+    }
+
+    impl FromNat for usize {
+        fn from_nat(value: Nat) -> Self {
+            match value {
+                Nat::Zero => 0,
+                Nat::Succ(n) => Self::from_nat(*n) + 1,
+            }
+        }
+    }
+
+    impl IntoNat for usize {
+        fn into_nat(self) -> Nat {
+            match self {
+                0 => Nat::Zero,
+                n => Nat::Succ(Box::new((n - 1).into_nat())),
+            }
+        }
+    }
+}
+
+fn main() {
+    use iota::SimpleIterator as _;
+
+    let mut iota = iota::Iota::new();
+    let mut b = bin_tree::Node::root(iota.next().unwrap());
+    for _ in 0..100 {
+        let new = bin_tree::Node::root(iota.next().unwrap());
+        b = b + new;
+    }
+    assert_eq!(b.to_string(), "0:( 1:( 4:( 10:( 22:( 46:( 94:() ), 62:( 78:() ) ), 30:( 38:( 86:() ), 54:( 70:() ) ) ), 14:( 18:( 42:( 90:() ), 58:( 74:() ) ), 26:( 34:( 82:() ), 50:( 66:(), 98:() ) ) ) ), 6:( 8:( 20:( 44:( 92:() ), 60:( 76:() ) ), 28:( 36:( 84:() ), 52:( 68:(), 100:() ) ) ), 12:( 16:( 40:( 88:() ), 56:( 72:() ) ), 24:( 32:( 80:() ), 48:( 64:(), 96:() ) ) ) ) ), 2:( 3:( 9:( 21:( 45:( 93:() ), 61:( 77:() ) ), 29:( 37:( 85:() ), 53:( 69:() ) ) ), 13:( 17:( 41:( 89:() ), 57:( 73:() ) ), 25:( 33:( 81:() ), 49:( 65:(), 97:() ) ) ) ), 5:( 7:( 19:( 43:( 91:() ), 59:( 75:() ) ), 27:( 35:( 83:() ), 51:( 67:(), 99:() ) ) ), 11:( 15:( 39:( 87:() ), 55:( 71:() ) ), 23:( 31:( 79:() ), 47:( 63:(), 95:() ) ) ) ) ) )");
+}