LoginSignup
14
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@yohhoy

rustcに怒られながら「1時間以内に～プログラマ失格」にトライした話

Last updated at Posted at 2015-05-27

最近話題のネタ「1時間以内に解けなければプログラマ失格となってしまう5つの問題」にRust歴 2週間未満の状態でチャレンジ。

  • レギュレーション：Rust Playground(Stable Channel)利用。問題は全部初見（他人/他言語の解答例を見ていない状態）。
  • 結果：計37分間かけて3問目途中で未完。Rustプログラマにはなれなかったよ…
  • TODO：あとで続きをやる 3〜5問目は125分間。全体で約160分間(＝2時間40分)でおしまい。

問題1

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

sum2は最初index方式で書いたのをイテレータ方式にリファクタリング。【7分】

fn sum1(list: &[i32]) -> i32 {
  let mut acc = 0;
  for i in list {
    acc += *i;
  }
  acc
}

fn sum2(list: &[i32]) -> i32 {
  let mut itr = list.iter();
  let mut acc = 0;
  while let Some(e) = itr.next() {
    acc += *e;
  }
  acc
}

fn sum3(list: &[i32]) -> i32 {
  if list.is_empty() {
    0
  } else {
    list[0] + sum3(&list[1..])
  }
}

fn main() {
  let list : Vec<i32> = (1..11).collect();
  println!("sum1={}", sum1(&list));
  println!("sum2={}", sum2(&list));
  println!("sum3={}", sum3(&list));
}

問題2

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

異なる長さのリストにも対応。文字/数値混在だと型ではまるのが目に見えてるので、（問題文にも制約がないし）全部charということにして回避。最初はif式羅列で解いたが、あまりにひどいのでmatch式1個に整理。【15分】

fn zip(l1: &[char], l2: &[char]) -> Vec<char> {
  let mut result: Vec<char> = Vec::new();
  let (mut i1, mut i2) = (l1.iter(), l2.iter());
  loop {
    match (i1.next(), i2.next()) {
      (Some(e1), Some(e2)) => {
        result.push(*e1);
        result.push(*e2);
      },
      (Some(e1), None) => {
        result.push(*e1);
      },
      (None, Some(e2)) => {
        result.push(*e2);
      },
      _ => break
    };
  }
  result
}

fn main() {
  let list1 = vec!['a', 'b', 'c'];
  let list2 = vec!['1', '2', '3'];
  println!("zip={:?}", zip(&list1, &list2));
}

後日談：標準ライブラリにIterator::zip()関数あるんだから、そっち使えば良いでしょと思ったらrustcに散々怒られた。とりあえず通ったのは下記。vec!(Vec型)のところを配列型に出来ないかといじってみたもののborrow checkerに敗北。

fn zip(l1: &[char], l2: &[char]) -> Vec<char> {
  l1.iter().zip(l2.iter())
    .flat_map(|(&a,&b)| vec!(a,b).into_iter())
    .collect()
}

問題3（前半戦）

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

最初はiter().take(...).map(|n| *n)と書いていてiter()とinto_iter()の違いを理解してないことを理解した。RustだとPython的な(a,b) = (b,c)のような一括代入は無理？100個出すのは play.rust-lang.org だとnumクレート／多倍長整数型が使えずに詰んだ。【15分/未完】

fn fib(n: u32) -> Vec<u32> {
  let mut seq = vec!(0, 1);
  if n < 3 {
    return seq.into_iter().take(n as usize).collect();
  }
  let (mut a, mut b) = (0, 1);
  for _ in 2..n {
    let c = a + b;
    seq.push(c);
    a = b;
    b = c;
  }
  seq
}

fn main() {
  println!("fib={:?}", fib(2));
  println!("fib={:?}", fib(10));
  // println!("fib={:?}", fib(100));
  // thread '<main>' panicked at 'arithmetic operation overflowed'
}

問題3（後半戦）

加算さえできれば十分なので多倍長整数型を自作した。Vec<T>フィールドを含む場合はCopyトレイト実装不可とか怒られたけど理由がわからない。しかたないのでclone()乱発。ゴリ押しだが動けばよかろう。【40分】

use std::ops::Add;
use std::fmt::{Debug, Formatter, Error};

struct MyUint(Vec<u8>);

impl Clone for MyUint {
  fn clone(&self) -> Self { MyUint(self.0.clone()) }
  fn clone_from(&mut self, _: &Self) { unimplemented!(); }
}

