名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

「yieldのお勉強 Lv.99」ヒント公開! #CodeIQ

現在 CodeIQ で出題中の「yieldのお勉強 Lv.99」×2 について。


挑戦者求む!【Ruby】yieldのお勉強 Lv.99 by @antimon2 antimon2│CodeIQ

挑戦者求む!【Python】yieldのお勉強 Lv.99 by @antimon2 antimon2│CodeIQ

(タイトルが一緒なので紛らわしいですね^_^;)

問題掲載開始から2週間あまりが経ちました。
おかげさまで難易度「★★★☆」にも関わらず多くの挑戦者様に挑戦いただいています(前回 Lv.2 の約半数にまで達しました♪)。

ただ、おそらくまだ「難しそうだから後回しにしよう」と足踏みしている方も多いと思います。
またお寄せいただいた回答の中にも、問題文中*1で桜先生が言っているあの言葉。

誰が、あの『コンパクトでキレイなコード』にたどり着けるかしら♪

これ、私の想定していた解答例のことなのですが、そこに達した方は、まだ1人もいらっしゃいません。
(ただかなりコード量の少ない解答はいくらかはよせられています(^-^))

そこで。
この問題を解くにあたってのヒント*2を、少しだけ公開しちゃいます。
Ruby編・Python編共通の、『コンパクトでキレイなコード』に向けての考え方のヒントです。
(もちろんヒントだけです。解答例は出しません)

「いやだ自分で考えたいっ!」と言う方はもちろんここで引き返してくださってもけっこうです。
ご興味のある方は、続きをどうぞ( ^-^)/

問題プログラム

問題は、Lv.1・Lv.2 と同様、テストを pass するようにプログラムコードを埋める実用問題です。
まずはとにかく、問題プログラムを掲載します。

問題プログラム(Ruby編):

問題プログラム(Python編):

Lv.2 と違い(Lv.1 と同様)、今回は Ruby編/Python編ともに(ほぼ)同じ内容となっています。
よって「考え方」だけなら、RubyでもPythonでもどちらでも応用できます。

問題は、「引数で与えられた複数イテレータの直積を列挙*3する関数(メソッド)を実装する」というもの。
ただし、引数に所謂「無限リスト(ストリーム)」が与えられた場合にも対応すること。
そうでなければ、Rubyなら Array#productPython なら itertools.product() という対応する関数/メソッドがすでに存在しています(そしてそれらは無限リストに(きちんとは)対応していません)。

また「無限リスト(ストリーム)」に対応する直積(の要素の列挙方法)はいくつかやり方があるのですが、それを、列挙される順番をテストコードで示すことによって指定しています。
「ここで示した順番で列挙されるように実装すること」という条件も含まれている、ということです。

次節でその「列挙順序」について、簡単に解説します。

直積の列挙順序

以下、説明のために2つのリスト(または無限リスト)の直積を考えます

参考:標準ライブラリが生成する直積の列挙順序

まずは、RubyArray#productPythonitertools.product() を利用した直積が、実際にどの順序で列挙するのか、を見てみましょう。

Ruby:

a = [1, 2, 3]
b = [1, 2, 3]
p a.product(b)
# => [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

Python:

import itertools
a = [1, 2, 3]
b = [1, 2, 3]
print(list(itertools.product(a, b)))
# => [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

表現が違いますが、どちらも同じ順序であることはお分かりですね。
所謂「辞書式順序」と呼ばれる順序になっています。
例えば Python なら、同じ結果になるような generator 関数は以下のように書けます(引数2つの場合):

def product(a, b):
    for x in a:
        for y in b:
            yield (x, y)

print(list(product(a, b)))
# => [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

動くようにしてみました。↓横軸が b、縦軸が a です。

(1, 1)(1, 2)(1, 3)(2, 1)(2, 2)(2, 3)(3, 1)(3, 2)(3, 3)

実線の円が、実際に列挙される組(tuple)を表すと共に、その動きが b の中から列挙対象となる数がどのように変化しているかを表しています。
同様、破線の長円は、a の中から列挙対象となる数の変化を表しています。
for 文の入れ子を考えても分かる通り、有限の場合はこの列挙方法が簡潔で仕様としても充分です。

ところが、b が無限リスト(ストリーム)の場合は、この方法だと問題があります。

例えば、以下*4↓:

a = [1, 2, 3]
b = itertools.count(1)  # 1, 2, 3, …(infinite)

for x in a:
    for y in b:
        print((x, y))
        # => (1, 1)
        # => (1, 2)
        # => (1, 3)
        # => (1, 4)
        #  : (1, y) が無限に続いて、いつまで経っても (2, 1) に達しない!

(2, 1) といった、容易に手に取ることができそうな組合せが、永遠に列挙対象にならないのです*5
もちろん a も b も無限だった場合でも問題は同じです。

そこで、全く異なる列挙方法(列挙順序)を考える必要があるワケです。

拙問で求める列挙順序

その列挙順序は、以下のような感じです:

(1, 1)(1, 2)(1, 3)(1, 4)(2, 1)(2, 2)(2, 3)(3, 1)(3, 2)(4, 1)

