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

最近話題のネタ「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 とか 3⁹ に間違えてて、パターン列挙するだけで時間浪費してつらい（正しくは 3⁸ 通り）。机上でアルゴリズム組んでから書くべきだった。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