簡単なプログラム
●数列の生成
要素が n 個の数列を生成する関数を 3 つ作ってみましょう。
- iota(n, start, step) は start から step 刻みの数列を生成する
- tabulete(n, func, start) は iota(n, start, 1).map(func) と同じ
- iterate(n, func, a) は初期値が a で、次項を func(前項) で生成する
リスト : 数列の生成
function iota(n: number, start = 0, step = 1): number[] {
const seq: number[] = [];
while (n-- > 0) {
seq.push(start);
start += step;
}
return seq;
}
function tabulate(n: number, func: (x: number) => number, start = 0): number[] {
const seq: number[] = [];
while (n-- > 0) {
seq.push(func(start++));
}
return seq;
}
function iterate(n: number, func: (x: number) => number, a: number): number[] {
const seq: number[] = [];
while(n-- > 0) {
seq.push(a);
a = func(a);
}
return seq;
}
console.log(iota(6));
console.log(iota(8, 1));
console.log(iota(8, 1, 2));
console.log(tabulate(6, x => x * x));
console.log(tabulate(8, x => x * x, 1));
console.log(iterate(6, x => x + 1, 0));
console.log(iterate(8, x => x + 2, 1));
[ 0, 1, 2, 3, 4, 5 ] [ 1, 2, 3, 4, 5, 6, 7, 8 ] [ 1, 3, 5, 7, 9, 11, 13, 15 ] [ 0, 1, 4, 9, 16, 25 ] [ 1, 4, 9, 16, 25, 36, 49, 64 ] [ 0, 1, 2, 3, 4, 5 ] [ 1, 3, 5, 7, 9, 11, 13, 15 ]
●FizzBuzz 問題
リスト : FizzBuzz 問題
function fizzbuzz(): string[] {
const buff: string[] = [];
for (let i = 1; i <= 100; i++) {
if (i % 15 == 0) {
buff.push("FizzBuzz");
} else if (i % 3 == 0) {
buff.push("Fizz");
} else if (i % 5 == 0) {
buff.push("Buzz");
} else {
buff.push(String(i));
}
}
return buff;
}
// console.log(fizzbuzz().toString());
// 数列の生成 iota() は省略
// 数値を文字列に変換
function change(n: number): string {
if (n % 15 == 0) return "FizzBuzz";
if (n % 3 == 0) return "Fizz";
if (n % 5 == 0) return "Buzz";
return String(n);
}
console.log(iota(100, 1).map(change).toString());
1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz,16,17,Fizz,19,Buzz,Fizz,22,23,Fizz,Buzz, 26,Fizz,28,29,FizzBuzz,31,32,Fizz,34,Buzz,Fizz,37,38,Fizz,Buzz,41,Fizz,43,44,FizzBuzz,46,47,Fizz, 49,Buzz,Fizz,52,53,Fizz,Buzz,56,Fizz,58,59,FizzBuzz,61,62,Fizz,64,Buzz,Fizz,67,68,Fizz,Buzz,71,Fizz, 73,74,FizzBuzz,76,77,Fizz,79,Buzz,Fizz,82,83,Fizz,Buzz,86,Fizz,88,89,FizzBuzz,91,92,Fizz,94,Buzz, Fizz,97,98,Fizz,Buzz
●数値積分
リスト : 中点則で円周率を求める
function midPoint(n: number): number {
const w = 1.0 / n;
let s = 0.0;
for (let i = 1; i <= n; i++) {
const x = (i - 0.5) * w;
s += 4.0 / (1.0 + x * x);
}
return s * w;
}
for (let n = 100; n <= 10000000; n *= 10) {
console.log(midPoint(n));
}
3.1416009869231254 3.1415927369231227 3.141592654423134 3.1415926535981615 3.1415926535897643 3.141592653589731
●平均値と標準偏差
リスト : 平均値と標準偏差
// 身長のデータ
const height = [
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
];
// 平均値
function mean(data: number[]): number {
let sum = 0;
for (let x of data) sum += x;
return sum / data.length;
}
// reduce() を使うと簡単
function mean1(data: number[]): number {
return data.reduce((a, x) => a + x) / data.length;
}
// 標準偏差
function sd(data: number[]): number {
const m = mean(data);
const s = data.reduce((a, x) => a + (x - m) * (x - m), 0);
return Math.sqrt(s / data.length);
}
console.log(mean(height));
console.log(mean1(height));
console.log(sd(height));
150.62699999999998 150.62699999999998 6.433472701426501
●パスカルの三角形
リスト : パスカルの三角形
// 2 次元配列バージョン
function pascal(n: number): void {
const table: number[][] = new Array(n);
for (let i = 0; i < n; i++) {
table[i] = new Array(n);
}
table[0][0] = 1;
table[1][0] = 1;
table[1][1] = 1;
for (let i = 2; i < n; i++) {
table[i][0] = 1;
for (let j = 1; j < i; j++ ) {
table[i][j] = table[i - 1][j - 1] + table[i - 1][j];
}
table[i][i] = 1;
}
table.forEach((xs, i) => console.log(xs.slice(0, i + 1)));
}
// 1 次元配列版
function pascal1(n: number): void {
const table: number[] = new Array(n);
table.fill(1);
console.log(table.slice(0, 1));
console.log(table.slice(0, 2));
for (let i = 2; i < n; i++) {
for (let j = i - 1; j > 0; j--) {
table[j] += table[j - 1];
}
// 表示
console.log(table.slice(0, i + 1));
}
}
// pascal(15);
pascal1(15);
[ 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 ]
●素数
リスト : 素数を求める (単純版)
// 素数のチェック
function checkPrime(ps: number[], x: number): boolean {
for (let p of ps) {
if (p * p > x) break;
if (x % p == 0) return false;
}
return true;
}
function prime(n: number): number[] {
const ps = [2];
for (let x = 3; x <= n; x += 2) {
if (checkPrime(ps, x)) {
ps.push(x);
}
}
return ps;
}
console.log(String(prime(100)));
console.log(String(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
●素因数分解
リスト : 素因数分解
function factorization(n: number): [number, number][] {
function factorSub(n: number, m: number): [number, number] {
let c = 0;
while (n % m == 0) {
c++;
n /= m;
}
return [c, n];
}
let result: [number, number][] = [];
let c: number;
[c, n] = factorSub(n, 2);
if (c > 0) result.push([2, c]);
for (let x = 3; x * x <= n; x += 2) {
[c, n] = factorSub(n, x);
if (c > 0) result.push([x, c]);
}
if (n > 1) result.push([n, 1]);
return result;
}
console.log(factorization(24));
console.log(factorization(12345678));
console.log(factorization(123456789));
console.log(factorization(1234567890));
console.log(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 ] ]
●順列と組み合わせ
簡単な例題として、1 から n までの整数から n 個を選ぶ順列と、1 から n までの整数から r を選ぶ組み合わせを生成するプログラムを作ります。配列の中から n 個を選ぶ順列や r 個を選ぶ組み合わせも簡単に作ることができます。興味のある方は挑戦してみてください。
リスト : 順列と組み合わせ
// 1 から n までの順列を生成する
function permutations(n: number, func: (x: number[]) => void): void {
const perm: number[] = [];
const visited: boolean[] = new Array(n + 1);
visited.fill(false);
function permSub(m: number): void {
if (m == n) {
func(perm);
} else {
for (let i = 1; i <= n; i++) {
if (!visited[i]) {
visited[i] = true;
perm[m] = i;
permSub(m + 1);
visited[i] = false;
}
}
}
}
permSub(0);
}
// 1 から n までの数値から r 個を選ぶ組み合わせ
function combinations(n: number, r: number, func: (x: number[]) => void): void {
const comb: number[] = new Array(r);
function combSub(i: number, j: number): void {
if (j == r) {
func(comb);
} else if (n - i + 1 == r - j) {
while (j < r) comb[j++] = i++;
func(comb);
} else {
comb[j] = i;
combSub(i + 1, j + 1);
combSub(i + 1, j);
}
}
combSub(1, 0);
}
permutations(3, console.log);
permutations(4, console.log);
combinations(5, 3, console.log);
combinations(6, 4, console.log);
[ 1, 2, 3 ] [ 1, 3, 2 ] [ 2, 1, 3 ] [ 2, 3, 1 ] [ 3, 1, 2 ] [ 3, 2, 1 ] [ 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, 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, 2, 3, 4 ] [ 1, 2, 3, 5 ] [ 1, 2, 3, 6 ] [ 1, 2, 4, 5 ] [ 1, 2, 4, 6 ] [ 1, 2, 5, 6 ] [ 1, 3, 4, 5 ] [ 1, 3, 4, 6 ] [ 1, 3, 5, 6 ] [ 1, 4, 5, 6 ] [ 2, 3, 4, 5 ] [ 2, 3, 4, 6 ] [ 2, 3, 5, 6 ] [ 2, 4, 5, 6 ] [ 3, 4, 5, 6 ]
●経路の探索
下記経路図において、A 地点から G 地点までの経路を、深さ優先探索、幅優先探索、反復深化で求めます。
経路図
M.Hiroi は経路の探索をいろいろなプログラミング言語で作っています。詳しい説明は拙作のページをお読みくださいませ。
- Algorithms with Python
- お気楽Ｃ言語プログラミング超入門
- お気楽Ｃ++プログラミング超入門
- お気楽 Perl プログラミング超入門
- お気楽 Go 言語プログラミング入門
- お気楽 SML/NJ 入門
- お気楽 OCaml プログラミング入門
- お気楽 Scheme プログラミング入門
- お気楽 Haskell プログラミング入門
- お気楽 Scala プログラミング入門
- Common Lisp 入門
リスト : 経路の探索
// 頂点
enum Nd {A = 0, B, C, D, E, F, G, S};
// 隣接リスト
const adjacent = [
[Nd.B, Nd.C], // A
[Nd.A, Nd.C, Nd.D], // B
[Nd.A, Nd.B, Nd.E], // C
[Nd.B, Nd.E, Nd.F], // D
[Nd.C, Nd.D, Nd.G], // E
[Nd.D], // F
[Nd.E] // G
];
// 深さ優先探索
function dfs(goal: Nd, path: Nd[]): void {
const p = path[path.length - 1];
if (p == goal) {
console.log(path.map(x => Nd[x]));
} else {
for (let x of adjacent[p]) {
if (path.indexOf(x) < 0) {
path.push(x);
dfs(goal, path);
path.pop();
}
}
}
}
console.log("----- depth first search -----")
dfs(Nd.G, [Nd.A]);
// 幅優先探索
function bfs(start: Nd, goal: Nd): void {
const que = [[start]];
while (que.length > 0) {
const path = que.shift(),
p = path[path.length - 1];
if (p == goal) {
console.log(path.map(x => Nd[x]));
} else {
for (let x of adjacent[p]) {
if (path.indexOf(x) < 0) {
que.push(path.concat([x]));
}
}
}
}
}
console.log("----- breadth first search -----")
bfs(Nd.A, Nd.G);
// 反復深化
function ids(start: Nd, goal: Nd): void {
function dfs(limit: number, path: Nd[]): void {
const p = path[path.length - 1];
if (path.length == limit) {
if (p == goal) {
console.log(path.map(x => Nd[x]));
}
} else {
for (let x of adjacent[p]) {
if (path.indexOf(x) < 0) {
path.push(x);
dfs(limit, path);
path.pop();
}
}
}
}
for (let limit = 1; limit <= Nd.S; limit++) {
console.log(`----- ${limit} -----`);
dfs(limit, [start]);
}
}
console.log("----- id search -----");
ids(Nd.A, Nd.G);
----- depth first search ----- [ 'A', 'B', 'C', 'E', 'G' ] [ 'A', 'B', 'D', 'E', 'G' ] [ 'A', 'C', 'B', 'D', 'E', 'G' ] [ 'A', 'C', 'E', 'G' ] ----- breadth first search ----- [ 'A', 'C', 'E', 'G' ] [ 'A', 'B', 'C', 'E', 'G' ] [ 'A', 'B', 'D', 'E', 'G' ] [ 'A', 'C', 'B', 'D', 'E', 'G' ] ----- id search ----- ----- 1 ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- [ 'A', 'C', 'E', 'G' ] ----- 5 ----- [ 'A', 'B', 'C', 'E', 'G' ] [ 'A', 'B', 'D', 'E', 'G' ] ----- 6 ----- [ 'A', 'C', 'B', 'D', 'E', 'G' ] ----- 7 -----
●小町算
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。ただし、1 の前に - 符号はつけないものとします。
例：1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
リスト : 小町算
// 演算子
enum OP {Plus = 10, Minus};
// 式を表示する
function printExpr(expr: number[]): void {
let s = expr[0].toString();
for (let i = 1; i < expr.length; i += 2) {
if (expr[i] == OP.Plus) {
s += " + " + expr[i + 1];
} else {
s += " - " + expr[i + 1];
}
}
s += " = 100";
console.log(s);
}
// 計算する
function calcExpr(expr: number[]): number {
let sum = expr[0];
for (let i = 1; i < expr.length; i += 2) {
if (expr[i] == OP.Plus) {
sum += expr[i + 1];
} else {
sum -= expr[i + 1];
}
}
return sum;
}
// 最後の要素を 10 倍して n を足す
function changeLast(a: number[], n: number): number[] {
const b = a.slice(0), i = a.length - 1;
b[i] = b[i] * 10 + n;
return b;
}
function komachi(n: number, expr: number[]): void {
if (n == 10) {
if (calcExpr(expr) == 100) printExpr(expr);
} else {
komachi(n + 1, expr.concat([OP.Plus, n]));
komachi(n + 1, expr.concat([OP.Minus, n]));
komachi(n + 1, changeLast(expr, n));
}
}
komachi(2, [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
●N Queens Problem
「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
図 : 8 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。詳しい説明は拙作のページ Puzzle DE Programming N Queens Problem をお読みください。
リスト : N Queens Problem
function nqueens(n: number): number {
const board: number[] = new Array(n),
used: boolean[] = new Array(n + 1);
let cnt = 0;
used.fill(false);
// 衝突の検出
function attack(x: number, m: number): boolean {
for (let i = 1; m >= 0; i++, m--) {
const q = board[m];
if (q + i == x || q - i == x) return true;
}
return false;
}
// 深さ優先探索
function dfs(m: number): void {
if (m == n) {
cnt++;
console.log(board);
} else {
for (let x = 1; x <= n; x++) {
if (used[x] || attack(x, m - 1)) continue;
used[x] = true;
board[m] = x;
dfs(m + 1);
used[x] = false;
}
}
}
dfs(0);
return cnt;
}
for (let i = 4; i >= 8; i++) {
console.log("----- ${i} -----");
const cnt = nqueens(i);
console.log(`total = ${cnt}`);
}
----- 4 -----
[ 2, 4, 1, 3 ]
[ 3, 1, 4, 2 ]
total = 2
----- 5 -----
[ 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 ]
total = 10
----- 6 -----
[ 2, 4, 6, 1, 3, 5 ]
[ 3, 6, 2, 5, 1, 4 ]
[ 4, 1, 5, 2, 6, 3 ]
[ 5, 3, 1, 6, 4, 2 ]
total = 4
----- 7 -----
[ 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 ]
total = 40
----- 8 -----
[ 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 ]
total = 92
●水差し問題
「水差し問題」はいろいろな呼び方があって、「水をはかる問題」とか「水を測り出す問題」と呼ばれることもあります。それでは問題です。
[問題]
大きな容器に水が入っています。目盛の付いていない 8 リットルと 5 リットルの容器を使って、大きな容器から 4 リットルの水を汲み出してください。4 リットルの水は、どちらの容器に入れてもかまいません。水をはかる最短手順を求めてください。なお、水の総量に制限はありません。
リスト : 水差し問題の解法
function waterJug(): void {
const MaxA = 8, MaxB = 5, Goal = 4;
// 操作関数表
const transfer: ((st: [number, number]) => [number, number])[] = [
st => [0, st[1]], // A を空にする
st => [st[0], 0], // B を空にする
st => [MaxA, st[1]], // A を満杯にする
st => [st[0], MaxB], // B を満杯にする
st => { // A -> B
const b = MaxB - st[1];
if (st[0] <= b) {
return [0, st[1] + st[0]];
} else {
return [st[0] - b, MaxB];
}
},
st => { // B -> A
const a = MaxA - st[0];
if (st[1] <= a) {
return [st[0] + st[1], 0];
} else {
return [MaxA, st[1] - a];
}
},
];
// 同じ状態があるか
function checkSameState(st: [number, number], move: [number, number][]): boolean {
return move.some(xs => xs[0] == st[0] && xs[1] == st[1]);
}
// 幅優先探索
function bfs(start: [number, number]): void {
const que = [[start]];
while (que.length > 0) {
const move = que.shift(),
st = move[move.length - 1];
if (st[0] == Goal || st[1] == Goal) {
console.log(move);
return;
}
for (let func of transfer) {
const newSt = func(st);
if (!checkSameState(newSt, move)) {
const newMove = move.slice(0);
newMove.push(newSt);
que.push(newMove);
}
}
}
}
bfs([0, 0]);
}
waterJug();
[ [ 0, 0 ], [ 0, 5 ], [ 5, 0 ], [ 5, 5 ], [ 8, 2 ], [ 0, 2 ], [ 2, 0 ], [ 2, 5 ], [ 7, 0 ], [ 7, 5 ], [ 8, 4 ] ]
●８パズル
皆さんお馴染みの「８パズル」を幅優先探索で解くプログラムです。詳しい説明は拙作のページをお読みください。
- Algorithms with Python: 幅優先探索と反復深化
- Ｃ言語超入門: スライドパズル
- Scheme 入門: パズルの解法 [2]
- Scala 入門: パズルの解法 (3)
- OCaml 入門: パズルの解法 (2)
リスト : ８パズルの解法
// 盤面
// 0 1 2
// 3 4 5
// 6 7 8
// 隣接リスト
const adjacent8 = [
[1, 3], // 0
[0, 2, 4], // 1
[1, 5], // 2
[0, 4, 6], // 3
[1, 3, 5, 7], // 4
[2, 4, 8], // 5
[3, 7], // 6
[4, 6, 8], // 7
[5, 7] // 8
];
// 局面
class State {
constructor(public board: number[], public space: number, public prev: State = null) { }
}
// 盤面の比較
function equalBoard(a: number[], b: number[]): boolean {
for (let i = 0; i < a.length; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
// 盤面を数値に変換
function hash(board: number[]): number {
return board.reduce((a, x) => a * 10 + x);
}
// 手順の表示
function printAnswer(st: State): void {
if (st.prev != null) {
printAnswer(st.prev);
}
console.log(st.board);
}
// 幅優先探索
function eightBfs(start: number[], goal: number[]): void {
const que: State[] = [new State(start, start.indexOf(0), null)],
tbl = new Set<number>();
tbl.add(hash(start));
while (que.length > 0) {
const st = que.shift();
if (equalBoard(st.board, goal)) {
printAnswer(st);
return;
} else {
for (let x of adjacent8[st.space]) {
const nb = st.board.slice(0); // 配列のコピー
nb[st.space] = nb[x];
nb[x] = 0;
const hv = hash(nb);
if (!tbl.has(hv)) {
tbl.add(hv);
que.push(new State(nb, x, st))
}
}
}
}
}
eightBfs([8,6,7,2,5,4,3,0,1], [1,2,3,4,5,6,7,8,0]);
[ 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 ]
●ペグ・ソリティア
ペグ・ソリテアは盤上に配置されたペグ（駒）を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは、次のルールに従って移動し、除去することができます。
- ペグは隣にあるペグをひとつだけ跳び越して、空き場所へ着地する。
- 跳び越されたペグは盤上から取り除かれる。
- 移動方向はふつう縦横のみの 4 方向だが、ルールによっては斜め方向の移動を許す場合もある。
- 同じペグの連続跳びは 1 手と数える。
盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名です。下図に 33 穴英国盤を示します。
図 : 33 穴英国盤
33 の穴にペグがありますが、そこからひとつペグを取り除いてゲームを始めます。図では黒丸でペグを表し、白丸で空き場所を表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、最初に取り除くペグの位置によって、解けない場合もあるので注意してください。
33 穴英国盤のように、ペグの数が多くなるとパソコンで解くのは大変になります。そこで、今回はサイズを小さくした簡単なペグ・ソリテアを反復深化で解いてみましょう。
●Hoppers
Hoppers は芦ヶ原伸之氏が考案されたペグ・ソリテアです。次の図を見てください。
図 : Hoppers
Hoppers は穴を 13 個に減らしていて、遊ぶのに手頃な大きさになっています。上図に示したように、最初に中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めることにします。
M.Hiroi はペグ・ソリティアをいろいろなプログラミング言語で解いたことがあります。解法プログラムの詳しい説明は拙作のページをお読みくださいませ。
- Ｃ言語入門: Yet Another Clang Problems (5)
- Go 言語入門: 反復深化と下限値枝刈り法
- Scheme 入門: パズルの解法 [3]
- Haskell 入門: パズルの解法 (5)
- Prolog 入門: パズルに挑戦！
- Common Lisp 入門: パズルに挑戦！
●プログラム
リスト : Hoppers の解法
// 跳び先表 [to, del]
const jumpTable: [number, number][][] =
[[[1, 2], [3, 6], [5, 10]], // 0
[[3, 5], [6, 11], [4, 7]], // 1
[[1, 0], [4, 6], [7, 12]], // 2
[[6, 9]], // 3
[[6, 8]], // 4
[[3, 1], [6, 7], [8, 11]], // 5
[[3, 0], [4, 2], [8, 10], [9, 12]], // 6
[[4, 1], [6, 5], [9, 11]], // 7
[[6, 4]], // 8
[[6, 3]], // 9
[[5, 0], [8, 6], [11, 12]], // 10
[[8, 5], [6, 1], [9, 7]], // 11
[[11, 10], [9, 6], [7, 2]] // 12
];
function hoppers(): void {
const board = new Array<boolean>(13),
MAXJUMP = 11,
HOLE = 6;
let cnt = 0;
board.fill(true);
// ペグの移動
function movePeg(from: number, del: number, to: number): void {
board[from] = false;
board[del] = false;
board[to] = true;
}
// ペグを元に戻す
function backPeg(from: number, del: number, to: number): void {
board[from] = true;
board[del] = true;
board[to] = false;
}
// 移動手順の表示
function printMove(move: [number, number][]): void {
let s = "", prev = -1;
for (let [from, to] of move) {
if (prev == -1) {
s += `[${from}, ${to}`;
} else if (prev == from) {
s += `, ${to}`;
} else {
s += `][${from}, ${to}`;
}
prev = to;
}
s += "]";
console.log(s);
}
// 反復深化
function dfs(jc: number, limit: number, move: [number, number][]): void {
if (jc <= limit) {
if (move.length == MAXJUMP) {
if (board[HOLE]) {
cnt++;
printMove(move);
}
} else {
for (let from = 0; from < board.length; from++) {
if (!board[from]) continue;
for (let [del, to] of jumpTable[from]) {
if (!board[del] || board[to]) continue;
movePeg(from, del, to);
const newJc = from == move[move.length - 1][1] ? jc : jc + 1;
move.push([from, to]);
dfs(newJc, limit, move);
move.pop();
backPeg(from, del, to);
}
}
}
}
}
for (let limit = 2; limit <= MAXJUMP; limit++) {
// 初手を 0 -> 6 に限定
console.log(`----- ${limit} ------`)
movePeg(0, 3, HOLE);
dfs(1, limit, [[0, HOLE]]);
if (cnt > 0) {
console.log(`total = ${cnt}`);
break;
}
}
}
hoppers();
●実行結果
----- 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] total = 18
●マスターマインドの解法
「マスターマインド」は 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] に矛盾しないコードを選択すればいいわけです。
●プログラム
リスト : マスターマインドの解法
// 順列の生成 (ジェネレータ版)
function* genPerm<T>(n: number, xs: T[]): IterableIterator<T[]> {
if (n == 0) {
yield [];
} else {
for (let ys of genPerm(n - 1, xs)) {
for (let x of xs) {
if (ys.indexOf(x) < 0) {
yield ys.concat([x]);
}
}
}
}
}
// bulls を数える
function countBulls(xs: number[], ys: number[]): number {
let c = 0;
for (let i = 0; i < xs.length; i++) {
if (xs[i] == ys[i]) c++;
}
return c;
}
// 同じ数字の個数を数える
function countSameNumber(xs: number[], ys: number[]): number {
let c = 0;
for (let i = 0; i < xs.length; i++) {
if (ys.indexOf(xs[i]) >= 0) c++;
}
return c;
}
// 質問したコードと結果を記録する
class Query {
constructor(private _code: number[], private _bulls: number, private _cows: number) { }
get code(): number[] { return this._code; }
get bulls(): number { return this._bulls; }
get cows(): number { return this._cows; }
}
// 今までの質問と矛盾しないか？
function checkQuery(query: Query[], xs: number[]): boolean {
for (let qs of query) {
const b = countBulls(qs.code, xs);
const c = countSameNumber(qs.code, xs) - b;
if (b != qs.bulls || c != qs.cows) return false;
}
return true;
}
// マスターマインドの解法
function masterMind(answer: number[]): void {
const query: Query[] = [];
let cnt = 0;
for (let code of genPerm(4, [0,1,2,3,4,5,6,7,8,9])) {
if (checkQuery(query, code)) {
const b = countBulls(code, answer);
const c = countSameNumber(code, answer) - b;
query.push(new Query(code, b, c));
console.log(`${++cnt}: ${code}, bulls = ${b}, cows = ${c}`);
if (b == 4) {
console.log("Good Job!!!");
return;
}
}
}
console.log("Oops! maybe bug");
}
masterMind([9,8,7,6]);
masterMind([9,4,3,1]);
●実行結果
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!!!