Zenn
Open12

Rustでグリッドの添え字範囲のチェックを楽にしたい

Rust
AtCoder
ピン留めされたアイテム
itohalitohal

TL;DR

  • 関数化で十分だ
  • 探索アルゴリズムに慣れろ

作成したもの

  • 2次元配列添え字が、その範囲内に入っているかをチェックする関数
  • 添え字と移動距離を入れると、移動先が範囲内であればその添え字を返してくれる関数

検索しがいがありそうなワード

トレイト、トレイト境界、ジェネリクス、構造体、演算子のオーバーロード、ユニットテスト

コードの全体像
use std::convert::TryFrom;
use std::convert::TryInto;
use std::ops::Add;


#[derive(Debug, Clone, Copy)]
struct GridIndex {
    i: isize,
    j: isize,
}

impl GridIndex {
    fn new<I>(i: I, j: I) -> Self
    where
        I: TryInto<isize> + Copy,
    {
        let i = i.try_into().ok().unwrap();
        let j = j.try_into().ok().unwrap();
        GridIndex { i, j }
    }
}

impl<I> Add<(I, I)> for GridIndex
where
    I: TryInto<isize> + Copy,
{
    type Output = GridIndex;

    fn add(self, rhs: (I, I)) -> Self::Output
    where
        I: TryInto<isize> + Copy,
    {
        let r0 = rhs.0.try_into().ok().unwrap();
        let r1 = rhs.1.try_into().ok().unwrap();
        let ni = self.i.saturating_add(r0);
        let nj = self.j.saturating_add(r1);
        return GridIndex::new(ni, nj);
    }
}

impl<I> TryFrom<(I, I)> for GridIndex
where
    I: TryInto<isize> + Copy,
{
    type Error = ();

    fn try_from((i, j): (I, I)) -> Result<Self, Self::Error>
    where
        I: TryInto<isize> + Copy,
    {
        let x = i.try_into().ok().unwrap();
        let y = j.try_into().ok().unwrap();

        return Ok(GridIndex::new(x, y));
    }
}

trait GridBounds {
    fn is_in_bounds<I>(&self, i: I, j: I) -> bool
    where
        I: TryInto<usize> + Copy;

    fn get_moved_index<I, J>(&self, indices: (I, I), directions: (J, J)) -> Option<(usize, usize)>
    where
        I: TryInto<isize> + Copy,
        J: TryInto<isize> + Copy;
}

impl<T> GridBounds for Vec<Vec<T>> {
    fn is_in_bounds<I>(&self, i: I, j: I) -> bool
    where
        I: TryInto<usize> + Copy,
    {
        let i = match i.try_into() {
            Ok(val) => val,
            Err(_) => return false,
        };
        let j = match j.try_into() {
            Ok(val) => val,
            Err(_) => return false,
        };

        i < self.len() && j < self[0].len()
    }

    fn get_moved_index<I, J>(&self, (i, j): (I, I), dij: (J, J)) -> Option<(usize, usize)>
    where
        I: TryInto<isize> + Copy,
        J: TryInto<isize> + Copy,
    {
        let ij = GridIndex::new(i, j);
        let nij = ij + dij;
        if !self.is_in_bounds(nij.i, nij.j) {
            return None;
        }

        return Some((nij.i as usize, nij.j as usize));
    }
}
itohalitohal

AtCoderでBFSとかするときに範囲チェック面倒だなってずっと思ってたので調査する

ChatGPTに聞いたら

トレイトを使用してカスタムメソッドを定義

すると良いらしい

trait GridBounds {
    fn is_in_bounds(&self, x: isize, y: isize) -> bool;
}

impl<T> GridBounds for Vec<Vec<T>> {
    fn is_in_bounds(&self, x: isize, y: isize) -> bool {
        x >= 0 && y >= 0 && (x as usize) < self.len() && (y as usize) < self[0].len()
    }
}

// 使用例
if grid.is_in_bounds(nx, ny) {
    // 範囲内の場合の処理
}
itohalitohal

使えるトレイトからグリッドの範囲チェックするやつないかなと思ってそれもChatGPTに聞いたけど、ピンポイントで範囲チェックするのはないっぽい
列挙してくれたのを一つずつ見るほどの熱量はないのでとりあえず無視

回答だけ以下に残す

