Zenn
Closed12

僕もコンピュータを使ってでもパズル王に勝ちたい！！

Rust
#
競技プログラミング
tkzwhrtkzwhr

まずはシンプルなmake10を考えてみる。

計算式は下記の5パターンを考えれば良い。

\begin{align*} ((a \diamond b) \diamond c) \diamond d & = 10 \\ (a \diamond (b \diamond c)) \diamond d & = 10 \\ (a \diamond b) \diamond (c \diamond d) & = 10 \\ a \diamond ((b \diamond c) \diamond d) & = 10 \\ a \diamond (b \diamond (c \diamond d)) & = 10 \end{align*}

\diamondには+, -, \times, \divのいずれかが入るので、1つの計算式について4\times4\times4=64通りを試せば良い。

a, b, c, dについては、箱に入った4つの数字を箱に戻さずに取り出すときの組み合わせなので、4\times3\times2\times1=24通りを試せば良い。（a, b, c, dの中で数字が重複する場合もあるため、実際には24通りより少なくなることもある）

ということで、make10を解くために、最大で5\times64\times24=7680通りを試すプログラムを作ってみる。

tkzwhrtkzwhr

括弧による優先順位を考慮するプログラムを作るのは面倒なので、逆ポーランド記法を使って解くことにする。

逆ポーランド記法で書き直した式は下記の通り。

\begin{align*} a \space b \space \diamond c \space \diamond \space d \space \diamond & = 10 \\ a \space b \space c \diamond \space \diamond \space d \space \diamond & = 10 \\ a \space b \space \diamond c \space d \space \diamond \space \diamond & = 10 \\ a \space b \space c \diamond \space \space d \diamond \space \diamond & = 10 \\ a \space b \space c \space d \diamond \space \diamond \space \diamond & = 10 \end{align*}
tkzwhrtkzwhr

ひとまず、標準入力から問題を受け付ける部分を実装する。

use std::io::{self, Write};

fn main() {
    print!("Input your numbers: ");
    io::stdout().flush().unwrap();

    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("input error");

    solve(input);
}

fn solve(input: String) {
    let split_numbers = input.trim().split(" ")
        .map(|x| x.parse::<u8>().expect("not a positive number"))
        .collect::<Vec<_>>();

    let (expect_answer, numbers) = split_numbers.split_last().expect("no enough numbers");

    println!("{:?} = {}", numbers, expect_answer);
}

実行してみる。

Input your numbers: 1 2 3 4 10
[1, 2, 3, 4] = 10
tkzwhrtkzwhr

逆ポーランド記法の計算式を生成する。

fn gen_formulas(numbers: Vec<u8>, patterns: Vec<String>) -> Vec<String> {
    let number_patterns = gen_permutation(&numbers);
    let operator_patterns = gen_operator_patterns(numbers.len() - 1);

    let mut formulas = vec![];

    for pattern in patterns {
        for number_pattern in number_patterns.iter() {
            for operator_pattern in operator_patterns.iter() {
                let mut buf = vec![];
                let mut number_cursor = 0;
                let mut operator_cursor = 0;
                for ch in pattern.chars() {
                    match ch {
                        '0' => {
                            buf.push(format!("{}", number_pattern.iter().nth(number_cursor).unwrap()));
                            number_cursor += 1;
                        },
                        _ => {
                            buf.push(format!("{}", operator_pattern.iter().nth(operator_cursor).unwrap()));
                            operator_cursor += 1;
                        }
                    }
                }
                formulas.push(buf.join(" "));
            }
        }
    }

    formulas
}

