TopCoder - Problem Statement for Chopsticks を Rust で実装してみる

TopCoder の Problem Statement for Chopstics を Rust で実装した例として載せておきます。いつまでモチベーションが続くかわかりませんが、定期的に問題を問いては載せておこうかと思います。ブログ書くと結構モチベーションになるかもしれませんね。

問題はだいたい次のような意味で、詳細な条件はページに飛んでください。

Cat Carol は友だち数人を家に招待したいと思っています。Carol はそれぞれちょっとだけ長さが違う箸を何本か持っています。お客さんは、2つの箸を受け取らないといけません。そして、2つの箸を受け取る際には、それら箸の長さはそれぞれ揃っていなければなりません。

今あなたのもとには int[] の length があります。各 length が示すのは、 Carol のもつ箸1本1本の長さです。Carol が招待できる友人の数を計算して出力してください。

要約すると、

それぞれある長さを持つ箸の情報が配列で与えられ、
ペアが作成可能であれば、1ペアとしてカウント。
最終的に何ペア作成できたかを出力。

という問題で、問題を解く方針としては、

各長さごとにカウンタを用意する。
最終的に各長さごとにもう一度イテレートし、2で割ってそれらを合計する。

という流れで十分かなと思います。下に Rust コードのサンプルを載せてあるので、答えみたくない方はここで止めてください。

fn main() {
    // ここいるのかはツッコまないでください
    let length = vec![5, 5];
    getmax(&length);
}

fn getmax(length: &Vec<i32>) -> i32 {
    let mut num = vec![0; 101];

    for i in 0..length.len() {
        num[length[i] as usize] += 1;
    }

    let mut result = 0;

    for i in 0..num.len() {
        result += num[i] / 2;
    }

    println!("{}", result);
    result
}

#[test]
fn example_0() {
    let test_data = vec![5, 5];
    assert!(getmax(&test_data) == 1);
}

#[test]
fn exmaple_1() {
    let test_data = vec![1];
    assert!(getmax(&test_data) == 0);
}

#[test]
fn example_2() {
    let test_data = vec![1, 2, 3, 2, 1, 2, 3, 2, 1];
    assert!(getmax(&test_data) == 4);
}

#[test]
fn example_3() {
    let test_data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
    assert!(getmax(&test_data) == 0);
}

#[test]
fn example_4() {
    let test_data = vec![35,35,35,50,16,30,10,10,35,50,16,16,16,30,50,30,16,35,50,30,10,50,50,16,16,
10,35,50,50,50,16,35,35,30,35,10,50,10,50,50,16,30,35,10,10,30,10,10,16,35];
    assert!(getmax(&test_data) == 24);
}

あとは、cargo test で、この実装がうまくいっているかどうかだけはわかります。

今回問題を問いていて Rust の実装側で気になった点をメモしておこうと思います。Rust を触り始めてまだ日が浅いので、誰か詳しい方いたら教えてください。

配列インデックスの変換方法について: num[length[i] as usize] として、とりあえず強引に i32 を usize に変換する処理を噛ませたけれど、length[i] をもっと賢く変換する方法があれば。もしくは変換のいらない方法。length は必ず i32 or i64 (integer型) で宣言する必要があるという問題上の制約を破ることはできませんが。
2度出てくる for 文: これはマクロにできる気がする？
周辺ツールの話: rustfmt 、配列が長くなると全部縦に並べるようなのですが、非常に見づらいのでなんとかならないですかね。たとえば、テストケースの example_4() の中の配列、rustfmt でフォーマットがかかると悲しいくらいに縦長になります。

感想とか

最初、HashMap で値を保持しようとして一度実装してみたのですが、よくよく考えたら配列でも保持可能だなということに気づいて修正しました。正直もともと Java 畑なのと、普段からコレクションの方が馴染みがあるので、まずコレクションで考えて、それを配列だけで表現するとどうなるんだろう？と考えるとはやいのかなと思いました。

multiplus

気まぐれに書評とか。

TopCoder - Problem Statement for Chopsticks を Rust で実装してみる

感想とか