Category: Rust

挿入ソートも n * (n – 1) / 2 の計算量になる。
対象データを一時領域に確保しておき、値が大きかどうかを判定して、大きい場合は入れ替えるという作業を繰り返す。
usizeは-にならないため、 j== 0の時は判定しています。

fn main() {
    let mut data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13];

    for i in 1..data.len() {
        let temp = data[i];
        let mut j = i - 1;
  
        while (j >= 0) && (data[j] > temp) {
            data[j + 1] = data[j];
            if j == 0 {
                break;
            }
            j -= 1;
        }
        if j == 0 && (data[j] > temp) {
            data[0] = temp;
        } else {
            data[j + 1] = temp;
        }
        println!("sorted data:{:?}", data);
    }
    println!("sorted data:{:?}", data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.52s
Running `target/debug/rust`
sorted data:[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sorted data:[4, 6, 15, 2, 8, 5, 11, 9, 7, 13]
sorted data:[2, 4, 6, 15, 8, 5, 11, 9, 7, 13]
sorted data:[2, 4, 6, 8, 15, 5, 11, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 15, 11, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 11, 15, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 9, 11, 15, 7, 13]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 15, 13]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

途中経過を見ると美しいが、これも計算量が多くなる模様。

use rand::Rng;
use std::cmp::Ordering;

static goal:[i32; 8] = [ 0b111000000, 0b000111000, 0b000000111, 0b100100100,
            0b010010010, 0b001001001, 0b100010001, 0b001010100];

fn check(player: i32) -> bool {
    for mask in goal {
        if player & mask == mask {
            return true
        }
    }
    return false 
}

fn minmax(p1: i32, p2: i32, turn: bool) -> i32 {
    if check(p2) {
        if turn {
            return 1
        } else {
            return -1
        }
    }
    let board: i32 = p1 | p2;
    if board == 0b111111111{
        return 0
    }

    let mut w = Vec::new();
    for i in 0..9 {
        if board & (1 << i) == 0 {
            w.push(i);
        }
    }

    let mut k = Vec::new();
    if turn {
        for i in w {
           k.push(minmax(p2, p1 | (1 << i), !turn))
        }
        return *k.iter().min().unwrap();
    } else {
        for i in w {
            k.push(minmax(p2, p1 | (1 << i), !turn))
        }
        return *k.iter().max().unwrap();
    }
    

}

fn play(p1: i32, p2: i32, turn: bool) {
    if check(p2) {
        println!("{:09b}, {:09b}", p1, p2);
        return
    } 

    let board: i32 = p1 | p2;
    if board == 0b111111111{
        println!("{:09b}, {:09b}", p1, p2);
        return
    }
    let mut w = Vec::new();
    for i in 0..9 {
        if board & (1 << i) == 0 {
            w.push(i);
        }
    }

    let mut r  = Vec::new();
    for i in w.clone() {
        r.push(minmax(p2, p1 | (1 << i), true))
    }
    let n = r.iter()
        .enumerate()
        .max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(Ordering::Equal))
        .map(|(index, _)| index).unwrap();
    let j = w[n];
    play(p2, p1 | (1 << j), !turn);
}

