Numer0nのAIを作った（データ表現編）

前回は***Numer0n***のルールと，アルゴリズムのお話をしました．

今回は，ざっくりいうと，いかにして高速に***<font color="#0080FF">EAT</font>/<font color="#0080FF">BITE</font>***の数を求めるかということについての話．
（下のgifは秘密の数が`8725`の時の挙動．5回で当てられている．）
![Numern_AI.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264330/65797b2e-bbb3-7852-0658-395d1f69643b.gif)
成果物はこちら．`stdin.rs`は見ない方がいいです．
<a href="https://github.com/lenna-kun/Numer0n_AI"><img src="https://github-link-card.s3.ap-northeast-1.amazonaws.com/lenna-kun/Numer0n_AI.png" width="460px"></a>

秘密の数(以降***SN_3***)と***コール***から***<font color="#0080FF">EAT</font>/<font color="#0080FF">BITE</font>***を求めるわけだが，どんな工夫ができるだろうか．

***<font color="#0080FF">以降，桁数を$n$とする．</font>***

#1. EATの求め方

***<font color="#0080FF">EAT</font>***を求めるには，各桁どうしを比較するだけ．
計算量は

$$\rm{O}(n)$$

各数字がどこにあるかという情報を削ることはできないため，これ以上高速にすることはできなさそう．
（実装では，***<font color="#0080FF">PACKED DECIMAL</font>***というデータ表現を用いて少しだけ工夫しているが，やっていることはあまり変わらない．）

#2. BITEの求め方

##2-1. 単純な求め方
***コール***された数の各桁を，***SN_3***の各桁と比較し，一致した回数をカウントしていく．（各桁について，1回一致したら***break***）
そして最後に***<font color="#0080FF">EAT</font>***数を引く．
単純な2重ループだから，計算量は

$$\rm{O}(n^2)$$

これはもう少し高速にできそう．
かといって，***SN_3***および***コール***を，***<font color="#0080FF">サイズ$n$の1次元配列</font>***と捉えて考える場合は，これより高速な求め方はなさそう．

##2-2. 高速な求め方

じゃあどうすればいいかっていうと，***<font color="#0080FF">データの表現方法</font>***を工夫する．
実は***<font color="#0080FF">BITE</font>***数は，データの表現方法を工夫することにより，

$$\rm{O}(1)$$

で求めることができる．

注目したいのは，求めたいのは，ある***SN_3***の中に，***コール***された数に***含まれる***数字が***含まれる***かどうかだけであって，どの数字がどの場所にあるかなんてどうでもいいということだ．

そこで，***SN_3***および***コール***数の$n$桁の中に，$0$~$9$の数字に含まれるか含まれないかを，ビット列により表現する．

```Rust:SN_3=3517の場合
//  各ビットは，それぞれの数字が含まれているかを表す
//  9 8 7 6 5 4 3 2 1 0
    0 0 1 0 1 0 1 0 1 0 // 3517
```
以降これを***ビットテーブル***と呼ぶ

###2-2-1. 通常ルールのNumer0nの場合
***ビットテーブル***どうしの***<font color="#0080FF">論理積</font>***を求め，それを***s***とする．

通常ルールの場合は，***s***における，立っているビットの個数から，***<font color="#0080FF">EAT</font>***数を引くだけ．

###2-2-2. カスタマイズされたルールのNumer0nの場合
同じように，***ビットテーブル***どうしの***<font color="#0080FF">論理積</font>***を求め，それを***s***とする．

カスタマイズされたルールの場合は，同じ数を何度使っても良いため，***コール***数において，各数字が何個存在するのかというデータが必要になる．
***コール***数に含まれる数字$i$の個数を$d_i~~(0\leq i\leq 9)$，
***s***の$i$ビット目を$s_i~~(1\leq i\leq 10)$とすると，***<font color="#0080FF">BITE</font>***数は，

$$\sum_{i=0}^9~(~{ d_i\times s_{i+1}}~)$$

から***<font color="#0080FF">EAT</font>***数を引いた値である．

##2-3. まとめ

ちょっとデータ表現を変えるだけで

$$\rm{O}(n^2)~=>~\rm{O}(1)$$

になった．
一応速度を測ったら，***4桁***の場合は***<font color="#0080FF">約4倍速くなっていた</font>***．
試しに***20桁***にしてみたら，***<font color="#0080FF">約10~14倍の差が出た</font>***．
桁数が増えれば増えるほど，この差はもっと大きくなる．

データ表現の中に，***不要な情報***が含まれている場合は，このような手法が有効であることがあるので，頭の片隅に置いておこう．

#3. 実装
言語は***<font color="#0080FF">Rust</font>***．
数字と，その桁数を引数にとり，そこから***ビットテーブル***を生成する関数．

```rust:bit_table.rs
pub type BitTable = u16;

pub fn from(num: i32, number_of_digits: u32) -> BitTable {
    (0..number_of_digits).fold(0u16, |acc, x| acc | (1 << (num / 10i32.pow(x) % 10)))
}
```
***Numer0n***の数を扱うための構造体と，実装したメソッドたち．

```rust:numer0n_item.rs
use super::bit_table;
use crate::bit_table::BitTable;

use super::packed_decimal;
use crate::packed_decimal::PackedDecimal;

#[derive(Copy, Clone)]
pub struct Numer0nItem {
    pub packed_decimal: PackedDecimal,
    pub overlap_array: [usize; 10],
    pub bit_table: BitTable,
}
impl Numer0nItem {
    pub fn from(num: i32) -> Self {
        Numer0nItem {
            packed_decimal: packed_decimal::from(num, 4),
            overlap_array: (0..4).fold([0; 10], |mut acc, x| {
                acc[num as usize / 10usize.pow(x as u32) % 10] += 1;
                acc
            }),
            bit_table: bit_table::from(num, 4),
        }
    }

    pub fn eat(self, call: &Self) -> usize { // EAT数を求める
        let xor = self.packed_decimal ^ call.packed_decimal;
        (0..4).fold(0, |et, i| if (xor << (4*i)) >> 12 == 0 { et + 1 } else { et })
    }
    
    pub fn eat_bite(self, call: &Self) -> usize { // EAT数 + BITE数を求める
        let and = self.bit_table & call.bit_table;
        (0..and.count_ones()).fold((0usize, 0usize, and), |(num, eb, and), _| {
            let shift = and.trailing_zeros() as usize + 1;
            (num+shift, eb + call.overlap_array[num+shift-1], and >> shift)
        }).1
    }
}
```
#4. おわりに
***Numer0n***のAIを作るうえで役立ちそうな話を，アルゴリズム編と，データ表現編の2回に分けて説明しました．
ここまで読んでいただきありがとうございました．