Month: January 2025

【Rust】ハノイの塔

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

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 ….

【Rust】簡易的なBloomfilter

ブルームフィルタを更新していくロジックがいまいちわからんが、なんとなく

use std::hash::{DefaultHasher, Hash, Hasher};

#[derive(Debug, PartialEq, Clone)]
struct BloomFilter {
    filter: [i32; 10],
}

impl BloomFilter {
    fn set_v(&mut self, val: String) {
        let list: Vec<u8> = self.n_hash(val);
        for l in list {
            let i = usize::from(l);
            if self.filter[i] == 0 {
                self.filter[i] = 1
            } else {
                self.filter[i] = 2 }
        }    
    }

    fn n_hash(&self, val: String) -> Vec<u8>{
        let hashed = siphash(val);
        let list: Vec<u8> = s_digit(hashed);
        return list
    }

    fn check_v(self, val: String) -> bool {
        let list: Vec<u8> = self.n_hash(val);
        let mut c_bf = BloomFilter { filter: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]};
        for l in list {
            let i = usize::from(l);
            if c_bf.filter[i] == 0 {
                c_bf.filter[i] = 1
            } else {
                c_bf.filter[i] = 2 }
        }
        return self == c_bf
    }
}

fn siphash(s: String) -> u64 {
    let mut siphash = DefaultHasher::new();
    s.hash(&mut siphash);
    return siphash.finish()
}

fn s_digit(n: u64) -> Vec<u8> {
    n.to_string()
        .chars()
        .into_iter()
        .map(|char| char.to_digit(10).unwrap() as u8)
        .collect()
}

fn main(){
    let mut bf = BloomFilter { filter: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]};
    bf.set_v("hello world".to_string());
    println!("{:?}", bf);
    println!("{}", bf.clone().check_v("hello world!".to_string()));
    println!("{}", bf.clone().check_v("hello world".to_string()));
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.33s
Running `target/debug/wallet`
BloomFilter { filter: [2, 2, 0, 1, 2, 1, 1, 2, 2, 2] }
false
true

【Rust】DefaultHasherで文字列から数値型へ

何度やっても同じ値になります。使い勝手は良さそう。

use std::hash::{DefaultHasher, Hash, Hasher};

fn siphash13(s: String) {
    let mut siphash = DefaultHasher::new();
    s.hash(&mut siphash);
    println!("{:?}", siphash.finish());
    println!("{:?}", siphash);
}

fn main(){
    let mut t = "hello wolrd".to_string();
    siphash13(t);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.35s
Running `target/debug/wallet`
397376489521336075
DefaultHasher(SipHasher13 { hasher: Hasher { k0: 0, k1: 0, length: 12, state: State { v0: 14783544211356068956, v2: 15472093343132851580, v1: 2669010635360672206, v3: 8002614515094862307 }, tail: 4284772972, ntail: 4, _marker: PhantomData } })

【Python】ブルームフィルタ

bloom filterの全体像。ハッシュ化した値をインデックス番号にして、bloom_filterの値を更新する。
bloom filterにハッシュ値が入っているかどうか確認することで、bloom filterに登録されているかを判定する。

bloom_filter = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

def hash_a(val):
    return hash_val

def hash_b(val):
    return hash_val


val = "hello world"

a_hashed = hash_a(val) # 1
b_hashed = hash_b(val) # 4

bloom_filter[a_hashed] = 1
bloom_filter[b_hashed] = 1

[0, 1, 0, 0, 4, 0, 0, 0, 0, 0]

bloom_filter[a_hashed]
bloom_filter[b_hashed]

import functools

class BloomFilter:
    def __init__(self, filter_size):
        self.filter_size = filter_size
        self.bloom_filter = [0 for _ in range(filter_size)]

    def set_v(self, val):
        indexes = self.n_hash(val)
        for index in indexes:
            self.bloom_filter[index] = 1

    def n_hash(self, val):
        hashed = abs(hash(val))
        d_lst = [int(n) for n in str(hashed)]
        return [
            self._hash_common(lambda acc, d: acc + d, d_lst),
            self._hash_common(lambda acc, d: acc + 3 * d, d_lst),
        ]

    def _hash_common(self, func, d_lst):
        execed = abs(functools.reduce(func, d_lst, 0))
        while execed >= self.filter_size:
            execed = execed / self.filter_size
        return int(execed)

    def exist_v(self, val):
        indexes = self.n_hash(val)
        for index in indexes:
            if self.bloom_filter[index] == 0:
                return False
            return True

bf = BloomFilter(10)
print(bf.bloom_filter)
bf.set_v(3)
print(bf.bloom_filter)
print(bf.exist_v(3))
print(bf.exist_v(10))

$ python3 bloom_filter.py
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1]
True
False

