Category: Algorithm

これのエラー処理に丸一日かかりました。。

fn main() {

    let mut maze = [
        [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
        [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
        [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 9, 9],
        [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
        [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
        [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
        [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
        [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
        [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
        [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
        [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
        [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
    ];

    let dir: [[i32; 2]; 4] = [[1, 0], [0, 1], [-1, 0], [0, -1]];

    let mut p:[i32; 4] = [1, 1, 0, 0]; // x, y, depth, d

    'main: while maze[p[0] as usize][p[1] as usize] != 1 {

        maze[p[0] as usize][p[1] as usize] = 2;

        'sub: for i in 0..4 {
            let mut j: i32 = 3;
            if i != 0 {
                j = (p[3] + i - 1) % 4
            } else if (p[3] - 1) < 0{
                j = (p[3] - 1 + 4) % 4
            } else {
                j = (p[3] - 1) % 4
            }
            println!("j: {}", j);
            println!("p0: {}", p[0]);
            println!("p1: {}", p[1]);
            println!("p2: {}", p[2]);
            println!("p3: {}", p[3]);
            if maze[(p[0] + dir[j as usize][0])as usize][(p[1] + dir[j as usize][1]) as usize] < 2 {
                p[0] += dir[j as usize][0]; // x
                p[1] += dir[j as usize][1]; // y
                p[3] = j as i32;   // d
                p[2] += 1;  // depth
                println!("yes: {}", j);
                println!("< 2 p0: {}", p[0]);
                println!("< 2 p1: {}", p[1]);
                println!("< 2 p2: {}", p[2]);
                println!("< 2 p3: {}", p[3]);
                break 'sub;
            } else if maze[(p[0] + dir[j as usize][0]) as usize][(p[1] + dir[j as usize][1]) as usize] == 2 {
                p[0] += dir[j as usize][0];
                p[1] += dir[j as usize][1];
                p[3] = j as i32;
                p[2] -= 1;
                println!("yes: {}", j);
                println!("= 2 p0: {}", p[0]);
                println!("= 2 p1: {}", p[1]);
                println!("= 2 p2: {}", p[2]);
                println!("= 2 p3: {}", p[3]);
                break 'sub;
            }
        }
    }
    println!("最終: {}", p[2]);
}

// 省略
最終: 28

mutexで見にくいが、やってることは単純で、上下左右ではなく、行けるだけ上、下、左、右に移動して、行けるところがなくなったら、元に戻るというロジック。これも素晴らしいね。

use std::collections::VecDeque;
use std::sync::Mutex;

static maze: Mutex<[[usize; 12]; 12]> = Mutex::new([
    [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
    [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
    [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 9, 9],
    [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
    [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
    [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
    [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
    [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
    [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
    [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
    [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
    [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
]);

fn search(p:[usize; 3]) {

    if maze.lock().unwrap()[p[0]][p[1]] == 1 {
        println!("ゴール:{}-{}", p[0], p[1]); 
        println!("移動回数:{}", p[2]); // z
        return;
    }
    maze.lock().unwrap()[p[0]][p[1]] = 2;

    if maze.lock().unwrap()[p[0] - 1][p[1]] < 2 {
        search([p[0]- 1, p[1], p[2] + 1]);
    }
    if maze.lock().unwrap()[p[0] + 1][p[1]] < 2 {
        search([p[0]+1, p[1], p[2] + 1]);
    }
    if maze.lock().unwrap()[p[0]][p[1] - 1] < 2 {
        search([p[0], p[1] -1, p[2] + 1]);
    }
    if maze.lock().unwrap()[p[0]][p[1] + 1] < 2 {
        search([p[0], p[1] + 1, p[2] + 1]);
    }
    maze.lock().unwrap()[p[0]][p[1]] = 0;
}

fn main() {
    search([1, 1, 0])
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.41s
Running `target/debug/rust`
ゴール:6-10
移動回数:28

壁は9, 既に行ったところは2、行ったことない場所は0、ゴールは1　とする問題設定が素晴らしいね。上下左右のマスをこれから行く場所として追加していくロジックも面白い。

use std::collections::VecDeque;

fn main() {
    let mut maze = [
        [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
        [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
        [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 9, 9],
        [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
        [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
        [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
        [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
        [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
        [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
        [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
        [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
        [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
    ];

    let mut pos: VecDeque<[usize; 3]> = vec![[1, 1, 0]].into();

    while pos.len() > 0 {
        let p = pos.pop_front().unwrap(); // x, y, depth

        if maze[p[0]][p[1]] == 1 {
            println!("ゴール:{}-{}", p[0], p[1]); 
            println!("移動回数:{}", p[2]); // z
            break;
        }
        maze[p[0]][p[1]] = 2;

        if maze[p[0] - 1][p[1]] < 2 {
            pos.push_back([p[0]- 1, p[1], p[2] + 1]);
        }
        if maze[p[0] + 1][p[1]] < 2 {
            pos.push_back([p[0]+1, p[1], p[2] + 1]);
        }
        if maze[p[0]][p[1] - 1] < 2 {
            pos.push_back([p[0], p[1] -1, p[2] + 1]);
        }
        if maze[p[0]][p[1] + 1] < 2 {
            pos.push_back([p[0], p[1] + 1, p[2] + 1]);
        }
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.26s
Running `target/debug/rust`
ゴール:6-10
移動回数:28

### 行きがけ順(上から左下へ)
下のような木構造の場合、左から順に 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 と探索していく。
0
1 2
3 4 5 6
これは、再帰処理を行う。

struct Tree {
    node: Vec<[i32; 2]>,
}

fn search(pos: usize) {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    println!("{}", pos);
    for i in tree.node[pos] {
        if i != 0 {
            search(i.try_into().unwrap());
        }
    }
}

fn main() {
    search(0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s
Running `target/debug/rust`
0
1
3
7
8
4
9
10
2
5
11
12
6
13
14

### 帰りがけ順(子ノード優先して上へ)
下のような木構造の場合、左から順に 3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0 と子ノードから順番に探索していく。一番上が一番最後になる。
0
1 2
3 4 5 6

fn search(pos: usize) {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    for i in tree.node[pos] {
        if i != 0 {
            search(i.try_into().unwrap());
        }
    }
    println!("{}", pos);
}

fn main() {
    search(0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.68s
Running `target/debug/rust`
7
8
3
9
10
4
1
11
12
5
13
14
6
2
0

### 通りがけ順(子ノードから上下上下)
下のような木構造の場合、左から順に 3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6 と子ノードから順番に探索していく。一番右の子ノードが一番最後になる。
0
1 2
3 4 5 6

fn search(pos: usize) {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    if tree.node[pos][0] != 0 && tree.node[pos][1] != 0 {
        search(tree.node[pos][0].try_into().unwrap());
        println!("{}", pos);
        search(tree.node[pos][1].try_into().unwrap());
    } else if tree.node[pos][0] != 0 || tree.node[pos][1] != 0 {
        search(tree.node[pos][0].try_into().unwrap());
        println!("{}", pos);
    } else {
        println!("{}", pos);
    }
}

fn main() {
    search(0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.26s
Running `target/debug/rust`
7
3
8
1
9
4
10
0
11
5
12
2
13
6
14

最初のif文では子ノードがあれば左を再帰処理、自信をprintして右を再帰処理
2つ目のif文ではどちらかに子ノードがあれば左を再帰処理
2つ目のif文では子ノードがないので自身をprint

帰りがけは完全に子ノードからボトムアップだが、通りがけは左からツリーを作っていくような順番だ。

Treeの中から一つだけ探したい場合は、幅優先探索が最も早い。
全ての答えを見つける時、決められた深さまで探索する時は、深さ優先探索がよく使われる。

基本ロジックはわかったので、応用編を試してみたいですな。

幅優先探索は、木構造で横に順番に探索していく。
木構造をプログラムで表現するには、各ノードの下のノードの番号を配列で持つようにする。
例えば 下のような木構造があった場合、
0
1 2
3 4 5 6

0は1, 2を子ノードとして持つので、[1, 2]
1は3, 4を子ノードとして持つので、[3, 4]
2は5, 6を子ノードとして持つので、[5, 6] となる。

use std::collections::VecDeque;

struct Tree {
    node: Vec<[i32; 2]>,
}

fn main() {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    
    let mut data: VecDeque<i32> = [0].into();

    while data.len() > 0 {
        let pos = data.pop_front();
        println!("{:?} ", pos.unwrap());
        for i in tree.node[pos.unwrap() as usize] {
            if i != 0 {
                data.push_back(i);
            }
        }
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

ノードのデータの表現の仕方が勉強になりますね。

fn main() {
    let data = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
    let target = 50;
    binary_search(data, target);
    
}

fn binary_search(data: Vec<u32>, target: u32) {
    let mut left = 0;
    let mut right = data.len() - 1;
    
    while left <= right {
        let mid = (left + right) / 2;
        if data[mid] == target {
            println!("ターゲットは要素の[{}]です。", mid);
            break;
        } else if data[mid] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.13s
Running `target/debug/rust`
ターゲットは要素の[4]です。

これは凄い面白いなあ

fn main() {
    let target = 40;
    let mut flg = format!("{}{}", target, "はデータの中にありません");
    let data = [50, 30, 90, 10, 20, 70, 60, 40, 80];
    for d in data {
        if d == 40 {
            flg = format!("{}{}", target, "はデータの中にあります!");
        }
    }
    println!("{}", flg);
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.56s
Running `target/debug/rust`
40はデータの中にあります!

### 関数を定義
配列だと、data: [u32; 10] というように要素数を指定しなければならないので、Vectorの方が使い勝手が良い。

fn main() {
    let data = vec![50, 30, 90, 10, 20, 70, 60, 40, 80, 55];
    let target = 40;
    linear_search(data, target);
    
}

fn linear_search(data: Vec<u32>, target: u32) {
    let mut flg = format!("{}{}", target, "はデータの中にありません");
    for d in data {
        if d == 40 {
            flg = format!("{}{}", target, "はデータの中にあります!");
        }
    }
    println!("{}", flg);
}

フィボナッチは再起的に計算を行う。

6 の場合は、
6 -> (4,5)
4 -> (2,3)
5 -> (3,4)
2 -> 【1】
3 -> (1, 2) -> 【1】【1】

fn fibonacci(n: u32)-> u32{
    if(n == 1) || (n == 2) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}


fn main() {
    println!("{}", fibonacci(6));
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.12s
Running `target/debug/rust`
8

8の時は21, 10は55となる。
なんか不思議な感じがする。

まず、prime(平方根)を計算する。sqrt()はf64にする必要がある。

fn main() {
    let x = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    for i in x {
        let y = (i as f64).sqrt();
        println!("{}", y);
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.29s
Running `target/debug/rust`
1
1.4142135623730951
1.7320508075688772
2
2.23606797749979
2.449489742783178
2.6457513110645907
2.8284271247461903
3

nが、2から平方根までの値で割り切れれば、素数ではない

fn main() {
    let x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
    for i in x {
        let mut flag = true;
        let prime = (i as f64).sqrt();
        if prime >= 2.0 {
            for j in 2..((prime + 1.0) as u32){
                if i % j == 0 {
                    flag = false;
                    break;
                }
            }
        }
        if flag == true {
            println!("{}は素数です", i);}
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.14s
Running `target/debug/rust`
1は素数です
2は素数です
3は素数です
5は素数です
7は素数です
11は素数です
13は素数です

floatへの変換を書かなければならない分、コードが冗長になるが、もう少しエレガントに書きたいものだ。○○か否かはTrue or Falseが書きやすい。

11を2進数にすると、
11/2 = 5 余り1
5/2 = 2 余り1
2/2 = 1 余り0
1/2 = 0 余り1

余りを先頭に足していく[1101]が答えになる。
それをそのままコードに落とし込む。こういう処理はfor文よりもwhileの方が向いている。なお、基数の値は、2進数から3、4と変えてもきちんと計算できる。

fn main() {
    let mut result = String::new();

    let mut target = 11;
    static cardinal: u32 = 2;
    
    while target >= cardinal {
        let rest = target % cardinal;
        result = format!("{}{}", rest.to_string(), result); 
        target = target / cardinal;
    }
    result = format!("{}{}", target.to_string(), result); 
    println!("{}", result);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.23s
Running `target/debug/rust`
1011

2進数から10進数への変換

fn main() {
    to_cardinal(2, 55);

}

fn from_cardinal(cardinal: u32, t: u32){
    let target:String = t.to_string();
    let digit = target.chars().count();

    let mut result = 0;

    for i in 0..digit {
        let base = cardinal.pow((digit - i - 1).try_into().unwrap());
        let s = target.chars().nth(i).unwrap();
        let num = s.to_digit(10).unwrap() * base;
        result = result + num;
    }
    println!("{}", result);
}

うーん、to_cardinalがなんか違うような気がする
なお、rustには基数変換のライブラリが多数ある模様