Countdown

.gitignore

/target

Cargo.lock

# This file is automatically @generated by Cargo.
# It is not intended for manual editing.
[[package]]
name = "cfg-if"
version = "0.1.10"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822"

[[package]]
name = "countdown"
version = "0.1.0"
dependencies = [
 "itertools",
 "rand",
]

[[package]]
name = "either"
version = "1.5.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "bb1f6b1ce1c140482ea30ddd3335fc0024ac7ee112895426e0a629a6c20adfe3"

[[package]]
name = "getrandom"
version = "0.1.14"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "7abc8dd8451921606d809ba32e95b6111925cd2906060d2dcc29c070220503eb"
dependencies = [
 "cfg-if",
 "libc",
 "wasi",
]

[[package]]
name = "itertools"
version = "0.9.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "284f18f85651fe11e8a991b2adb42cb078325c996ed026d994719efcfca1d54b"
dependencies = [
 "either",
]

[[package]]
name = "libc"
version = "0.2.70"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "3baa92041a6fec78c687fa0cc2b3fae8884f743d672cf551bed1d6dac6988d0f"

[[package]]
name = "ppv-lite86"
version = "0.2.8"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "237a5ed80e274dbc66f86bd59c1e25edc039660be53194b5fe0a482e0f2612ea"

[[package]]
name = "rand"
version = "0.7.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "6a6b1679d49b24bbfe0c803429aa1874472f50d9b363131f0e89fc356b544d03"
dependencies = [
 "getrandom",
 "libc",
 "rand_chacha",
 "rand_core",
 "rand_hc",
]

[[package]]
name = "rand_chacha"
version = "0.2.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f4c8ed856279c9737206bf725bf36935d8666ead7aa69b52be55af369d193402"
dependencies = [
 "ppv-lite86",
 "rand_core",
]

[[package]]
name = "rand_core"
version = "0.5.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19"
dependencies = [
 "getrandom",
]

[[package]]
name = "rand_hc"
version = "0.2.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ca3129af7b92a17112d59ad498c6f81eaf463253766b90396d39ea7a39d6613c"
dependencies = [
 "rand_core",
]

[[package]]
name = "wasi"
version = "0.9.0+wasi-snapshot-preview1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "cccddf32554fecc6acb585f82a32a72e28b48f8c4c1883ddfeeeaa96f7d8e519"

Cargo.toml

[package]
name = "countdown"
version = "0.1.0"
authors = ["Surma <[email protected]>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
rand = "0.7.3"
itertools = "0.9.0"

[[bin]]
name = "countdown"
path = "main.rs"

main.rs

use std::collections::HashMap;
use std::string::ToString;

use itertools::Itertools;
use rand::prelude::*;

#[derive(Clone, Debug)]
enum Op {
    Plus,
    Minus,
    Mul,
    Div,
}

impl ToString for Op {
    fn to_string(&self) -> String {
        match self {
            Op::Plus => "+".to_string(),
            Op::Minus => "-".to_string(),
            Op::Mul => "*".to_string(),
            Op::Div => "/".to_string(),
        }
    }
}

#[derive(Clone, Debug)]
enum Expr {
    Number(isize),
    Expr(Op, Box<Expr>, Box<Expr>),
}

impl ToString for Expr {
    fn to_string(&self) -> String {
        match self {
            Expr::Number(v) => format!("{}", v),
            Expr::Expr(op, left, right) => format!(
                "({}{}{})",
                left.to_string(),
                op.to_string(),
                right.to_string()
            ),
        }
    }
}

fn all_possible_values_in_order(numbers: &[isize]) -> HashMap<isize, Expr> {
    let mut result = HashMap::new();
    if numbers.len() == 1 {
        let number = numbers[0];
        result.insert(number, Expr::Number(number));
        return result;
    }

    for i in 1..numbers.len() {
        let (left, right) = numbers.split_at(i);
        let left_values = all_possible_values_in_order(left);
        let right_values = all_possible_values_in_order(right);
        for (left_value, left_expr) in &left_values {
            for (right_value, right_expr) in &right_values {
                result.insert(
                    left_value + right_value,
                    Expr::Expr(
                        Op::Plus,
                        left_expr.clone().into(),
                        right_expr.clone().into(),
                    ),
                );
                result.insert(
                    left_value - right_value,
                    Expr::Expr(
                        Op::Minus,
                        left_expr.clone().into(),
                        right_expr.clone().into(),
                    ),
                );
                result.insert(
                    left_value * right_value,
                    Expr::Expr(Op::Mul, left_expr.clone().into(), right_expr.clone().into()),
                );
                if *right_value != 0 && left_value % right_value == 0 {
                    result.insert(
                        left_value / right_value,
                        Expr::Expr(Op::Div, left_expr.clone().into(), right_expr.clone().into()),
                    );
                }
            }
        }
    }
    result
}

fn all_possible_values(numbers: &[isize]) -> HashMap<isize, Expr> {
    let mut result = HashMap::new();
    for permutation in numbers.iter().copied().permutations(numbers.len()) {
        let values = all_possible_values_in_order(&permutation);
        for (value, expr) in &values {
            result.insert(*value, expr.clone());
        }
    }
    result
}

fn main() {
    let mut rng = thread_rng();
    let numbers = vec![6, 9, 25, 50, 75, 100];
    let goal: isize = rng.gen_range(101, 990);
    println!("Number: {:?}", numbers);
    println!("Goal: {}", goal);
    let values = all_possible_values(&numbers);
    if values.contains_key(&goal) {
        println!("Solved: {}", values.get(&goal).unwrap().to_string());
    } else {
        println!("Impossible");
    }
}