fn main() {
    play(0, 0, true);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.32s
Running `target/debug/rust`
001110010, 110001101

う、なんか違うな…

    let mut rnd = rand::thread_rng();
    let k = rnd.gen_range(1..n);
    let j = w[k];

このようにすると、ランダム性が出る。。

マスを0と1で表現して、2進法の加算で判定する。

fn main() {

    println!("{:09b}", 0b111000000 & 0b000111111);
    println!("{:09b}", 0b111000000 & 0b101100010);
    println!("{:09b}", 0b111000000 & 0b111000010);
}

000000000
101000000
111000000

ちなみに、0b111000000など2進数の型はi32

use rand::Rng;

static goal:[i32; 8] = [ 0b111000000, 0b000111000, 0b000000111, 0b100100100,
            0b010010010, 0b001001001, 0b100010001, 0b001010100];

fn check(player: i32) -> bool {
    for mask in goal {
        if player & mask == mask {
            return true
        }
    }
    return false 
}

fn play(p1: i32, p2: i32) {
    if check(p2) {
        println!("{:09b}, {:09b}", p1, p2);
        return
    } 

    let board: i32 = p1 | p2;
    if board == 0b111111111{
        println!("{:09b}, {:09b}", p1, p2);
        return
    }
    let mut w = Vec::new();
    for i in 0..9 {
        if board & (1 << i) == 0 {
            w.push(i);
        }
    }
    let n = w.len() + 1;
    let mut rnd = rand::thread_rng();
    let r = rnd.gen_range(1..n);
    play(p2, p1 | (1 << r));
}

fn main() {
    play(0, 0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.30s
Running `target/debug/rust`
010001000, 001111000

これはさっぱりわからん…

ファイル、フォルダの取得
fs::read_dir()がファイルの一覧取得

use std::error::Error;
use std::fs;
use std::path;

pub fn read_dir(path: &str) -> Result<Vec<path::PathBuf>, Box<dyn Error>>{
    let dir = fs::read_dir(path)?;
    let mut files: Vec<path::PathBuf> = Vec::new();
    for item in dir.into_iter() {
        files.push(item?.path());
    }
    Ok(files)
}


fn main() {
    let files = read_dir("./");
    println!("{:?}", files);
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.43s
Running `target/debug/rust`
Ok([“./target”, “./.gitignore”, “./Cargo.lock”, “./Cargo.toml”, “./.git”, “./src”])

### 再帰的にディレクトリ内のファイルを取得

use std::error::Error;
use std::fs;
use std::path;

pub fn read_dir(path: &path::PathBuf) {
    let dir = fs::read_dir(path).unwrap();
    let mut files: Vec<path::PathBuf> = Vec::new();
    for item in dir.into_iter() {
        
        let name = item.unwrap().path();
        if name.is_dir() {
            read_dir(&name);
        } else {
            files.push(name);
        }
    }
    println!("{:?}", files);
}


fn main() {
    let path = path::PathBuf::from("./src");
    read_dir(&path);
}

    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.20s
     Running `target/debug/rust`
["./src/test/test.rs"]
["./src/binary_search.rs", "./src/linear_search.rs", "./src/fibonacci.rs", "./src/tree_search.rs", "./src/main.rs", "./src/maze.rs", "./src/cardinal.rs", "./src/vending_machine.rs", "./src/fizzbuzz.rs", "./src/8queen.rs", "./src/prime.rs"]

これは感覚的に理解しやすいですね。

### 幅優先探索
再帰で検索するのではなく、ディレクトリをvectorに追加していき、各ディレクトリのファイルをそれぞれ取得していく。答えは同じだが、深さで検索するのではなく、対象を一つ一つ処理していくところが面白い。

fn main() {
    let mut queue: VecDeque<path::PathBuf> = VecDeque::new();
    queue.push_back("./src".into());
    let mut files: Vec<path::PathBuf> = Vec::new();

    while queue.len() > 0 {
        let path = queue.pop_front();
        let dir = fs::read_dir(path.unwrap()).unwrap();
        for item in dir.into_iter() {
            let name = item.unwrap().path();
            if name.is_dir() {
                queue.push_back(name);
            } else {
                files.push(name);
            }
        }
    }
    println!("{:?}", files);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.42s
Running `target/debug/rust`
["./src/binary_search.rs", "./src/linear_search.rs", "./src/fibonacci.rs", "./src/tree_search.rs", "./src/main.rs", "./src/maze.rs", "./src/cardinal.rs", "./src/vending_machine.rs", "./src/fizzbuzz.rs", "./src/read_dir.rs", "./src/8queen.rs", "./src/prime.rs", "./src/test/test.rs"]

再起的なので、対象枚数が増えるほど、指数関数的に計算数が増えていく。

use std::env;

fn hanoi(n: i32, src: String, dist: String, via: String) { // n, 移動元、移動先、経由
    if n > 1 {
        hanoi(n - 1, src.clone(), via.clone(), dist.clone());
        println!("{} -> {}", src.clone(), dist.clone());
        hanoi(n - 1, via.clone(), dist.clone(), src.clone());
    } else {
        println!("{} -> {}", src.clone(), dist.clone());
    }

}

fn main() {
    let args: Vec<String> = env::args().collect();
    let n = args[1].parse::<i32>().unwrap();
    println!("入力値:{}", n);

    hanoi(n, "a".to_string(), "b".to_string(), "c".to_string());
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.26s
Running `target/debug/rust 3`
入力値:3
a -> b
a -> c
b -> c
a -> b
c -> a
c -> b
a -> b

### 考察
3 a b c (a->b)
2 a c b (a->c)
1 a b c (a->b)
1 b c a (b->c)
3 a b c (a->b)
2 ….