fn gen_permutation<T>(arr: &Vec<T>) -> Vec<Vec<&T>> {
    fn inner<'a, T>(arr: Vec<&'a T>, stack: Vec<&'a T>, output: &mut Vec<Vec<&'a T>>) {
        if arr.is_empty() {
            output.push(stack);
        } else {
            for (i, &v) in arr.iter().enumerate() {
                let new_arr = arr.iter()
                    .enumerate()
                    .filter_map(|(j, &w)| if i != j { Some(w) } else { None })
                    .collect();
                let mut new_stack: Vec<&T> = stack.clone();
                new_stack.push(v);
                inner(new_arr, new_stack, output);
            }
        }
    }

    let mut result = vec![];
    inner(arr.iter().collect(), vec![], &mut result);
    result
}

fn gen_operator_patterns(size: usize) -> Vec<Vec<&'static str>> {
    fn inner(size: usize, stack: Vec<&'static str>, output: &mut Vec<Vec<&'static str>>) {
        if stack.len() == size {
            output.push(stack);
        } else {
            inner(size, vec![stack.clone(), vec!["+"]].concat(), output);
            inner(size, vec![stack.clone(), vec!["-"]].concat(), output);
            inner(size, vec![stack.clone(), vec!["*"]].concat(), output);
            inner(size, vec![stack.clone(), vec!["/"]].concat(), output);
        }
    }

    let mut result = vec![];
    inner(size, vec![], &mut result);
    result
}

 fn solve(input: String) {
     let split_numbers = input.trim().split(" ")
         .map(|x| x.parse::<u8>().expect("not a positive number"))
         .collect::<Vec<_>>();
 
     let (expect_answer, numbers) = split_numbers.split_last().expect("no enough numbers");
+
+    let patterns = vec![
+        "00*0*0*".to_string(),
+        "000**0*".to_string(),
+        "00*00**".to_string(),
+        "000*0**".to_string(),
+        "0000***".to_string()
+    ];
+    let formulas = gen_formulas(numbers.to_vec(), patterns);
 
     println!("{:?} = {}", numbers, expect_answer);
+    println!("{}", formulas.join("\n"));
+    println!("{}", formulas.len());
 }

実行してみる。

Input your numbers: 1 2 3 4 10
[1, 2, 3, 4] = 10
1 2 + 3 + 4 +
1 2 + 3 + 4 -
1 2 + 3 + 4 *
1 2 + 3 + 4 /
1 2 + 3 - 4 +

(中略)

4 3 2 1 / * /
4 3 2 1 / / +
4 3 2 1 / / -
4 3 2 1 / / *
4 3 2 1 / / /
7680

できてそう。

tkzwhrtkzwhr

逆ポーランド記法の式を計算するロジックを実装する。

fn calc_rpn(formula: String) -> Option<(f32, String)> {
    fn calc(op: &str, stack: &mut Vec<f32>, formula_stack: &mut Vec<String>) -> bool {
        let v2 = stack.pop().unwrap();
        let f2 = formula_stack.pop().unwrap();
        let v1 = stack.pop().unwrap();
        let f1 = formula_stack.pop().unwrap();

        let result = match op {
            "+" => Some((v1 + v2, format!("({} + {})", f1, f2))),
            "-" => Some((v1 - v2, format!("({} - {})", f1, f2))),
            "*" => Some((v1 * v2, format!("({} * {})", f1, f2))),
            "/" => {
                if v2 == 0.0 {
                    None
                } else {
                    Some((v1 / v2, format!("({} / {})", f1, f2)))
                }
            },
            _   => None
        };

        match result {
            Some((answer, formula)) => {
                stack.push(answer);
                formula_stack.push(formula);
                true
            }
            None => false
        }
    }

    let tokens = formula.split(" ").collect::<Vec<_>>();

    let mut stack: Vec<f32> = vec![];
    let mut formula_stack: Vec<String> = vec![];

    for token in tokens {
        match token {
            "+" | "-" | "*" | "/" => {
                let is_succeeded = calc(token, &mut stack, &mut formula_stack);
                if !is_succeeded {
                    return None;
                }
            },
            _ => {
                let n = token.parse::<f32>().unwrap();
                stack.push(n);
                formula_stack.push(token.to_string());
            }
        }
    }

    Some((stack.pop().unwrap(), formula_stack.pop().unwrap()))
}

 fn solve(input: String) {
     let split_numbers = input.trim().split(" ")
         .map(|x| x.parse::<u8>().expect("not a positive number"))
         .collect::<Vec<_>>();
 
     let (expect_answer, numbers) = split_numbers.split_last().expect("no enough numbers");
 
    let patterns = vec![
        "00*0*0*".to_string(),
        "000**0*".to_string(),
        "00*00**".to_string(),
        "000*0**".to_string(),
        "0000***".to_string()
    ];
     let formulas = gen_formulas(numbers.to_vec(), patterns);
 
-    println!("{:?} = {}", numbers, expect_answer);
-    println!("{}", formulas.join("\n"));
-    println!("{}", formulas.len());
+    for formula in formulas {
+        match calc_rpn(formula) {
+            Some((answer, infix_formula)) => {
+                if answer == *expect_answer as f32 {
+                    println!("{} = {}", infix_formula, expect_answer);
+                    break;
+                }
+            }
+            None => {}
+        }
+    }
 }

