choose expression search

main.rs

use indexmap::IndexMap;
use rand::{rngs::ThreadRng, seq::SliceRandom, thread_rng};

/// Represented as a number from 0 to 2
type Var = u8;

/// A choose function Var -> Var -> Var is represented by a 3x3 lookup table
type Func = [[Var; 3]; 3];

fn main()
{
	let funcs = generate_funcs();

	let mut exprs: IndexMap<u128, String> = IndexMap::new();
	exprs.insert(leaf_sig(0), "a".to_string());
	exprs.insert(leaf_sig(1), "b".to_string());
	exprs.insert(leaf_sig(2), "c".to_string());
	// let mut exprs: IndexMap<u128, ()> = IndexMap::new();
	// exprs.insert(leaf_sig(0), ());
	// exprs.insert(leaf_sig(1), ());
	// exprs.insert(leaf_sig(2), ());

	for _ in 1..=3
	{
		let exprs_clone = exprs.clone();
		for (l_sig, l_expr) in &exprs_clone
		{
			for (r_sig, r_expr) in &exprs_clone
			{
				let sig = node_sig(&l_sig, &r_sig, &funcs);
				let expr = format!("<{}{}>", l_expr, r_expr);
				let result = exprs.get(&sig);
				match result
				{
					Some(existing) =>
					{
						if expr != *existing
						{
							println!("{} = {}", expr, existing);
						}
					}
					None =>
					{
						println!("{}", expr);
						exprs.insert(sig, expr);
						// exprs.insert(sig, ());
					}
				}
			}
			//println!("{}", exprs.len());
		}
	}

	let counted = exprs.len();
	println!("{}", counted);

	// Monte carlo
	let exprs_vec: Vec<u128> = exprs.keys().cloned().collect();

	let mut rng = thread_rng();
	let mut count = 0;
	let mut total = 0;
	for _ in 0..100000
	{
		let sig = generate_rand_with_depth(&exprs_vec, 6, &mut rng, &funcs);
		if exprs.contains_key(&sig)
		{
			count += 1;
		}
		total += 1;
	}
	println!("{} / {}", count, total);
	println!("Est. {}", counted * total / count);
}

/// Generate a random expression with a given depth beyond the supplied set of expressions
fn generate_rand_with_depth(exprs_vec: &Vec<u128>, depth: u8, rng: &mut ThreadRng, funcs: &[Func; 64]) -> u128
{
	if depth == 0
	{
		return *exprs_vec.choose(rng).unwrap();
	}
	let l = generate_rand_with_depth(exprs_vec, depth - 1, rng, funcs);
	let r = generate_rand_with_depth(exprs_vec, depth - 1, rng, funcs);
	node_sig(&l, &r, &funcs)
}

/// Generate all possible choose functions
fn generate_funcs() -> [Func; 64]
{
	let mut funcs = [[[0; 3]; 3]; 64];
	for i in 0..64
	{
		let mut code = i;
		funcs[i] = [[0; 3]; 3];
		for l in 0..3
		{
			for r in 0..3
			{
				if l == r
				{
					funcs[i][l as usize][r as usize] = l;
				}
				else
				{
					funcs[i][l as usize][r as usize] = if code & 1 == 0 { l } else { r };
					code >>= 1;
				}
			}
		}
	}
	funcs
}

/// Compute the signature of a leaf expression
fn leaf_sig(a: Var) -> u128
{
	let mut sig = 0;
	for i in 0..64
	{
		sig |= (a as u128) << (i * 2);
	}
	sig
}

/// Compute the signature of a node expression
fn node_sig(l: &u128, r: &u128, funcs: &[Func; 64]) -> u128
{
	let mut sig = 0;
	for i in 0..64
	{
		let l_var = (l >> (i * 2)) & 3;
		let r_var = (r >> (i * 2)) & 3;
		let func = funcs[i as usize];
		let result = func[l_var as usize][r_var as usize];
		sig |= (result as u128) << (i * 2);
	}
	sig
}