【ポケモン剣盾?】ハイドロポンプの略称を全部列挙する【プンポロドイハ】

諸悪の根源

 私はドロポン派です。

 

ポケモン公式が「ハイドロポンプの略称」という俗っぽい話題に言及したことで、Twitter各所でハイドロポンプの略称が話題に上がるようになりました。古来から各派閥に分かれて血を血で洗う争いが続いていたので、公式の爆弾投下によってTwitterが戦場にならないか心配ですね。ドロポン以外ならプンポロドイハが好きです。ドッヘンアイアも好きです。

そのような流れの中で、下のようなツイートを見かけました。

 各文字を含めるか含めないかで考えれば2^7=128、空文字と「ハイドロポンプ」は含めないので答えは128 - 2 = 126通りです。(数Aでは…?)

 さて、これをもう少し改変して次のような問題を考えてみます。

 定期テストで出てきたらめちゃくちゃ時間食われるのでスルー安定です…。

人力で126通り書き上げるのはとても大変ですが、コンピュータに任せればサクッとやってくれます。

……ホンマか?

言っておいて簡単じゃなかったら困るので自分で解いてみました。

(ちょっと難しかったです…)

「各文字について入れる/入れないで分岐して126通りの文字列を作った後ソートする」という方針だと「ソートする」の部分が少し厄介です。私は幅優先探索で解いてみました。

最後に

 問題の条件には気を付けましょう。

追記

アイアンヘッドの略称の列挙は「ア」が2個含まれているので、もう少し難易度が上がります。誰か挑戦してみませんか?

追記2

フォロワーさんから「再帰で書いた方が速かった」と刺されたので考え直してみましたが、深さ優先で解くべき問題でしたね。再帰ではなくStackを使って書いてみました。文字の追加の順番が逆になるので注意が必要です。

 計測結果

f:id:yatsuna_827:20200616174327p:plain

 

TinyMTの更新を行列で書いてみようのコーナー(後編)

初めに

TinyMTの更新を行列で書いてみようのコーナー(前編) - yatsuna_827’s blogのつづき。 前編では数式が盛り沢山だったせいで多数の数学アレルギー患者に急性発作を引き起こさせてしまいましたが、今回は1と・しか出てこないので比較的安全だと思います。

前回求めた行列

$$ \begin{align} \begin{bmatrix} {\boldsymbol s}'_{0} & {\boldsymbol s}'_{1} & {\boldsymbol s}'_{2} & {\boldsymbol s}'_{3} \end{bmatrix} = \begin{bmatrix} {\boldsymbol s}_{0} & {\boldsymbol s}_{1} & {\boldsymbol s}_{2} & {\boldsymbol s}_{3} \end{bmatrix} \begin{bmatrix} {\boldsymbol O} & U_{31}C_{mat1} & U_{31}(L'_{1}L'_{10}+ C_{mat2}) & U_{31} L'_{1} \\ I & C_{mat1} & L'_{1}L'_{10} + C_{mat2} & L'_{1} \\ {\boldsymbol O} & I+C_{mat1} & L'_{1}L'_{10} + C_{mat2} & L'_{1} \\ {\boldsymbol O} & (I + R_{1})C_{mat1} & R'_{1}L_{10} + R'_{1}C_{mat2} & R'_{1} \end{bmatrix} \end{align} $$
確認したところで、一列ずつ行きましょう。

1列目

零行列 {\boldsymbol O}単位行列 Iしか無いので特筆することは無いです。 見やすいように0は・で表します。零行列は全部・なので割愛。単位行列f:id:yatsuna_827:20171231173417p:plain
です。(こっちも言うまでも無いですが)

2列目

まず前編を書いた後で気づいたのですが、 U_{31}C_{mat1} = C_{mat1}が成り立ちます。 C_{mat1}は最下位bitのみに作用するので、最上位bitが欠落しようが何の関係も無いのです。なので、2列目の1行目と2行目はどちらも C_{mat1}です。
mat1は0x8f7011eeで、2進数に直すと10001111011100000001000111101110となります。 C_{mat1}はこれを最下段に並べた行列で、 f:id:yatsuna_827:20171231174059p:plain
となります。  I + C_{mat1}はこれに単位行列を加えた行列で、 f:id:yatsuna_827:20171231174426p:plain
です。
そして (I+R_{1})C_{mat1} = C_{mat1} + R_{1}C_{mat1}は、 C_{mat1} R_{1}C_{mat1}を加えた行列です。
 R_{1}C_{mat1}は自信が無かったのでExcelくんに計算してもらいました。結果的には C_{mat1}を右と上にそれぞれ1ずつずらした行列です。 よって (I+R_{1})C_{mat1} = C_{mat1} + R_{1}C_{mat1}は、 f:id:yatsuna_827:20171231175904p:plain