impl Add for MyUint {
  type Output = MyUint;
  fn add(self, rhs: MyUint) -> MyUint {
    let mut result = Vec::new();
    let mut lhs = self.0.into_iter();
    let mut rhs = rhs.0.into_iter();
    let mut carry = 0;
    loop {
      match (lhs.next(), rhs.next()) {
        (Some(l), Some(r)) => {
          let n = l + r + carry;
          result.push(n % 100);
          carry = n / 100;
        },
        (Some(v), _) | (_, Some(v)) => {
          let n = v + carry;
          result.push(n % 100);
          carry = n / 100;
        }
        _ => {
          if 0 < carry { result.push(carry) }
          break;
        }
      }
    }
    MyUint(result)
  }
}

impl Debug for MyUint {
  fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
    let mut s = String::new();
    for n in (&self.0).iter() {
      s = format!("{:02}{}", *n, s);
    }
    if s.starts_with("0") {
      s.remove(0);
    }
    write!(f, "{}", s)
  }
}

fn fib(n: usize) -> Vec<MyUint> {
  let mut seq = vec!(MyUint(vec!(0)), MyUint(vec!(1)));
  if n < 3 {
    return seq.into_iter().take(n as usize).collect();
  }
  let (mut a, mut b) = (seq[0].clone(), seq[1].clone());
  for _ in 2..n {
    let c = a.clone() + b.clone();
    seq.push(c.clone());
    a = b;
    b = c;
  }
  seq
}

fn main() {
  println!("fib={:?}", fib(100));
}

後日談：中途半端なCloneトレイト実装するくらいなら#[derive(Clone)]でよい。result.push(...); carry=...;重複は排除可能。変数c計算時のaでclone()呼出はムダ。改善後コード＠Gist

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。

Rustは文字列処理がつらい。リスト処理よりもつらい。ひねくり回せば1論理行で書けそうな気がしたけど諦めた。format!マクロに頼りすぎ。【15分】

fn solve(list: &[i32]) -> String {
  let mut list = list.iter()
    .map(|&n| n.to_string())
    .collect::<Vec<String>>();
  list.sort();
  list.reverse();
  list.connect("")
}

fn main() {
  let list = [50, 2, 1, 9];
  println!("solve={}", solve(&list));
}

後日談：アルゴリズム間違ってる。[420, 42, 423]で42342042を返す（正しくは42423420）。sort＋reverseするなら最初から逆順ソートしときゃいい。改善後コード＠Gist

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。

出だしから組合せ総数を 9*3 とか 39 に間違えてて、パターン列挙するだけで時間浪費してつらい（正しくは 38 通り）。机上でアルゴリズム組んでから書くべきだった。Rustっぽいコードになったかは不明。あとCのノリで考えてると文字/文字列の扱いがやっぱりつらい。【70分】

#[derive(Copy,Clone)]
enum Op {
  Concat,
  Plus,
  Minus
}

impl Op {
  fn new(n: usize) -> Op {
    match n {
      0 => Op::Concat,
      1 => Op::Plus,
      2 => Op::Minus,
      _ => panic!()
    }
  }
}

fn eval(ops: &[Op; 9], target: i64) -> bool {
  let mut val = 0;
  let mut acc = 1;  // digit '1'
  let mut prev = Op::Concat;
  for i in 0..9 {
    let digit = (i as i64) + 2;
    match ops[i] {
      Op::Concat => {
        acc = acc * 10 + digit
      },
      op @ _ => {
        match prev {
          Op::Concat => { val = acc },
          Op::Plus => { val += acc },
          Op::Minus => { val -= acc },
        }
        acc = digit;
        prev = op;
      }
    }
  }
  target == val
}

fn dump(ops: &[Op; 9]) {
  let mut s = "1".to_string();
  for n in 0..8 {
    match ops[n] {
      Op::Plus => { s.push('+') },
      Op::Minus => { s.push('-') },
      _ => (),
    }
    s.push(('2' as u8 + n as u8) as char);
  }
  println!("{}", s);
}

fn solve() {
  let mut ops = [Op::Concat; 9];
  ops[8] = Op::Plus;
  for n in 0..(3usize.pow(8)) {
    let mut m = n;
    for i in 0..8 {
      ops[i] = Op::new(m % 3);
      m /= 3;
    }
    if eval(&ops, 100) {
      dump(&ops);
    }
  }
}

fn main() {
  solve();
}

後日談：型変換処理なのでOp::newよりもOp::fromの方が適切か。バイナリリテラルb'2'なら最初からu8型。出力の並びの良さからパターン列挙順を反転。改善後コード＠Gist

14
14
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?