区間内の素数

for (int j = 2; j * j < b; j += i) {
    // 処理
}

をRustで書くと、for文ではなく、while文になる。Rustの場合、for文は基本、for i in hoge となるから

let mut j = 2;
while j * j < b {
    // 処理
    j += i;
}
fn segment_sieve(a: i64, b: i64) {
   let mut is_prime[bool; 22];
   let mut is_prime_small[bool; 37];

   for i in 0.. {
      if i*i < b {
         break;
      }
      is_prime_small[i] = true;
   }

   for i in 0.. {
      if i < b - a {
         break;
      }
      is_prime[i] = true;
   }

   for i in 2.. {
      if i * i < b {
         break;
      }
      if is_prime_small[i] {
         let mut j = 2 * i;
         while  j * j < b {
            j += i;
            is_prime_small[j] = false;
         }

         let mut j = max(2LL, (a + i - 1) / i) * i;
         while j < b {
            j = j + i;
            is_prime[j - a] = false;
         }
      }
   }
}

素数の個数


fn sieve(n: i32)  {
   let prime: [i32; 11];
   let is_prime: [bool; 12];
   let mut p = 0;

   for i in 0..n {
      is_prime[i] = true;
   }
   is_prime[0] = is_prime[1] = false;
   for i in 2.. {
      if i <= n {
         break;
      }
      if is_prime[i] {
         p = p + 1;
         prime[p] = i;
         for j in 2*i.. {
            if j <= 2 {
               break;
            }
            is_prime[j] = false;
         }
      }
      return p;
   }  
}

素数判定