となります。

3列目

まずは L'_{1}L'_{10}を展開しましょう。  L_{n}L_{m} = L_{n+m}が成り立つので、括弧を展開すると $$ \begin{align} (I + L_{1})(I + L_{10}) &= I + L_{1} + L_{10} + L_{1}L_{10} \\ &= I + L_{1} + L_{10} + L_{11} \end{align} $$ となります。 ただし、4行目の R'_{1}L_{10}の展開は R_{1}L_{10} = L_{9}は成り立たないので注意です。(押し出されたbitの情報が欠損するため。)
こちらは、
$$ \begin{align} (I + R_{1})L_{10} = L_{10} + R_{1}L_{10}
\end{align} $$ で終わりです。
また、 U_{31} L_{n}を作用させると、自動的に最上位bitは押し出されて欠落するので、 $$ U_{31}L_{n}=L_{n} $$ が成り立ちます。

以上を踏まえると、3列目は1行目から順に $$ \begin{align} U_{31} + L_{1} + L_{10} + L_{11} + C_{mat2} \\ I + L_{1} + L_{10} + L_{11} + C_{mat2} \\ I + L_{1} + L_{10} + L_{11} + C_{mat2} \\ L_{10} + R_{1}L_{10} + C_{mat2} + R_{1}C_{mat2} \end{align} $$
となります。
 U_{31} + L_{1} + L_{10} + L_{11}
f:id:yatsuna_827:20171231213341p:plain
という行列で、mat2の値はmat2 0xfc78ff1f(2進数で11111100011110001111111100011111)なので、 C_{mat2}
f:id:yatsuna_827:20171231213538p:plain
なので、1行目は
f:id:yatsuna_827:20171231213616p:plain
という行列になります。2行目、3行目はほぼ同じ行列で、(1,1)成分が1になっただけです。
f:id:yatsuna_827:20171231213729p:plain

4行目、 L_{10} + R_{1}L_{10}
f:id:yatsuna_827:20171231214959p:plain
です。よく見ると R_{1}L_{10} L_{9}とは若干異なっているのがわかると思います。
 C_{mat2} + R_{1}C_{mat2}
f:id:yatsuna_827:20171231215202p:plain
なので、4行目は
f:id:yatsuna_827:20171231215228p:plain
となります。

4列目

ほとんどまんまです。1行目は
$$ U_{31}(I + L_{1}) = U_{31} + L_{1} $$ なので、
f:id:yatsuna_827:20171231215959p:plain
2行目、3行目は I + L_{1}で、
f:id:yatsuna_827:20171231220042p:plain
4行目は I + R_{1}で、
f:id:yatsuna_827:20171231220112p:plain
です。

組み合わせる

これらの行列を並べると、前回求めた更新を表す行列ができあがります。
f:id:yatsuna_827:20171231220223p:plain
ワッショイ!

最後に

計算が苦手なので大変でした(小並感)。ですが、Excelを使うことで、計算が合っているかどうかを確かめながら作業を進めることができました。
線形代数の初めの方に出てくるクッソめんどくさい行列計算は、Excelを使うととても楽です。逆行列も求められます。ということで…

オマケ

Excelを使って、直接逆行列を求めてみました。
f:id:yatsuna_827:20171231220847p:plain

最後の最後に

前編を書き上げた後で計算ミスやら記述ミスやらが次々発覚してサイレント修正しながら後編を書きました。大晦日に。ガキ使見ながら。弟たちは友達の家に遊びに行っているというのに。。。
それは置いておくとして、本家MTも同様に624項をまとめて1つの内部状態 {\boldsymbol x}_{n}とみなすことで、行列を用いて {\boldsymbol x}_{n+1} = {\boldsymbol x}_{n}Aと表せるので、誰かやってみてください。求める過程自体は、おそらくTinyMTよりも簡単だと思います。来年のAdvent Calenderのネタにどうでしょうか。
それではよいお年を。

TinyMTの更新を行列で書いてみようのコーナー(前編)

はじめに

この記事はPokémon RNG Advent Calendar 2017 21日目の記事です。

