先日投稿した42に関する投稿が、このブログにしてはアクセスを稼いでいる。その投稿の内容よりも、42の話題性、その関心に起因するものだろう。
42 SILICON VALLEY Piscine 2017資料を読み解く 印象、考察、そして余談。 - Technically Impossible
42 SILICON VALLEY Piscine 2017プロジェクト資料を読み解く 印象、考察、そして余談。 - Technically Impossible
学期末で、些か暇を持て余している。せっかくPiscine受講者の方々がアクセスしてくれているのだから、先日の投稿に加えて、何か「お持ち帰り」感のある情報を提供できないだろうか、と考えた。
Piscineの特性を考えると、公開されている課題について、そのプログラムを示しても有意義ではないだろう。ダミー・コードが含まれている場合もあるとはいえ、コードはGitHubに公開されている。何よりPeer learningを伴うため、コードだけを見たところで、受講者が自分自身でそのロジックを説明できなければ意味がない。
Peer learnngのパートナーはランダムに選別されるのだという。課題を理解している者が、理解していない者へ教えるという構図が常に成り立つとは限らない。課題を理解していないものが、理解している者へ教える場面もあり得るのだ。そのような場面で、いきなりプログラムを提示することなど無理だろう。むしろ課題を解くための考え方、アプローチを示すことを求められているのではないだろうか。
受講者の中には、C言語そのものよりも、プログラミング自体についての初学者もいるようだ。課題の回答に通じるプログラムを直接的に示すよりも、課題を題材にして、ロジックを見出す考え方、解法に至るアプローチを伝えることの方が、プログラム自体を示すよりも汎用的で有用ではないかと考えた。
ここでは42SV、2017年PiscineのDay02の課題を題材に、私なりのアプローチを説明してみようと思う。対象の課題はExercise 04～07（06は除外）だ。特に次の事柄を伝えることに焦点を絞った。
- 力技による真正面からの正攻法でも良いが、より効率的なアプローチを見出すこと。
- Piscineの課題には関連があり、後に続く課題を解くには、前の課題のアプローチが応用できること。
この投稿がPiscine受講生の一助になれば、と思う。
間違っていたらゴメン。
Exercise 04
Create a function that displays all different combinations of three different digits in
ascending order, listed by ascending order - yes, repetition is voluntary.
• 987 isn’t there because 789 already is.
• 999 isn’t there because the digit 9 is present more than once.
異なる数字の組み合わせで3桁の数を昇順列記する、ことを求められている。000～999のうち、異なる数字で構成されている数を昇順列記することになる。力技で解くならば、対象範囲の数を構成する数字、一つひとつを検証するプログラムを書くことになるだろう。
それは課題を真正面からとらえた正攻法だが、力技でもある。より効率的に解くには、全体を俯瞰して見ることで、列記すべき数にまたがる規則性を見つけやすくなる。視覚的にパターンを捉えることができれば、論理的思考もまとまりやすくなる。10進数の数の場合、10×10の行列を作り、それらを組み合わせてみる。こんな具合だ。
※ブログ掲載の都合上、行列を転置している。右へ90度回転し、縦長の行列として眺めてほしい。縦軸を00～99、横軸が0～9を組み合わせた3桁の数が並んでいる。
10×10の行列を1ブロックと捉えてほしい。赤が1ブロックの対角成分、青は数字が重複する箇所、黄色が列記すべき数だ。白の領域では、数字の組み合わせが、黄色の領域と重複するため対象範囲外。回答に含めるべき数、それを導くための規則性、ロジックを容易に見いだせるのではないだろうか。
力技で解く場合、白の領域を特定するのが厄介だ。1000個の数に対して、
- 数を構成する数字の重複を調べる。
- 数の組合わせの重複を調べる。
000～999に対する1000回のループ中で、これらの検証を行うことになる。これを実装するプログラムと、上記行列に含まれる黄色の領域を導き出すロジックを想像、比較してみてほしい。きっと後者の方が実装は簡単で、力業に比べて遥かに効率的なプログラムになることが、感覚的に理解できるだろう。
Exercise 05
Create a function that displays all different combination of two digits between 00
and 99, listed by ascending order.
課題は次のことを求めている。
- 2桁の数字で異なる組み合わせを昇順列記する。
- 構成する数字の重複は考慮する必要がない。
実際のところ、これはExercise 04で用いた行列の考え方を採用すれば、かなり簡単に解くことができる。縦横、00～99で構成される100×100の行列を想像してみてほしい。その対角成分、上側が列記すべき数字（組合わせ）になる。
縦横、00～09で構成される10×10の行列を考え、それを縦横99まで延長したものを想像してみてほしい。
求められているロジックはExercise 04のものが応用でき、実装はより簡単であることが感覚的に理解できるだろう。もしExercise 04を力技で解いていたならば、05も力技で解くことになる。プログラムの効率が悪いだけでなく、時間の使い方も効率が悪くなる。私が先日の投稿で触れた
明示されてはいないものの、課題には１度限りで完結させず、他の課題への関連や発展を含意するような仕掛けが目に付いた。以前に経験した課題の知見を引き継ぐ前提で設計されているようだ。おそらく、この知見の再活用を前提に負荷を考慮しているのだろう。とにかく課題数に容赦がないのだ。
全ての課題を一から考え直す場合、知見の応用、再活用ができることに気付いた場合では、負荷は大きく違うことだろう。
それは、こういうことなのだ。
懸念事項
ところで、なぜ数字の重複は問われていないのだろうか？これは意図的に仕掛けられた落とし穴だろうか、あるいは何かしらのヒントに通じているのだろうか？
こういう些細なところに疑問を抱いたならば、その感覚は大切にしたほうが良いと思う。
Exercise 07
• Create a function that displays all different combinations of n numbers by ascending
order.
• n will be so that : 0 < n < 10.
1~9までの内、一つの数字が指定される。これをnとする。異なる数字で構成されるn桁の数を昇順列記せよ、というのが課題だ。これを力技で解くことは無理ではないが、その処理、ならびに実装は大変な手間になるのではないだろうか？ここでも、先に用いたアプローチが応用できる。
n=1の場合は簡単だ。0～9を列記すればよい。
n=2の場合は？Exercise 05で例示した表の00～09を見てほしい。桁揃えのための前0は無視する。
端的にはこういうことだ。
n=3の場合は？これはExercise 04でやった。改めて掲載の行列を縦長にして見つめ直してほしい。このとき行列の縦軸を2桁の数字の列、横軸を1桁の数字の列として、行列の数はその組み合わせとして眺める。
n=4の場合は？これがExercise 05の懸念事項に通じている。Exercise 05では数字の重複を考慮しなかった。Exercise 07では数字の重複を考慮しなければならない。
Exercise 05で数字の重複を考慮した場合、対象範囲はどうなっていただろう？その一部を図示しているのだが、延長上にある対象範囲を想像しながら見てほしい。
Exercese 05では対角ブロック（グレーの領域）の対角成分（赤い領域）より上が表示対象範囲だった。数字の重複を考慮すると、その表示対象から、さらに黄色の領域を絞り込まなければならない。図示している領域は回答となる範囲の一部だが、対象範囲を絞り込むロジックを見出せそうなパターンが、感覚的に分かるだろう。Exercise 07では、この黄色の領域が対象範囲だ。
ちなみにn=2の結果、判明した対象の数同士で行列を作った場合、n=4の行列はこのようになる。先ほどの行列と比べ、どちらが分かりやすく、ロジックを組みやすいだろうか。
いずれにせよ、やはり対象範囲を絞り込むロジックを見出せそうなパターンが存在することが、感覚的に分かる。
n=5の場合はどうだろう。ここからが、この課題の独自性だ。n=5以降で同じアプローチを適用したならば、手間は結構なものになりそうなことは想像がつく。ここまでの成果を応用することを考えてみる。このようなアプローチはどうだろう？
| n=1 | 0～9を列記した。 n=0、1の対象数同士の行列から、数字の重複を排除した範囲だった。 |
| n=2 | n=1の対象数同士の行列から、数字の重複を排除した範囲だった。 |
| n=3 | n=1、2の対象数同士の行列から、数字の重複を排除した範囲だった。 |
| n=4 | n=2の対象数同士の行列から、数字の重複を排除した範囲だった。 |
| n=5 | n=2、3の対象数同士の行列を考える。 |
| n=6 | n=3の対象数同士の行列を考える。 |
| n=7 | n=3、4の対象数同士の行列を考える。 |
| n=8 | n=4の対象数同士の行列を考える。 |
| n=9 | n=4、5の対象数同士の行列を考える。 |
すでにn=2、3、4の対象範囲となる数、そのロジックは確認済みだ。n=5以降の対象範囲となる数は、それらを利用して求めることができる。対象範囲の数同士を組み合わせた行列を作れば、要求されているロジックに通じる、何らかの規則性を見出せるのではないだろうか。
特にn=6、8の場合はn=2、4の場合のロジックが応用できそうだ。
n=5、7、9の場合は、n=3の場合のロジックが応用できるのではないだろうか。
Exercise 05では、なぜ数字の重複を考慮しなかったのだろう。n=4の場合で、重複の考慮に関わらず、何らかの規則性を見出すことができることは分かっている。問題は、どちらが分かりやすいかだ。
あるいは抜本的に異なるアプローチ、例えば、いずれのnの場合においても、統一的なロジックを見出して実装することができるかもしれない。それはロジックとして、さらに効率が良いだろうが、新たなアプローチの模索は、制限時間内での実装時間配分を考慮した、トレードオフのリスクを前提としている。
さらにあるいは、よりシンプルで効率の良いロジックもあるかもしれない。この辺がExercise 07の山場だ。
ちなみに行列を作る時にはExcelを用いると良い。42 TokyoではiMacを採用しているという。Excelがインストールされていなければ、webを活用すればよいだろう。
products.office.com
www.google.com
余談－力技のトレードオフ。
力技は必ずしも悪いものではない。限られた時間内で、効率的なロジックを見出そうとしても、考えるだけで実装できなければ、何の成果も得られない。例え力技でも、制限時間内に正しい出力結果が得られる実装が完了できれば問題ない。Piscineに限らず、どのような場面でも最低限、求められていることだ。
例え処理速度が速くとも、誤った結果が出力されるならば、どうしようもない。誤ったアプローチでは起こりがちだ。Piscineに限らず、最低限の成果を確保するか、さらなる成果を求めるかはトレードオフの関係にある。
まずアプローチが思い浮かばない場合には、力技から始めてみるのも一つの方法だ。実装中にアプローチが閃いたならば、制限時間を考慮して余裕があれば、そのアプローチを試せばよいのだし、そうでなければ確実に正解が分かっているロジックでの作業を続けた方が良いこともある。
Day04にも同様なロジック問題を見つけた。後日、時間のある時に話題として取り上げようと思う。
By Odin, by Thor ! Use your brain !!!
impsbl.hatenablog.jp
