1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:

use std::rc::Rc;
use std::convert::TryInto;

#[derive(Clone)]
enum Expr {
    Var0, Number(i64),
    UnaryOp(Rc<(char,Expr)>),
    BinaryOp(Rc<(char,Expr,Expr)>)
}
impl std::fmt::Display for Expr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Expr::Number(x) => write!(f,"{}",x),
            Expr::Var0 => write!(f,"n"),
            Expr::UnaryOp(t) => write!(f,"({} {})",t.0,t.1),
            Expr::BinaryOp(t) => write!(f,"({} {} {})",t.0,t.1,t.2)
        }
    }
}

static UNARY_OPS: [char;1] = ['~'];
static BINARY_OPS: [char;4] = ['+','-','*','/'];
static NUMBERS_MIN: i64 = 1;
static NUMBERS_MAX: i64 = 2;

fn gen_expr(depth: u32, callback: &mut dyn FnMut(Expr)) {
    callback(Expr::Var0);
    for x in NUMBERS_MIN..=NUMBERS_MAX {
        callback(Expr::Number(x));
    }
    if depth != 0 {
        gen_expr(depth-1, &mut |x| {
            for op in UNARY_OPS.iter() {
                callback(Expr::UnaryOp(Rc::new((*op,x.clone()))));
            }
        });
        gen_expr(depth-1, &mut |x| {
            gen_expr(depth-1, &mut |y| {
                for op in BINARY_OPS.iter() {
                    let t = (*op,x.clone(),y.clone());
                    callback(Expr::BinaryOp(Rc::new(t)));
                }
            });
        });
    }
}

fn try_div(x: i64, y: i64) -> Option<i64> {
    if x.checked_rem(y)? == 0 {Some(x/y)} else {None}
}

fn evaluate(t: &Expr, n: i64) -> Option<i64> {
    match t {
        Expr::Var0 => Some(n),
        Expr::Number(x) => Some(*x),
        Expr::UnaryOp(t) => match t.0 {
            '~' => evaluate(&t.1,n)?.checked_neg(),
            _ => unreachable!()
        },
        Expr::BinaryOp(t) => {
            let x = evaluate(&t.1,n)?;
            let y = evaluate(&t.2,n)?;
            match t.0 {
                '+' => x.checked_add(y),
                '-' => x.checked_sub(y),
                '*' => x.checked_mul(y),
                '/' => try_div(x,y),
                '^' => x.checked_pow(y.try_into().ok()?),
                _ => unreachable!()
            }
        }
    }
}

fn matches(t: &Expr, a: &[i64]) -> bool {
    for (n,y) in a.iter().enumerate() {
        match evaluate(t, n as i64) {
            None => return false,
            Some(value) => if *y != value {return false;}
        }
    }
    return true;
}

fn filter_by_img(depth: u32, a: &[i64]) {
    let mut buffer: Vec<String> = Vec::new();
    gen_expr(depth, &mut |t| {
        if matches(&t,a) {
            let s = format!("{}",t);
            println!("{}",s);
            buffer.push(s);
        }
    });
    println!("----");
    if let Some(s) = buffer.iter().min_by_key(|s| s.len()) {
        println!("{}",s);
    }
}

fn main() {
    filter_by_img(3,&[1,3,6,10]);
}