MoonBit Online Judgeを使って競プロ形式でMoonBitを勉強した/Rustと書き味を比較してみる
はじめに
MoonBit Online Judgeは、MoonBit公式が設置している、問題を解きながらMoonBitを学習できるサービスです。
サービスを紹介し、その後いくつかの問題を見ながら、MoonBitとRustを比べつつ感想を書きます。
MoonBit Online Judgeの使い方
MoonBit Online Judgeのページにアクセスすると、以下のような画面が開きます。
右上にあるLoginをクリックして、GitHubアカウントを利用してログインします。ログインしないと提出することができないので、注意してください。
一番上にあるSupply Problem in Hikingという問題を開いてみます。
右上に問題文が表示され、その下にテストケースがあります。また、左上でソースコードを編集できるようになっています。
はじめ、ソースコードは以下のようになっています。
///|
fn solution(k : Int, data : Array[Int]) -> Int {
...
}
また、テストケースは以下のようになっています。
///|
test {
inspect!(solution(2, [1, 2, 3, 3, 2]), content="9")
inspect!(solution(3, [4, 1, 5, 2, 1, 3]), content="9")
inspect!(solution(1, [3, 2, 4, 1]), content="10")
inspect!(solution(1, [5, 3, 2, 4, 1]), content="15")
}
このテストを通過するようにソースコードを編集し、Submitボタンを押して提出するという流れになっています。
問題としては、簡単なものから、コンピュータサイエンスや競技プログラミングで有名な問題までいろいろと用意されています。また、ある程度完成されたソースコードから誤りを見つけるような問題もあります。
MoonBitとRustを比べてみる
いくつかの問題を紹介し、その答えを提示しながら、MoonBitでプログラムを書いた感想を書きます。私は競技プログラミングをRustで取り組んでいたので、Rustで同じ問題の答えを書いてみて、それと比較する形を取ります。[1]
Count Liars (メソッドチェーン)
問題
scores[i]で与えられます。
生徒は、以下の条件で嘘つきになります。
- 自分の点数以下の生徒は、自分の点数より大きい生徒の数よりも多い
嘘つきの数を求めてください。
比較
それぞれ以下のように書けます。
///|
fn solution(scores : Array[Int]) -> Int {
scores
.filter(fn(score) {
let higher_count = scores.filter(fn(s) { s > score }).length()
higher_count <= scores.length() - higher_count - 1
})
.length()
}
fn solution(scores: &[u32]) -> usize {
scores
.iter()
.filter(|score| {
let higher_count = scores.iter().filter(|s| s > score).count();
higher_count <= scores.len() - higher_count - 1
})
.count()
}
よくあるメソッドチェーンですが、大体同じように書けています。
RPN Calculator (matchの使い方)
問題
逆ポーランド記法で算術式が与えられるので、その値を計算してください。
ただし、値はすべて符号なし32-bit整数であるとし、二項演算は+, -, *のみであるとします。
比較
スタックに値を積んでよしなに処理するのが一般的なので、どちらもその方法を取ります。
それぞれ以下のように書けます。
///|
fn solution(s : String) -> UInt! {
let s = s.split(" ")
let stack = []
for s in s {
match s {
"" => continue
"+" | "-" | "*" => {
let a = stack.pop().unwrap()
let b = stack.pop().unwrap()
match s {
"+" => stack.push(b + a)
"-" => stack.push(b - a)
"*" => stack.push(b * a)
_ => abort("unreachable")
}
}
_ => stack.push(@strconv.FromStr::from_string(s.to_string()))
}
}
stack[0]
}
fn solution(s: &str) -> u32 {
let mut stack = vec![];
for s in s.split_ascii_whitespace() {
match s {
"" => continue,
"+" | "-" | "*" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
match s {
"+" => stack.push(b + a),
"-" => stack.push(b - a),
"*" => stack.push(b * a),
_ => unreachable!(),
}
}
_ => stack.push(u32::from_str_radix(s, 10).unwrap()),
}
}
stack[0]
}
match式も大体同じような書き味です。
MoonBitのエラー処理は、返り値の型をT raiseのようにして、エラーが発生しうることを表現します。(Judgeのバージョンが古いので、T!と書いていることに注意してください。)
上の例では、@strconv.FromStr::from_string(s.to_string())の部分でエラーが発生したら、それを伝搬することができます。
競技プログラミングの文脈でエラー処理を説明する例を取り上げるのは難しいのですが、Rustよりエラー処理が書きやすくなっていると思います。
Supply Problem in Hiking (平衡二分探索木)
問題
data[i]円かかります。
また、食料は
旅行を完遂するために必要な費用の最小値を計算してください。
比較
逆に、この買い方を毎日行っても、持ち運べる食料の制限に抵触しないので、この買い方が最善であると分かります。
それぞれ以下のように書けます。
///|
pub fn solution(k : Int, data : Array[Int]) -> Int {
let set = @sorted_map.new()
let mut ans = 0
for i in 0..<data.length() {
let c = set.get(data[i]).or_default()
set[data[i]] = c + 1
if i >= k {
let c = set.get(data[i - k]).unwrap()
if c == 1 {
set.remove(data[i - k])
} else {
set[data[i - k]] = c - 1
}
}
let (m, _) = set.iter().head().unwrap()
ans += m
}
ans
}
use std::collections::BTreeMap;
fn solution(k: usize, data: &[u64]) -> u64 {
let mut set: BTreeMap<u64, usize> = BTreeMap::new();
let mut ans = 0;
for i in 0..data.len() {
*set.entry(data[i]).or_default() += 1;
if i >= k {
let c = set.entry(data[i - k]).or_default();
if *c == 1 {
set.remove(&data[i - k]);
} else {
*c -= 1;
}
}
let (m, _) = set.iter().next().unwrap();
ans += m;
}
ans
}
RustにはEntry APIがあり、値の取得や更新、削除をいい感じに書くことができます。
MoonBitでは、Optionであればunwrap_or()や、hashmapであればget_or_default()のような関数が用意されており完全に同じではないものの、似たような書き味で書くことができます。
Sliding Window Maximum (構造体、Trait)
問題
配列arrと整数msという配列を生成してください。ただし、ms[i]は
比較
上の問題の最大値バージョンです。今度はセグメント木を実装して求めることにします。計算量は
それぞれ以下のように書けます。
///|
fn solution(arr : Array[Int], k : Int) -> Array[Int] {
let segtree = SegTree::make(arr.length(), fn(a, b) { @math.maximum(a, b) }, 0)
for i, a in arr {
segtree.update(i, a)
}
let ans = []
for i in 0..<(arr.length() - k + 1) {
let a = segtree.prod(i, i + k)
ans.push(a)
}
ans
}
///|
struct SegTree[T] {
tree : Array[T]
op : (T, T) -> T
e : T
size : Int
} derive(Show)
///|
fn[T] SegTree::make(size : Int, op : (T, T) -> T, e : T) -> SegTree[T] {
SegTree::{ tree: Array::make(size << 1, e), op, e, size }
}
///|
fn[T] SegTree::update(self : SegTree[T], i : Int, s : T) -> Unit {
let mut i = i + self.size
self.tree[i] = s
while i > 1 {
i = i >> 1
self.tree[i] = (self.op)(self.tree[i << 1], self.tree[(i << 1) | 1])
}
}
///|
fn[T] SegTree::prod(self : SegTree[T], left : Int, right : Int) -> T {
let mut left = left + self.size
let mut right = right + self.size
let mut sl = self.e
let mut sr = self.e
while left < right {
if (left & 1) == 1 {
sl = (self.op)(sl, self.tree[left])
left += 1
}
if (right & 1) == 1 {
right -= 1
sr = (self.op)(self.tree[right], sr)
}
left = left >> 1
right = right >> 1
}
(self.op)(sl, sr)
}
fn solution(arr: &[u32], k: usize) -> Vec<u32> {
let mut segtree = SegmentTree::new(arr.len(), |x, y| std::cmp::max(*x, *y), 0);
for i in 0..arr.len() {
segtree.update(i, arr[i]);
}
let mut ans = vec![];
for i in 0..arr.len() + 1 - k {
let a = segtree.prod(i, i + k);
ans.push(a);
}
ans
}
struct SegmentTree<T> {
size: usize,
tree: Vec<T>,
op: fn(&T, &T) -> T,
e: T,
}
impl<T: Clone> SegmentTree<T> {
fn new(size: usize, op: fn(&T, &T) -> T, e: T) -> Self {
Self {
size,
tree: vec![e.clone(); size << 1],
op,
e,
}
}
fn update(&mut self, mut i: usize, s: T) {
assert!(i < self.size);
i += self.size;
self.tree[i] = s;
while i > 1 {
i >>= 1;
self.tree[i] = (self.op)(&self.tree[i << 1], &self.tree[i << 1 | 1]);
}
}
fn prod(&self, mut left: usize, mut right: usize) -> T {
left += self.size;
right += self.size;
let (mut sl, mut sr) = (self.e.clone(), self.e.clone());
while left < right {
if left & 1 == 1 {
sl = (self.op)(&sl, &self.tree[left]);
left += 1;
}
if right & 1 == 1 {
right ^= 1;
sr = (self.op)(&self.tree[right], &sr);
}
left >>= 1;
right >>= 1;
}
(self.op)(&sl, &sr)
}
}
MoonBitでは、for i, a in arr {...}の形でarrのi番目の要素aを取り出せます。
構造体については少し書き方は異なるものの、慣れれば違和感なく書けると思います。
Rustでセグメント木を実装するパターンでよくあるものとして、以下のようにTraitでモノイドを表現して書くやり方がありますが、MoonBitではTraitが関連型を持てないので、表現できません。
struct SegmentTree<M: Monoid> {
size: usize,
tree: Vec<M::S>,
}
trait Monoid {
type S;
fn op(lhs: &Self::S, rhs: &Self::S) -> Self::S;
const E: Self::S;
}
struct Max<T> {
_marker: std::marker::PhantomData<T>,
}
impl Monoid for Max<u32> {
type S = u32;
fn op(lhs: &Self::S, rhs: &Self::S) -> Self::S {
std::cmp::max(*lhs, *rhs)
}
const E: Self::S = 0;
}
fn solution(arr: &[u32], k: usize) -> Vec<u32> {
let mut segtree: SegmentTree<Max<u32>> = SegmentTree::new(arr.len());
for i in 0..arr.len() {
segtree.update(i, arr[i]);
}
...
全体
struct SegmentTree<M: Monoid> {
size: usize,
tree: Vec<M::S>,
}
trait Monoid {
type S;
fn op(lhs: &Self::S, rhs: &Self::S) -> Self::S;
const E: Self::S;
}
struct Max<T> {
_marker: std::marker::PhantomData<T>,
}
impl Monoid for Max<u32> {
type S = u32;
fn op(lhs: &Self::S, rhs: &Self::S) -> Self::S {
std::cmp::max(*lhs, *rhs)
}
const E: Self::S = 0;
}
fn solution(arr: &[u32], k: usize) -> Vec<u32> {
let mut segtree: SegmentTree<Max<u32>> = SegmentTree::new(arr.len());
for i in 0..arr.len() {
segtree.update(i, arr[i]);
}
let mut ans = vec![];
for i in 0..arr.len() + 1 - k {
let a = segtree.prod(i, i + k);
ans.push(a);
}
ans
}
impl<M: Monoid<S = T>, T: Clone> SegmentTree<M> {
fn new(size: usize) -> Self {
Self {
size,
tree: vec![M::E; size << 1],
}
}
fn update(&mut self, mut i: usize, s: T) {
assert!(i < self.size);
i += self.size;
self.tree[i] = s;
while i > 1 {
i >>= 1;
self.tree[i] = (M::op)(&self.tree[i << 1], &self.tree[i << 1 | 1]);
}
}
fn prod(&self, mut left: usize, mut right: usize) -> T {
left += self.size;
right += self.size;
let (mut sl, mut sr) = (M::E, M::E);
while left < right {
if left & 1 == 1 {
sl = (M::op)(&sl, &self.tree[left]);
left += 1;
}
if right & 1 == 1 {
right ^= 1;
sr = (M::op)(&self.tree[right], &sr);
}
left >>= 1;
right >>= 1;
}
(M::op)(&sl, &sr)
}
}
もう少し抽象度を落とせば、MoonBitでも以下のように実装できます。[2]
///|
struct SegTree[T] {
tree : Array[T]
size : Int
}
///|
trait Monoid {
op(Self, Self) -> Self
e() -> Self
}
///|
struct Max[T](T)
///|
impl Monoid for Max[Int] with op(lhs : Max[Int], rhs : Max[Int]) {
Max(@math.maximum(lhs.0, rhs.0))
}
///|
impl Monoid for Max[Int] with e() {
Max(0)
}
...
全体
///|
struct SegTree[T] {
tree : Array[T]
size : Int
}
///|
trait Monoid {
op(Self, Self) -> Self
e() -> Self
}
///|
struct Max[T](T)
///|
impl Monoid for Max[Int] with op(lhs : Max[Int], rhs : Max[Int]) {
Max(@math.maximum(lhs.0, rhs.0))
}
///|
impl Monoid for Max[Int] with e() {
Max(0)
}
///|
fn[T : Monoid] SegTree::make(size : Int) -> SegTree[T] {
SegTree::{ tree: Array::make(size << 1, T::e()), size }
}
///|
fn[T : Monoid] SegTree::update(self : SegTree[T], i : Int, s : T) -> Unit {
let mut i = i + self.size
self.tree[i] = s
while i > 1 {
i = i >> 1
self.tree[i] = T::op(self.tree[i << 1], self.tree[(i << 1) | 1])
}
}
///|
fn[T : Monoid] SegTree::prod(self : SegTree[T], left : Int, right : Int) -> T {
let mut left = left + self.size
let mut right = right + self.size
let mut sl = T::e()
let mut sr = T::e()
while left < right {
if (left & 1) == 1 {
sl = T::op(sl, self.tree[left])
left += 1
}
if (right & 1) == 1 {
right -= 1
sr = T::op(self.tree[right], sr)
}
left = left >> 1
right = right >> 1
}
T::op(sl, sr)
}
///|
fn solution(arr : Array[Int], k : Int) -> Array[Int] {
let segtree : SegTree[Max[Int]] = SegTree::make(arr.length())
for i in 0..<arr.length() {
segtree.update(i, Max(arr[i]))
}
let ans = []
for i in 0..<(arr.length() - k + 1) {
let a = segtree.prod(i, i + k)
ans.push(a.0)
}
ans
}
Count Connected Regions (多重配列)
問題
0, 1からなる二次元グリッドが与えられます。グリッドの中で1が上下左右に連結している領域の数を求めてください。
比較
適当な探索アルゴリズムを用いればよいです。
それぞれ以下のように書けます。
///|
fn solution(grid : Array[Array[Int]]) -> Int {
let h = grid.length()
if h == 0 {
return 0
}
let w = grid[0].length()
let seen = Array::makei(h, fn(_) { Array::make(w, false) })
let mut ans = 0
for i in 0..<h {
for j in 0..<w {
if seen[i][j] || grid[i][j] == 0 {
continue
}
ans += 1
let q = [(i, j)]
seen[i][j] = true
while not(q.is_empty()) {
let (y, x) = q.pop().unwrap()
if y + 1 < h && not(seen[y + 1][x]) && grid[y + 1][x] == 1 {
q.push((y + 1, x))
seen[y + 1][x] = true
}
if x + 1 < w && not(seen[y][x + 1]) && grid[y][x + 1] == 1 {
q.push((y, x + 1))
seen[y][x + 1] = true
}
if y > 0 && not(seen[y - 1][x]) && grid[y - 1][x] == 1 {
q.push((y - 1, x))
seen[y - 1][x] = true
}
if x > 0 && not(seen[y][x - 1]) && grid[y][x - 1] == 1 {
q.push((y, x - 1))
seen[y][x - 1] = true
}
}
}
}
ans
}
fn solution(grid: Vec<Vec<u8>>) -> usize {
let h = grid.len();
if h == 0 {
return 0;
}
let w = grid[0].len();
let mut seen = vec![vec![false; w]; h];
let mut ans = 0;
for i in 0..h {
for j in 0..w {
if seen[i][j] || grid[i][j] == 0 {
continue;
}
ans += 1;
let mut q = vec![(i, j)];
seen[i][j] = true;
while let Some((y, x)) = q.pop() {
if y + 1 < h && !seen[y + 1][x] && grid[y + 1][x] == 1 {
q.push((y + 1, x));
seen[y + 1][x] = true;
}
if x + 1 < w && !seen[y][x + 1] && grid[y][x + 1] == 1 {
q.push((y, x + 1));
seen[y][x + 1] = true;
}
if y > 0 && !seen[y - 1][x] && grid[y - 1][x] == 1 {
q.push((y - 1, x));
seen[y - 1][x] = true;
}
if x > 0 && !seen[y][x - 1] && grid[y][x - 1] == 1 {
q.push((y, x - 1));
seen[y][x - 1] = true;
}
}
}
}
ans
}
二次元配列を作成するときは、let seen = Array::make(h, Array::make(w, false))のようにすると参照が複製され、一箇所を変更するとすべてが変更されるような望ましくない挙動になります。それを回避するためにlet seen = Array::makei(h, fn(_) { Array::make(w, false) })のように書きます。
MoonBit, Rust以外でも書いておくと、Pythonでのよくあるミスとして以下のようなものがありますが、これと同じ話です。
seen = [[False] * 2] * 3
seen[0][0] = True
print(seen[1][0]) # True
Array::make()にもその旨が記載されています。
Rustではwhile let Some(_) = ...のようなパターンマッチが可能ですが、今のところMoonBitではできないようです。
総括
Rustと構文が似ていることは確認できたと思います。
一般にRustといえば所有権やライフタイムが難しいとされがちですが、その辺を気にせず雑に書けて、型システムの恩恵もしっかり受けられるので、楽しい言語です。
あとがき
私がMoonBit Online Judgeにログインしようとしたところ、エラーが出てログインできませんでした。そこで、公式のDiscordに連絡し、すぐにログインできるように修正していただけました。
そのような経緯からこの記事を書くことにしました。
50問くらい問題を解いて、執筆時点ではリーダーボードに名前が掲載されています。
-
MoonBitのプログラムについて、MoonBit Online Judgeのバージョンが最新でないため、一部現在推奨される書き方でないものがあることに注意してください。この記事の方針としてはMoonBit Online Judgeで提出できる形のソースコードを提示したいため、そのようになっています。 ↩︎
-
何が違うのか分からない方へ：Rustの実装は値を構造体に包まずにそのまま格納して、型情報が演算を担います。MoonBitの実装は値を構造体に包んで格納して、その構造体が演算を担います。値を更新するときは、Rustの実装は値を渡せばよく、MoonBitの実装は構造体に包んで渡す必要があります。 ↩︎
Discussion