c++ のfor(int i = 2; i * i <= n; i++) { をrustで書くと、 [code] for i in 2.. { if i * i > n { break; } // 処理 } [/code] となるらしい... なるほど~ [code] use std::collections::HashMap; fn is_prime(n i32) -> bool { for i in 2..(i*i < n) { if(n % i == 0) { return false; } } return n != 1; } fn divisor(n i32) -> Vec<i32> { let mut res: Vec<i32> = Vec::new(); for i in 1..(i*i < n) { if (n % i == 0) { res.push(i); if (i != n / i) { res.push(n / i); } } } return res; } fn prime_factor(n: i32) -> HashMap<i32, i32> { let mut res = HashMap::new(); for i in 2..(i*i <= n) { while (n % i == 0) { res.insert( i, i ); n = n / i; } } if ( n != 1) { res[&n] = 1; } return res; } [/code]

Rustでフレームワークを自作したい

ルーティングが一つの場合、TcpListener::bindでlistenerを作ってあげれば良い
ただ、フレームワークの場合、ルーティングが複数でないと意味がない…

use std::fs;
use std::io;
use std::io::prelude::*;
use std::net::{TcpListener, TcpStream};

fn main() {

   let path = "./data/index.html";
   
   let listenr = TcpListener::bind("192.168.33.10:8000").unwrap();
   println!("Listening on http://192.168.33.10:8000");

   for stream in listenr.incoming() {
      match stream {
         Ok(stream) => {
            let _ = handle_connection(stream, path);
         }
         Err(e) => {
            println!("Connection failed: {}", e);
         }
      }
   }
}

fn handle_connection(mut stream: TcpStream, path: &str) -> io::Result<()>  {
   let mut buffer = [0; 1024];
   stream.read(&mut buffer).unwrap();

   let request = String::from_utf8_lossy(&buffer);
   println!("Received request:\n{}", request);

   let header = "HTTP/1.1 200 OK\r\nContent-Type: text/html; charset=UTF-8\r\n\r\n";

   
   let contents = fs::read_to_string(path)?;
   println!("File contents:\n{}", contents);

   let response = format!("{}{}", header, contents);
   stream.write_all(response.as_bytes()).unwrap();
   stream.flush().unwrap();

   Ok(())
}

index.html

<p>This is framework!</p>

### ルーティングが複数の場合

use std::fs;
use std::io;
use std::io::prelude::*;
use std::net::{TcpListener, TcpStream};

fn main() {

   let path = "./data/index.html";
   
   let listenr = TcpListener::bind("192.168.33.10:8000").unwrap();
   println!("Listening on http://192.168.33.10:8000");

   for stream in listenr.incoming() {
      match stream {
         Ok(stream) => {
            let _ = handle_connection(stream);
         }
         Err(e) => {
            println!("Connection failed: {}", e);
         }
      }
   }
}

fn handle_connection(mut stream: TcpStream)  {
   let mut buffer = [0; 1024];
   stream.read(&mut buffer).unwrap();

   let request = String::from_utf8_lossy(&buffer);
   println!("Received request:\n{}", request);

   let response = if request.starts_with("GET /hello ") {
      http_response(200, "text/html", "<h1>Hello from Rust!</h1>")
   } else if request.starts_with("GET / ") {
      http_response(200, "text/html", "<h1>Welcome to the Rust server!</h1>")
   } else {
      http_response(404, "text/html", "<h1>404 Not Found</h1>")
   };
   stream.write_all(response.as_bytes()).unwrap();
   stream.flush().unwrap();
}

fn http_response(status_code: u16, content_type: &str, body: &str) -> String {
   format!(
       "HTTP/1.1 {} {}\r\nContent-Type: {}\r\nContent-Length: {}\r\n\r\n{}",
       status_code,
       get_status_text(status_code),
       content_type,
       body.len(),
       body
   )
}

fn get_status_text(code: u16) -> &'static str {
   match code {
       200 => "OK",
       404 => "Not Found",
       _ => "Unknown",
   }
}

ルートとコンテンツをhashmapにした場合

let mut buffer = [0; 1024];
   stream.read(&mut buffer).unwrap();

   let request = String::from_utf8_lossy(&buffer);
   let request_line = request.lines().next().unwrap_or("");
   println!("Received request:\n{}", request);

   let mut routes = HashMap::new();
   routes.insert (
      "/hello",
      "<h1>Hello from Rust!</h1>",
   );

   routes.insert (
      "/",
      "<h1>Welcome to the Rust server!</h1>",
   );

   let path = request_line
        .split_whitespace()
        .nth(1)
        .unwrap_or("/");
   
   let response_body = routes.get(path)
        .cloned()
        .unwrap_or_else(|| "<h1>404 Not Found</h1>");

   let response = http_response(200, "text/html", &response_body);

グラフの探索

const V: i32;

fn dfs(v: i32, c: i32) -> bool {
   let color: Vec<i32> = Vec::new();
   color[v] = c;
   for i in 0..G.len() {
      if color[G[v][i]] == c {
         return false;
      } 
      if color[G[v][i]] == 0 && !dfs(G[v][i], -c) {
         return false;
      }
   }
   return true;
}

fn main() {
   for i in 0..V {
      if color[i] == 0 {
         if !dfs(i, 1) {
            println!("No");
         }
      }
   }
   println!("Yes");
}

簡易的なデバッカー(python)

import sys

def trace_calls(frame, event, arg):
    if event != 'call':
        return
    code = frame.f_code
    func_name = code.co_name
    print(f"\n 呼び出し: {func_name}() at line {frame.f_lineno} in {code.co_filename}")
    return trace_lines

def trace_lines(frame, event, arg):
    if event != 'line':
        return
    lineno = frame.f_lineno
    filename = frame.f_code.co_filename
    local_vars = frame.f_locals
    print(f"- 実行中: line {lineno} in {filename}")
    print("変数:", local_vars)
    input("Enterキーで次の行へ...")
    return trace_lines

sys.settrace(trace_calls)

def test():
    x = 5
    y = 10
    z = x + y
    print("結果:", z)

test()

sys.settrace(None)

$ python3 debugger.py

呼び出し: test() at line 24 in /home/vagrant/dev/algorithm/basic/python/debugger.py
– 実行中: line 25 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {}
Enterキーで次の行へ…
– 実行中: line 26 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {‘x’: 5}
Enterキーで次の行へ…
– 実行中: line 27 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {‘x’: 5, ‘y’: 10}
Enterキーで次の行へ…
– 実行中: line 28 in /home/vagrant/dev/algorithm/basic/python/debugger.py
変数: {‘x’: 5, ‘y’: 10, ‘z’: 15}
Enterキーで次の行へ…
結果: 15

rustでは実行時フックがない

use std::io::{self, Write};

fn pause() {
   print!("Enterキーで次のステップへ...");
   io::stdout().flush().unwrap();
   let _ = io::stdin().read_line(&mut String::new());
}

fn main() {
   println!("📍 デバッグ開始");

   let x = 5;
   println!("🔍 x = {}", x);
   pause();

   let y = 10;
   println!("🔍 y = {}", y);
   pause();

   let z = x + y;
   println!("🔍 z = x + y = {}", z);
   pause();

   println!("✅ 結果: {}", z);
}

グラフのDFS(深さ優先探索)

use std::collections::HashMap;
use std::collections::VecDeque;


fn dfs(graph: HashMap<&str, Vec<&str>>, start: &str) {
   let mut visited: Vec<&str> = Vec::new();
   visited.push(start);

   for neighbor in graph.clone().get(start).unwrap() {
      if !visited.contains(&neighbor) {
         dfs(graph.clone(), neighbor);
      }
   }
}

fn main() {
   let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();

   graph.insert("A", vec!["B", "C"]);
   graph.insert("B", vec!["A", "D", "E"]);
   graph.insert("C", vec!["A", "F"]);
   graph.insert("D", vec!["B"]);
   graph.insert("E", vec!["B", "F"]);
   graph.insert("F", vec!["C", "E"]);

   println!("{:?}", graph);

   // bfs(graph, "A");
}

グラフのBFS(幅優先探索)

use std::collections::HashMap;
use std::collections::VecDeque;

fn bfs(graph: HashMap<&str, Vec<&str>>, start: &str) {
   let mut deque: VecDeque<&str> = VecDeque::new();
   let mut visited: Vec<&str> = Vec::new();

   deque.push_back(start);

   while !deque.is_empty() {
      let vertex = deque.pop_front().unwrap();
      if !visited.contains(&vertex) {
         visited.push(vertex);
         if graph.get(vertex) != None {
            let vs = graph.get(vertex).unwrap();
            for v in vs {
               // println!("{}", v);
               deque.push_back(v);
            }
         }
      }
   }
}


fn main() {
   let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();

   graph.insert("A", vec!["B", "C"]);
   graph.insert("B", vec!["A", "D", "E"]);
   graph.insert("C", vec!["A", "F"]);
   graph.insert("D", vec!["B"]);
   graph.insert("E", vec!["B", "F"]);
   graph.insert("F", vec!["C", "E"]);

   println!("{:?}", graph);

   bfs(graph, "A");
}

グラフ

#[derive(Debug)]
struct Edge {
   to: i32,
   cost: i32,
}


fn main() {
   let V = 3;
   let E = 3;

   let matrix = [[0,1], [0,2], [1,2]];
   let mut edges: Vec<Edge> = Vec::new();

   for i in 0..E {
      let ed = Edge { to: matrix[i][0], cost: matrix[i][1]};
      edges.push(ed);
   }

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

Expedition 2431

fn main() {
   let mut N = 4; // gas station num
   let P = 10; // initial gas
   let L = 25; // distance

   let mut A: Vec<i32> = vec![10, 14, 20, 21]; // gas station distance
   let mut B: Vec<i32> = vec![10, 5, 2, 4]; // gas volume supply

   A.push(L);
   B.push(0);
   N += 1;

   let que; // manage gas station

   let mut ans = 0; // num of gas supply
   let mut pos = 0; // position
   let mut tank = P; // gas volume

   for i in 0..N {
      let d = A[i] - pos; // distance

      while (tank - d < 0) {
         if que.empty() {
            que.push(-1);
            return;
         }
         tank += que.top();
         que.pop();
         ans += 1;
      }

      tank -= d;
      pos = A[i];
      que.push(B[i]);
   }
   println!("{}", ans);
}

priority queはstackで大きい順に値を入れていく。