adventar.org

21日の枠が空いていたので、怖い人に脅されて急遽昔やったネタを引っ張り出してきました。

これ。

twitter.com

さっさと書き上げるはずだったのですが、なんと計算したメモがロクに読めたもんじゃないという事態が発生し、一から計算し直す羽目に。
その結果クリスマスはルーズリーフと格闘して過ごしました。どうにも計画性が無さすぎて困る。 というわけで、一気に書き上げる気力が残っていないので、前後編に分かれます。

本題

去年のAdvent Calenderではおだんぽよ氏が行列を用いてTinyMTの逆算処理を求めていましたが、 この記事ではその行列を具体的に求めていきたいと思います。

更新処理の確認

まずはTinyMTの更新処理のソースコードを見てみましょう。

inline static void tinymt32_next_state(tinymt32_t * random) { 
     uint32_t x; 
     uint32_t y; 

     y = random->status[3]; 
     x = (random->status[0] & TINYMT32_MASK) 
    ^ random->status[1] 
    ^ random->status[2]; 
     x ^= (x << TINYMT32_SH0); 
     y ^= (y >> TINYMT32_SH0) ^ x; 
     random->status[0] = random->status[1]; 
     random->status[1] = random->status[2]; 
     random->status[2] = x ^ (y << TINYMT32_SH1); 
     random->status[3] = y; 
     random->status[1] ^= -((int32_t)(y & 1)) & random->mat1; 
     random->status[2] ^= -((int32_t)(y & 1)) & random->mat2; 
 } 

https://github.com/MersenneTwister-Lab/TinyMTより

これを、random->status[n] = s[n]と置いたり、定数に具体的な値を入れたりして、もうちょっと読みやすく書き直すと以下のようになります。

y = s[3]; 
x = (s[0] & 0x7FFFFFFF) ^ s[1] ^ s[2]; 
x ^= (x << 1); 
y ^= (y >> 1) ^ x; 

s'[0] = s[1]; 
s'[1] = s[2]; 
s'[2] = x ^ (y << 10); 
s'[3] = y; 

if(y&1==1){
   s'[1] ^= mat1 // 0x8f7011eeだけど却ってややこしくなるからそのまま 
   s'[2] ^= mat2 // 0xfc78ff1fだけど同上 
}

基本事項の確認

この前の記事と同様に、整数を2進数表記して F_2上のベクトルとして扱っていきます。
(最終的には内部状態を128次ベクトルとして次の状態へ移す行列を考えますが、 各statusごとに分割して処理が書かれているので、一度各statusごとの式に落とし込んでから128次ベクトルにまとめ上げていきます。)
このあたりはoupo先生の記事とかMTを作った松本眞氏の講義ノートとかを参考にしたので詳しくはそちらで。
○各statusやx,y等の32bit整数を32次横ベクトルとみなし、それぞれ {\boldsymbol x},  {\boldsymbol s}_n等と表します。
○これにより、各処理は以下のように表すことができます。
排他的論理和xor(^)
32bit整数a, bの排他的論理和を取る処理a^bは、 {\boldsymbol a}+{\boldsymbol b}に相当します。
・ビットシフト(<< n, >> n)
単位行列の対角上にある1を、左nビットシフトは左に、右nビットシフトは右にnずらした行列との積で表せます。
例) 11 << 2 (%16) $$ \begin{align} \begin{bmatrix} 1 & 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{bmatrix}= \begin{bmatrix} 1 & 1 & 0 & 0 \end{bmatrix} \end{align} $$
論理積and(&)
a&bは、 aI^{t}bで表せます。言い換えると、aと対角上にbの各成分を並べた行列との積です。
例) 11 & 6 $$ \begin{align} \begin{bmatrix} 1 & 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}= \begin{bmatrix} 0 & 0 & 1 & 0 \end{bmatrix} \end{align} $$

・また、if(y&1==1) a^=bは、32列目に {\boldsymbol b}の各要素並べた行列 Aを用いて、 a + yAと表せます。
例) if(y&1) a^=11を表す行列 A $$ A = \begin{align} \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ \end{bmatrix} \end{align} $$

さて、準備が整ったところで計算していきましょう。

1行目~4行目

