Rust – Page 3 – ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

【Rust】ルックアップテーブル【アルゴリズム】

fn main() {

   let Q = [
      100, 200, 250, 300, 360
   ];

   let R = [
      401, 302, 101, 102, 301
   ];

   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   let x  = x.trim_end().to_owned();
   let a = x.parse::<i32>().unwrap();

   let n = Q.len();

   while a > 0 {
      let mut i = 0;
      while i < n {
         if a < Q[i] {
            println!("整理番号{}番の方は{}会場です。", a, R[i]);
            i = n;
         } else {
            i += 1;
         }

      }
   }
}

整理番号100番の方は302会場です。

### 選択ソート

fn main() {

   let A = [
      84, 121, 43, 93, 140, 83, 14, 93, 181, 58
   ];

   let n = A.len();
   seq_sort(n, A);
}

fn seq_sort(n: usize, mut A: [i32; 10]) {
   let mut i = 0;
   let mut B: [i32; 10] = [0; 10];
   let mut k;
   for i in 0..n {
      
      let mut a = 999;
      let mut j = 0;
      for j in j..n {
         if a > A[j] {
            a = A[j];
            k = j;
         }
      }
      A[k] = 999;
      B[i] = a;
   }
   
}

【Rust】バイナリーサーチ【アルゴリズム】

fn main() {

   let mut commodity: [String; 8] = [
      "ジュース".to_string(),
      "紅茶".to_string(),
      "アイスティ".to_string(),
      "コーヒー".to_string(),
      "アイスコーヒー".to_string(),
      "ショートケーキ".to_string(),
      "チーズケーキ".to_string(),
      "トースト".to_string(),
   ];

   let mut price: [i32; 8] = [
      280, 300, 320, 350, 370, 550, 600, 650
   ];

   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   let x  = x.trim_end().to_owned();
   let a = x.parse::<i32>().unwrap();

   let n = commodity.len() as i32;
   bin_search(a, n, price);
   // seq_search();
}

