【Rust】【アルゴリズム】くじ引き

4回くじを引くという条件から、nパターンの4回分を全通り試して、一致する組み合わせを探している。
全通りを探す場合、ループの中でループをするという書き方が多い。

static MAX_N: usize = 50;

fn main() {
    let mut n: i32;
    let mut m: i32;
    let mut k: Vec<i32> = Vec::new();

    println!("紙の枚数 n を入力してください。");
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let n = line.trim().parse::<i32>().unwrap();
    println!("期待する数字の和 m を入力してください。");
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let m = line.trim().parse::<i32>().unwrap();

    println!("紙に書かれている数字をそれぞれ入力してください。");
    for i in 0..n {
        println!("{}番目の数字:", i + 1);
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        let n = line.trim().parse::<i32>().unwrap();
        k.push(n);
    }

    let mut flg = false;

    for a in 0..n {
        for b in 0..n {
            for c in 0..n {
                for d in 0..n {
                    if k[a as usize] + k[b as usize] + k + k[d as usize] == m {
                        flg = true;
                        println!("発見! 組み合わせは{},{},{},{}", k[a as usize], k[b as usize], k, k[d as usize]);
                    }
                }
            }
        }
    }

    if !flg {
        println!("そのような組み合わせはありません。");
    }
}

紙の枚数 n を入力してください。
3
期待する数字の和 m を入力してください。
10
紙に書かれている数字をそれぞれ入力してください。
1番目の数字:
3
2番目の数字:
3
3番目の数字:
2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,2,2,3
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3

【Rust】iter(), into_iter()を使って、JR東日本のどこかにビューーン!をRustで実装する!

ここでは東北、秋田、山形新幹線の駅からそれぞれ一つづつランダムに駅を抽出する組み合わせを出力するという簡易的な実装例とする。
実際のどこかにビューーン!は、更に上越、北陸新幹線もあり、候補47駅、5つの新幹線の中から4つの駅を出力しているので、若干ロジックが異なるが、考え方はおおよそ同じだ。※[東北、秋田、山形、上越、北陸]から、4つをランダムに抽出して、そこから更にランダムに抽出しているのかもしれない。

サーバ側では、各駅がどの新幹線駅かというデータを持っておき、iteratorからfilterでそれぞれの新幹線ごとにvectorに入れて、そこからランダムに抽出する。下のサンプルでは、最後に往復料金でソートしてprintln!している。

use rand::prelude::IndexedRandom;

#[derive(Debug, Clone)]
struct Destination {
    bullet_train: String,
    station: String,
    ticket_price: u32
}

fn main() {
    let data = [
        Destination{ bullet_train: "東北".to_string(), station: "那須塩原".to_string(), ticket_price: 12040},
        Destination{ bullet_train: "東北".to_string(), station: "新白河".to_string(), ticket_price: 13580},
        Destination{ bullet_train: "東北".to_string(), station: "郡山".to_string(), ticket_price: 16680},
        Destination{ bullet_train: "東北".to_string(), station: "福島".to_string(), ticket_price: 18220},
        Destination{ bullet_train: "東北".to_string(), station: "白石蔵王".to_string(), ticket_price: 21080},
        Destination{ bullet_train: "東北".to_string(), station: "仙台".to_string(), ticket_price: 22180},
        Destination{ bullet_train: "東北".to_string(), station: "古川".to_string(), ticket_price: 23280},
        Destination{ bullet_train: "秋田".to_string(), station: "雫石".to_string(), ticket_price: 32200},
        Destination{ bullet_train: "秋田".to_string(), station: "田沢湖".to_string(), ticket_price: 32640},
        Destination{ bullet_train: "秋田".to_string(), station: "角館".to_string(), ticket_price: 34040},
        Destination{ bullet_train: "秋田".to_string(), station: "大曲".to_string(), ticket_price: 34700},
        Destination{ bullet_train: "秋田".to_string(), station: "秋田".to_string(), ticket_price: 36040},
        Destination{ bullet_train: "山形".to_string(), station: "米沢".to_string(), ticket_price: 21060},
        Destination{ bullet_train: "山形".to_string(), station: "高畠".to_string(), ticket_price: 21500},
        Destination{ bullet_train: "山形".to_string(), station: "赤湯".to_string(), ticket_price: 22240},
        Destination{ bullet_train: "山形".to_string(), station: "かみのやま温泉".to_string(), ticket_price: 22900},
        Destination{ bullet_train: "山形".to_string(), station: "さくらんぼ東根".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "村山".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "大石田".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "新庄".to_string(), ticket_price: 26000},
    ];

    let mut JR_Voom = Vec::new();

    let tohoku: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "東北")
        .collect();
    JR_Voom.push(tohoku.choose(&mut rand::thread_rng()).unwrap());

    let akita: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "秋田")
        .collect();
    JR_Voom.push(akita.choose(&mut rand::thread_rng()).unwrap());

    let yamagata: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "山形")
        .collect();
    JR_Voom.push(yamagata.choose(&mut rand::thread_rng()).unwrap());
    JR_Voom.sort_by(|a, b| a.ticket_price.cmp(&b.ticket_price));

    for (i, destination) in JR_Voom.iter().enumerate() {
        println!("{:}: {}駅 (往復{}円)", i + 1, destination.station, destination.ticket_price);
    }
    
}