・1行目 そのまんまです。 $$ {\boldsymbol y} = {\boldsymbol s}_3 $$ ・2行目  {\boldsymbol s}_0& 0x7FFFFFFFに相当する行列を掛けます。
( {\boldsymbol s}_0の下位31bitを取るので、 U_{31}と置きます。) $$ \begin{align} {\boldsymbol x} & = {\boldsymbol s}_0 \begin{bmatrix} 0 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1 \end{bmatrix} + {\boldsymbol s}_1 + {\boldsymbol s}_2 \\ & = {\boldsymbol s}_0 U_{31} + {\boldsymbol s}_1 + {\boldsymbol s}_2 \end{align} $$
・3行目 左辺と右辺で文字を変えるべきなのでしょうが、=を左辺への代入だと思ってください。。。
(以下、左nビットシフトを表す行列を L_{n}、右nビットシフトを表す行列を R_{n}と置きます。) $$ \begin{align} {\boldsymbol x} &= {\boldsymbol x} + {\boldsymbol x} L_{1} \\ &= {\boldsymbol x} (I + L_{1}) \\ &= {\boldsymbol s}_{0}U_{31} (I+L_{1}) + {\boldsymbol s}_{1}(I+L_{1}) + {\boldsymbol s}_{2} (I+L_{1}) \end{align} $$
・4行目  $$ \begin{align} {\boldsymbol y} &= {\boldsymbol y} + {\boldsymbol y} R_{1} + {\boldsymbol x} \\ &= {\boldsymbol y} (I + R_{1}) + {\boldsymbol x} \\ &= {\boldsymbol s}_{0}U_{31} (I+L_{1}) + {\boldsymbol s}_{1}(I+L_{1}) + {\boldsymbol s}_{2} (I+L_{1}) + {\boldsymbol s}_{3} (I + R_{1}) \end{align} $$

これで {\boldsymbol x}と{\boldsymbol y}が出ました。
次はこれらをstatusへ代入していきます。

5行目以降