つまり「斜め」に列挙する、というワケ。
これなら、左上から順に、「容易に手の届きそうな組合せ」から順に、すべて列挙できそうですよね?*6

ポイントは、先ほども言ったように「斜め」に列挙している、ということ。
ここに気付いた方は、《検閲》 という方法*7で列挙を実現し、正解を出していました(^-^)

ただし。
この方法、言葉で書くのはそこそこ直感的で分かりやすそうなんですが、コードに落とすと、色々と考えなくてはならないことが増えるし、処理は煩雑になるし、色々めんどくさかったりします^_^;
例えば。
今は2次元(イテレータが2つ)なので単純に「斜め(の線)」で考えれば良かったのですが。
3次元(イテレータが3つ)になると、他純な直線上の動きではなくなります。まず同じ原理で考えられるグループが「面(平面)」になり、《検閲》*8、と、少しややこしくなります。
これをさらに4次元以上(イテレータが4つ以上)にも対応させようとすると、相当キレイな法則性を見付けないと難しくなってきます。また、法則性を見付けて投稿してくださった方が実際にいるのですが、やはり処理が煩雑だったり色々無駄が出てきていたりしています。

ぶっちゃけて言います。
桜先生の言っていた「コンパクトでキレイなコード」は、この発想にこだわる限り、生まれません!*9

列挙方法を見いだすためのヒント

やっとこさ、本題です。

求める列挙順序は先ほど示した通りです。
でも、それを実現する列挙方法は、他にもあります。

もう一度、あの列挙方法のアニメーションを見てください。
以下に再掲しますので、目をこらして、よーく見てみてください。
だんだん、何かが見えてきませんか?

(1, 1)(1, 2)(1, 3)(1, 4)(2, 1)(2, 2)(2, 3)(3, 1)(3, 2)(4, 1)

ね? 何か見えてきたでしょ?w

その方法とは、ズバリ。
複数イテレータを生成して、それをパラレルに処理させる」という方法。

もうちょっとだけ詳しく言うと。
列挙のために必要なイテレータを、タイミングを見計らって1個ずつ新規生成します。
そのイテレータを、うまく並べて、1個ずつ『次の値』を取得して yield します。
これの繰り返し。
「まずこのイテレータから『次の値』を取得。次はこっちから。次にこっちに戻って、次はこっちで、ここで新しいイテレータを作って、こっちから『次の値』を取得して、次はこっちで…」
というような感じ*10

はい、ここまで!
もうこれ以上は言えません! 核心に迫り過ぎちゃいます!

でも、…もう一言だけ、これは言っておこうかな。
先ほど見せた(うっすらと見える)複数イテレータ、あのグループ分けの仕方は、あくまで一例です。他にもグループ分け(分割)の仕方があるかもしれません。
ただこの方法なら、3次元や4次元以上でもうまく再帰的にキレイに扱うことも…。

Good Luck!

さぁ、ここまでは手の内を明かしました。
これで「アレをどう使えば良いか」とか「コレはどう扱えば良いか」とか、色々お分かりになったのではないか、と思います(^-^)*11

挑戦締切まで、残りは2週間弱。
まだ解いていない方は、これらを参考に、ぜひ正解を導き出してくださいo(^▽^)o
すでに解いてしまった方も、この考え方を元にコードを一から書き直して、『コンパクトでキレイなコード』をめざしてくださいo(^▽^)o

Good Luck!
*12

*1:問題文は掲載期間終了後にどこかに再掲載はしません。今のウチに確認しておいてください。

*2:ヒントを出して良いか運営側に確認済です。

*3:より正確には『直積集合の各要素を列挙』ですね

*4:実際には b がリストではなく iterator である時点で、もし有限だったとしてもこの書き方だと問題があります。b が全て列挙し終わったら x が a の次の値に移っても b にはもう列挙すべきものが残っていない状態になってしまうので。なので Lv.2 問題で作った IteratorCloner のような仕組みが必要になってきます。

*5:for ループではなく itertools.product を利用した場合、内部で無限リスト(イテレータ)をリストに変換しようとして無限列挙が走り、見た目には一件も列挙されないままそのうち MemoryError で落ちます。最悪PCがフリーズするのでご注意。また Ruby の場合は Array#product はそもそも(レシーバも引数も)配列にしか対応していません。

*6:実際、数学の話で言うと、可算集合可算集合の直積が可算集合であることを示すために、この列挙方法を使ってすべて対応付け出来る、という証明論法が用いられます。

*7:書きかけたのですが、「日本語を翻訳してコードに落としたら解答ができてしまう」内容だったので削除しました^_^;ご了承ください

*8:同上^_^;

*9:冒頭でも言いましたが、実際にはこの方法に従っていてかつコード量のかなり少ない優秀な解答もすでに寄せられています。

*10:あくまで「こんな感じ」というだけです。実際の実装はこの通りとは限りません。

*11:逆に謎が深まった部分もあるかも…。

*12:関係ないですが今回むちゃくちゃ脚注多いですね^_^;