上記のクレートリストの中に、直接的に「2次元グリッドの範囲チェック」のためのトレイトを提供するものはありません。
しかし、いくつかのクレートはこの目的に役立つツールやデータ構造を提供する可能性があります。
以下に、それぞれの特徴と使えそうなクレートを説明します。

1. 候補となるクレート
nalgebra
線形代数ライブラリで、ベクトルや行列を扱うための多機能クレートです。
2次元グリッドに似た構造のデータを扱うことも可能ですが、直接的に範囲チェックのトレイトを提供しているわけではありません。
ndarray
多次元配列（n次元配列）を扱うライブラリです。
配列のインデックス範囲を確認するために便利なメソッドが含まれています。array.index((i, j)) のような操作ができます。
範囲外のアクセスを試みた場合はエラーを返します。
itertools
イテレーション処理を簡素化するためのツールを提供します。
範囲チェックのための特別なトレイトはありませんが、座標を効率的に生成するツールが含まれています（例えば、iproduct! マクロ）。
fixedbitset
固定サイズのビットセットを扱うライブラリです。
範囲チェックそのものには関係しませんが、範囲内の要素を管理するために使えるかもしれません。
pathfinding
パス探索アルゴリズムを提供するライブラリで、グリッド操作にも適しています。
範囲チェックを含めたグリッド操作のサポートは間接的に行えますが、トレイトとして提供されているわけではありません。
indexing
データのインデックスに関する便利なツールを提供します。
範囲チェックを補助するために利用できる可能性があります。
itohalitohal

引数がisizeとかusizeとかを気にしてキャストするのも面倒なので両方に対応させたい
とりあえずChatGPTに聞いてのまとめ

ChatGPTに教えてもらった実装例は以下

use std::convert::TryInto;

trait GridBounds {
    fn is_in_bounds<I>(&self, x: I, y: I) -> bool
    where
        I: TryInto<usize> + Copy; // `TryInto<usize>`を実装している型を受け入れる
}

impl<T> GridBounds for Vec<Vec<T>> {
    fn is_in_bounds<I>(&self, x: I, y: I) -> bool
    where
        I: TryInto<usize> + Copy,
    {
        // usizeへの変換を試みる
        let x = match x.try_into() {
            Ok(val) => val,
            Err(_) => return false,
        };
        let y = match y.try_into() {
            Ok(val) => val,
            Err(_) => return false,
        };

        // 範囲内かどうかを判定
        x < self.len() && y < self[0].len()
    }
}

fn main() {
    let grid = vec![vec![1, 2, 3], vec![4, 5, 6]];

    // isizeのテスト
    if grid.is_in_bounds(1isize, 2isize) {
        println!("範囲内です (isize)");
    } else {
        println!("範囲外です (isize)");
    }

    // usizeのテスト
    if grid.is_in_bounds(1usize, 2usize) {
        println!("範囲内です (usize)");
    } else {
        println!("範囲外です (usize)");
    }

    // 負数のテスト
    if grid.is_in_bounds(-1isize, 2isize) {
        println!("範囲内です (負数)");
    } else {
        println!("範囲外です (負数)");
    }
}
itohalitohal

範囲チェックはできたので、次は移動をしてみる

関数get_moved_index
引数： 添え字のタプル、移動方向のタプル（どちらもusizeに変換可能な型）
返り値：移動した先の添え字のタプル、もしくはNoneのOption

というのを作りたいから以下のように書いたがエラーが出る


    // 前略
    fn get_moved_index<I>(&self, (i, j): (I, I), (di, dj): (I, I)) -> Option<(usize, usize)>
    where
        I: TryInto<usize> + Copy,
    {
        let ni = i + di;
        let nj = j + dj;
        if !self.is_in_bounds(ni, nj) {
            return None;
        }
        let i = ni.try_into().ok().unwrap();
        let j = nj.try_into().ok().unwrap();

        return Some((i, j));
    }

どうやら足し算でエラーが出ている様子。Addを追加しろとのことらしい

