null部の部誌

プログラミングの話とか色々。

Pythonの複合文をインデントせずに書く

この前p3+q3+r3=s3 (p, q, r, sは自然数)の解って(3, 4, 5, 6)の立法数倍以外にあるのかなーと思ってpaiza_runしてみたところ、

エラーが途中までしか見えませんがSyntaxErrorになりました。悲しい。

インデントのない複合文

複合文っていうのは要するにifとかforとかwithとかの、 :の後に文を書くアレです。とりあえずifで説明をします。

ifっていうと大抵こんな感じですよね。

if flag:
    hoge()

条件と:のあと改行・インデントして処理を書きます。これは、以下のように書くことと同等です。

if flag: hoge()

インデントをすると文字数が爆発するので、paiza_runとかではこのようにしてインデントを回避できると便利です。

ちなみに、

if flag: hoge(); fuga(); piyo()

これは、以下のコードと同等です。

if flag:
    hoge()
    fuga()
    piyo()

直感的といえば直感的なんですが、C/C++とは違うので注意が必要かもしれません。

ネストがしたい

そういえば私はp3+q3+r3=s3 (p, q, r, sは自然数)の解を探し求めているのでした。頭を全く使いたくないので愚直に(p, q, r, s)を4重ループで回します。

インデントをしたくないのでこう書きたくなります。

r=range(1,10)
for w in r:for x in r:for y in r:for z in r:if w**3+x**3+y**3==z**3:print(w,x,y,z)

しかしこれは冒頭で述べたようにSyntaxErrorになります。リファレンスを見てみましょう。

8. 複合文 (compound statement) — Python 3.6.1 ドキュメント

スイートは、ヘッダのコロンの後ろにセミコロンで区切られた一つまたはそれ以上の単純文を並べるか、ヘッダ行後のインデントされた文の集まりです。後者の形式のスイートに限り、ネストされた複合文を入れることができます ; 以下の文は、 else 節がどの if 節に属するかがはっきりしないという理由から不正になります :
if test1: if test2: print(x)

じゃあwithとかなら良いのかっていうとこれもSyntaxErrorになります。複合文はインデントしないとネストできないのです。大人しくインデントしましょう。

それでも僕はインデントをしたくない

残念ながらTwitterは140字の制限があるのです。インデントなんかしてたらpaiza_runに投げられないのです。そこで登場するのがリスト内包表記。

リスト内包表記を使うと4重ループとifをワンライナーできます。join()とかで適当に整形すれば最初にやろうとしていた出力と同じ出力を得ることもできますが、それをやるには140字は少なすぎる。リスト内包表記はいいぞ。

余談

13+63+83=93という結構小さい解が普通にあって意外でした。ところで連続する3立方数の和が立方数になるのは、33+43+53=63の場合以外にあるのでしょうか。数学のプロ教えてください。

2016年度文化祭展示作品「文豪チャット」公開

今年度も文化祭の作品として、さくらミケ氏と合作でプログラムを作成しました。UIはA.js(仮名)氏が作ってくれました。

どんなプログラムかざっくり言うと、
「文豪風に喋る会話プログラム」
です。会話の相手は夏目漱石太宰治など、また文豪以外にも猫とかエヴァとかあります。

Vectorにて配布中! 是非お楽しみくださいませ。
文豪チャットの詳細情報 : Vector ソフトを探す!

操作説明は以下のさくらミケ氏のブログにあるので、私のブログにおいては割愛させていただきます。
2017年文化祭展示作品 文豪チャット|猫もあきれるプログラミング日記

