やっさんの雑記

プログラミングでやってみたこととか

素因数分解botについて

おはようございますこんにちはこんばんは。

一部の界隈にはどうも今日は大事な日らしいですが、いかがお過ごしでしょうか。


ということで6時間くらい内容考えて、そういえば5月くらいに稼働を始めてから一度も素因数分解bot(@yasuand_bot_f)について全く詳しい説明とか書いてないというのを思い出したので書きます。

素数だ!うおおおおおおおおおおおおおおおおおお!!!*1

何をするbot

まず。ツイ廃あらーととツイート数カウントくんで自動的に投稿される、



というようなツイートに含まれる、その日のpost数を素因数分解します。

ツイ廃あらーとで流れてくる、


というようなツイートは素因数分解の対象ではありません。

また、



というように直接@で数字を投げても素因数分解します。

他の機能

post数が素数だったり、@で素数を投げられるとふぁぼります。

また、その日の00:00:00~00:10:00の間にツイ廃あらーとで流れてきたpost数のうち、最小素因数が一番大きい人に対して表彰をして、対象のツイットをふぁぼります。ツイート数カウントくんの自動投稿は表彰機能の対象外ですし、またツイ廃あらーとの投稿であっても残念ながら00:00:00~00:10:00の間には流れてこなかったものも表彰機能の対象外です*2

最小素因数は、「合成数nの素因数のうち一番小さいもの」という意味で使っています。つまり、post数が素数(もしくは1)であれば自動的に表彰機能の対象外になります。

どうやって動かしているか

アルゴリズムは簡単で、UserStreamで流れてきた投稿に対して正規表現にマッチングするかどうか調べて、それと同時に投稿文字列からpost数を表す文字列を抜き出してそれを数値に変換して素因数分解しているだけです。

素因数分解のアルゴリズムも単純で、単に試行除算しているだけです。難しいなんちゃら法とかよくわかんないし。

制限

post数が1だったりだとか、@で1を投げられると素因数分解しません。最初はそのまま1と返していましたが、あまりにも味気ないしいい返しも思い浮かばなかったのでスルーすることにしました。

数字の上限についても、大きい数字を投げられてもわりと平気で、Rubyで書いているので自動的に多倍長整数の演算をしてくれます。Ruby賢い。

ただし、やはり140桁の整数*3が素数かどうか判定しろとかいわれても現実問題としてこれはほぼ不可能に近いので、試行除算の回数が一定数以上だったり素因数分解後の結果が140字におさまらないときはスルーします。

素因数分解しないときにスルーする仕様はユーザに対して優しいのかどうかちょっと悩みどころ。

ツイ廃あらーととツイート数カウントくんについては投稿元クライアントの名前とURLも見ているので、他クライアントから文字列をコピペしたり改変したりして呟いても素因数分解しません。@で直接数字を投げた場合は投稿元クライアントは見ていないので素因数分解します。

また、全角数字は数字ではないので、全角数字が混ざっていると素因数分解しません。

なぜ作ったか

そのときのノリで作った。後悔はしていない。

botを作って得られたもの

  • 正規表現バリバリに使うので正規表現の使い方。
  • Rubyスクリプトをサーバ上でデーモンとして動かす方法。
  • Twitterの諸々の仕様についての理解。

最後に

こういうクソbotでもいいので、知っている/使える技術を組み合わせて何か作るのは学習のモチベにもなるのでとてもいいと思います。何か作るときはたいてい自分が今使える技術だけでは作れなくて何か調べたり考えたりしながら作らないといけないと思っているので、モチベの向上以外にも実際に技術を修得するのにとても役立ちそうです。

実際に手を動かす作業はプログラミングとかに限らずどの分野でもとても大事な作業だと思うので、(僕私にはあまりいいもの面白いものが作れないから…)などと尻込みしている人は是非挑戦してみましょう。

それではよいお年を

*1:当方、東工大生ではなく東大生です

*2:最近ツイ廃あらーとでその日のpost数が流れてくるのがやや遅れ気味なので、もしかするとそのうち00:15:00までにしたりするかもしれませんが、今のところ変えるつもりはありません

*3:実際には@yasuand_bot_f の部分を抜くので最大125桁