fn bin_search(a: i32, n: i32, price: [i32; 8]) {
   let mut p = -1;
   let mut l = 0;
   let mut h = n - 1;

   while (l <= h && p == -1) {
      if (a > price[((l+h) / 2) as usize]) {
         l = (l + h) / 2 + 1;
      } else {
         if (a == price[((l+h)/2) as usize]) {
            p = (l +h) / 2;
         } else {
            h = (l + h) / 2 - 1;
         }
      }
   }
   println!("{}", p);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s
Running `target/debug/basic`
300
1

【Rust】素数: エラトスネテスのふるい【アルゴリズム】

fn main() {

   let mut s: [i32; 101] = [1; 101];

   let mut i = 2;
   while i <= 100 {
      s[i] = 1;
      i += 1;
   }

   i = 2;
   while i * i <= 100 {
      let mut j = 2;

      while i * j <= 100 && s[i]!= 0 {
         s[i*j] = 0;
         j += 1;
      }
      i += 1;
   }

   i = 2;
   while i < 100 {
      if s[i] == 1 {
         println!("{}", i);
      }
      i += 1;
   }
}

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

紀元前の話

【Rust】素数【アルゴリズム】

fn main() {

   let mut s: [i32; 100] = [0; 100];

   let mut i = 1;
   s[0] = 2;

   let mut n = 3;
   let mut j = 0;
   while n <= 100 {
      let quotient = n / s[j];
      let reminder = n % s[j];

      if reminder == 0 {
         n = n + 2;
         j = 1;
      } else {
         if quotient >= s[j] {
            j += 1;
         } else {
            s[j] = n;
            i += 1;
            j = 1;
            n = n + 2;
         }
      }
   }

   let mut i = 0;
   while s[i] != 0 {
      println!("{}", s[i]);
      i += 1;
   }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.40s
Running `target/debug/basic`
thread ‘main’ panicked at src/main.rs:11:22:
attempt to divide by zero
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

整数を”0″で割るとundefinedでエラーになる。。。
うーん　どう表現したら良いんやろうか

【Rust】二次元配列【アルゴリズム】

配列の個数がわかっている場合、[[i32; 5]; 6]というような書き方をする。
わかっていない場合はvectorにすれば良い。

fn main() {

   let score:[[i32; 5]; 6] = [
      [65, 71, 74, 82, 97],
      [84, 83, 73, 64, 65],
      [74, 74, 78, 80, 78],
      [90, 90, 90, 90, 90],
      [87, 78, 85, 60, 88],
      [93, 95, 94, 92, 95],
   ];
   println!("番号 国語 数学 理科 社会 英語 合計 平均");

   let mut i = 0;
   while i < 5 {
      let (mut t, mut j) = (0, 0);
      print!("{} ", i);
      while (j <= 4) {
         print!("{} ", score[i][j]);
         t = t + score[i][j];
         j += 1;
      }

      let av = t / j as i32;
      println!("{} {}", t, av);
      i += 1;
   }
}

番号国語数学理科社会英語合計平均
0 65 71 74 82 97 389 77
1 84 83 73 64 65 369 73
2 74 74 78 80 78 384 76
3 90 90 90 90 90 450 90
4 87 78 85 60 88 398 79

なるほどー

【Rust】配列【アルゴリズム】

fn main() {

   let mut a;
   let raikyaku: [i32; 7] = [521, 195, 221, 329, 352, 399, 450];

   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   let y  = x.trim_end().to_owned();
   a = y.parse::<usize>().unwrap();
   while a != 9 {
      if (a < 0 || a > 6) {
         println!("error");
      } else {
         println!("{}人", raikyaku[a]);
      }
      let mut x = String::new();
      std::io::stdin().read_line(&mut x).expect("Failed to read line");
      x = x.trim_end().to_owned();
      a = x.parse::<usize>().unwrap();
   }
}

fn main() {

   let raikyaku: [i32; 7] = [521, 195, 221, 329, 352, 399, 450];
   let (mut t, mut i) = (0, 0);

   while i < 7 {
      t = t + raikyaku[i];
      i += 1;
   }

   let av = t / i as i32;
   println!("合計: {}", t);
   println!("平均: {}", av);
}

合計: 2467
平均: 352

【Rust】OpCodeのバイトコード(u8)へのシリアライズ•デシリアライズ

バイトコードに変換するのはあくまでOpCode, Argであって、OpCodeと引数を元に処理するプログラム自体はバイトコードには変換しない。Instruction自体は別に持っておく。

use std::io::{BufReader, BufWriter, Read, Write};

#[derive(Debug, Clone, Copy)]
#[repr(u8)]
pub enum OpCode {
    LoadLiteral,
    Add,
}

impl From<u8> for OpCode {
    #[allow(non_upper_case_globals)]
    fn from(o: u8) -> Self {
      const LoadLiteral: u8 = OpCode::LoadLiteral as u8;
      const Add: u8 = OpCode::Add as u8;
  
      match o {
        LoadLiteral => OpCode::LoadLiteral,
        Add => OpCode::Add,
        _ => panic!("Opcode \"{:02X}\" unrecognized!", o),
      }
    }
  }

#[derive(Debug, Clone, Copy)]
#[repr(C)]
struct Instruction {
    op: OpCode,
    arg0: u8,
}

impl Instruction {
    fn new(op: OpCode, arg0: u8) -> Self {
        Self { op, arg0 }
    }

    fn serialize(
        &self,
        writer: &mut impl Write,
    ) -> Result<(), std::io::Error> {
        writer.write_all(&[self.op as u8, self.arg0])?;
        Ok(())
    }
}

fn write_program(file: &str) {
    let instructions = [
        Instruction::new(OpCode::LoadLiteral, 42),
        Instruction::new(OpCode::LoadLiteral, 36),
        Instruction::new(OpCode::Add, 0),
    ];

    if let Ok(writer) = std::fs::File::create(file) {
        let mut writer = BufWriter::new(writer);
        for instruction in &instructions {
            instruction.serialize(&mut writer).unwrap();
        }
        println!("Written {} instructions", instructions.len());
    }
}

fn main() {
    write_program("bytecode.bin");
}

fn interpret(instructions: &[Instruction]) -> Option<i64> {
    let mut stack = vec![];

    for instruction in instructions {
        match instruction.op {
          OpCode::LoadLiteral => {
            stack.push(instruction.arg0 as i64);
          }
          OpCode::Add => {
            let rhs = stack.pop().expect("Stack underflow");
            let lhs = stack.pop().expect("Stack underflow");
            stack.push(lhs + rhs);
          }
        }
      }
    stack.pop()
}

なるほど、データの流れは理解できました。

### デシリアライズ

use std::io::{BufReader, BufWriter, Read, Write};

#[derive(Debug, Clone, Copy)]
#[repr(u8)]
pub enum OpCode {
    LoadLiteral,
    Add,
}

impl From<u8> for OpCode {
    #[allow(non_upper_case_globals)]
    fn from(o: u8) -> Self {
      const LoadLiteral: u8 = OpCode::LoadLiteral as u8;
      const Add: u8 = OpCode::Add as u8;
  
      match o {
        LoadLiteral => OpCode::LoadLiteral,
        Add => OpCode::Add,
        _ => panic!("Opcode \"{:02X}\" unrecognized!", o),
      }
    }
  }

#[derive(Debug, Clone, Copy)]
#[repr(C)]
struct Instruction {
    op: OpCode,
    arg0: u8,
}

impl Instruction {
    fn new(op: OpCode, arg0: u8) -> Self {
        Self { op, arg0 }
    }

    fn serialize(
        &self,
        writer: &mut impl Write,
    ) -> Result<(), std::io::Error> {
        writer.write_all(&[self.op as u8, self.arg0])?;
        Ok(())
    }

    fn deserialize(
        reader: &mut impl Read,
    ) -> Result<Self, std::io::Error> {
        let mut buf = [0u8; 2];
        reader.read_exact(&mut buf)?;
        Ok(Self::new(buf[0].into(), buf[1]))
    }
}

fn write_program(file: &str) {
    let instructions = [
        Instruction::new(OpCode::LoadLiteral, 42),
        Instruction::new(OpCode::LoadLiteral, 36),
        Instruction::new(OpCode::Add, 0),
    ];

    if let Ok(writer) = std::fs::File::create(file) {
        let mut writer = BufWriter::new(writer);
        for instruction in &instructions {
            instruction.serialize(&mut writer).unwrap();
        }
        println!("Written {} instructions", instructions.len());
    }
}

fn read_program(file: &str) -> Option<Vec<Instruction>> {
    if let Ok(reader) = std::fs::File::open(file) {
        let mut reader = BufReader::new(reader);
        let mut instructions = vec![];
        while let Ok(inst) = Instruction::deserialize(&mut reader) {
            instructions.push(inst);
        }
        Some(instructions)
    } else {
        None
    }
}

fn main() {
    let mut args = std::env::args();
    args.next();
    match args.next().as_ref().map(|s| s as &str) {
        Some("w") => write_program("bytecode.bin"),
        Some("r") => {
            if let Some(instructions) = read_program("bytecode.bin") {
                let result = interpret(&instructions);
                println!("result: {result:?}");
            }
        }
        _ => println!("Please specify w or r as an argument"),
    }
    
}

fn interpret(instructions: &[Instruction]) -> Option<i64> {
    let mut stack = vec![];

    for instruction in instructions {
        match instruction.op {
          OpCode::LoadLiteral => {
            stack.push(instruction.arg0 as i64);
          }
          OpCode::Add => {
            let rhs = stack.pop().expect("Stack underflow");
            let lhs = stack.pop().expect("Stack underflow");
            stack.push(lhs + rhs);
          }
        }
      }
    stack.pop()
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.61s
Running `target/debug/ruscal r`
result: Some(78)

バイトコードを読み取って、スタックを実行している。

【Rust】Tree構造の構築

fn main() {
    let s = "Hello world";
    println!("source: {:?}, parsed:\n {:?}", s, source(s));
  
    let s = "(123  456 ) world";
    println!("source: {:?}, parsed:\n {:?}", s, source(s));
  
    let s = "((car cdr) cdr)";
    println!("source: {:?}, parsed:\n {:?}", s, source(s));
  
    let s = "()())))((()))";
    println!("source: {:?}, parsed:\n {:?}", s, source(s));
  }
  
  fn advance_char(input: &str) -> &str {
    let mut chars = input.chars();
    chars.next();
    chars.as_str()
  }
  
  fn peek_char(input: &str) -> Option<char> {
    input.chars().next()
  }
  
  fn source(mut input: &str) -> (&str, TokenTree) {
    let mut tokens = vec![];
    while !input.is_empty() {
      input = if let Some((next_input, token)) = token(input) {
        match token {
          Token::LParen => {
            let (next_input, tt) = source(next_input);
            tokens.push(tt);
            next_input
          }
          Token::RParen => {
            return (next_input, TokenTree::Tree(tokens))
          }
          _ => {
            tokens.push(TokenTree::Token(token));
            next_input
          }
        }
      } else {
        break;
      }
    }
    (input, TokenTree::Tree(tokens))
  }
  
  #[derive(Debug, PartialEq)]
  enum Token<'src> {
    Ident(&'src str),
    Number(f64),
    LParen,
    RParen,
  }
  
  #[derive(Debug, PartialEq)]
  enum TokenTree<'src> {
    Token(Token<'src>),
    Tree(Vec<TokenTree<'src>>),
  }
  
  fn token(input: &str) -> Option<(&str, Token)> {
    if let Some(res) = ident(whitespace(input)) {
      return Some(res);
    }
  
    if let Some(res) = number(whitespace(input)) {
      return Some(res);
    }
  
    if let Some(res) = lparen(whitespace(input)) {
      return Some(res);
    }
  
    if let Some(res) = rparen(whitespace(input)) {
      return Some(res);
    }
  
    None
  }
  
  fn whitespace(mut input: &str) -> &str {
    while matches!(peek_char(input), Some(' ')) {
      let mut chars = input.chars();
      chars.next();
      input = chars.as_str();
    }
    input
  }
  
  fn ident(mut input: &str) -> Option<(&str, Token)> {
    let start = input;
    if matches!(
      peek_char(input),
      Some(_x @ ('a'..='z' | 'A'..='Z'))
    ) {
      input = advance_char(input);
      while matches!(
        peek_char(input),
        Some(_x @ ('a'..='z' | 'A'..='Z' | '0'..='9'))
      ) {
        input = advance_char(input);
      }
      Some((
        input,
        Token::Ident(&start[..(start.len() - input.len())]),
      ))
    } else {
      None
    }
  }
  
  fn number(mut input: &str) -> Option<(&str, Token)> {
    let start = input;
    if matches!(
      peek_char(input),
      Some(_x @ ('-' | '+' | '.' | '0'..='9'))
    ) {
      input = advance_char(input);
      while matches!(
        peek_char(input),
        Some(_x @ ('.' | '0'..='9'))
      ) {
        input = advance_char(input);
      }
      if let Ok(num) =
        start[..(start.len() - input.len())].parse::<f64>()
      {
        Some((input, Token::Number(num)))
      } else {
        None
      }
    } else {
      None
    }
  }
  
  fn lparen(mut input: &str) -> Option<(&str, Token)> {
    if matches!(peek_char(input), Some('(')) {
      input = advance_char(input);
      Some((input, Token::LParen))
    } else {
      None
    }
  }
  
  fn rparen(mut input: &str) -> Option<(&str, Token)> {
    if matches!(peek_char(input), Some(')')) {
      input = advance_char(input);
      Some((input, Token::RParen))
    } else {
      None
    }
  }
  
  #[cfg(test)]
  mod test {
    use super::*;
  
    #[test]
    fn test_whitespace() {
      assert_eq!(whitespace("    "), "");
    }
  
    #[test]
    fn test_ident() {
      assert_eq!(ident("Adam"), Some(("", Token::Ident("Adam"))));
    }
  
    #[test]
    fn test_number() {
      assert_eq!(
        number("123.45 "),
        Some((" ", Token::Number(123.45)))
      );
    }
  }

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.85s
Running `target/debug/ruscal`
source: “Hello world”, parsed:
(“”, Tree([Token(Ident(“Hello”)), Token(Ident(“world”))]))
source: “(123 456 ) world”, parsed:
(“”, Tree([Tree([Token(Number(123.0)), Token(Number(456.0))]), Token(Ident(“world”))]))
source: “((car cdr) cdr)”, parsed:
(“”, Tree([Tree([Tree([Token(Ident(“car”)), Token(Ident(“cdr”))]), Token(Ident(“cdr”))])]))
source: “()())))((()))”, parsed:
(“))((()))”, Tree([Tree([]), Tree([])]))

