🧲

10, 9, 8, ..., 2, 1 の間に＋, −, ×, ÷ や括弧を入れて 2023 にする問題の解法

2023/01/09に公開

問題

ここでは

10 ? 9 ÷ 8 ? 7 ? 6 ? 5 ? 4 ? 3 ? 2 ? 1

に括弧 (, ) を付けて計算の優先順を決め、? に (独立に) 演算子 +, -, ×, ÷ を入れたとき、計算結果が 2023 となる式を列挙します。

計算結果が 2023 となる式は、たとえば

(((10 × 9) ÷ (((8 - 7) ÷ 6) ÷ ((5 ÷ 4) × 3))) - (2 × 1))

があります。計算結果

解法

括弧の付け方を再帰的にすべて試します。

「1段目」の括弧の付け方は次の 9 通りあります。

10 ? (9 ÷ 8 ? 7 ? 6 ? 5 ? 4 ? 3 ? 2 ? 1)

(10 ? 9) ÷ (8 ? 7 ? 6 ? 5 ? 4 ? 3 ? 2 ? 1)

(10 ? 9 ÷ 8) ? (7 ? 6 ? 5 ? 4 ? 3 ? 2 ? 1)

(10 ? 9 ÷ 8 ? 7 ? 6 ? 5 ? 4 ? 3 ? 2) ? 1

たとえば、括弧を

(10 ? 9 ÷ 8 ? 7) ? (6 ? 5 ? 4 ? 3 ? 2 ? 1)

と付けるとします。左側 10 ? 9 ÷ 8 ? 7、右側 6 ? 5 ? 4 ? 3 ? 2 ? 1 は元の問題と同じ構造で、サイズが小さくなっているため再帰的に括弧を付けられます。

Pythonでの実装例

def f(numbers):
    if len(numbers) == 1:
        yield str(numbers[0])

    for i in range(1, len(numbers)):
        for left in f(numbers[:i]):
            for right in f(numbers[i:]):
                for op in "+-*/":
                    yield "({} {} {})".format(left, op, right)


for expr in f([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]):
    print(expr)

# (10 + (9 + (8 + (7 + (6 + (5 + (4 + (3 + (2 + 1)))))))))
# (10 - (9 + (8 + (7 + (6 + (5 + (4 + (3 + (2 + 1)))))))))
# ︙

演算子の入れ方については、9 と 8 の間を「分ける」とき ÷ のみを、それ以外のとき +, -, ×, ÷ を試せばよいです。

なお、括弧の付け方の個数はカタラン数を用いて $C_9$ と書けて、演算子の入れ方は $4^8$ 通りあるので、できあがる式は全部で $C_9 \times 4^8 = 318636032$ 個あります。

実装例

use std::{fmt, rc::Rc, time::Instant};

#[derive(Debug)]
enum Expr {
    Number(u32),
    Infix {
        left: Rc<Expr>,
        op: Op,
        right: Rc<Expr>,
    },
}

#[derive(Clone, Copy, Debug)]
enum Op {
    Add, // +
    Sub, // -
    Mul, // *
    Div, // /
}

impl Expr {
    fn eval(&self) -> f64 {
        match self {
            Expr::Number(x) => *x as f64,
            Expr::Infix { left, op, right } => {
                let l = left.eval();
                let r = right.eval();
                match op {
                    Op::Add => l + r,
                    Op::Sub => l - r,
                    Op::Mul => l * r,
                    Op::Div => l / r,
                }
            }
        }
    }
}

impl fmt::Display for Expr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Expr::Number(x) => write!(f, "{}", x),
            Expr::Infix { left, op, right } => {
                write!(f, "({} {} {})", left, op, right)
            }
        }
    }
}

impl fmt::Display for Op {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Op::Add => write!(f, "+"),
            Op::Sub => write!(f, "-"),
            Op::Mul => write!(f, "*"),
            Op::Div => write!(f, "/"),
        }
    }
}

fn f(numbers: &[u32]) -> Vec<Expr> {
    if numbers.is_empty() {
        return Vec::new();
    }

    if numbers.len() == 1 {
        return vec![Expr::Number(numbers[0])];
    }

    let mut result = Vec::new();
    for i in 1..numbers.len() {
        let left: Vec<_> = f(&numbers[..i]).into_iter().map(Rc::new).collect();
        let right: Vec<_> = f(&numbers[i..]).into_iter().map(Rc::new).collect();
        let ops: &[Op] = if numbers[i - 1] == 9 && numbers[i] == 8 {
            &[Op::Div]
        } else {
            &[Op::Add, Op::Sub, Op::Mul, Op::Div]
        };
        for l in &left {
            for r in &right {
                for &op in ops {
                    result.push(Expr::Infix {
                        left: Rc::clone(l),
                        op,
                        right: Rc::clone(r),
                    });
                }
            }
        }
    }

    result
}

fn main() {
    let now = Instant::now();

    let exprs = f(&[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]);

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

    let mut hit = 0;
    for expr in exprs {
        let y = expr.eval();
        if (y - 2023.0).abs() <= 0.001 {
            println!("{} = {}", expr, y);
            hit += 1;
        }
    }

    println!("hit = {}", hit);
    println!("elapsed = {:?}", now.elapsed());
}

// total = 318636032
// ((10 * (9 / ((8 - 7) / (6 * (5 / (4 / 3)))))) - (2 * 1)) = 2023
// ((10 * (9 / ((8 - 7) / (6 * (5 / (4 / 3)))))) - (2 / 1)) = 2023
// ︙
// hit = 530
// elapsed = 42.8500126s

問題

解法

実装例

Discussion