BTCではSPVがScriptPubKeyをbloomfilterにセットして、リモートノードがマッチングアルゴリズムで判定する。
-> リモートノード側では、トランザクションごとに、ScriptPubKey, Outpointがマッチするかを判定して、マッチする場合はブルームフィルタを更新している。

なるほど、直接pubkeyのデータをやり取りしない分、安全性が向上するということね。これをRustでやりたい。

文字列を数値に変換するには、文字列を数値として持っておいて、それを変換でしょうか。

static ASCII_LOWER: [char; 26] = [
    'a', 'b', 'c', 'd', 'e', 
    'f', 'g', 'h', 'i', 'j', 
    'k', 'l', 'm', 'n', 'o',
    'p', 'q', 'r', 's', 't', 
    'u', 'v', 'w', 'x', 'y', 
    'z',
];

【Rust】8クイーン問題

fn check()は逆順にして、左下もしくは右下にあるかチェックしてる？
なんとなくわかるが、完全に理解していないのが辛いところ。。

use std::collections::VecDeque;

static N: usize = 8;

fn check(x: usize, mut col: VecDeque<usize>)-> bool {
    col.make_contiguous().reverse();

    let mut i = 0;
    for row in col {
        if ((x + i + 1) == row) || ((x as i32- i as i32 - 1) == row.try_into().unwrap()) {
            return false
        }
        i = i + 1;
    }
    return true
}

fn search(mut col: VecDeque<usize>){
    if col.clone().len() == N {
        println!("{:?}", &col);
    }

    for i in 0..N {
        if !col.contains(&i) {
            // println!("{:?}", &col);
            // println!("{}", i);
            if check(i, col.clone()) == true {
                col.push_back(i);
                search(col.clone());
                col.pop_front();
            }
        }
    }
}

