Solver written in Rust to solve https://twitter.com/tkihira/status/1609313732034965506

2023puzzle.rs

use std::collections::{HashMap, HashSet};

const M: u64 = 1_000_000_007;

fn main() {
    const N: usize = 10;
    let array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
    let mut dp: [[HashSet<u64>; N + 1]; N + 1] = Default::default();
    let mut path = HashMap::new();
    for l in 1..=N {
        for i in 0..=N - l {
            let j = i + l;
            if l == 1 {
                dp[i][j].insert(array[i]);
                continue;
            }
            let mut s = HashSet::new();
            for k in i + 1..j {
                for a in &dp[i][k] {
                    for b in &dp[k][j] {
                        if k != 2 {
                            let add = add(a, b);
                            let sub = sub(a, b);
                            let mul = mul(a, b);
                            s.insert(add);
                            path.insert((i, j, add), (k, *a, *b, '+'));
                            s.insert(sub);
                            path.insert((i, j, sub), (k, *a, *b, '-'));
                            s.insert(mul);
                            path.insert((i, j, mul), (k, *a, *b, '*'));
                        }
                        if *b != 0 {
                            let div = div(a, b);
                            s.insert(div);
                            path.insert((i, j, div), (k, *a, *b, '/'));
                        }
                    }
                }
            }
            dp[i][j].extend(&s);
        }
    }
    let t = 2023;
    let found = dp[0][N].contains(&t);
    println!("{t} exists?: {}", found);
    if found {
        println!("Backgracking {t}");
        backtrack(&path, 0, N, t);
    }
}

fn add(a: &u64, b: &u64) -> u64 {
    (a + b) % M
}

fn sub(a: &u64, b: &u64) -> u64 {
    if a < b {
        a + M - b
    } else {
        a - b
    }
}

fn mul(a: &u64, b: &u64) -> u64 {
    a * b % M
}

fn pow(a: &u64, x: u64, m: &u64) -> u64 {
    if x == 0 {
        return 1;
    }
    if x % 2 == 0 {
        let y = pow(a, x / 2, m);
        y * y % m
    } else {
        pow(a, x - 1, m) * a % m
    }
}

fn div(a: &u64, b: &u64) -> u64 {
    a * pow(b, M - 2, &M) % M
}

fn backtrack(
    path: &HashMap<(usize, usize, u64), (usize, u64, u64, char)>,
    start: usize,
    end: usize,
    target: u64,
) {
    if end - start <= 1 {
        return;
    }
    let (k, a, b, op) = path.get(&(start, end, target)).unwrap();
    println!("{a} for [{start}, {k}], {b} for [{k}, {end}]: {}", op);
    backtrack(path, start, *k, *a);
    backtrack(path, *k, end, *b);
}