`consider further restricting this bound: ` + std::ops::Add`

use std::ops::Add;
    // 略
    fn get_moved_index<I>(&self, (i, j): (I, I), (di, dj): (I, I)) -> Option<(usize, usize)>
    where
        I: TryInto<usize> + Copy,
    {
        let ni = i + di;
        let nj = j + dj;
        if !self.is_in_bounds(ni, nj) {
            return None;
        }
        let i = ni.try_into().ok().unwrap();
        let j = nj.try_into().ok().unwrap();

        return Some((i, j));
    }

追加したら追加のエラー。移動先が範囲内かのチェックで、トレイト境界との齟齬があるからだめらしい

the trait bound `usize: From<<I as Add>::Output>` is not satisfied
required for `<I as Add>::Output` to implement `Into<usize>`
required for `usize` to implement `TryFrom<<I as Add>::Output>`
required for `<I as Add>::Output` to implement `TryInto<usize>`

ChatGPTに聞いたら、

このエラーメッセージは、Add トレイトを使って計算した結果が Into<usize> に変換できないということを意味しています。つまり、Add で計算した結果が usize 型に変換できることが必要ですが、それがうまくいっていない状態です。

Add の結果が usize 型に変換可能であることを保証するために、適切な型変換を明示的に行います

fn add_and_convert<I>(i: I, ni: I) -> Result<usize, &'static str>
where
    I: TryInto<usize> + Copy + Add<Output = I>,
{
    // 足し算を行い、その結果をusizeに変換
    let result = i + ni;
    
    // 足し算の結果をusizeに変換（TryIntoを使う）
    result.try_into().map_err(|_| "Conversion failed")
}

ドキュメントをとりあえず眺める

OutputがRequired Associated Typesとなっている。足し算結果の型がこれに依存してる
addメソッドに関しては、今回の場合ジェネリクスのI（想定はisizeとusize）に依存している。isize + usizeってどうなるんだ

itohalitohal

isize + usizeがどうなるか気になるため、get_moved_index関数を使ってテストしようとして以下のようなテストコードを書いたがエラーが出た
そもそもIで同一の型を要求しているため、違う型同士が計算されることはない。
考えなくてよかった心配らしい
添え字と移動方向は別々にしないと困る

つまりはI(添え字の型) + J(移動方向の型) = I(添え字の型)になってほしい

mismatched types
`-1isize` cannot fit into type `usize`

#[test]
fn test_move() {
    let grid = vec![vec![1, 1], vec![1, 1]];
    assert!(Some((1, 1)) == grid.get_moved_index((0, 0), (1, 1)));
    assert!(None == grid.get_moved_index((0, 0), (2, 2)));
    assert!(Some((0, 1)) == grid.get_moved_index((1usize, 0usize), (-1isize, 1usize)));
}
itohalitohal
    fn get_moved_index<I, J>(&self, (i, j): (I, I), (di, dj): (J, J)) -> Option<(usize, usize)>
    where
        I: TryInto<usize> + Copy + Add<Output = I>,
        J: TryInto<usize> + Copy + Add<Output = I>,
    {
        let ni = i + di;
        let nj = j + dj;
        if !self.is_in_bounds(ni, nj) {
            return None;
        }
        let i = ni.try_into().ok().unwrap();
        let j = nj.try_into().ok().unwrap();

        return Some((i, j));
    }

こんな感じのコードを書いたら

method `get_moved_index` has 2 type parameters but its trait declaration has 1 type parameter

というエラーが出てググってもChatGPTに聞いてもよくわからなかったが、どうやら実装する方のimpl側だけ変更してて、trait側の変更していなかったためのエラーらしい

trait GridBounds {
    fn is_in_bounds<I>(&self, i: I, j: I) -> bool
    where
        I: TryInto<usize> + Copy;

    fn get_moved_index<I, J>(&self, indices: (I, I), directions: (J, J)) -> Option<(usize, usize)>
    where
        I: TryInto<usize> + Copy + Add<Output = I>,
        J: TryInto<usize> + Copy + Add<Output = I>;
}

ちゃんとtrait側の変更したら直った
人騒がせなエラーだ

itohalitohal

上のような実装をしたら足し算でエラーが出る

mismatched types
expected type parameter `I`
   found type parameter `J`
a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

visitしろと言われたURLみても正直わからないが、多分Iに対するAdd<Output = I>はI + I = Iしか許容してないんだろうと勝手に考えておく
それに演算子のオーバーロードのところでBar + Foo + BarFooの例があるのでAddを拡張すればよさそう
とか思ったが流石にプリミティブ型にはだめらしい

only traits defined in the current crate can be implemented for primitive types
define and implement a trait or new type instead

impl Add<usize> for isize {
    type Output = isize;

    fn add(self, _rhs: isize) -> isize {
        self + _rhs
    }
}
itohalitohal

ここで思ったのだが、二次元配列に対する拡張じゃなくて、範囲を持ってる添え字の構造体を作ればいいのでは？
どうせusize + isizeで、下の範囲超えたらというのはchecked_add/subなりでどうにでもなる気がした
https://rs.nkmk.me/rust-int-overflow-checked-wrapping/

上のことを思ってちょびちょび書いていたのだが、あんまりにもその構造体の役割が重すぎないか？と気付いたのでやめた
そしてi32でも最大値が2^{31}-1でだいたい2e9なので、AtCoderでの空間を考えると十分な大きさなのでisizeで扱っちゃっていいと思う。内部的にはisizeだけど表から見たらusizeというイメージ

というわけで足し算をさせるための型、というか構造体を作る

impl GridIndex {
    fn new<I>(i: I, j: I) -> Self
    where
        I: TryInto<isize> + Copy,
    {
        let i = i.try_into().ok().unwrap();
        let j = j.try_into().ok().unwrap();
        GridIndex { i, j }
    }
}

ここで足し算には、計算して型の範囲を超えたときその型の最大値/最小値の近い方として扱うsaturating_*を使う
さっきも言ったが値の大きさは十分なはずで、それを超えたときに変にエラーを起こさせるより戻しちゃっても大丈夫だろう
https://rs.nkmk.me/rust-int-overflow-checked-wrapping/

impl<I> Add<(I, I)> for GridIndex
where
    I: TryInto<isize> + Copy,
{
    type Output = GridIndex;

    fn add(self, rhs: (I, I)) -> Self::Output
    where
        I: TryInto<isize> + Copy,
    {
        let r0 = rhs.0.try_into().ok().unwrap();
        let r1 = rhs.1.try_into().ok().unwrap();
        let ni = self.i.saturating_add(r0);
        let nj = self.j.saturating_add(r1);
        return GridIndex::new(ni, nj);
    }
}
itohalitohal

表からの引数の型と内側で使う型が異なるので変換できる必要がある。つまりはTryIntoを実装する必要があるだろう

https://doc.rust-jp.rs/rust-by-example-ja/conversion/try_from_try_into.html

TryFromでもいいらしい

impl<I> TryFrom<(I, I)> for GridIndex
where
    I: TryInto<isize> + Copy,
{
    type Error = ();

    fn try_from((i, j): (I, I)) -> Result<Self, Self::Error>
    where
        I: TryInto<isize> + Copy,
    {
        let x = i.try_into().ok().unwrap();
        let y = j.try_into().ok().unwrap();

        return Ok(GridIndex::new(x, y));
    }
}

型Iはisizeに変換可能な型を前提にするようにwhere句、トレイト境界で指定しているのでunwrapしていいはず

itohalitohal

新しい型GridIndexを作ったうえで、そいつに足し算を実装した。
そして添え字は引数の型ではなくGridIndexで扱うようにした。
つまりはIとJに対するAddが要らなくなった

若干の注意点として、範囲内かをチェックする方の引数の型はusizeである。添え字なので負の値になりえない。
移動するほうはisizeになりうるし、その後が楽なのでisizeに変換できるやつならOKとしている
変換可能だが不都合/エラーが起こるのはisize\rightarrowusizeで、usize\rightarrowisizeは大丈夫なはず
他の型だとだめな場合があるよという場合は、知らん。AtCoderで使うなら想定用途からそう大きくは外れないはず

というわけでget_moved_indexを修正

    fn get_moved_index<I, J>(&self, (i, j): (I, I), dij: (J, J)) -> Option<(isize, isize)>
    where
        I: TryInto<isize> + Copy,
        J: TryInto<isize> + Copy,
    {
        let ij = GridIndex::new(i, j);
        let nij = ij + dij;
        if !self.is_in_bounds(nij.i, nij.j) {
            return None;
        }

        return Some((nij.i, nij.j));
    }
itohalitohal

テストにAtCoderの問題を解く
https://atcoder.jp/contests/abc387/tasks/abc387_d

もともとはこいつに「BFS書けますよね笑」とかいう煽りを受けたせいで始めた物語
特に範囲チェックをミスったとかではなく、更新部分がダイクストラとごちゃったのとチェックする距離が現在の距離以下なら見ないようにするはずが未満で見てた
さらに最初に縦か横移動を固定するはずが両方行ってたりして悲しかった

https://atcoder.jp/contests/abc387/submissions/61405804

無事出来た。絶対にこんな労力を割く必要はない
が、見やすいかもしれない