$ sudo apt install nodejs
$ node -v
v12.22.9
$ sudo apt install npm
$ npm -v
8.5.1
参考)
https://www.digitalocean.com/community/tutorials/how-to-install-node-js-on-ubuntu-20-04
さー、gulpやるぞー
【Rust】○✖️ゲーム(minmax)
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];
このようにすると、ランダム性が出る。。
【Rust】○✖️ゲーム
マスを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
これはさっぱりわからん…
【Rust】指定パスのファイル、ディレクトリを取得(depth & linear)
ファイル、フォルダの取得
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"]
【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