リスト : 九九表
fn ninety_nine() {
println!(" | 1 2 3 4 5 6 7 8 9");
println!("--+---------------------------");
for x in 1..10 {
print!("{} | ", x);
for y in 1..10 {
print!("{:>2} ", x * y)
}
println!("");
}
println!("");
}
fn main() {
ninety_nine();
}
| 1 2 3 4 5 6 7 8 9 --+--------------------------- 1 | 1 2 3 4 5 6 7 8 9 2 | 2 4 6 8 10 12 14 16 18 3 | 3 6 9 12 15 18 21 24 27 4 | 4 8 12 16 20 24 28 32 36 5 | 5 10 15 20 25 30 35 40 45 6 | 6 12 18 24 30 36 42 48 54 7 | 7 14 21 28 35 42 49 56 63 8 | 8 16 24 32 40 48 56 64 72 9 | 9 18 27 36 45 54 63 72 81
リスト : 平均値と標準偏差
// 乱数で生成した身長のデータ
const HEIGHT: [f64; 100] = [
148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3
];
// 合計値を求める
fn sum(data: &[f64]) -> f64 {
let mut acc: f64 = 0.0;
for i in 0 .. data.len() {
acc += data[i];
}
acc
}
// 平均値を求める
fn avg(data: &[f64]) -> f64 {
sum(data) / data.len() as f64
}
// 標準偏差を求める
fn sd(data: &[f64]) -> f64 {
let m = avg(data);
let mut s = 0.0;
for i in 0 .. data.len() {
let x = data[i];
s += (x - m) * (x - m);
}
(s / data.len() as f64).sqrt()
}
fn main() {
println!("{}", sum(&HEIGHT));
println!("{}", avg(&HEIGHT));
println!("{}", sd(&HEIGHT));
}
15062.699999999997 150.62699999999998 6.433472701426501
リスト : パスカルの三角形
// 二次元配列版
fn pascal() {
const N: usize = 16; // 配列の大きさは定数でなければいけない (型は usize)
// ブロックで定義された const はブロックの中だけ有効
let mut table = [[1; N]; N]; // 二次元配列 (1 で初期化)
for i in 2 .. N {
for j in 1 .. i {
table[i][j] = table[i - 1][j - 1] + table[i - 1][j];
}
}
for i in 0 .. N {
for j in 0 .. i + 1 {
print!("{} ", table[i][j]);
}
println!("");
}
}
// 一次元配列版
fn pascal1() {
const N: usize = 20;
let mut table = [1; N];
println!("{}", table[0]);
println!("{} {}", table[0], table[1]);
for i in 2 .. N {
let mut j = i - 1;
while j > 0 {
table[j] += table[j - 1];
j -= 1;
}
// 表示
for k in 0 .. i + 1 {
print!("{} ", table[k]);
}
println!("");
}
}
fn main() {
pascal();
pascal1();
}
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1
リスト : 素数 (単純版)
// 素数のチェック
fn is_prime(x: i32, ps: &Vec<i32>) -> bool {
for p in ps {
if p * p > x { break; }
if x % p == 0 { return false; }
}
true
}
fn prime(n: i32) {
let mut ps = vec![2];
let mut x = 3;
while x <= n {
if is_prime(x, &ps) {
ps.push(x);
}
x += 2;
}
println!("{:?}", ps);
}
fn main() {
prime(100);
prime(500);
}
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]
リスト : 素因数分解
fn factorization(n: i32) {
fn factor_sub(n: i32, m: i32) -> (i32, i32) {
let mut c = 0;
let mut x = n;
while x % m == 0 {
c += 1;
x /= m;
}
(c, x)
}
let (c, n) = factor_sub(n, 2);
if c > 0 { print!("({},{})", 2, c); }
let mut x = 3;
let mut m = n;
while x * x <= m {
let (c, n) = factor_sub(m, x);
if c > 0 { print!("({},{})", x, c); }
m = n;
x += 2;
}
if m > 1 { print!("({},{})", m, 1); }
println!("");
}
fn main() {
factorization(24);
factorization(12345678);
factorization(123456789);
factorization(1234567890);
factorization(1111111111);
}
(2,3)(3,1) (2,1)(3,2)(47,1)(14593,1) (3,2)(3607,1)(3803,1) (2,1)(3,2)(5,1)(3607,1)(3803,1) (11,1)(41,1)(271,1)(9091,1)
リスト : ユークリッドの互除法
// 最大公約数 (あえて match を使ってみる)
fn gcd(a: i32, b: i32) -> i32 {
match b {
0 => a,
_ => gcd(b, a % b)
}
}
// 最小公倍数
fn lcm(a: i32, b: i32) -> i32 {
a * b / gcd(a, b)
}
fn main() {
println!("{}", gcd(42, 30));
println!("{}", gcd(15, 70));
println!("{}", lcm(5, 7));
println!("{}", lcm(14, 35));
}
6 5 35 70
累乗のアルゴリズムについては、拙作のページ「Algorithms with Python: 再帰定義」をお読みください。
リスト : 累乗
// 再帰呼び出し
fn power(n: f64, m: i32) -> f64 {
match m {
0 => 1.0,
1 => n,
_ => {
let x = power(n, m / 2);
if m % 2 == 0 {
x * x
} else {
x * x * n
}
}
}
}
fn main() {
for i in 0..10 {
println!("{}", power(2.0, i));
}
}
1 2 4 8 16 32 64 128 256 512
組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Rust の整数 (i32 や i64 など) は多倍長整数ではないので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗やフィボナッチ関数と同じように、再帰定義を使って簡単にプログラムできます。
リスト : 組み合わせの数
fn comb(n: i64, r: i64) -> i64 {
// if のほうが簡単だが、あえて match を使ってみる
match (n, r) {
(0, _) | (_, 0) => 1,
_ => comb(n, r - 1) * (n - r + 1) / r
}
}
fn main() {
println!("{}", comb(5, 3));
println!("{}", comb(20, 10));
println!("{}", comb(30, 15));
}
10 184756 155117520
もちろん、この方法でも大きな組み合わせの数を求めようとすると桁あふれします。ご注意くださいませ。
リスト : 順列の生成
// 1 から n までの数字から m 個を選ぶ
fn permutations(n: i32, m: i32, func: fn(&Vec<i32>) -> ()) {
fn perm(n: i32, m: i32, func: fn(&Vec<i32>) -> (), xs: &mut Vec<i32>) {
if m == 0 {
func(xs);
} else {
for x in 1 .. n + 1 {
if !xs.contains(&x) {
xs.push(x);
perm(n, m - 1, func, xs);
xs.pop();
}
}
}
}
perm(n, m, func, &mut vec![]);
}
// ベクタの表示
fn print_vector(xs: &Vec<i32>) {
println!("{:?}", xs);
}
fn main() {
permutations(4, 4, print_vector);
}
[1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] [1, 4, 3, 2] [2, 1, 3, 4] [2, 1, 4, 3] [2, 3, 1, 4] [2, 3, 4, 1] [2, 4, 1, 3] [2, 4, 3, 1] [3, 1, 2, 4] [3, 1, 4, 2] [3, 2, 1, 4] [3, 2, 4, 1] [3, 4, 1, 2] [3, 4, 2, 1] [4, 1, 2, 3] [4, 1, 3, 2] [4, 2, 1, 3] [4, 2, 3, 1] [4, 3, 1, 2] [4, 3, 2, 1]
リスト : 組み合わせの生成
// 1 から n までの数字から r 個を選ぶ
fn combinations(n: i32, r: i32, func: fn(&Vec<i32>) -> ()) {
fn comb(n: i32, m: i32, r: i32, func: fn(&Vec<i32>) -> (), xs: &mut Vec<i32>) {
if r == 0 {
func(xs);
} else if m <= n {
xs.push(m);
comb(n, m + 1, r - 1, func, xs);
xs.pop();
comb(n, m + 1, r, func, xs);
}
}
comb(n, 1, r, func, &mut vec![]);
}
// ベクタの表示
fn print_vector(xs: &Vec<i32>) {
println!("{:?}", xs);
}
fn main() {
combinations(5, 3, print_vector);
}
[1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。ただし、1 の前に - 符号はつけないものとします。
例：1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
リスト : 小町算
const ADD: i32 = -1;
const SUB: i32 = -2;
// 式の計算
fn calc_expr(expr: &Vec<i32>) -> i32 {
let mut acc = expr[0];
let mut x = 1;
while x < expr.len() {
if expr[x] == ADD {
acc += expr[x + 1];
} else {
acc -= expr[x + 1];
}
x += 2;
}
acc
}
// 式の表示
fn print_expr(xs: &Vec<i32>) {
for x in xs {
match *x {
ADD => print!(" + "),
SUB => print!(" - "),
_ => print!("{}", x)
}
}
println!(" = 100");
}
// 小町算の解法
fn komachi(n: i32, expr: &mut Vec<i32>) {
if n == 10 {
if calc_expr(expr) == 100 {
print_expr(expr);
}
} else {
let idx = expr.len();
expr.push(ADD);
expr.push(n);
komachi(n + 1, expr);
expr[idx] = SUB;
komachi(n + 1, expr);
expr.pop();
expr.pop();
let save = expr[idx - 1];
expr[idx- 1] = expr[idx - 1] * 10 + n;
komachi(n + 1, expr);
expr[idx - 1] = save;
}
}
fn main() {
komachi(2, &mut vec![1]);
}
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100 123 + 4 - 5 + 67 - 89 = 100 123 + 45 - 67 + 8 - 9 = 100 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100 123 - 45 - 67 + 89 = 100
「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
列
1 2 3 4 5 6 7 8
*-----------------*
1 | Q . . . . . . . |
2 | . . . . Q . . . |
3 | . . . . . . . Q |
行 4 | . . . . . Q . . |
5 | . . Q . . . . . |
6 | . . . . . . Q . |
7 | . Q . . . . . . |
8 | . . . Q . . . . |
*-----------------*
図 : 8 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。詳しい説明は拙作のページ「Puzzle DE Programming: N Queens Problem」をお読みください。
リスト : N Queens Problem
// 衝突の検出
fn attack(q: i32, qs: &Vec<i32>) -> bool {
let mut i = qs.len();
let mut d = 1;
while i > 0 {
if q + d == qs[i - 1] || q - d == qs[i - 1] { return true; }
i -= 1;
d += 1;
}
false
}
// N Queens Problem の解法
fn nqueens(n: i32) {
fn queen_sub(n: i32, qs: &mut Vec<i32>) {
if n == qs.len() as i32 {
println!("{:?}", qs);
} else {
for q in 1 .. n + 1 {
if !qs.contains(&q) && !attack(q, qs) {
qs.push(q);
queen_sub(n, qs);
qs.pop();
}
}
}
}
queen_sub(n, &mut vec![]);
}
fn main() {
for n in 4 .. 9 {
nqueens(n);
}
}
[2, 4, 1, 3] [3, 1, 4, 2] [1, 3, 5, 2, 4] [1, 4, 2, 5, 3] [2, 4, 1, 3, 5] [2, 5, 3, 1, 4] [3, 1, 4, 2, 5] [3, 5, 2, 4, 1] [4, 1, 3, 5, 2] [4, 2, 5, 3, 1] [5, 2, 4, 1, 3] [5, 3, 1, 4, 2] [2, 4, 6, 1, 3, 5] [3, 6, 2, 5, 1, 4] [4, 1, 5, 2, 6, 3] [5, 3, 1, 6, 4, 2] [1, 3, 5, 7, 2, 4, 6] [1, 4, 7, 3, 6, 2, 5] [1, 5, 2, 6, 3, 7, 4] ・・・省略・・・ [7, 3, 6, 2, 5, 1, 4] [7, 4, 1, 5, 2, 6, 3] [7, 5, 3, 1, 6, 4, 2] [1, 5, 8, 6, 3, 7, 2, 4] [1, 6, 8, 3, 7, 4, 2, 5] [1, 7, 4, 6, 8, 2, 5, 3] ・・・省略・・・ [8, 2, 5, 3, 1, 7, 4, 6] [8, 3, 1, 6, 2, 5, 7, 4] [8, 4, 1, 3, 6, 2, 7, 5]
ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │●│ │●│ │ │Ｋ│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │●│ │●│ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
●：ナイト (K) が動ける位置 問題
問題 : 騎士の巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。今回は 5 行 5 列の盤面でナイトの移動経路の総数を求めるプログラムを作ります。
盤面は 2 次元配列で表すことにします。この場合、騎士の移動手順は 5 行 5 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 5 行 5 列の 2 次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 9 行 9 列の大きさになります。壁に 0 以外の値 (-1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
リスト : 騎士の巡歴
// 盤面の大きさ
const BSIZE: usize = 9;
// 移動
static DX: [i32; 8] = [1, 2, 2, 1, -1, -2, -2, -1];
static DY: [i32; 8] = [-2, -1, 1, 2, 2, 1, -1, -2];
// 盤面の初期化
fn init_board(board: &mut [[i32; BSIZE]; BSIZE]) {
for x in 2 .. 7 {
for y in 2 .. 7 {
board[x][y] = 0;
}
}
}
// 盤面の表示
fn print_board(board: &[[i32; BSIZE]; BSIZE]) {
for x in 2 .. 7 {
for y in 2 .. 7 {
print!("{:>2} ", board[x][y]);
}
println!("");
}
println!("");
}
// 「騎士の巡歴」の解法
fn knight_tour(n: i32, x: i32, y: i32, board: &mut [[i32; BSIZE]; BSIZE]) {
if n > 25 {
print_board(board);
} else {
for i in 0 .. DX.len() {
let x1 = x + DX[i];
let y1 = y + DY[i];
if board[x1 as usize][y1 as usize] == 0 {
board[x1 as usize][y1 as usize] = n;
knight_tour(n + 1, x1, y1, board);
board[x1 as usize][y1 as usize] = 0;
}
}
}
}
fn main() {
let mut board = [[-1; BSIZE]; BSIZE];
init_board(&mut board);
board[2][2] = 1;
knight_tour(2, 2, 2, &mut board);
}
1 16 21 10 25 20 11 24 15 22 17 2 19 6 9 12 7 4 23 14 3 18 13 8 5 ・・・省略・・・ 1 16 11 6 3 10 5 2 17 12 15 22 19 4 7 20 9 24 13 18 23 14 21 8 25
解は全部で 304 通りあります。
リスト : ナンバープレース (数独)
// 盤面の大きさ
const BSIZE: usize = 9;
// 盤面の表示
fn print_sudoku(board: &[[i32; BSIZE]; BSIZE]) {
for x in 0 .. BSIZE {
for y in 0 .. BSIZE {
print!("{} ", board[x][y]);
}
println!("");
}
}
// 条件のチェック
fn check_sudoku(x: usize, y: usize, n: i32, board: &[[i32; BSIZE]; BSIZE]) -> bool {
for i in 0 .. BSIZE {
if board[i][y] == n || board[x][i] == n { return false; }
}
let x1 = (x / 3) * 3;
let y1 = (y / 3) * 3;
for i in 0 .. 3 {
for j in 0 .. 3 {
if board[x1 + i][y1 + j] == n { return false; }
}
}
true
}
// ナンバープレースの解法
fn sudoku(x: usize, y: usize, board: &mut [[i32; BSIZE]; BSIZE]) {
if y >= BSIZE {
print_sudoku(board);
} else if x >= BSIZE {
sudoku(0, y + 1, board);
} else if board[x][y] != 0 {
sudoku(x + 1, y, board);
} else {
for n in 1 .. 10 {
if !check_sudoku(x, y, n, board) { continue; }
board[x][y] = n;
sudoku(x + 1, y, board);
board[x][y] = 0;
}
}
}
fn main() {
// 問題 (出典: 数独 - Wikipedia の問題例)
let mut sudoku_board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
];
print_sudoku(&sudoku_board);
println!("--------------------");
sudoku(0, 0, &mut sudoku_board);
}
5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 -------------------- 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
「マスターマインド」は 0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。
[6, 2, 8, 1] : 正解 --------------------------------- 1: [0, 1, 2, 3] : cows 2 : bulls 0 2: [1, 0, 4, 5] : cows 1 : bulls 0 3: [2, 3, 5, 6] : cows 2 : bulls 0 4: [3, 2, 7, 4] : cows 0 : bulls 1 5: [3, 6, 0, 8] : cows 2 : bulls 0 6: [6, 2, 8, 1] : cows 0 : bulls 4 図 : マスターマインドの動作例
今回はマスターマインドを解くプログラムを作ることにします。
このゲームは 10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。
矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。
[6, 2, 8, 1] が正解の場合
[0, 1, 2, 3] => bulls = 0, cows = 2
[0, 1, 2, 3] と比較する
--------------------------------------------------------
[0, X, X, X] 0 から始まるコードは bulls = 1
になるので矛盾する。
・・・・
[1, 0, 3, 4] cows = 3, bulls = 0 になるので矛盾する
・・・・
[1, 0, 4, 5] cows = 2, bulls = 0 で矛盾しない。
--------------------------------------------------------
[1, 0, 4, 5] => bulls = 0, cows = 1
次は、[0, 1, 2, 3] と [1, 0, 4, 5] に矛盾しない数字を選ぶ
図 : マスターマインドの推測アルゴリズム
[0, 1, 2, 3] で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、[0, X, X, X] というコードは [0, 1, 2, 3] と比較すると bulls が 1 となるので、矛盾していることがわかります。
次に [1, 0, 3, 4] というコードを考えてみます。[0, 1, 2, 3] の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、[1, 0, 3, 4] と [0, 1, 2, 3] と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。
次に [1, 0, 4, 5] というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は [0, 1, 2, 3] と [1, 0, 4, 5] に矛盾しないコードを選択すればいいわけです。
リスト : マスターマインドの解法
// 順列の生成 (ベクタに格納して返す)
fn permutations(n: i32, m: i32) -> Vec<Vec<i32>> {
fn perm(n: i32, m: i32, xs: &mut Vec<i32>, ps: &mut Vec<Vec<i32>>) {
if m == 0 {
ps.push(xs.clone());
} else {
for x in 0 .. n + 1 {
if xs.contains(&x) { continue; }
xs.push(x);
perm(n, m - 1, xs, ps);
xs.pop();
}
}
}
let mut ps: Vec<Vec<i32>> = vec![];
perm(n, m, &mut vec![], &mut ps);
ps
}
// bulls を数える
fn count_bulls(xs: &Vec<i32>, ys: &Vec<i32>) -> i32 {
let mut c = 0;
for i in 0 .. xs.len() {
if xs[i] == ys[i] { c += 1; }
}
c
}
// 同じ数を数える
fn count_same_number(xs: &Vec<i32>, ys: &Vec<i32>) -> i32 {
let mut c = 0;
for x in xs {
if ys.contains(x) { c += 1; }
}
c
}
// 結果を格納する構造体
struct Query {
code: Vec<i32>, bulls: i32, cows: i32
}
// 今までの質問と矛盾していないか
fn check_query(code: &Vec<i32>, query_table: &[Query]) -> bool {
for q in query_table {
let b = count_bulls(&(q.code), code);
let c = count_same_number(&(q.code), code) - b;
if b != q.bulls || c != q.cows { return false; }
}
true
}
// マスターマインドの解法
fn master_mind(answer: &Vec<i32>, code_table: &Vec<Vec<i32>>) {
let mut qs: Vec<Query> = vec![];
let mut n = 1;
for ref code in code_table {
if check_query(code, &qs) {
let b = count_bulls(code, answer);
let c = count_same_number(code, answer) - b;
qs.push(Query {code: (*code).clone(), bulls: b, cows: c});
println!("{}: {:?}, bulls = {}, cows = {}", n, code, b, c);
n += 1;
if b == 4 {
println!("Good Job!!!");
return;
}
}
}
println!("Oops!, maybe bug!!");
}
fn main() {
let code_table = permutations(9, 4);
master_mind(&vec![9,8,7,6], &code_table);
master_mind(&vec![9,4,3,1], &code_table);
}
1: [0, 1, 2, 3], bulls = 0, cows = 0 2: [4, 5, 6, 7], bulls = 0, cows = 2 3: [5, 4, 8, 9], bulls = 0, cows = 2 4: [6, 7, 9, 8], bulls = 0, cows = 4 5: [8, 9, 7, 6], bulls = 2, cows = 2 6: [9, 8, 7, 6], bulls = 4, cows = 0 Good Job!!! 1: [0, 1, 2, 3], bulls = 0, cows = 2 2: [1, 0, 4, 5], bulls = 0, cows = 2 3: [2, 3, 5, 4], bulls = 0, cows = 2 4: [3, 4, 0, 6], bulls = 1, cows = 1 5: [3, 5, 6, 1], bulls = 1, cows = 1 6: [6, 5, 0, 2], bulls = 0, cows = 0 7: [7, 4, 3, 1], bulls = 3, cows = 0 8: [8, 4, 3, 1], bulls = 3, cows = 0 9: [9, 4, 3, 1], bulls = 4, cows = 0 Good Job!!!
下記経路図において、A から G までの経路を深さ優先探索、幅優先探索、反復深化で求めます。アルゴリズムの詳しい説明は拙作のページ「お気楽Ｃ言語プログラミング超入門: 経路の探索」をお読みくださいませ。
Ｂ───Ｄ───Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ───Ｅ───Ｇ
図 : 経路図
リスト : 経路の探索
//
// 隣接行列による解法
//
const SIZE: usize = 7;
static MAT: [[bool; SIZE]; SIZE] = [
// A B C D E F G
[false, true, true, false, false, false, false], // A
[true, false, true, true, false, false, false], // B
[true, true, false, false, true, false, false], // C
[false, true , false, false, true, true, false], // D
[false, false, true, true, false, false, true ], // E
[false, false, false, true, false, false, false], // F
[false, false, false, false, true, false, false], // G
];
// 深さ優先探索
fn dfs(goal: usize, path: &mut Vec<usize>) {
let x = path[path.len() - 1];
if x == goal {
println!("{:?}", path);
} else {
for i in 0..SIZE {
if !MAT[x][i] || path.contains(&i) { continue; }
path.push(i);
dfs(goal, path);
path.pop();
}
}
}
// パスの生成
fn make_path(path: &Vec<usize>, x: usize) -> Vec<usize> {
let mut xs = vec![];
for &a in path {
xs.push(a);
}
xs.push(x);
xs
}
// 幅優先探索
fn bfs(start: usize, goal: usize) {
let mut que = vec![vec![start]];
while que.len() > 0 {
let path = que.remove(0);
let x = path[path.len() - 1];
if x == goal {
println!("{:?}", path);
} else {
for i in 0..SIZE {
if !MAT[x][i] || path.contains(&i) { continue; }
que.push(make_path(&path, i));
}
}
}
}
// 反復深化
fn ids(start: usize, goal: usize) {
fn dfs(limit: usize, goal: usize, path: &mut Vec<usize>) {
let x = path[path.len() - 1];
if limit == path.len() {
if x == goal {
println!("{:?}", path);
}
} else {
for i in 0..SIZE {
if !MAT[x][i] || path.contains(&i) { continue; }
path.push(i);
dfs(limit, goal, path);
path.pop();
}
}
}
for limit in 2 .. SIZE + 1 {
println!("----- {} -----", limit);
dfs(limit, goal, &mut vec![start]);
}
}
//
// 隣接リストによる解法
//
// 深さ優先探索
fn dfs_adj(goal: usize, path: &mut Vec<usize>, adj: &[Vec<usize>]) {
let x = path[path.len() - 1];
if x == goal {
println!("{:?}", path);
} else {
for y in &adj[x] {
if path.contains(y) { continue; }
path.push(*y);
dfs_adj(goal, path, adj);
path.pop();
}
}
}
// 幅優先探索
fn bfs_adj(start: usize, goal: usize, adj: &[Vec<usize>]) {
let mut que = vec![vec![start]];
while que.len() > 0 {
let path = que.remove(0);
let x = path[path.len() - 1];
if x == goal {
println!("{:?}", path);
} else {
for y in &adj[x] {
if path.contains(y) { continue; }
que.push(make_path(&path, *y));
}
}
}
}
// 反復深化
fn ids_adj(start: usize, goal: usize, adj: &[Vec<usize>]) {
fn dfs(limit: usize, goal: usize, path: &mut Vec<usize>, adj: &[Vec<usize>]) {
let x = path[path.len() - 1];
if limit == path.len() {
if x == goal {
println!("{:?}", path);
}
} else {
for y in &adj[x] {
if path.contains(y) { continue; }
path.push(*y);
dfs(limit, goal, path, adj);
path.pop();
}
}
}
for limit in 2 .. SIZE + 1 {
println!("----- {} -----", limit);
dfs(limit, goal, &mut vec![start], adj);
}
}
fn main() {
println!("----- dfs -----");
dfs(6, &mut vec![0]);
println!("----- bfs -----");
bfs(0, 6);
println!("----- ids -----");
ids(0, 6);
// 隣接リスト Vec は static に配置できないようだ
let adj: [Vec<usize>; SIZE] = [
vec![1, 2],
vec![0, 2, 3],
vec![0, 1, 4],
vec![1, 4, 5],
vec![2, 3, 6],
vec![3],
vec![4]
];
println!("----- dfs_adj -----");
dfs_adj(6, &mut vec![0], &adj);
println!("----- bfs_adj -----");
bfs_adj(6, 0, &adj);
println!("----- ids_adj -----");
ids_adj(6, 0, &adj);
}
----- dfs ----- [0, 1, 2, 4, 6] [0, 1, 3, 4, 6] [0, 2, 1, 3, 4, 6] [0, 2, 4, 6] ----- bfs ----- [0, 2, 4, 6] [0, 1, 2, 4, 6] [0, 1, 3, 4, 6] [0, 2, 1, 3, 4, 6] ----- ids ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- [0, 2, 4, 6] ----- 5 ----- [0, 1, 2, 4, 6] [0, 1, 3, 4, 6] ----- 6 ----- [0, 2, 1, 3, 4, 6] ----- 7 ----- ----- dfs_adj ----- [0, 1, 2, 4, 6] [0, 1, 3, 4, 6] [0, 2, 1, 3, 4, 6] [0, 2, 4, 6] ----- bfs_adj ----- [6, 4, 2, 0] [6, 4, 2, 1, 0] [6, 4, 3, 1, 0] [6, 4, 3, 1, 2, 0] ----- ids_adj ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- [6, 4, 2, 0] ----- 5 ----- [6, 4, 2, 1, 0] [6, 4, 3, 1, 0] ----- 6 ----- [6, 4, 3, 1, 2, 0] ----- 7 -----
皆さんお馴染みの「８パズル」を幅優先探索で解くプログラムです。詳しい説明は拙作のページ「Ｃ言語超入門: スライドパズル」をお読みください。
//
// 8 パズル (幅優先探索)
//
use std::collections::HashSet;
const ESIZE: usize = 9;
const MAXS: usize = 9 * 8 * 7 * 6 * 5 * 4 * 3;
// 局面
struct State {
board: [i32; ESIZE],
space: usize,
prev: usize
}
// 探索
fn position(x: i32, xs: &[i32]) -> usize {
for i in 0 .. ESIZE + 1 {
if xs[i] == x { return i; }
}
ESIZE
}
// 解の表示
fn print_answer(xs: &Vec<State>, x: usize) {
if xs[x].prev != MAXS {
print_answer(xs, xs[x].prev);
}
println!("{:?}", xs[x].board);
}
// 幅優先探索
fn eight_bfs(start: &[i32; ESIZE], goal: &[i32; ESIZE], adj: &[Vec<usize>]) {
let mut que: Vec<State> = Vec::with_capacity(MAXS);
let mut chk: HashSet<[i32; ESIZE]> = HashSet::new();
let mut rp = 0;
que.push(State { board: *start,
space: position(0, start),
prev: MAXS });
chk.insert(*start);
while rp < que.len() {
let s = que[rp].space;
for x in &adj[s] {
let mut new_board = que[rp].board;
new_board[s] = new_board[*x];
new_board[*x] = 0;
if !chk.contains(&new_board) {
chk.insert(new_board);
que.push(State { board: new_board, space: *x, prev: rp });
if new_board == *goal {
print_answer(&que, que.len() - 1);
return;
}
}
}
rp += 1;
}
}
fn main() {
// 隣接リスト
let adj8: [Vec<usize>; ESIZE] = [
vec![1, 3], // 0
vec![0, 2, 4], // 1
vec![1, 5], // 2
vec![0, 4, 6], // 3
vec![1, 3, 5, 7], // 4
vec![2, 4, 8], // 5
vec![3, 7], // 6
vec![4, 6, 8], // 7
vec![5, 7] // 8
];
println!("----- eight_bfs -----");
eight_bfs(&[8,6,7,2,5,4,3,0,1], &[1,2,3,4,5,6,7,8,0], &adj8);
}
----- eight_bfs ----- [8, 6, 7, 2, 5, 4, 3, 0, 1] [8, 6, 7, 2, 0, 4, 3, 5, 1] [8, 0, 7, 2, 6, 4, 3, 5, 1] [0, 8, 7, 2, 6, 4, 3, 5, 1] [2, 8, 7, 0, 6, 4, 3, 5, 1] [2, 8, 7, 3, 6, 4, 0, 5, 1] [2, 8, 7, 3, 6, 4, 5, 0, 1] [2, 8, 7, 3, 6, 4, 5, 1, 0] [2, 8, 7, 3, 6, 0, 5, 1, 4] [2, 8, 0, 3, 6, 7, 5, 1, 4] [2, 0, 8, 3, 6, 7, 5, 1, 4] [2, 6, 8, 3, 0, 7, 5, 1, 4] [2, 6, 8, 0, 3, 7, 5, 1, 4] [2, 6, 8, 5, 3, 7, 0, 1, 4] [2, 6, 8, 5, 3, 7, 1, 0, 4] [2, 6, 8, 5, 3, 7, 1, 4, 0] [2, 6, 8, 5, 3, 0, 1, 4, 7] [2, 6, 0, 5, 3, 8, 1, 4, 7] [2, 0, 6, 5, 3, 8, 1, 4, 7] [2, 3, 6, 5, 0, 8, 1, 4, 7] [2, 3, 6, 0, 5, 8, 1, 4, 7] [2, 3, 6, 1, 5, 8, 0, 4, 7] [2, 3, 6, 1, 5, 8, 4, 0, 7] [2, 3, 6, 1, 5, 8, 4, 7, 0] [2, 3, 6, 1, 5, 0, 4, 7, 8] [2, 3, 0, 1, 5, 6, 4, 7, 8] [2, 0, 3, 1, 5, 6, 4, 7, 8] [0, 2, 3, 1, 5, 6, 4, 7, 8] [1, 2, 3, 0, 5, 6, 4, 7, 8] [1, 2, 3, 4, 5, 6, 0, 7, 8] [1, 2, 3, 4, 5, 6, 7, 0, 8] [1, 2, 3, 4, 5, 6, 7, 8, 0]
ペグ・ソリテアは盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは、次のルールに従って移動し、除去することができます。
参考文献『特集コンピュータパズルへの招待 ペグ・ソリテア編』によると、最初の空き位置と最後に残ったペグの位置が同じになることを「補償型の解」といい、最初の空き位置が盤の中央で、なおかつ、補償型の解がある場合を「中央補償型の解」と呼ぶそうです。
Hoppers は芦ヶ原伸之氏が考案されたペグ・ソリテアです。次の図を見てください。
●───●───● │＼ ／│＼ ／│ │ ● │ ● │ │／ ＼│／ ＼│ ●───○───● │＼ ／│＼ ／│ │ ● │ ● │ │／ ＼│／ ＼│ ●───●───● 図 : Hoppers
Hoppers は穴を 13 個に減らしていて、遊ぶのに手頃な大きさになっています。上図に示したように、最初に中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。
リスト : ペグソリティア (Hoppers)
const HSIZE: usize = 13;
const HOLE: usize = 6;
const MAXJUMP: usize = 11;
static mut CNT: i32 = 0;
// 手順の表示
fn print_moves(moves: &Vec<(usize, usize)>) {
print!("[{}, {}", moves[0].0, moves[0].1);
for i in 1 .. MAXJUMP {
if moves[i - 1].1 == moves[i].0 {
print!(", {}", moves[i].1);
} else {
print!("][{}, {}", moves[i].0, moves[i].1)
}
}
println!("]");
unsafe { CNT += 1; }
}
// 反復深化による解法
fn hoppers(board: &mut [bool], limit: i32, jc: i32,
moves: &mut Vec<(usize, usize)>, jtbl: &[Vec<(usize, usize)>]) {
if jc > limit { return; }
if moves.len() == MAXJUMP {
if board[HOLE] { print_moves(moves); }
} else {
for from in 0 .. HSIZE {
if !board[from] { continue; }
for &(del, to) in &jtbl[from] {
if !board[del] || board[to] { continue; }
board[from] = false;
board[del] = false;
board[to] = true;
let new_jc = if moves[moves.len() - 1].1 == from { jc } else { jc + 1 };
moves.push((from, to));
hoppers(board, limit, new_jc, moves, jtbl);
moves.pop();
board[to] = false;
board[del] = true;
board[from] = true;
}
}
}
}
fn main() {
// Hoppers
let jump_table: [Vec<(usize, usize)>; HSIZE] = [
vec![(1, 2), (3, 6), (5, 10)],
vec![(3, 5), (6, 11), (4, 7)],
vec![(1, 0), (4, 6), (7, 12)],
vec![(6, 9)],
vec![(6, 8)],
vec![(3, 1), (6, 7), (8, 11)],
vec![(3, 0), (4, 2), (8, 10), (9, 12)],
vec![(4, 1), (6, 5), (9, 11)],
vec![(6, 4)],
vec![(6, 3)],
vec![(5, 0), (8, 6), (11, 12)],
vec![(8, 5), (6, 1), (9, 7)],
vec![(11, 10), (9, 6), (7, 2)]
];
let mut hoppers_board = [
true, true, true,
true, true,
true, true, true,
true, true,
true, true, true
];
// 初手を 0 -> 6 に限定
hoppers_board[0] = false;
hoppers_board[3] = false;
for limit in 2 .. MAXJUMP as i32 + 1 {
println!("----- {} -----", limit);
hoppers(&mut hoppers_board, limit, 1, &mut vec![(0, 6)], &jump_table);
unsafe {
if CNT > 0 { break; }
}
}
}
----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- [0, 6][9, 3][2, 0, 6][11, 1][10, 0, 2, 6][8, 4][12, 2, 6] [0, 6][9, 3][2, 0, 6][11, 1][10, 6][4, 8][12, 2, 0, 10, 6] [0, 6][9, 3][2, 0, 6][11, 1][12, 2, 6][8, 4][10, 0, 2, 6] [0, 6][9, 3][2, 6][8, 4][10, 0, 2, 6][7, 5][12, 10, 0, 6] [0, 6][9, 3][2, 6][8, 4][10, 0, 2, 6][11, 1][12, 2, 0, 6] [0, 6][9, 3][2, 6][8, 4][10, 0, 6][7, 5][12, 10, 0, 2, 6] [0, 6][9, 3][2, 6][8, 4][12, 2, 0, 6][5, 7][10, 12, 2, 6] [0, 6][9, 3][2, 6][8, 4][12, 2, 0, 6][11, 1][10, 0, 2, 6] [0, 6][9, 3][2, 6][8, 4][12, 2, 6][5, 7][10, 12, 2, 0, 6] [0, 6][9, 3][10, 0, 6][7, 5][2, 0, 10, 6][4, 8][12, 10, 6] [0, 6][9, 3][10, 0, 6][7, 5][2, 6][8, 4][12, 10, 0, 2, 6] [0, 6][9, 3][10, 0, 6][7, 5][12, 10, 6][4, 8][2, 0, 10, 6] [0, 6][9, 3][10, 6][4, 8][2, 0, 6][11, 1][12, 2, 0, 10, 6] [0, 6][9, 3][10, 6][4, 8][2, 0, 10, 6][7, 5][12, 10, 0, 6] [0, 6][9, 3][10, 6][4, 8][2, 0, 10, 6][11, 1][12, 2, 0, 6] [0, 6][9, 3][10, 6][4, 8][12, 10, 0, 6][1, 11][2, 12, 10, 6] [0, 6][9, 3][10, 6][4, 8][12, 10, 0, 6][7, 5][2, 0, 10, 6] [0, 6][9, 3][10, 6][4, 8][12, 10, 6][1, 11][2, 12, 10, 0, 6]