何度か実行すると以下のようになる。うん、見たことある光景である。
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.55s
Running `target/debug/app`
1: 郡山駅 (往復16680円)
2: 新庄駅 (往復26000円)
3: 秋田駅 (往復36040円)

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.08s
Running `target/debug/app`
1: 米沢駅 (往復21060円)
2: 古川駅 (往復23280円)
3: 雫石駅 (往復32200円)

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.16s
Running `target/debug/app`
1: 福島駅 (往復18220円)
2: 米沢駅 (往復21060円)
3: 田沢湖駅 (往復32640円)

プログラムでランダムに抽出しているだけだが、これに一喜一憂しているのだからしょうがない。多分、●●駅の方が△△駅よりも出やすくするといった駅によっての重み付とかはないと思うが、実際のところは分かりません。。

【Rust】字句解析(Lexical analysis)の初級

use std::io::stdin;

fn main() {

    let mut memory = Memory {
        slots: vec![0.0; 10],
    }
    let mut prev_result: f64 = 0.0;
    for line in stdin().lines() {
        let line = line.unwrap();
        if line.is_empty() {
            break;
        }

        let tokens: Vec<&str> = line.split(char::is_whitespace).collect();

        let is_memory = tokens[0].starts_with("mem");
        if is_memory && tokens[0].ends_with('+') {
            add_and_print_memory(&mut memory, tokens[0], prev_result);
            continue;
        } else if is_memory && tokens[0].ends_with('-') {
            add_and_print_memory(&mut memory, tokens[0], -prev_result);
            continue;
        }

        let left = eval_token(tokens[0], &memory);
        let right = eval_token(tokens[2], &memory);
        let result = eval_expression(left, tokens[1], right);
        print_output(result);

        prev_result = result;
    }
}

struct Memory {
    slots: Vec<f64>,
}