ここまでで動画の問題を解けるだけ解いてみる。

Input your numbers: 2 5 5 9 13
(((9 - 5) * 2) + 5) = 13

Input your numbers: 4 8 8 9 23
(((8 - 4) * 8) - 9) = 23

Input your numbers: 3 5 8 9 24
(((3 * 9) + 5) - 8) = 24

Input your numbers: 1 3 5 7 19
(((1 + 7) * 3) - 5) = 19

できてそう。

tkzwhrtkzwhr

数値が4つではないパターンを考えてみる。

数値が2つのときのRPNパターンは下記の通り。

  • 1 1 +

数値が3つのときのパターンは下記の通り。

  • 1 1 1 + +
  • 1 1 + 1 +

数値が4つのときのパターンは下記の通り。

  • 1 1 1 1 + + +
  • 1 1 1 + 1 + +
  • 1 1 1 + + 1 +
  • 1 1 + 1 + 1 +
  • 1 1 + 1 1 + +
  • 1 1 + + 1 1 +

ただし、最後の行は途中でスタックが0になってしまうので、RPNとしては無効である。

以上を踏まえると、下記の通りパターンを生成すれば良さそうである。

  • 最初の2つは必ず数値になる
  • 最後は必ず記号になる
  • N個の数字では、間に入る数値と記号はそれぞれN-2個である
  • 途中でスタックが0になってしまうRPNは除外する
tkzwhrtkzwhr

計算式パターンを洗い出す処理を実装する。

fn gen_patterns(n: usize) -> Vec<String> {
    let mid = (0..n-2).map(|_| vec!["0", "*"]).collect::<Vec<Vec<&str>>>().concat();
    let patterns = gen_permutation(&mid)
        .into_iter()
        .map(|x| {
            let mid = x.into_iter().map(|y| *y).collect::<Vec<_>>();
            format!("00{}*", mid.join(""))
        })
        .collect::<Vec<_>>();
    let patterns: HashSet<String> = patterns.into_iter().collect();
    patterns.into_iter()
        .filter(|x| {
            let mut stack_cursor = 0;
            for ch in x.chars() {
                match ch {
                    '0' => stack_cursor += 1,
                    _ => {
                        stack_cursor -= 1;
                        if stack_cursor == 0 {
                            return false;
                        }
                    }
                }
            }
            true
        })
        .collect()
}

 fn solve(input: String) {
     let split_numbers = input.trim().split(" ")
         .map(|x| x.parse::<u8>().expect("not a positive number"))
         .collect::<Vec<_>>();

     let (expect_answer, numbers) = split_numbers.split_last().expect("no enough numbers");

-    let patterns = vec![
-        "00*0*0*".to_string(),
-        "000**0*".to_string(),
-        "00*00**".to_string(),
-        "000*0**".to_string(),
-        "0000***".to_string()
-    ];
+    let patterns = gen_patterns(numbers.len());
     let formulas = gen_formulas(numbers.to_vec(), patterns);

     for formula in formulas {
         match calc_rpn(formula) {
             Some((answer, infix_formula)) => {
                 if answer == *expect_answer as f32 {
                     println!("{} = {}", infix_formula, expect_answer);
                     break;
                 }
             }
             None => {}
         }
     }
 }

実行してみる。

Input your numbers: 1 2 2 6 7 9 16

結果が表示されなくなってしまった😇

tkzwhrtkzwhr

デバッグコードを仕込んでみる。

     let patterns = gen_patterns(numbers.len());
+    println!("number of patterns: {}", patterns.len());
     let formulas = gen_formulas(numbers.to_vec(), patterns);
+    println!("number of formulas: {}", formulas.len());

Input your numbers: 1 2 3 4 10
number of patterns: 5
number of formulas: 7680
((1 + 2) + (3 + 4)) = 10

Input your numbers: 1 2 3 4 5 15
number of patterns: 14
number of formulas: 430080

(1 + (2 + ((3 + 4) + 5))) = 15
Input your numbers: 1 2 3 4 5 6 21
number of patterns: 42

事前に生成するパターンが指数的に増えるため、生成処理に時間がかかっているっぽい。

tkzwhrtkzwhr

gen_formulas を、クロージャを受け取るように変更し、随時判定するようにしてみる。

fn gen_formulas<F>(numbers: Vec<u8>, patterns: Vec<String>, mut f: F) where F: FnMut(String) -> bool {
    let number_patterns = gen_permutation(&numbers);
    let operator_patterns = gen_operator_patterns(numbers.len() - 1);

    for pattern in patterns {
        for number_pattern in number_patterns.iter() {
            for operator_pattern in operator_patterns.iter() {
                let mut buf = vec![];
                let mut number_cursor = 0;
                let mut operator_cursor = 0;
                for ch in pattern.chars() {
                    match ch {
                        '0' => {
                            buf.push(format!("{}", number_pattern.iter().nth(number_cursor).unwrap()));
                            number_cursor += 1;
                        },
                        _ => {
                            buf.push(format!("{}", operator_pattern.iter().nth(operator_cursor).unwrap()));
                            operator_cursor += 1;
                        }
                    }
                }
                if !f(buf.join(" ")) {
                    return;
                }
            }
        }
    }
}

fn solve(input: String) {
    let split_numbers = input.trim().split(" ")
        .map(|x| x.parse::<u8>().expect("not a positive number"))
        .collect::<Vec<_>>();

    let (expect_answer, numbers) = split_numbers.split_last().expect("no enough numbers");

    let patterns = gen_patterns(numbers.len());
    gen_formulas(numbers.to_vec(), patterns, |formula| {
        match calc_rpn(formula) {
            Some((answer, infix_formula)) => {
                if answer == *expect_answer as f32 {
                    println!("{} = {}", infix_formula, answer);
                    return false;
                }
            }
            None => {}
        }

        true
    });
}

再度実行してみる。

Input your numbers: 1 2 2 6 7 9 16
(1 * ((2 + 2) * ((6 + 7) - 9))) = 16

解けた。

（福良さんとは違う式が出てきているが、数が増えるほど別解が発生しやすくなるので仕方がない）

tkzwhrtkzwhr

動画に出てきた残りの問題についても解いていく。

Input your numbers: 1 2 2 6 7 9 16
(1 * ((2 + 2) * ((6 + 7) - 9))) = 16
Input your numbers: 1 2 3 3 3 9 13
(1 - (2 * (((3 + 3) - 3) - 9))) = 13
Input your numbers: 1 4 5 6 6 6 9
((1 - 4) + (5 + ((6 / 6) + 6))) = 9
Input your numbers: 1 5 6 7 13
(1 - (6 * (5 - 7))) = 13
Input your numbers: 1 2 3 6 6 24
(1 * ((2 / 3) * (6 * 6))) = 24
Input your numbers: 2 3 4 4 19
(3 + ((4 + 4) * 2)) = 19
Input your numbers: 2 4 7 9 9 14
((2 + (4 * (9 - 9))) * 7) = 14
Input your numbers: 3 4 7 8 8 9 8
((3 + 4) - ((7 - (8 + 8)) / 9)) = 8
Input your numbers: 1 3 4 6 8
(((1 - 3) + 4) + 6) = 8
Input your numbers: 1 3 4 6 9
(1 + ((4 / 3) * 6)) = 9
Input your numbers: 2 3 9 9 14
(2 + ((9 / 3) + 9)) = 14
Input your numbers: 1 3 4 4 5 22
(((1 + (3 * 4)) + 4) + 5) = 22
Input your numbers: 1 4 6 6 8
(((1 * 6) - 4) + 6) = 8
Input your numbers: 1 1 4 6 6 8 17
(1 * ((1 - 4) + ((6 + 6) + 8))) = 17
Input your numbers: 4 4 5 7 8 16
((4 - (4 + (5 - 7))) * 8) = 16
Input your numbers: 3 3 4 7 25
(3 * (7 + (4 / 3))) = 25
Input your numbers: 2 2 6 8 9 17
((2 * (2 + 6)) - (8 - 9)) = 17
Input your numbers: 1 8 9 9 16
(8 * (1 + (9 / 9))) = 16
Input your numbers: 2 5 5 6 6 8 15
(2 - (5 - (6 * ((5 + 6) - 8)))) = 15
Input your numbers: 2 2 3 6 8 12
(2 * (((3 / 2) * 8) - 6)) = 12
Input your numbers: 6 6 7 8 9 22
((6 + (6 - 7)) + (8 + 9)) = 22
Input your numbers: 1 6 8 8 18
((1 + 8) * (8 - 6)) = 18

鶴崎さんが止まった26問目も解けたので、ここまでにする。

tkzwhrtkzwhr
ソースコード
use std::collections::HashSet;
use std::io::{self, Write};

fn main() {
    print!("Input your numbers: ");
    io::stdout().flush().unwrap();

    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("input error");

    solve(input);
}

fn solve(input: String) {
    let split_numbers = input.trim().split(" ")
        .map(|x| x.parse::<u8>().expect("not a positive number"))
        .collect::<Vec<_>>();

    let (expect_answer, numbers) = split_numbers.split_last().expect("no enough numbers");

    let patterns = gen_patterns(numbers.len());
    gen_formulas(numbers.to_vec(), patterns, |formula| {
        match calc_rpn(formula) {
            Some((answer, infix_formula)) => {
                if answer == *expect_answer as f32 {
                    println!("{} = {}", infix_formula, answer);
                    return false;
                }
            }
            None => {}
        }

        true
    });
}

fn gen_formulas<F>(numbers: Vec<u8>, patterns: Vec<String>, mut f: F) where F: FnMut(String) -> bool {
    let number_patterns = gen_permutation(&numbers);
    let operator_patterns = gen_operator_patterns(numbers.len() - 1);

    for pattern in patterns {
        for number_pattern in number_patterns.iter() {
            for operator_pattern in operator_patterns.iter() {
                let mut buf = vec![];
                let mut number_cursor = 0;
                let mut operator_cursor = 0;
                for ch in pattern.chars() {
                    match ch {
                        '0' => {
                            buf.push(format!("{}", number_pattern.iter().nth(number_cursor).unwrap()));
                            number_cursor += 1;
                        },
                        _ => {
                            buf.push(format!("{}", operator_pattern.iter().nth(operator_cursor).unwrap()));
                            operator_cursor += 1;
                        }
                    }
                }
                if !f(buf.join(" ")) {
                    return;
                }
            }
        }
    }
}

