Skip to content

Instantly share code, notes, and snippets.

@InfiniteCoder01

InfiniteCoder01/challenge.cpp

Created August 15, 2025 14:55
Show Gist options
  • Save InfiniteCoder01/f979d2e11ad255af36c55f54eff24186 to your computer and use it in GitHub Desktop.
Save InfiniteCoder01/f979d2e11ad255af36c55f54eff24186 to your computer and use it in GitHub Desktop.
Download ZIP
A new and HARDER challenge from Nigel for converting Rust to C/C++
Raw
challenge.cpp
#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;
}
Raw
challenge.rs
// 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:() ) ) ) ) ) )");
}
@nigelwithrow
Copy link

nigelwithrow commented Aug 17, 2025

I approve

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment