皆さんお馴染みのゲーム「三目並べ」で、両者が最善を尽くすと引き分けになることを示すプログラムです。詳しい説明は拙作のページ Puzzle DE Programming 三目並べ をお読みください。
//
// tictactoe.rs : 三目並べ
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
// 駒
#[derive(PartialEq, Copy, Clone)]
enum Piece {
Maru, Batu, Free
}
// 盤面の型
type Board = [Piece; 9];
// 定数
static MAX_VALUE: i32 = 2;
static MIN_VALUE: i32 = -2;
static MARU_WIN: i32 = 1;
static BATU_WIN: i32 = -1;
static DRAW: i32 = 0;
// 盤面
// 0 1 2
// 3 4 5
// 6 7 8
// 勝利の判定
fn check_win(board: &Board) -> i32 {
let line_table = vec![[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]];
let mut result = DRAW;
for ls in line_table {
let p = board[ls[0]];
if p != Piece::Free {
if p == board[ls[1]] && p == board[ls[2]] {
result = if p == Piece::Maru { MARU_WIN } else { BATU_WIN };
break;
}
}
}
result
}
// 先手の思考
fn think_maru(n: usize, board: &mut Board) -> i32 {
let mut value = MIN_VALUE;
for i in 0 .. board.len() {
if board[i] == Piece::Free {
board[i] = Piece::Maru;
let mut v = check_win(board);
if v == DRAW && n < board.len() - 1 {
v = think_batu(n + 1, board);
}
if v > value {
value = v;
}
board[i] = Piece::Free;
}
}
value
}
// 後手の思考
fn think_batu(n: usize, board: &mut Board) -> i32 {
let mut value = MAX_VALUE;
for i in 0 .. board.len() {
if board[i] == Piece::Free {
board[i] = Piece::Batu;
let mut v = check_win(board);
if v == DRAW && n < board.len() - 1 {
v = think_maru(n + 1, board);
}
if v < value {
value = v;
}
board[i] = Piece::Free;
}
}
value
}
fn main() {
let mut board: Board = [Piece::Free; 9];
for i in 0 .. board.len() {
board[i] = Piece::Maru;
println!("{} => {}", i, think_batu(1, &mut board));
board[i] = Piece::Free;
}
}
0 => 0 1 => 0 2 => 0 3 => 0 4 => 0 5 => 0 6 => 0 7 => 0 8 => 0
ところで、ルールを 3 つ並んだほうが負けに変更すると、初手が中央以外は後手必勝になります。プログラムの修正は関数 check_win() の返り値 result を -result に変更するだけです。
0 => -1 1 => -1 2 => -1 3 => -1 4 => 0 5 => -1 6 => -1 7 => -1 8 => -1
15 人の女生徒が毎日 3 人ずつ 5 組に分かれて散歩をするとき、1 週間 (7 日) のうちに、どの女生徒も他のすべての女生徒と 1 回ずつ同じ組になるような組み合わせを作ってください。
出典 : 大村平 (著), 『数理パズルの話』, 日科技連出版社, 1998
「カークマンの 15 人の女生徒」の解法プログラムは 集合のグループ分け で作成したプログラムを改造すると簡単です。
//
// kirkman.rs : カークマンの 15 人の女生徒
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
// 重複チェック
fn check_student(xs: &Vec<usize>, y: usize, chk: &Vec<Vec<usize>>) -> bool {
for x in xs {
if chk[*x].contains(&y) {
return false;
}
}
true
}
// 生徒の追加
fn add_student(xs: &Vec<usize>, y: usize, chk: &mut Vec<Vec<usize>>) {
for x in xs {
chk[*x].push(y);
chk[y].push(*x);
}
}
// 生徒の削除
fn del_student(xs: &Vec<usize>, y: usize, chk: &mut Vec<Vec<usize>>) {
for x in xs {
chk[*x].pop();
chk[y].pop();
}
}
// 生徒 (0 以外の 14 人)
static STUDENT: [usize; 14] = [1,2,3,4,5,6,7,8,9,10,11,12,13,14];
// 解法
fn kirkman(ls: &[usize], a: &mut Vec<Vec<usize>>, b: &mut Vec<Vec<Vec<usize>>>, chk: &mut Vec<Vec<usize>>) {
if ls.len() == 0 {
b.push(a.clone());
if b.len() == 7 {
for xs in b {
println!("{:?}", xs);
}
std::process::exit(0); // 解を一つ見つけたら終了
}
kirkman(&STUDENT, &mut vec![vec![0]], b, chk);
b.pop();
} else {
for i in 0 .. a.len() {
if a[i].len() < 3 && check_student(&a[i], ls[0], chk) {
add_student(&a[i], ls[0], chk);
a[i].push(ls[0]);
kirkman(&ls[1..], a, b, chk);
a[i].pop();
del_student(&a[i], ls[0], chk);
}
}
if a.len() < 5 {
a.push(vec![ls[0]]);
kirkman(&ls[1..], a, b, chk);
a.pop();
}
}
}
fn main() {
let mut chk: Vec<Vec<usize>> = vec![vec![]; 15];
kirkman(&STUDENT, &mut vec![vec![0]], &mut vec![], &mut chk);
}
[[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11], [12, 13, 14]] [[0, 3, 6], [1, 4, 9], [2, 5, 12], [7, 10, 13], [8, 11, 14]] [[0, 4, 13], [1, 3, 14], [2, 7, 11], [5, 8, 10], [6, 9, 12]] [[0, 8, 12], [1, 6, 11], [2, 3, 10], [4, 7, 14], [5, 9, 13]] [[0, 7, 9], [1, 10, 12], [2, 4, 8], [3, 11, 13], [5, 6, 14]] [[0, 5, 11], [1, 8, 13], [2, 9, 14], [3, 7, 12], [4, 6, 10]] [[0, 10, 14], [1, 5, 7], [2, 6, 13], [3, 8, 9], [4, 11, 12]]
「11 パズル」を反復深化と下限値枝刈り法で解くプログラムです。詳しい説明は拙作のページ Ｃ言語超入門: スライドパズル (2) をお読みください。
//
// eleven.rs : 11 パズル
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
// 盤面
// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
//
// 盤面の型
type Board = [usize; 12];
// 距離
static DISTANCE: [[usize; 12]; 12] = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // 0 dummy
[0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5], // 1
[1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4], // 2
[2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3], // 3
[3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2], // 4
[1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4], // 5
[2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3], // 6
[3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2], // 7
[4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1], // 8
[2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3], // 9
[3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2], // 10
[4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1], // 11
];
// 深さ優先探索 (反復深化)
fn dfs(board: &mut Board, goal: &Board, s: usize, adj: &Vec<Vec<usize>>, limit: usize, low: usize, move_piece: &mut Vec<usize>) {
let n = move_piece.len() - 1;
if n == limit {
if *board == *goal {
println!("{:?}", &move_piece[1..]);
std::process::exit(0); // 解を一つ見つけたら終了
}
} else {
for x in &adj[s] {
let p = board[*x];
if move_piece[n] == p { continue; }
move_piece.push(p);
board[s] = p;
board[*x] = 0;
let new_low = low - DISTANCE[p][*x] + DISTANCE[p][s];
if new_low + n <= limit {
dfs(board, goal, *x, adj, limit, new_low, move_piece);
}
board[*x] = p;
board[s] = 0;
move_piece.pop();
}
}
}
fn main() {
// 隣接リスト
let adjacent: Vec<Vec<usize>> = vec![
vec![1, 4], // 0
vec![0, 2, 5], // 1
vec![1, 3, 6], // 2
vec![2, 7], // 3
vec![0, 5, 8], // 4
vec![1, 4, 6, 9], // 5
vec![2, 5, 7, 10], // 6
vec![3, 6, 11], // 7
vec![4, 9], // 8
vec![5, 8, 10], // 9
vec![6, 9, 11], // 10
vec![7, 10] // 11
];
let mut start: Board = [0, 3, 2, 1, 8, 7, 6, 5, 4, 11, 10, 9];
let goal: Board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0];
let parity = [
true, false, true, false,
false, true, false, true,
true, false, true, false,
];
let mut lower = 0;
for i in 0 .. 12 {
lower += DISTANCE[start[i]][i];
}
if (parity[0] == parity[11] && lower % 2 != 0) ||
(parity[0] != parity[11] && lower % 2 == 0) {
lower += 1;
}
let mut limit = lower;
while limit <= 53 {
println!("----- {} -----", limit);
dfs(&mut start, &goal, 0, &adjacent, limit, lower, &mut vec![0]);
limit += 2;
}
}
----- 23 ----- ----- 25 ----- ----- 27 ----- ----- 29 ----- ----- 31 ----- ----- 33 ----- ----- 35 ----- ----- 37 ----- ----- 39 ----- ----- 41 ----- ----- 43 ----- ----- 45 ----- ----- 47 ----- ----- 49 ----- ----- 51 ----- ----- 53 ----- [3, 2, 6, 5, 1, 6, 2, 7, 5, 1, 9, 10, 11, 4, 8, 5, 1, 9, 10, 11, 4, 8, 5, 1, 9, 10, 11, 4, 8, 9, 10, 2, 7, 3, 1, 5, 9, 10, 2, 11, 4, 8, 11, 7, 6, 4, 7, 6, 3, 2, 6, 7, 8]
「ラテン方陣」は数独の枠の条件を無くした方陣です。ラテン方陣の定義を 参考文献 より引用します。
『ラテン方陣を一般的にいうなら、n 行 n 列の正方形の枡に n 種類の記号を n 個ずつ配列して、各行各列に記号の重複のないものを n 次のラテン方陣というのです。』
このラテン方陣をパズルに応用したものが数独というわけです。
簡単な例を示しましょう。3 次のラテン方陣は次に示す 12 通りになります。
0 1 2 0 1 2 0 2 1 0 2 1 1 0 2 1 0 2
1 2 0 2 0 1 1 0 2 2 1 0 0 2 1 2 1 0
2 0 1 1 2 0 2 1 0 1 0 2 2 1 0 0 2 1
標準形
1 2 0 1 2 0 2 0 1 2 0 1 2 1 0 2 1 0
0 1 2 2 0 1 0 1 2 1 2 0 0 2 1 1 0 2
2 0 1 0 1 2 1 2 0 0 1 2 1 0 2 0 2 1
図 : 3 次のラテン方陣
この中で、最初の行と列の要素を昇順に並べたものを「標準形」といいます。3 次のラテン方陣の場合、標準形は 1 種類しかありません。ラテン方陣は任意の行を交換する、または任意の列を交換してもラテン方陣になります。3 次のラテン方陣の場合、標準形から行または列を交換することで、残りの 11 種類のラテン方陣を生成することができます。
今回は標準形ラテン方陣の総数を求めるプログラムを作ります。
//
// latin.rs : ラテン方陣
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
use std::time::Instant;
static mut CNT: i32 = 0;
fn check(board: &Vec<Vec<usize>>, x: usize, y: usize, m: usize) -> bool {
for i in 0 .. board.len() {
if board[x][i] == m || board[i][y] == m {
return false;
}
}
true
}
fn latin(board: &mut Vec<Vec<usize>>, x: usize, y: usize) {
let n = board.len();
if y == n {
unsafe { CNT += 1; }
} else if x == n {
latin(board, 1, y + 1);
} else {
for m in 1 .. n + 1 {
if check(board, x, y, m) {
board[x][y] = m;
latin(board, x + 1, y);
board[x][y] = 0;
}
}
}
}
fn main() {
for n in 3 .. 8 {
let mut a: Vec<Vec<usize>> = vec![vec![0; n]; n];
// 初期化
for m in 0 .. n {
a[0][m] = m + 1;
a[m][0] = m + 1;
}
let start = Instant::now();
unsafe { CNT = 0; }
latin(&mut a, 1, 1);
unsafe { println!("{}", CNT); }
let end = start.elapsed();
println!("{}.{:03}秒経過しました。", end.as_secs(), end.subsec_nanos() / 1_000_000);
}
}
プログラムは簡単なので説明は割愛します。実行結果は次のようになりました。
1 0.000秒経過しました。 4 0.000秒経過しました。 56 0.000秒経過しました。 9408 0.011秒経過しました。 16942080 30.524秒経過しました。 実行環境 : Rust 1.62.1, Ubuntu 18.04 (WSL), Intel Core i5-6200U 2.30GHz
単純なプログラムなので実行時間は遅いですね。高次の標準形ラテン方陣の総数は、簡単に求めることができない非常にハードな問題だといわれています。興味のある方は挑戦してみてください。
「循環配列 (リングバッファ)」によるキューの実装です。アルゴリズムの詳しい説明は拙作のページ お気楽Ｃ++プログラミング超入門: キュー をお読みください。なお、Rust の標準ライブラリには VecDequeu<T> が用意されているので、私たちがキューを自作する必要はありませんが、Rust のお勉強ということで、なるべく unsafe な機能を使わないでプログラムを作ってみましょう。
| 名前 | 機能 |
|---|---|
| fn new(n: usize) -> Queue<T> | 指定した大きさのキューを作る (コンストラクタ) |
| fn dequeue(&mut self) -> Option<T> | キューからデータを取り出して返す |
| fn enqueue(&mut self, x: T) -> bool | キューにデータを追加する |
| fn front(&self) -> Option<&T> | キューの先頭データの参照を返す |
| fn is_empty(&self) -> bool | キューが空の場合は true を、そうでなければ false を返す |
| fn is_full(&self) -> bool | キューが満杯の場合は true を、そうでなければ false を返す |
| fn len(&self) -> usize | キューに格納されたデータ数を返す |
| fn clear(&mut self) | キューを空にする |
//
// queue.rs : キュー (リングバッファ) の簡単な実装
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
// キュー
struct Queue<T> {
buff: Vec<Option<T>>,
front: usize,
rear: usize,
size: usize
}
// キューのメソッド
impl<T> Queue<T> {
// キューの生成
fn new(n: usize) -> Queue<T> {
let mut b = Vec::new();
for _ in 0 .. n { b.push(None); }
Queue {
buff: b, // vec![None; n] で初期化すると T に Clone の指定が必要になる
front: 0,
rear: 0,
size: 0
}
}
// データの挿入
fn enqueue(&mut self, x: T) -> bool {
if self.size == self.buff.len() {
return false;
}
self.buff[self.rear] = Some(x);
self.rear += 1;
self.size += 1;
if self.rear == self.buff.len() {
self.rear = 0;
}
true
}
// データの取り出し
fn dequeue(&mut self) -> Option<T> {
if self.size == 0 {
return None;
}
let x = self.buff[self.front].take();
self.front += 1;
self.size -= 1;
if self.front == self.buff.len() {
self.front = 0;
}
x
}
// 先頭データの参照を返す
fn front(&self) -> Option<&T> {
if self.size == 0 {
None
} else {
self.buff[self.front].as_ref()
}
}
// 要素数を返す
fn len(&self) -> usize { self.size }
// キューは空か？
fn is_empty(&self) -> bool { self.size == 0 }
// キューは満杯か？
fn is_full(&self) -> bool { self.size == self.buff.len() }
// キューを空にする
fn clear(&mut self) {
self.front = 0;
self.rear = 0;
self.size = 0;
for i in 0 .. self.buff.len() {
self.buff[i] = None;
}
}
}
// 簡単なテスト
fn main() {
let mut que = Queue::new(10);
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 5 {
que.enqueue(i);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
while !que.is_empty() {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 10 {
que.enqueue(i + 10);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for _ in 0 .. 8 {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
que.clear();
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
}
true false 0 false false 5 Some(0) Some(0) Some(1) Some(1) Some(2) Some(2) Some(3) Some(3) Some(4) Some(4) true false 0 false true 10 Some(10) Some(10) Some(11) Some(11) Some(12) Some(12) Some(13) Some(13) Some(14) Some(14) Some(15) Some(15) Some(16) Some(16) Some(17) Some(17) false false 2 true false 0
連結リストを使ったキューの実装です。メソッドはリングバッファと同じです。アルゴリズムの詳しい説明は拙作のページ お気楽Ｃ++プログラミング超入門: キュー をお読みください。なお、Rust の標準ライブラリには LinkedList<T> が用意されているので、私たちがキューを自作する必要はありませんが、Rust のお勉強ということで、なるべく unsafe な機能を使わないでプログラムを作ってみましょう。
//
// queue1.rs : 連結リストによるキューの実装
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
use std::rc::Rc;
use std::cell::RefCell;
// 連結リスト
struct List<T> {
car: T,
cdr: RefCell<Link<T>>
}
type Link<T> = Option<Rc<List<T>>>;
/*
* 連結リストを次のように定義する方法もある
*
* struct List<T> {
* car: T,
* cdr: Link<T>
* }
*
* type Link<T> = Option<Rc<RefCell<List<T>>>>;
*
* 参考 URL : Learning Rust With Entirely Too Many Linked Lists
*
*/
// キュー
struct Queue<T> {
front: Link<T>,
rear: Link<T>,
size: usize
}
// キューのメソッド
impl<T> Queue<T> {
// キューの生成
fn new() -> Queue<T> {
Queue { front: None, rear: None, size: 0 }
}
// データの挿入
fn enqueue(&mut self, item: T) {
let new_node = Rc::new(List {car: item, cdr: RefCell::new(None)});
if self.size == 0 {
self.front = Some(new_node.clone());
} else {
let node = self.rear.take().unwrap();
let mut ptr = node.cdr.borrow_mut();
*ptr = Some(new_node.clone());
}
self.rear = Some(new_node);
self.size += 1;
}
// データの取り出し
fn dequeue(&mut self) -> Option<T> {
self.front.take().map(|node| {
if self.size == 1 {
self.rear = None; // リファレンスカウントを -1 するため
}
match Rc::try_unwrap(node) {
Ok(node) => {
self.front = node.cdr.into_inner();
self.size -= 1;
node.car
},
Err(_) => panic!("dequeue error")
}
})
}
// 先頭要素の参照を返す
fn front(&self) -> Option<&T> {
self.front.as_ref().map(|node| {
&node.car
})
}
// キューの要素数を求める
fn len(&self) -> usize { self.size }
// キューは空か？
fn is_empty(&self) -> bool { self.size == 0 }
// キューは満杯か？
fn is_full(&self) -> bool { false }
// キューを空にする
fn clear(&mut self) {
self.front = None;
self.rear = None;
self.size = 0;
}
}
// 簡単なテスト
fn main() {
let mut que = Queue::new();
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 5 {
que.enqueue(i);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
while !que.is_empty() {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 10 {
que.enqueue(i + 10);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for _ in 0 .. 8 {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
que.clear();
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
}
true false 0 false false 5 Some(0) Some(0) Some(1) Some(1) Some(2) Some(2) Some(3) Some(3) Some(4) Some(4) true false 0 false false 10 Some(10) Some(10) Some(11) Some(11) Some(12) Some(12) Some(13) Some(13) Some(14) Some(14) Some(15) Some(15) Some(16) Some(16) Some(17) Some(17) false false 2 true false 0
「循環配列 (リングバッファ)」による両端キュー (ディーキュー, deque) の実装です。アルゴリズムの詳しい説明は拙作のページ お気楽Ｃ++プログラミング超入門: キュー をお読みください。なお、Rust の標準ライブラリには VecDeque<T> が用意されているので、私たちが両端キューを自作する必要はありません。Rust のお勉強ということで、なるべく unsafe な機能を使わないでプログラムを作ってみましょう。
| メソッド名 | 機能 |
|---|---|
| fn new(n: usize) -> Deque<T> | 指定した大きさのディーキューを作る (コンストラクタ) |
| fn push_front(&mut self, x: T) -> bool | 先頭にデータを追加する |
| fn push_back(&mut self, x: T) -> bool | 末尾にデータを追加する |
| fn pop_front(&mut self) -> Option<T> | 先頭からデータを取り出す |
| fn pop_back(&mut self) -> Option<T> | 末尾からデータを取り出す |
| fn front(&self) -> Option<&T> | 先頭データへの参照を返す |
| fn back(&self) -> Option<&T> | 末尾データへの参照を返す |
| fn len(&self) -> usize | ディーキューの要素数を返す |
| fn is_empty(&self) -> bool | ディーキューが空ならば true を返す |
| fn is_full(&self) -> bool | ディーキューが満杯ならば true を返す |
| fn clear(&mut self) | ディーキューを空にする |
//
// deque.rs : 両端キュー (リングバッファ) の簡単な実装
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
// ディーキュー
struct Deque<T> {
buff: Vec<Option<T>>,
front: usize,
rear: usize,
size: usize
}
// ディーキューのメソッド
impl<T> Deque<T> {
// ディーキューの生成
fn new(n: usize) -> Deque<T> {
let mut b = Vec::new();
for _ in 0 .. n { b.push(None); }
Deque {
buff: b, front: 0, rear: 0, size: 0
}
}
// 末尾にデータを挿入
fn push_back(&mut self, x: T) -> bool {
if self.buff.len() == self.size {
return false;
}
self.buff[self.rear] = Some(x);
self.rear += 1;
self.size += 1;
if self.rear == self.buff.len() { self.rear = 0; }
true
}
// 先頭からデータを取り出す
fn pop_front(&mut self) -> Option<T> {
if self.size == 0 {
return None;
}
let x = self.buff[self.front].take();
self.front += 1;
self.size -= 1;
if self.front == self.buff.len() {
self.front = 0;
}
x
}
// 先頭にデータを挿入
fn push_front(&mut self, x: T) -> bool {
if self.buff.len() == self.size {
return false;
}
if self.front == 0 {
self.front = self.buff.len() - 1;
} else {
self.front -= 1;
}
self.size += 1;
self.buff[self.front] = Some(x);
true
}
// 末尾からデータを取り出す
fn pop_back(&mut self) -> Option<T> {
if self.size == 0 {
return None;
}
if self.rear == 0 {
self.rear = self.buff.len() - 1;
} else {
self.rear -= 1;
}
self.size -= 1;
self.buff[self.rear].take()
}
// 先頭データへの参照を返す
fn front(&self) -> Option<&T> {
if self.size == 0 {
None
} else {
self.buff[self.front].as_ref()
}
}
// 末尾データへの参照を返す
fn back(&self) -> Option<&T> {
if self.size == 0 {
None
} else {
let i = if self.rear == 0 { self.buff.len() - 1 } else { self.rear - 1 };
self.buff[i].as_ref()
}
}
// 要素数を返す
fn len(&self) -> usize { self.size }
// ディーキューは空か？
fn is_empty(&self) -> bool { self.size == 0 }
// ディーキューは満杯か？
fn is_full(&self) -> bool { self.size == self.buff.len() }
// ディーキューを空にする
fn clear(&mut self) {
self.front = 0;
self.rear = 0;
self.size = 0;
for i in 0 .. self.buff.len() {
self.buff[i] = None;
}
}
}
// 簡単なテスト
fn main() {
let mut deq = Deque::new(8);
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
for i in 0 .. 4 {
deq.push_back(i);
deq.push_front(i + 10);
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
println!("{:?}", deq.back());
println!("{:?}", deq.front());
for _ in 0 .. 3 {
println!("{:?}", deq.pop_back());
println!("{:?}", deq.pop_front());
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
deq.clear();
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
}
0 true false 8 false true Some(3) Some(13) Some(3) Some(13) Some(2) Some(12) Some(1) Some(11) 2 false false 0 true false
双方向リストによる両端キュー (ディーキュー, deque) の実装です。メソッドはリングバッファと同じです。双方向リストは循環リストによる実装方法を拙作のページ Algorithms with Python 連結リストとキュー で説明していますが、このプログラムは循環リストを使っていません。実装方法がちょっと異なるので注意してください。なお、Rust の標準ライブラリには LinkedList<T> が用意されているので、私たちが両端キューを自作する必要はありません。Rust のお勉強ということで、なるべく unsafe な機能を使わないでプログラムを作ってみましょう。
//
// deque1.rs : 双方向リストによる両端キューの実装
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
use std::rc::Rc;
use std::cell::RefCell;
// 双方向リスト
struct List<T> {
item: T,
prev: RefCell<Link<T>>,
next: RefCell<Link<T>>
}
type Link<T> = Option<Rc<List<T>>>;
/*
* 双方向リストを次のように定義する方法もある
*
* struct List<T> {
* item: T,
* prev: Link<T>,
* next: Link<T>
* }
*
* type Link<T> = Option<Rc<RefCell<List<T>>>>;
*
* 参考 URL : Learning Rust With Entirely Too Many Linked Lists
*
*/
// キュー
struct Deque<T> {
front: Link<T>,
rear: Link<T>,
size: usize
}
// キューのメソッド
impl<T> Deque<T> {
// キューの生成
fn new() -> Deque<T> {
Deque { front: None, rear: None, size: 0 }
}
// 末尾にデータを挿入
fn push_back(&mut self, x: T) {
let new_node = Rc::new(List {item: x, prev: RefCell::new(None), next: RefCell::new(None)});
if self.size == 0 {
self.front = Some(new_node.clone());
} else {
let node = self.rear.take().unwrap();
let mut ptr1 = node.next.borrow_mut();
*ptr1 = Some(new_node.clone());
let mut ptr2 = new_node.prev.borrow_mut();
*ptr2 = Some(node.clone());
}
self.rear = Some(new_node);
self.size += 1;
}
// 先頭にデータを挿入
fn push_front(&mut self, x: T) {
let new_node = Rc::new(List {item: x, prev: RefCell::new(None), next: RefCell::new(None)});
if self.size == 0 {
self.rear = Some(new_node.clone());
} else {
let node = self.front.take().unwrap();
let mut ptr1 = node.prev.borrow_mut();
*ptr1 = Some(new_node.clone());
let mut ptr2 = new_node.next.borrow_mut();
*ptr2 = Some(node.clone());
}
self.front = Some(new_node);
self.size += 1;
}
// 先頭からデータを取得する
fn pop_front(&mut self) -> Option<T> {
self.front.take().map(|node| {
if self.size == 1 {
self.rear = None; // リファレンスカウントを -1 するため
} else {
// next の prev を None に書き換える
let ptr0 = node.next.borrow();
let ptr1 = ptr0.as_ref().unwrap();
let mut ptr2 = ptr1.prev.borrow_mut();
*ptr2 = None;
}
match Rc::try_unwrap(node) {
Ok(node) => {
self.front = node.next.into_inner();
self.size -= 1;
node.item
},
Err(_) => panic!("pop_front error")
}
})
}
// 末尾からデータを取得する
fn pop_back(&mut self) -> Option<T> {
self.rear.take().map(|node| {
if self.size == 1 {
self.front = None; // リファレンスカウントを -1 するため
} else {
// prev の next を None に書き換える
let ptr0 = node.prev.borrow();
let ptr1 = ptr0.as_ref().unwrap();
let mut ptr2 = ptr1.next.borrow_mut();
*ptr2 = None;
}
match Rc::try_unwrap(node) {
Ok(node) => {
self.rear = node.prev.into_inner();
self.size -= 1;
node.item
},
Err(_) => panic!("pop_back error")
}
})
}
// 先頭要素の参照を返す
fn front(&self) -> Option<&T> {
self.front.as_ref().map(|node| {
&node.item
})
}
// 末尾要素の参照を返す
fn back(&self) -> Option<&T> {
self.rear.as_ref().map(|node| {
&node.item
})
}
// キューの要素数を求める
fn len(&self) -> usize { self.size }
// キューは空か？
fn is_empty(&self) -> bool { self.size == 0 }
// キューは満杯か？
fn is_full(&self) -> bool { false }
// キューを空にする
fn clear(&mut self) {
while !self.is_empty() { self.pop_front(); }
}
}
// Deque が drop されたときは双方向リストも drop する
impl<T> Drop for Deque<T> {
fn drop(&mut self) { self.clear(); }
}
fn main() {
let mut deq = Deque::new();
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
for i in 0 .. 4 {
deq.push_back(i);
deq.push_front(i + 10);
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
println!("{:?}", deq.back());
println!("{:?}", deq.front());
for _ in 0 .. 3 {
println!("{:?}", deq.pop_back());
println!("{:?}", deq.pop_front());
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
deq.clear();
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
}
0 true false 8 false false Some(3) Some(13) Some(3) Some(13) Some(2) Some(12) Some(1) Some(11) 2 false false 0 true false
ハッシュ表 (オープンアドレス法) の簡単な実装です。Rust の標準ライブラリには HashMap (HashSet) が用意されているので、私たちがハッシュ表を作成する必要はありませんが、Rust のお勉強ということで、あえてプログラムを作ってみましょう。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python ハッシュ法 をお読みくださいませ。
| 名前 | 機能 |
|---|---|
| fn new(n: usize) -> HashTable<K, V> | 大きさ n のハッシュ表を生成する |
| fn contains_key(&self, key: &K) -> bool | ハッシュ表にキーがあれば true を返す |
| fn get(&self, key: &K) -> Option<&V> | キーに対応する値の参照を返す |
| fn insert(&mut self, key: K, value: V) -> bool | ハッシュ表にキーと値を登録する |
| fn remove(&mut self, key: &K) -> bool | ハッシュ表からキーと値を削除する |
| fn len(&self) -> usize | ハッシュ表の要素数を返す |
| fn is_empty(&self) -> bool | ハッシュ表が空であれば true を返す |
| fn is_full(&self) -> bool | ハッシュ表が満杯であれば true を返す |
| fn clear(&mut self) | ハッシュ表を空にする |
//
// hash.rs : ハッシュ表 (オープンアドレス法)
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
// ハッシュ表の要素
enum HashItem<K: Hash + PartialEq + Eq, V> {
Empty,
Delete,
Item(K, V)
}
use HashItem::*;
// ハッシュ表
struct HashTable<K: Hash + PartialEq + Eq, V> {
table: Vec<HashItem<K, V>>,
limit: usize,
size: usize
}
// メソッドの定義
impl<K: Hash + PartialEq + Eq, V> HashTable<K, V> {
// ハッシュ表の生成
fn new(n: usize) -> HashTable<K, V> {
let mut ht = Vec::new();
// 10007 は素数
for _ in 0 .. n { ht.push(Empty); }
HashTable { table: ht, limit: n, size: 0 }
}
// インデックスの計算
fn get_index(&self, key: &K) -> usize {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
hasher.finish() as usize % self.limit
}
// キーのインデックスを求める
fn get_key_index(&self, key: &K) -> Option<usize> {
let mut i = self.get_index(key);
let mut cnt = 0;
while cnt < self.limit {
match &self.table[i] {
&Empty => return None,
&Item(ref k, _) if key == k => return Some(i),
_ => (),
}
cnt += 1;
i += 1;
if i == self.limit { i = 0; }
}
None
}
// データの有無を調べる
fn contains_key(&self, key: &K) -> bool {
self.get_key_index(key).is_some()
}
// キーに対応する値を求める
fn get(&self, key: &K) -> Option<&V> {
match self.get_key_index(key) {
None => None,
Some(i) => match &self.table[i] {
&Item(_, ref v) => Some(v),
_ => None
}
}
}
// データの挿入
fn insert(&mut self, key: K, value: V) -> bool {
let mut i = self.get_index(&key);
let mut cnt = 0;
while cnt < self.limit {
let p = &mut self.table[i];
match p {
&mut Empty | &mut Delete => {
*p = Item(key, value);
self.size += 1;
return true;
},
&mut Item(ref k, ref mut v) if *k == key => {
*v = value;
return true;
},
_ => ()
}
cnt += 1;
i += 1;
if i == self.limit { i = 0; }
}
false
}
// データの削除
fn remove(&mut self, key: &K) -> bool {
match self.get_key_index(key) {
None => false,
Some(i) => {
self.table[i] = Delete;
self.size -= 1;
true
}
}
}
// 要素数を返す
fn len(&self) -> usize { self.size }
// ハッシュ表は空か？
fn is_empty(&self) -> bool { self.size == 0 }
// ハッシュ表は満杯か？
fn is_full(&self) -> bool { self.size == self.table.len() }
// ハッシュ表を空にする
fn clear(&mut self) {
for i in 0 .. self.table.len() { self.table[i] = Empty; }
self.size = 0;
}
}
#[derive(Hash, PartialEq, Eq)]
struct Foo {
num: i32
}
// 簡単なテスト
fn main() {
let mut ht: HashTable<Foo, i32> = HashTable::new(11);
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
for x in 1 .. 12 {
ht.insert(Foo { num: x }, x * 10);
}
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
for x in 0 .. 13 {
let key = Foo { num: x };
println!("{}", ht.contains_key(&key));
println!("{:?}", ht.get(&key));
println!("{}", ht.remove(&key));
println!("{}", ht.contains_key(&key));
}
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
for x in 0 .. 11 {
ht.insert(Foo { num: x }, x * 10);
}
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
ht.clear();
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
}
0 true false 11 false true false None false false true Some(10) true false true Some(20) true false true Some(30) true false true Some(40) true false true Some(50) true false true Some(60) true false true Some(70) true false true Some(80) true false true Some(90) true false true Some(100) true false true Some(110) true false false None false false 0 true false 11 false true 0 true false
ハッシュ表 (チェイン法) の簡単な実装です。メソッドはオープンアドレス法と同じです。Rust の標準ライブラリには HashMap (HashSet) が用意されているので、私たちがハッシュ表を作成する必要はありませんが、Rust のお勉強ということで、あえてプログラムを作ってみましょう。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python ハッシュ法 をお読みくださいませ。
//
// hash1.rs : ハッシュ表 (チェイン法)
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
// 連結リスト
enum List<K: Hash + PartialEq + Eq, V> {
Nil,
Cell(K, V, Box<List<K, V>>)
}
use List::*;
impl<K: Hash + PartialEq + Eq, V> List<K, V> {
// リストの生成
fn new(key: K, value: V, node: List<K, V>) -> List<K, V> {
Cell(key, value, Box::new(node))
}
// キーに対応する値の参照を返す (immutable)
fn get(&self, key: &K) -> Option<&V> {
let mut node = self;
loop {
match *node {
Cell(ref k, ref v, _) if k == key => return Some(v),
Cell(_, _, ref node1) => node = &node1,
_ => return None
}
}
}
// キーに対応する値の参照を返す (mutable)
fn get_mut(&mut self, key: &K) -> Option<&mut V> {
match *self {
Cell(ref k, ref mut v, _) if k == key => Some(v),
Cell(_, _, ref mut node1) => node1.get_mut(key),
_ => None
}
}
// キーを格納しているリストを削除する
fn remove(&mut self, key: &K) -> bool {
let mut node = std::mem::replace(self, Nil);
match node {
Cell(ref k, _, ref mut node1) if k == key => {
let node2 = std::mem::replace(node1.as_mut(), Nil);
*self = node2;
return true;
}
_ => *self = node // 元に戻す
}
match *self {
Cell(_, _, ref mut node1) => node1.as_mut().remove(key),
_ => false
}
}
}
// ハッシュ表
struct HashTable<K: Hash + PartialEq + Eq, V> {
table: Vec<List<K, V>>,
limit: usize,
size: usize
}
// ハッシュ表のメソッド
impl<K: Hash + PartialEq + Eq, V> HashTable<K, V> {
// ハッシュ表の生成
fn new(n: usize) -> HashTable<K, V> {
let mut ht = Vec::new();
for _ in 0 .. n { ht.push(Nil); }
HashTable { table: ht, limit: n, size: 0 }
}
// キーのインデックスを求める
fn get_index(&self, key: &K) -> usize {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
hasher.finish() as usize % self.limit
}
// キーの有無をチェック
fn contains_key(&self, key: &K) -> bool {
self.table[self.get_index(key)].get(key).is_some()
}
// キーに対応する値の参照を返す
fn get(&self, key: &K) -> Option<&V> {
self.table[self.get_index(key)].get(key)
}
// データの挿入
fn insert(&mut self, key: K, value: V) {
let i = self.get_index(&key);
{
match self.table[i].get_mut(&key) {
Some(p) => { *p = value; self.size += 1; return; },
_ => ()
}
}
// 先頭に追加
let next = std::mem::replace(&mut self.table[i], Nil);
self.table[i] = List::new(key, value, next);
self.size += 1;
}
// データの削除
fn remove(&mut self, key: &K) -> bool {
let i = self.get_index(&key);
if self.table[i].remove(key) {
self.size -= 1;
true
} else {
false
}
}
// 要素数を返す
fn len(&self) -> usize { self.size }
// ハッシュ表は空か？
fn is_empty(&self) -> bool { self.size == 0 }
// ハッシュ表は満杯か？ (常に false を返す)
fn is_full(&self) -> bool { false }
// ハッシュ表を空にする
fn clear(&mut self) {
for i in 0 .. self.limit {
self.table[i] = Nil;
}
self.size = 0;
}
}
#[derive(Hash, PartialEq, Eq)]
struct Foo {
num: i32
}
fn main() {
let mut ht: HashTable<Foo, i32> = HashTable::new(7);
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
for x in 1 .. 12 {
ht.insert(Foo { num: x }, x * 10);
}
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
for x in 0 .. 13 {
let key = Foo { num: x };
println!("{}", ht.contains_key(&key));
println!("{:?}", ht.get(&key));
println!("{}", ht.remove(&key));
println!("{}", ht.contains_key(&key));
}
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
for x in 0 .. 11 {
ht.insert(Foo { num: x }, x * 10);
}
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
ht.clear();
println!("{}", ht.len());
println!("{}", ht.is_empty());
println!("{}", ht.is_full());
}
0 true false 11 false false false None false false true Some(10) true false true Some(20) true false true Some(30) true false true Some(40) true false true Some(50) true false true Some(60) true false true Some(70) true false true Some(80) true false true Some(90) true false true Some(100) true false true Some(110) true false false None false false 0 true false 11 false false 0 true false