【Rust】括弧によるグループ化

fn main() {
    let input = "123 456 world";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "(car cdr) cdr";
    println!("source: {}, parsed: {:?}", input, source(input));

    let input = "()())))((()))";
    println!("source: {}, parsed: {:?}", input, source(input));
}

fn advance_char(input: &str) -> &str {
    let mut chars = input.chars();
    chars.next();
    chars.as_str()
}

fn peek_char(input: &str) -> Option<char> {
    input.chars().next()
}

fn source(mut input: &str) -> Vec<Token> {
    let mut tokens = vec![];
    while !input.is_empty() {
        input = if let (next_input, Some(token)) = token(input) {
            tokens.push(token);
            next_input
        } else {
            break;
        }
    }
    tokens
}

#[derive(Debug, PartialEq, Eq)]
enum Token {
    Ident,
    Number,
    LParen,
    RParen,
}

fn token(i: &str) -> (&str, Option<Token>) {
    if let (i, Some(ident_res)) = ident(whitespace(i)) {
        return (i, Some(ident_res));
    }

    if let (i, Some(number_res)) = number(whitespace(i)) {
        return (i, Some(number_res));
    }

    if let (i, Some(lparen_res)) = lparen(whitespace(i)) {
        return (i, Some(lparen_res));
    }

    if let (i, Some(rparen_res)) = rparen(whitespace(i)) {
        return (i, Some(rparen_res));
    }

    (whitespace(i), None)
}