fn main() {
    let col: VecDeque<usize> = VecDeque::new();
    search(col);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.23s
Running `target/debug/rust`
[4, 1, 3, 5, 7, 2, 0, 6]
[1, 3, 5, 7, 2, 0, 6, 4]
[5, 2, 4, 6, 0, 3, 1, 7]
[2, 4, 6, 0, 3, 1, 7, 5]
[1, 3, 5, 7, 2, 0, 6, 4]
…

【Rust】迷路で進行方向からの右手手法

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

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

【Rust】迷路のゴールを深さ優先探索(再帰処理)で探す

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

【Rust】迷路のゴールを幅優先探索で探す

壁は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

【Rust】HD_WALLET

hd-wallet= {version = “0.6.1”, features = [“slip10”, “curve-secp256k1”]}

fn main(){

    let seed = b"16-64 bytes of high entropy".as_slice();
    let master_key = slip10::derive_master_key::<Secp256k1>(seed).unwrap();
    let master_key_pair = hd_wallet::ExtendedKeyPair::from(master_key.clone());

    let child_key_pair = slip10::derive_child_key_pair_with_path(
        &master_key_pair,
        [1 + hd_wallet::H, 10],
    );
    println!("{:?}", master_key.clone());
    println!("{:?}", master_key_pair);
    println!("{:?}", child_key_pair);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.40s
Running `target/debug/wallet`
ExtendedSecretKey { secret_key: SecretScalar, chain_code: [23, 173, 212, 211, 8, 246, 142, 67, 143, 93, 79, 203, 0, 30, 52, 69, 214, 224, 93, 10, 56, 224, 214, 213, 121, 161, 164, 145, 108, 174, 89, 36] }
ExtendedKeyPair { public_key: ExtendedPublicKey { public_key: Point { curve: “secp256k1”, value: “…” }, chain_code: [23, 173, 212, 211, 8, 246, 142, 67, 143, 93, 79, 203, 0, 30, 52, 69, 214, 224, 93, 10, 56, 224, 214, 213, 121, 161, 164, 145, 108, 174, 89, 36] }, secret_key: ExtendedSecretKey { secret_key: SecretScalar, chain_code: [23, 173, 212, 211, 8, 246, 142, 67, 143, 93, 79, 203, 0, 30, 52, 69, 214, 224, 93, 10, 56, 224, 214, 213, 121, 161, 164, 145, 108, 174, 89, 36] } }
ExtendedKeyPair { public_key: ExtendedPublicKey { public_key: Point { curve: “secp256k1”, value: “…” }, chain_code: [17, 99, 196, 6, 250, 193, 242, 28, 104, 2, 74, 97, 184, 68, 251, 28, 33, 167, 163, 11, 173, 44, 118, 177, 219, 183, 145, 105, 192, 135, 11, 200] }, secret_key: ExtendedSecretKey { secret_key: SecretScalar, chain_code: [17, 99, 196, 6, 250, 193, 242, 28, 104, 2, 74, 97, 184, 68, 251, 28, 33, 167, 163, 11, 173, 44, 118, 177, 219, 183, 145, 105, 192, 135, 11, 200] } }

ちょっとよくわからん…

【Python】HD walletの親鍵/子鍵とchaincodeの概要

子の秘密鍵は、親のchaincdeと[親の公開鍵+index]をhmac_sha512でハッシュ化して作成している。

### マスター秘密鍵、公開鍵

import os
import binascii
import hmac
import hashlib
import ecdsa

seed = os.urandom(32)
root_key = b"Bitcoin seed"

def hmac_sha512(data, key_message):
    hash = hmac.new(data, key_message, hashlib.sha512).digest()
    return hash

def create_pubkey(private_key):
    publickey = ecdsa.SigningKey.from_string(private_key, curve=ecdsa.SECP256k1).verifying_key.to_string()
    return publickey

master = hmac_sha512(seed, root_key)

master_secretkey = master[:32]
master_chaincode = master[32:]

master_publickey = create_pubkey(master_secretkey)
master_publickey_integer = int.from_bytes(master_publickey[32:], byteorder="big")

if master_publickey_integer %2 == 0:
    master_publickey_x = b"\x02" + master_publickey[:32]
else:
    master_publickey_x = b"\x03" + master_publickey[:32]

print(binascii.hexlify(master_secretkey))
print(binascii.hexlify(master_chaincode))
print(binascii.hexlify(master_publickey_x))

$ python3 master_key.py
b’8a6dbaaff700682778dcbae2bc8718452fe5ed80fc9026a9b564420f8d5b0d80′
b’4ce8b10cc0c0874467d8f438c412fdbf21fba51517e668dbc4bd105af6861dec’
b’03cb15210804ca8f0d45b620832be935e2f90c3830f13f04c4bd6e8b4648f27817′
(secretkey, chaincode, pubkey)

### 子秘密鍵、子公開鍵

index = 0
index_bytes = index.to_bytes(8, "big")

data = master_publickey_x + index_bytes

result_hmac512 = hmac_sha512(data, master_chaincode)
sum_integer = int.from_bytes(master_secretkey,"big") + int.from_bytes(result_hmac512[:32],"big")

p = 2 ** 256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
child_secretkey = (sum_integer % p).to_bytes(32,"big")

child_chaincode = result_hmac512[32:]

child_publickey = create_pubkey(child_secretkey)
child_publickey_integer = int.from_bytes(child_publickey[32:], byteorder="big")

if child_publickey_integer %2 == 0:
    child_publickey_x = b"\x02" + child_publickey[:32]
else:
    child_publickey_x = b"\x03" + child_publickey[:32]

print(binascii.hexlify(child_secretkey))
print(binascii.hexlify(child_chaincode))
print(binascii.hexlify(child_publickey_x))

b’5ff011a3e9cd672aaf0dc9fd52cb3172ac2815cb270f919135e6b0f0e6e03d54′
b’15f4d148b2d7730076d5e670249649ea8f0fd8572dad3818680e347196149dda’
b’03480a1dbb4a87d867bee3d364b608e21d685af271876707b9f9d5b75c6df6fde7′
—
b’23faf6fad81cd93e12c003c944ba3ef215dae714c638756386b6b9404da5aac9′
b’e3563dc6891e238cd0d8ebf99e65ebfc67cecf42364de9756b89859bbd049b62′
b’02039253af3e828bfbf1e560fe0e923a144fc4496ded3b6bbfa0d568cf7177d1c3′

なるほど、一見複雑そうに見えるが、なかなか面白いね