ソースコードはこちらから。
GitHub - sakurakitten/Bungo-chat: 文豪チャット( http://www.vector.co.jp/soft/winnt/amuse/se515415.html )のソースなどです. 必要なデータファイルはこちら(https://github.com/sakurakitten/Bungo-chat-data )

バグ報告はこの記事のコメント欄でもGitHubのIssueでも何でも良いですが、作者から返信が来ていないかたまにチェックしていただけるとありがたいです。(その点ではGitHubのIssueが一番ですね)
既知の不具合については、GitHub以外で報告されたものも気付き次第Issueを立てておくので、バグ報告する前に同じバグ報告がされていないかチェックしていただけると助かります。

さて、この記事では、会話の応答文の生成に用いられている手法などについて書いていきます。なお、分担して制作したプログラムのうち、さくらミケ氏担当の部分については、この記事では割愛させていただきます。

目次

コンセプト

目指したもの
りんな

目指してないもの
iOS - Siri - Apple

両方とも人間の発話に応答するプログラムですが、私にとってのりんなとSiriの違いを的確に表す画像がこちらです。

要するに、今回のプログラムでは、「道案内」や「Webで検索しました」などの便利機能はなしで、単に会話の相手を務めることを目指しています。

最初は「コミュ障カメレオン」というオリジナルキャラクターの会話AIを作るみたいな流れだったんですが、日本語の文章を大量に入手する手段として青空文庫を紹介したのがきっかけで、文豪の会話AIを作ることになりました。

各種制約

「文化祭作品」としての制約

  • インターネット環境なし
  • Visual C++ 2008
  • Windows XP/Vista/7 で動作
  • あんまり自由に色々インストールできない雰囲気

自ら設定した制約

  • 異なる文豪のAIが同じように会話すると面白くない
  • その文豪「らしさ」が失われないようにすべき
  • 文豪の著書以外の文章はなるべく使用しない

制作当時、学校のパソコンに入っているIDEVC++ 2008だったことで、あれがないこれがないとグチグチ言っていたのですが、どうやらstd::tr1というところに色々入っているらしい、というのを最近知りました(かなしい)。
後半の制約は「文豪の会話AI」というコンセプトを選択した結果生じたものですが、特に「文豪の著書以外の文章はなるべく使用しない」が最も厳しい制約だったように思います。

会話文生成プログラム

マルコフ連鎖による文生成

文生成の手法としてマルコフ連鎖というものが有名らしい、ということで実装してみました。

この手法では、ある単語についてその次に来うる単語のリストを作成しておき、文生成の時には、ある単語に対して次に来うる単語を適当に選び、さらにその単語に対して次に来うる単語を…、ということを繰り返して文を生成します。

たとえば、「きのこの山は好き。だけどたけのこの里はそこまで好きじゃない。」*1という文章に対して、前後の単語のつながりを表にすると、

きのこ
山, 里
好き, そこまで
好き 。, じゃ
だけど
だけど たけのこ
たけのこ
じゃ ない
ない

ここから単語を適当に辿って新たな文を作ります。たとえば、「たけのこ」から始めると、

「たけのこ」→「の」→「山」→「は」→「好き」→「。」

なんてのが作れます。元の文章にはない文ができました。

この例では一つ前の単語から次の単語を決めていますが、実際のプログラムでは、一つ前の単語と二つ前の単語が一致する単語のリストから単語を選んでいます。

さて、これをどう会話に組み込むかについて、最初は相手の発言に含まれる単語の一つを文を生成するようにしたのですが、全然会話になりませんでした。ボツにすることも考えたのですが、それももったいないので、相手が寡黙な時に自分から話を始めるために、これを用いて適当な文を生成しています。今思うと、「相手の発言に含まれる単語の一つを含む文」という条件は会話には緩すぎるので、相手の会話に含まれる単語やその関連語の出現確率を上げるとかするともっと良くなるかもしれないです。

この手法による文生成は、文法的には不自然でない文を作りやすいですが、文が長くなるにつれて前後で内容のつながりがなくなり、意味的にはさっぱりわからない文ができることが多いです。短い文が出るまで繰り返すみたいなことをやると改善するかもしれません。また、地の文を基にして文を生成しているため、会話として不自然になりがちなので、会話文のみを基にするのが良い気がします。

返答リストから乱択

何かの参考になるかなと自分のLINEのトーク履歴を眺めていたところ、9割くらい「へえ」「そう」「はあ」「ほー」「なるほど」「はい」のような当たり障りのない相槌*2で会話していることに気がつきました。LINEみたいな短文でのやりとりでは、相槌は結構役に立つ気がしたので、これを取り入れてみようと思いました。

ただ、確率で「へえ」とか「なるほど」とか言うという作りでは、「文豪らしい会話を!」とかいう制約に引っかかるので、著書から相槌を抽出して、それを使うようにしています。その抽出方法とは、

手動

手動です手動。文章から「」『』で囲まれた文を取り出して、その中から相槌に使えそうなものを人手で集めました。感動詞のみからなる文を抽出するとか、短い/単語数が少ない文を抽出するとかで自動化もできたかもしれませんし、学習的なことをさせても良かったのですが、そんなことを考えるよりも手動でやった方が早い気がしました。こういう人がいるから神エクセルが無くならないのでしょう。

ただこれが結構上手く行くんですよね。当たり障りのない返事ばかりなので。

ついでに、質問に対し適当に答えるものも作りました。たとえば「誰」が含まれる発言に対し、「妻がその人の名をいいましたか」(夏目漱石)といったような応答が用意されています。また、質問をはぐらかす、「今日は駄目です」(夏目漱石)のような応答もあります。特に「いつ」については、答えの中の日時にあたる部分を適当な日時に置き換えることでちょっとバラエティを出す、という小細工が仕組まれています。

ちなみにこれは黒歴史なんですが、公開当時は「君の名は。」という映画が流行していた*3もので、「君の名は。」と質問すると「名前はまだ無い。」(夏目漱石)とか「如何にも自分は隴西の李徴である」(中島敦)とか答えるようになっています。「名前はなんですか」みたいな尋ね方でも同様に返答できます。

この手法は、作業さえ頑張ればそこそこのクオリティになるので、割とおすすめです。作業さえ。

まとめ

会話プログラムを作るのはとっても楽しいです。今後も開発を続ける気満々です。時間があればTwitter botにしてみるとか、新たな手法を追加するとかやってみたいと思っています。ソースも公開されているので、いじってみたい方は是非フォークして遊んでください!(再利用しやすいコードかというと……うーん………)

*1:この文章に戦争を起こす意図はありません。似た構造の2文が欲しかっただけです。もっと中立な例文募集中

*2:当たり障りのないとは書いていますが、自分の中では話題に対する興味とか話の流れとかで厳格に使い分けています

*3:でも名前を答える機能自体については「君の名は。」の前から考えていたんですよ!!証拠のメール(4月29日付)もありますっ!!!(必死)

Women's CodeSprint 3に参加してみた

某プロから「Women’s CodeSprint 3という女性向けコンテストがあるから参加してみて!」みたいなメンションが来たので、ちょっと参加してみました。

結果

6問中4完、188.24点/245点満点で、186位/3541人でした。 Programming Problems and Competitions :: HackerRank
順位表見たら日本の中では2位!とか思ったんですがそもそも日本人8人しかいませんね……少ないなあ………

概観

開始時刻にとりあえず問題をパッと見たのですが、

  • Easy 2問
  • Medium 3問
  • Hard 1問

の合計6問を48時間で解くということで、恐らくTシャツ枠は速解き勝負だろうなと思いました。私は速解き勢になれるほど時間に自由がないので、まったり参加することにしました。

あまり本質的ではないのですが、非ASCII文字を含むコードを受け付けてくれないようで、日本語コメントを書いていると弾かれるのが少々面倒でした。

A. Birthday Chocolate (Easy, 10点)

与えられた数列について、連続するm項の和がdとなるような箇所の個数を求めればよい。

d、m共に小さいので、何も考えなくても数列の項それぞれに対しm項の和を計算するだけで解けます。

「連続するm項の和」ということで、数列の最後の方での和を計算する際に範囲外アクセスをしないようにする必要がありますが、多めに配列を確保しておいて、数列の外にあたる部分はINFで埋めておくと場合分けとか考えなくて済むので楽だと思います。(INFがあまり大きいとオーバーフローするので、d≦31だしINF=32で良いと思います)

B. ASCII Flower (Easy, 20点)

花のAAをr行c列出力する。

AAを1行ずつに分けて考えます。くらいしか書くことがない。

C. Hackathon Shirts (Medium, 30点)

n個の値のうち、v個の閉区間の少なくとも1つに含まれるものの数を出力せよ、というクエリがq個来る。

O(nv)しか思いつかず、まあギリギリ間に合うかな!wと思っていたらクエリがq個来るのを忘れていてTLE。二分探索してチェックする閉区間を減らしたりcout・cinをprintf・scanfにしてみたりと色々小手先の高速化をしてみたらちょっとだけTLEケースが減りました。結局、重なっている区間はまとめて1つの区間として扱うことでACしました。(これは序盤で思いついてはいたんだけれども、区間が1つも重なっていなくて全く高速化されないテストケースが絶対にあるはずだと思っていたので、あまり実装する気が無かった)

区間をまとめる処理については、v個の区間をpairのリストにしてソートし、隣接している区間が重なっている(または接している)かを調べて、重なっていれば一方を更新してもう一方は削除、というのを前から後ろにかけて繰り返せばよいです。

重なっている(または接している)隣接した区間 v_1=(a_1, b_1), v_2=(a_2, b_2)とすると、重なっている(または接している)条件は b_1 \leqq a_2-1で、区間をまとめると v_3=(a1, max(b_1, b_2))となります。
私は最初b_1>b_2の場合を考えていなくてバグらせました。ただただ頭が悪いです。ただこの問題はテストケースを自作するのが簡単なので、すぐに気づけました。

ハマったこと

いろんな位置で削除をすることになるので、ランダムアクセスすることもなさそうだし、区間を表すpairのリストにはstd::listを使ってみました。vectorでTLEするかどうかは知らないです。std::listはあんまり使ったことがないので、色々とハマりました。

std::listはstd::sortができない

std::sortはランダムアクセス可能なイテレータを扱うらしく、双方向イテレータであるstd::list::iteratorは使えないようです。代わりに、std::list::sortを使うことでソートすることができます。ならし計算量はO(N log N)。

双方向イテレータにはoperator +がない

まあ普通に考えればランダムアクセスができないので、itr+5とかできないのはそれはそうなんですが、じゃあ隣のイテレータはどうやって取得すれば良いのだろうと思ったら、std::prevとstd::nextというものがあるようで、たとえばitr+n的なことをnext(itr, n)というように書くことができます。
ただよく考えたらitr2=itr;++itr2;としてループ回せば良い気がします。

eraseの返値は削除した要素の次の要素を指すイテレータ

これはstd::listに限らずSTLコンテナはだいたいそうだと思うのですが、「eraseするとイテレータが壊れるけど、eraseがちゃんと新しいイテレータをくれるからOK!」とか言ってforループ内でeraseすると、消した要素の次を指すイテレータがさらに++itrされてしまいます。今回は、削除した直後のイテレータはマージした結果の区間を指していてほしいので、比較した2つの区間のうち前方にある方を削除することで実現しています。削除しない場合は普通に++itrをします。

そんなこんなで計算量はO(q(v log v+n+nv))です。ハイ。これが想定解な訳ないだろと思って上位陣のコードをちらっと見たんですが、何をやっているのか私には読めませんでした。精進します。

D. Choosing Recipes (Medium, 50点)

r個のレシピと、p個の材料がある。それぞれのレシピはp個の材料のどれを使いどれを使わないのかが書かれている。p個の材料にはそれぞれ価格が設定されている。材料は一度買うと無限に使うことができる。今、既に持っている材料と、作るレシピの数nを与えられたとき、買わなければならない材料の価格の総和の最小値を求めよ、というクエリがq個来る。

r≦30でn≦10なので全探索しても最大_{30} C _{10} \approx 3.0 \times 10^7なのでまあギリギリイケるかな(適当)

_r C _n の全列挙は、手で書き出す時みたいな感じでやります。

適当にk番目の要素を選んで、 f:id:pizzacat83:20170315204740p:plain

次はk+1番目以降の要素を選びます。 f:id:pizzacat83:20170315205103p:plain

これを繰り返してn個選ぶと、必ず昇順で選ばれるので、同じ組が重複して2回以上数えられてしまうことはありません。

さて、これを再帰関数として実装します。ナップサック問題と違って、単純に各レシピのコストの和を最小化するわけではないので、それまでに選んだレシピの情報を何らかの形で渡す必要があります。引数は今まで選んだレシピのvectorでも良いかもしれませんが、問題文でレシピがビットの配列であることがさんざん強調されていることもあり、「あと何個レシピを選ぶか」「今まで選んだレシピにおいてある材料を使うかどうかのビット配列」「何番目の要素から探索するか」を引数にとって、コストの最小値を返すことにしました。n個選び終わったら、引数のビット配列からコストを計算します。既に持っている材料については、その材料のコストを0にしておけば問題ないでしょう。

ってクエリq個来るじゃないか

まーた複数クエリの分の計算量を忘れていました。さすがにTLEしそうです。なのでメモ化をします。計算量は O(q(2^prn))。おしまい。

ちなみに、「今までに選んだレシピのvector」が違っても「あと何個レシピを選ぶか」「今まで選んだレシピにおいてある材料を使うかどうかのビット配列」「何番目の要素から探索するか」が同じであれば結果は変わらないので、後者を引数にした方が効率的でしょう。「それ以前の状態がどうであっても、これが等しいなら値が等しくなる」ということに気付くことが、メモ化の一番重要なことなのかもしれません。その点では、この問題はレシピをビットの配列として入力させるよりも、使う材料のリストで与えた方が面白かったのではないかな、と思いました。

ところでstd::bitsetはビット演算に慣れていなくても扱えるので良いですね。std::bitset::to_ulongで整数として扱うこともできますし、operator []で配列のように扱うこともできます。std::bitset::to_stringもあるので、デバッグ出力も問題なくできます。良い。

E. Elevator Simulation (Medium, 50点)

与えられたルールに従って、エレベータをシミュレートせよ。

現在テストケース4つくらいWAしているので、以下の内容は誤りを含んでいる可能性が高いです。ACしたら追記します。
2017/03/16追記: ACしました。
「最後に乗車した乗客の降車時刻」を求めるべきであるところを、「最後に降車した乗客の降車時刻」を出力していました。

実装するだけです。私は無限にバグらせることが容易に予想できたので、これでもかとデバッグ出力をしました。

全部vectorでもいけるかもしれませんが、人が待っている列はFIFOって書いてあるしqueueとか使うとよいと思います。「教師は生徒の前に割り込む」というルールは、「教師の列」と「生徒の列」を作って、教師の列が空である場合に限り生徒の列からエレベータに乗せるようにして実装しました。あるいは乗客の情報を優先度付きキューに入れることでもできそうな気もします。

「エレベータが満員の時、後から来た教師は最も遅く乗車した生徒を追い出して乗る」というルールについては、エレベータの乗客から生徒を後ろから探して、その生徒をeraseし、教師をpush_backして、追い出された生徒は生徒の列とは別のstackに突っ込むことで実装しました。追い出された生徒よりも早く列に並んだ生徒は、多分存在しないはずです(証明はしていません)。

エレベータから人を下ろす際は、事前に乗客を目的階でソートしておくと、後ろからどんどんpop_backするだけになります。その後、乗客がまだ残っていれば上昇し、もう残っていなければ下降します。

2017/03/16追記:
最後に乗車した乗客は、将来列に並ぶ人の配列と、全ての待ち行列がemptyになっているかどうかを判定すれば良く、もしそうであればその情報も併せてエレベータのvectorに突っ込みます。この時これ以上人は来ないので、教師に追い出される等を考える必要はありません。エレベータから人を降ろす処理の中で、もし「最後に乗車した乗客」である場合に、その時刻を出力し終了すればよいです。

ハマったこと

std::reverse_iteratorをそのままでeraseはできない

やろうとするとコンパイルエラーが出ます。そこで、reverse_iteratorが内部的に持っているイテレータを、std::reverse_iterator::baseで取得します。ただし、この内部的に持っているイテレータは、reverse_iteratorが指している要素の一つ前(begin側)を指すイテレータなので、取得したイテレータに+1したものをeraseに渡すことになります。

以下の記事は図解もあってとても分かりやすいと思います。 改善版 reverse_iterator 使用中のerase()の仕方 - 自習室

std::tupleの使い方

「教師か生徒か」「到着時間」「目的階」の3つの情報をまとめて扱いたかったのですが、構造体は比較関数を書くのが面倒なので、std::tupleを使ってみました。宣言はsyd::pairっぽく書けるし、 std::make_pairの代わりにstd::make_tupleなんてものがあります。ただし、pairは値をfirst, secondで扱うことができますが、tupleの場合はget<0>(tpl)みたいな形になります。

まあだからなんだと言われるとそうなんですが、私は何が何番目に格納されているのか訳が分からなくなるし、型が一緒だとその誤りも結構見つけづらいので、やっぱり3つ以上の値の意味を数字と結びつけるのは無理だと感じました。今後は素直に構造体を書いて、分かりやすいメンバ名をつけるようにした方が、総合的に楽だと思いました。

なお、これは個人の感想です。問題なくtupleを扱えるような人であれば、pair in pairみたいなことをしなくても良いので、便利ではないかと思います。

F. Spring Decorating (Hard, 75(30)点)

R, B, Gからなる長さnの文字列を作る。文字列中に出現するRB, RG, BR, BG, GR, GBの個数の上限が与えられたとき、上限6つのいずれも超えない文字列の個数を、 mod(10^9+7)で求めよ。
テストケースの40%は、RG=BG=GR=GBをみたす。

部分点解法

RG, BG, GR, GBはいずれも登場しないので、RBとBRについてのみ考えます。

RBがちょうどx個、BRがちょうどy個出現する文字列の数を考えます。RBの次にRBが、またはBRの次にBRが来ることはないので、|x-y| = 0, 1となります。

(i) |x-y| = 1のとき

x-y = -1をみたす文字列はx-y = 1のRとBを入れ替えた文字列となるので、x-y = 1についてのみ考えます。

これをみたす文字列は、RBとBRだけ抽出すると、RBで始まり、RBとBRが交互に来て、最後はBRになります。すなわち、RBとBRの並びが一意に定まります。

よって、n個の文字列の中でどこが色の境目になるかを決めれば、その色の境目にRBとBRのうち適切な方を割り当てられるので、文字列は一意に定まります。したがってn個の文字列の文字と文字の間n-1箇所から、色の境目となる(x+y)個を選ぶ場合の数を求めればよく、これは \displaystyle _{n-1} C _{x+y}=\frac {(n-1)!} {\{(n-1)-(x+y)\}!(x+y)!}と計算できます。結局これのmod(10^9+7)を計算することになりますが、除算を含む式の剰余を求めるので、ひと工夫必要です。

aとpが互いに素のとき、フェルマーの小定理を用いて除算を乗算に置き換えることができます。知識問題。
yukicoderのwiki合同式について色々書いてあります。 https://yukicoder.me/wiki/mathematical_property数学的な性質 - yukicoder
yukicoderには順列や組み合わせの剰余を求める問題がありますし、確か蟻本にも組み合わせの剰余を求める問題が載っています。

(ii) |x-y| = 0 すなわち x = y のとき

(i)と違って、RBに始まりRBで終わるか、BRに始まりBRに終わるかで、RBとBRの並びが2通り考えられます。ただしこれはRとBについて対称なので、片方について考えて2倍すれば良いです。

あとは(i)と同様で、場合の数は \displaystyle 2 _{n-1} C _{x+y}=2 \times \frac {(n-1)!} {\{(n-1)-(x+y)\}!(x+y)!}となります。

ここまで考えたら、あとはxとyをRBとBRの制約と|x-y| = 0, 1をみたすようにループを回して、総和をとるだけです。

これは罠で

x = y = 0の時を考えます。これをみたす文字列は、上式の通り、「全てR」「全てB」の2通り。ではありません。

「全てG」もこの制約を満たすのです。なお、x = y = 0でないときは、RG, BG, GR, GBのいずれかが出現してしまうので、Gについては考えなくて良いです。私はこれに気づけずINF時間悩み続け、n文字の文字列 3^n個全て調べる愚直解を書いてやっと気が付きました。ふう。

本解

まだACしていません。ACしたら追記します。

ひとりごと

#codelikeawoman ってどういう意味なんだろう。「コンピュータ科学における男女格差の改善を手助けするコンテストです。」みたいなことが書いてあるけど、女性らしいコーディングって何だろう……

はじめに

はじめまして、ぴざきゃっと(@pizzacat83)と申します。

このブログについて

このブログでは主にプログラミングについて書いていくつもりです。初心者なのでおかしなことを書くかもしれません。コメント等でご指摘いただけると嬉しいです。

このブログのタイトルは「null部の部誌」ですが、これは架空の組織であり、仮にそんな部活が実在していたとしてもこのブログとは無関係です。
かといって、何らかの実在の部活の部誌でもないです。非公式の部誌でもありません。単なる個人のブログです。
要するに、タイトルに深い意味は何らありません。

また、このブログに書かれた内容は、ソースコードを含めて、すべて無保証です。このブログに書かれていることを実行することなどは、自己責任でお願いします。