fn add_and_print_memory(memory: &mut Memory, token: &str, prev_result: f64) {
    let slot_index: usize = token[3..token.len() - 1].parse().unwrap();
    memory.slots[slot_index] += prev_result;
    print_output(memory.slots[slot_index]);
}
fn eval_token(token: &str, memory: &Memory) -> f64 {
    if token.starts_with("mem") {
        let slot_index: usize = token[3..].parse().unwrap();
        memory.slots[slot_index]
    } else {
        token.parse().unwrap()
    }
}
fn eval_expression(left: f64, operator: &str, right: f64) -> f64 {
    match operator {
        "+" => left + right,
        "-" => left - right,
        "*" => left * right,
        "/" => left / right,
        _ => {
            unreachable!()
        }
    }
}
fn print_output(value: f64) {
    println!(" => {}", value);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.49s
Running `target/debug/app`
1 + 2
=> 3
mem1+
=> 3
3 + 4
=> 7
mem2-
=> -7
mem1 * mem2
=> -21

【Rust】ポーカー

このソース見た時、凄い感慨したんよね。絵柄と1~13の数字でdeckを作るところ。
pocker chaseの裏側ってどうやってんだろうずっと思ってたんだけど、これを見ると、カードの配り方や、最後の役完成時の判定をどうやってるかがわかる。素晴らしい!

use rand::seq::SliceRandom;

#[derive(Debug, Clone, Copy, PartialEq)]
enum Suit {
    Club,
    Diamond,
    Heart,
    Spade,
}

#[derive(Debug, Clone, Copy, PartialEq)]
struct Card {
    suit: Suit,
    rank: i32,
}

fn main() {
    let mut deck: Vec<Card> = Vec::new();
    let suits = [Suit::Club, Suit::Diamond, Suit::Heart, Suit::Spade];

    for suit in suits {
        for rank in 1..=13 {
            deck.push(Card {suit, rank});
        }
    }
    let mut rng = rand::thread_rng();
    deck.shuffle(&mut rng);
    

    let mut hand: Vec<Card> = Vec::new();
    for _ in 0..5 {
        hand.push(deck.pop().unwrap());
    }

    hand.sort_by(|a, b| a.rank.cmp(&b.rank));

    for (i, card) in hand.iter().enumerate() {
        println!("{:}: {:?} {:}", i +1, card.suit, card.rank);
    }

    println!("入れ替えたいカードの番号を入力してください(例: 1 2 3)");
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();

    let numbers : Vec<usize> = input.split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<usize>>();
    for number in numbers {
        hand[number - 1] = deck.pop().unwrap();
    }

    hand.sort_by(|a, b| a.rank.cmp(&b.rank));

    for (i, card) in hand.iter().enumerate() {
        println!("{:}: {:?} {:}", i +1, card.suit, card.rank);
    }

    let suit = hand.first().unwrap().suit;
    let flash = hand.iter().all(|c| c.suit == suit);

    let mut count = 0;
    for i in 0..hand.len() - 1 {
        for j in i + 1..hand.len() {
            if hand[i].rank == hand[j].rank {
                count += 1;
            }
        }
    }

    if flash {
        println!("flash!");
    } else if count >= 3 {
        println!("スリーカード!");
    } else if count == 2 {
        println!("2ペア");
    } else if count == 1 {
        println!("1ペア");
    } else {
        println!("役なし...");
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.62s
Running `target/debug/app`
1: Spade 3
2: Spade 4
3: Club 5
4: Diamond 8
5: Spade 13
入れ替えたいカードの番号を入力してください(例: 1 2 3)
1 2 3 4
1: Diamond 10
2: Club 10
3: Diamond 12
4: Heart 12
5: Spade 13
2ペア

【Rust】逆ポーランド記法

演算子を前に置くのをポーランド記法という 4 + 5 * 8 – 9 / 3 は、「- + 4 * 5 8 / 9 3」っと書く。
逆に、演算子を後ろに置くのを逆ポーランド記法という。「4 5 8 * + 9 3 / -」と書く。
逆ポーランド記法はスタックで処理しやすく、色々な場面で使われる。

fn calc(expression: String) {
    let mut stack: Vec<i32> = Vec::new();
    for i in expression.split(' ') {
        println!("{:?}", stack);
        if i == '+'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a + b);
        } else if i == '-'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a - b);
        } else if i == '*'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a * b);
        } else if i == '/'.to_string() {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            stack.push(a / b);
        } else {
            stack.push(i.parse::<i32>().unwrap());
        }
    }
    println!("{:?}", stack);
}

fn main() {
    calc("4 6 2 + * 3 1 - 5 * -".to_string());
}

[]
[4]
[4, 6]
[4, 6, 2]
[4, 8]
[32]
[32, 3]
[32, 3, 1]
[32, 2]
[32, 2, 5]
[32, 10]
[22]

なるほど、これは面白い。
コンパイラのOP_CODEでも同じようなことをやったような気がする。

【Rust】Boyer-Moore法

use std::collections::HashMap;