fn gen_permutation<T>(arr: &Vec<T>) -> Vec<Vec<&T>> {
    fn inner<'a, T>(arr: Vec<&'a T>, stack: Vec<&'a T>, output: &mut Vec<Vec<&'a T>>) {
        if arr.is_empty() {
            output.push(stack);
        } else {
            for (i, &v) in arr.iter().enumerate() {
                let new_arr = arr.iter()
                    .enumerate()
                    .filter_map(|(j, &w)| if i != j { Some(w) } else { None })
                    .collect();
                let mut new_stack: Vec<&T> = stack.clone();
                new_stack.push(v);
                inner(new_arr, new_stack, output);
            }
        }
    }

    let mut result = vec![];
    inner(arr.iter().collect(), vec![], &mut result);
    result
}

fn gen_operator_patterns(size: usize) -> Vec<Vec<&'static str>> {
    fn inner(size: usize, stack: Vec<&'static str>, output: &mut Vec<Vec<&'static str>>) {
        if stack.len() == size {
            output.push(stack);
        } else {
            inner(size, vec![stack.clone(), vec!["+"]].concat(), output);
            inner(size, vec![stack.clone(), vec!["-"]].concat(), output);
            inner(size, vec![stack.clone(), vec!["*"]].concat(), output);
            inner(size, vec![stack.clone(), vec!["/"]].concat(), output);
        }
    }

    let mut result = vec![];
    inner(size, vec![], &mut result);
    result
}

fn gen_patterns(n: usize) -> Vec<String> {
    let mid = (0..n-2).map(|_| vec!["0", "*"]).collect::<Vec<Vec<&str>>>().concat();
    let patterns = gen_permutation(&mid)
        .into_iter()
        .map(|x| {
            let mid = x.into_iter().map(|y| *y).collect::<Vec<_>>();
            format!("00{}*", mid.join(""))
        })
        .collect::<Vec<_>>();
    let patterns: HashSet<String> = patterns.into_iter().collect();
    patterns.into_iter()
        .filter(|x| {
            let mut stack_cursor = 0;
            for ch in x.chars() {
                match ch {
                    '0' => stack_cursor += 1,
                    _ => {
                        stack_cursor -= 1;
                        if stack_cursor == 0 {
                            return false;
                        }
                    }
                }
            }
            true
        })
        .collect()
}

fn calc_rpn(formula: String) -> Option<(f32, String)> {
    fn calc(op: &str, stack: &mut Vec<f32>, formula_stack: &mut Vec<String>) -> bool {
        let v2 = stack.pop().unwrap();
        let f2 = formula_stack.pop().unwrap();
        let v1 = stack.pop().unwrap();
        let f1 = formula_stack.pop().unwrap();

        let result = match op {
            "+" => Some((v1 + v2, format!("({} + {})", f1, f2))),
            "-" => Some((v1 - v2, format!("({} - {})", f1, f2))),
            "*" => Some((v1 * v2, format!("({} * {})", f1, f2))),
            "/" => {
                if v2 == 0.0 {
                    None
                } else {
                    Some((v1 / v2, format!("({} / {})", f1, f2)))
                }
            },
            _   => None
        };

        match result {
            Some((answer, formula)) => {
                stack.push(answer);
                formula_stack.push(formula);
                true
            }
            None => false
        }
    }

    let tokens = formula.split(" ").collect::<Vec<_>>();

    let mut stack: Vec<f32> = vec![];
    let mut formula_stack: Vec<String> = vec![];

    for token in tokens {
        match token {
            "+" | "-" | "*" | "/" => {
                let is_succeeded = calc(token, &mut stack, &mut formula_stack);
                if !is_succeeded {
                    return None;
                }
            },
            _ => {
                let n = token.parse::<f32>().unwrap();
                stack.push(n);
                formula_stack.push(token.to_string());
            }
        }
    }

    Some((stack.pop().unwrap(), formula_stack.pop().unwrap()))
}

結論

限られた時間で作り上げる鶴崎さんもすごいし、脳内でこれをやってしまう福良さんもすごい。

このスクラップは2023/10/16にクローズされました