fn whitespace(mut input: &str) -> &str {
    while matches!(input.chars().next(), Some(' ')) {
        input = advance_char(input);
    }
    input
}

fn ident(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        peek_char(input),
        Some(_x @ ('a'..='z' | 'A'..='Z'))
    ) {
        input = advance_char(input);
        while matches!(
            peek_char(input),
            Some(_x @ ('a'..='z' | 'A'..='Z' | '0'..='9'))
        ) {
            input = advance_char(input);
        }
        (input, Some(Token::Ident))
    } else {
        (input, None)
    }
}

fn number(mut input: &str) -> (&str, Option<Token>) {
    if matches!(
        peek_char(input),
        Some(_x @ ('-'|'+'|'.'|'0'..='9'))
    ) {
        input = advance_char(input);
        while matches!(
            peek_char(input),
            Some(_x @ ('.'|'0'..='9'))
        ) {
            input = advance_char(input);
        }
        (input, Some(Token::Number))
    } else {
        (input, None)
    }
}

fn lparen(mut input: &str) -> (&str, Option<Token>) {
    if matches!(peek_char(input), Some('(')) {
        input = advance_char(input);
        (input, Some(Token::LParen))
    } else {
        (input, None)
    }
}

fn rparen(mut input: &str) -> (&str, Option<Token>) {
    if matches!(peek_char(input), Some(')')) {
        input = advance_char(input);
        (input, Some(Token::RParen))
    } else {
        (input, None)
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_whitespace() {
        assert_eq!(whitespace("    "), "");
    }

    #[test]
    fn test_indent() {
        assert_eq!(ident("Adam"), "");
    }

    #[test]
    fn test_number() {
        assert_eq!(number("123.45 "), " ");
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.58s
Running `target/debug/ruscal`
source: 123 456 world, parsed: [Number, Number, Ident]
source: (car cdr) cdr, parsed: [LParen, Ident, Ident, RParen, Ident]
source: ()())))((())), parsed: [LParen, RParen, LParen, RParen, RParen, RParen, RParen, LParen, LParen, LParen, RParen, RParen, RParen]

Category: Rust