更新後のstatusを {\boldsymbol s}'_{n}とします。
・5, 6行目 ただ代入するだけです。 $$ \begin{align} {\boldsymbol s}'_{0} = {\boldsymbol s}_{1} \\ {\boldsymbol s}'_{1} = {\boldsymbol s}_{2} \end{align} $$ ・7行目 ちょっと長ったらしくなります。見やすくするために L'_{n} = I + L_{n},  R'_{n} = I + R_{n}と置きます。 $$ \begin{align} {\boldsymbol s}'_{2} &= {\boldsymbol x} + {\boldsymbol y}L_{10} \\ &= {\boldsymbol s}_{0}U_{31} (I+L_{1}) + {\boldsymbol s}_{1}(I+L_{1}) + {\boldsymbol s}_{2} (I+L_{1}) \\ &\quad + ({\boldsymbol s}_{0}U_{31} (I+L_{1}) + {\boldsymbol s}_{1}(I+L_{1}) + {\boldsymbol s}_{2} (I+L_{1}) + {\boldsymbol s}_{3} (I + R_{1}))L_{10} \\ &= {\boldsymbol s}_{0}U_{31}L'_{1}L'_{10} + {\boldsymbol s}_{1}L'_{1}L'_{10} + {\boldsymbol s}_{2}L'_{1}L'_{10} + {\boldsymbol s}_{3}R'_{1}L_{10} \end{align} $$ ・8行目  {\boldsymbol y}を代入するだけです。 $$ \begin{align} {\boldsymbol s}'_{3} = {\boldsymbol s}_{0}U_{31} L'_{1} + {\boldsymbol s}_{1}L'_{1} + {\boldsymbol s}_{2} L'_{1} + {\boldsymbol s}_{3} R'_{1} \end{align} $$ ・if内の処理  if(y&1) s[1] ^= mat1を表す行列を C_{mat1}if(y&1) s[2] ^= mat2を表す行列を C_{mat2}と置きます。  L_{n}を作用させると最下位bitは必ず0になるので、 L_{n}C_{mat} = {\boldsymbol O}(よって L'_{n}C_{mat} = C_{mat})が成り立つことに注意します。 $$ \begin{align} {\boldsymbol s}'_{1} &= {s}'_{1} + {\boldsymbol y}C_{mat1} \\ &= {\boldsymbol s}_{2} + ({\boldsymbol s}_{0}U_{31} L'_{1} + {\boldsymbol s}_{1}L'_{1} + {\boldsymbol s}_{2} L'_{1} + {\boldsymbol s}_{3} R'_{1})C_{mat1} \\ &= {\boldsymbol s}_{0}U_{31} L'_{1}C_{mat1} + {\boldsymbol s}_{1}L'_{1}C_{mat1} + {\boldsymbol s}_{2} (I+L'_{1}C_{mat1}) + {\boldsymbol s}_{3} R'_{1}C_{mat1} \\ &= {\boldsymbol s}_{0}U_{31} C_{mat1} + {\boldsymbol s}_{1}C_{mat1} + {\boldsymbol s}_{2} (I+C_{mat1}) + {\boldsymbol s}_{3} (I + R_{1})C_{mat1} \end{align} $$ $$ \begin{align} {\boldsymbol s}'_{2} &= {\boldsymbol s}'_{2} + {\boldsymbol y}C_{mat2} \\ &= ({\boldsymbol s}_{0}U_{31}L'_{1}L'_{10} + {\boldsymbol s}_{1}L'_{1}L'_{10} + {\boldsymbol s}_{2}L'_{1}L'_{10} + {\boldsymbol s}_{3}R'_{1}L'_{10}) +({\boldsymbol s}_{0}U_{31} L'_{1} + {\boldsymbol s}_{1}L'_{1} + {\boldsymbol s}_{2} L'_{1} + {\boldsymbol s}_{3} R'_{1})C_{mat2} \\ &= {\boldsymbol s}_{0}U_{31}(L'_{1}L'_{10} + C_{mat2}) + {\boldsymbol s}_{1}(L'_{1}L'_{10} + C_{mat2}) + {\boldsymbol s}_{2}(L'_{1}L'_{10} + C_{mat2}) + {\boldsymbol s}_{3}(R'_{1}L_{10} + R'_{1}C_{mat2}) \end{align} $$

整理してみる。

何とか処理を式に落とし込むことができたので、行列にしやすいように整理してみます。 $$ {\boldsymbol s}'_{0} = {\boldsymbol s}_{0} {\boldsymbol O} + {\boldsymbol s}_{1} + {\boldsymbol s}_{2}{\boldsymbol O}+ {\boldsymbol s}_{3}{\boldsymbol O} \\ {\boldsymbol s}'_{1} = {\boldsymbol s}_{0}U_{31} C_{mat1} + {\boldsymbol s}_{1}C_{mat1} + {\boldsymbol s}_{2} (I+C_{mat1}) + {\boldsymbol s}_{3} (I + R_{1})C_{mat1} \\ {\boldsymbol s}'_{2} = {\boldsymbol s}_{0}U_{31}(L'_{1}L'_{10} + C_{mat2}) + {\boldsymbol s}_{1}(L'_{1}L'_{10} + C_{mat2}) + {\boldsymbol s}_{2}(L'_{1}L'_{10} + C_{mat2}) + {\boldsymbol s}_{3}(R'_{1}L_{10} + R'_{1}C_{mat2}) \\ {\boldsymbol s}'_{3} = {\boldsymbol s}_{0}U_{31} L'_{1} + {\boldsymbol s}_{1}L'_{1} + {\boldsymbol s}_{2} L'_{1} + {\boldsymbol s}_{3} R'_{1} $$ さて、これで各 {\boldsymbol s}'_{n} {\boldsymbol s}_{n}を並べたベクトルをそれぞれ作り、内部状態の更新を行列で表現すると $$ \begin{align} \begin{bmatrix} {\boldsymbol s}'_{0} & {\boldsymbol s}'_{1} & {\boldsymbol s}'_{2} & {\boldsymbol s}'_{3} \end{bmatrix} = \begin{bmatrix} {\boldsymbol s}_{0} & {\boldsymbol s}_{1} & {\boldsymbol s}_{2} & {\boldsymbol s}_{3} \end{bmatrix} \begin{bmatrix} {\boldsymbol O} & U_{31}C_{mat1} & U_{31}(L'_{1}L'_{10}+ C_{mat2}) & U_{31} L'_{1} \\ I & C_{mat1} & L'_{1}L'_{10} + C_{mat2} & L'_{1} \\ {\boldsymbol O} & I+C_{mat1} & L'_{1}L'_{10} + C_{mat2} & L'_{1} \\ {\boldsymbol O} & (I + R_{1})C_{mat1} & R'_{1}L_{10} + R'_{1}C_{mat2} & R'_{1} \end{bmatrix} \end{align} $$
となることがわかりました。
あとはこの行列を具体的に{0, 1}で表すだけですね!
後編に続く!!!TinyMTの更新を行列で書いてみようのコーナー(後編) - yatsuna_827’s blog