fn main() {
    let text = ['J','A','P','A','N','H','O','L','D','I','N','G',];
    let pattern = ['H','O','L','D'];

    let mut skip = HashMap::new();
    for i in 0..(pattern.len() - 1) {
        skip.insert(
            pattern[i],
            pattern.len() - i - 1,
        );
    }
    println!("{:?}", skip);

    let mut i = pattern.len() - 1;
    while i < text.len() {
        let mut flg = true;
        for j in 0..pattern.len() {
            if text[i-j] != pattern[pattern.len()-1-j] {
                flg = false;
                break;
            }
        }
        if flg == true {
            println!("{}", i - pattern.len() + 1);
            break;
        } else if skip.get(&text[i]).is_some(){
            i += skip[&text[i]];
        } else {
            i += pattern.len();
        }
    }
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
{‘H’: 3, ‘O’: 2, ‘L’: 1}
5

【Rust】文字列探索の力任せ法

線形ソートみたいな感じ
text[i + j] != pattern[j]とすることで、patterを一文字ずつ合致するか判定する。
regexもこれと同じアルゴリズムなんだろうか???

fn main() {
    let text = ['J','A','P','A','N','H','O','L','D','I','N','G',];
    let pattern = ['H','O','L','D'];

    for i in 0..text.len() {

        let mut flg = true;
        for j in 0..pattern.len() {
            if text[i + j] !=  pattern[j] {
                flg = false;
                break;
            }
        }
        if flg {
            println!("{}", i);
        }    
    }
}

Running `target/debug/rust`
5

【Rust】ダイクストラ法

fn dijkstra(edges: Vec<Vec<[usize; 2]>>, num_v: usize)  -> Vec<usize>{
    let inf = 999;
    let mut dist = Vec::new();
    for _ in 0..num_v {
        dist.push(inf);
    }
    dist[0] = 0;

    let mut q = Vec::new();
    for i in 0..num_v {
        q.push(i);
    }
    
    while *&q.len() > 0 {
        let mut r = q[0];
        for i in &q{
            if dist[*i] < dist[r] {
                r = *i;
            }
        } 
        let n = q.iter().position(|n| *n == r).unwrap();
        let u = q[n];
        q.retain(|&x| x != u);
        
        for i in edges[u].clone() {
            if dist[i[0]] > dist[u] + i[1] {
                dist[i[0]] = dist[u] + i[1];
            }
        }      
    }
    return dist;
}

fn main() {
    let edges = vec![
        vec![[1, 4], [2, 3]],
        vec![[2, 1], [3, 1], [4, 5]],
        vec![[5, 2]],
        vec![[4, 3]],
        vec![[6, 2]],
        vec![[4, 1], [6, 4]],
        vec![],
    ];
    println!("{:?}", edges);

    println!("{:?}", dijkstra(edges, 7));
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
[[[1, 4], [2, 3]], [[2, 1], [3, 1], [4, 5]], [[5, 2]], [[4, 3]], [[6, 2]], [[4, 1], [6, 4]], []]
[0, 4, 3, 5, 6, 5, 8]

おおおお、これは凄いな…

【Rust】bellman fordアルゴリズム

最短距離を探すアルゴリズム

fn bellman_ford(edges: Vec<[usize; 3]>, num_v: usize)  -> Vec<usize>{
    let inf = 999;
    let mut dist = Vec::new();
    for _ in 0..num_v {
        dist.push(inf);
    }
    

    dist[0] = 0;
    let mut changed = true;

    while changed == true {
        changed = false;
        for edge in &edges {
            if dist[edge[1]] > dist[edge[0]] + edge[2] {
                dist[edge[1]] =  dist[edge[0]] + edge[2];
                changed = true;
            }
        }
    }
    return dist;
}

fn main() {
    let edges = vec![[0, 1, 4], [0, 2, 3], [1, 2, 1], [1, 3, 1], 
    [1, 4, 5], [2, 5, 2], [4, 6, 2], [5, 4, 1], 
    [5, 6, 4]];

    let dist = bellman_ford(edges, 7);
    println!("{:?}", dist);
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.22s
Running `target/debug/rust`
[0, 4, 3, 5, 6, 5, 8]

いまいちよーわからん…

【Rust】最短経路問題

M, N = 6, 5

route = [[0 for i in range(N + 1)]for j in range(M + 1)]

print(route)

$ python3 test.py
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

fn main() {
    let M = 6;
    let N = 5;

    let mut route: Vec<Vec<usize>> = Vec::new();
    
    for _ in 0..(M+1) {
        let mut L: Vec<usize> = Vec::new();
        for _ in 0..(N+1) {
            L.push(0);
        } 
        route.push(L);
    }
    println!("{:?}", route);
}

[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

fn main() {
    let M = 6;
    let N = 5;

    let mut route: Vec<Vec<usize>> = Vec::new();
    
    for _ in 0..(M+1) {
        let mut L: Vec<usize> = Vec::new();
        for _ in 0..(N+1) {
            L.push(0);
        } 
        route.push(L);
    }

    for i in 0..(M+1){
        route[i][0] = 1;
    }
    
    for i in 1..(N+1) {
        route[0][i] = 1;
        for j in 1..(M+1) {
            route[j][i] = route[j - 1][i] + route[j][i - 1];
        }
    }
    println!("{:?}", route);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
[[1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6], [1, 3, 6, 10, 15, 21], [1, 4, 10, 20, 35, 56], [1, 5, 15, 35, 70, 126], [1, 6, 21, 56, 126, 252], [1, 7, 28, 84, 210, 462]]

おおお、なるほど、これは凄い。

実はこう書ける

fn search(m: usize, n: usize) -> usize {
    if (m == 0) || (n == 0) {
        return 1
    }

    return search(m-1, n) + search(m, n - 1);
}

fn main() {
    let M = 6;
    let N = 5;

    println!("{}", search(M, N));
}

なるほど、これは凄い。
経路の問題も基本は、位置を数字で表現するのね。