先日、ロジック問題に対する一つのアプローチを紹介した。アプローチ手法は異なれども、自分で考えることはロジック問題に限らず、何かにつけ共通する活動の一つだ。
42 SILICON VALLEY Piscine 2017 Day02を考える 私なりのアプローチ。 - Technically Impossible
しかし考え過ぎるのは良くない。時には考える必要がない、あるいは考えない方が良い場面もある。それは、いわゆる定石が適用できる、あるいはそれを積極的に適用すべき場面だ。特にプログラミングにおいては、そのような定石となる「アルゴリズム」が存在する場合だ。
Day02のロジック問題を、一から自分で考える問題とするならば、アルゴリズム問題は知識を活用し、適用するための問題だ。加えて、提供された限られた学習機会を通じて、どれだけのことを学び、実践適用できるかを試している問題にも見える。
ただし課題にアルゴリズム問題と明記されているわけではなく、受講者が判別、判断する必要がある。Day04 Exercise 08、09はその典型例だ。
42SV、2017年PiscineのDay04の課題を題材に、その取り組み方を説明してみよう。対象の課題はExercise 08～09だ。この投稿がPiscine受講生の一助になれば、と思う。
Exercise 08
• The aim of this game is to place eight queens on a chessboard, without them being able to meet in one shot.
• Evidently, recurstivity is required to solve this problem.
• Create a function that returns the number of possibilities to place those eight queens on the chessboard without them being able to reach each other.
• Your function must return its result in less than two seconds.
チェス盤にクイーンの駒を8個、お互いの進行方向が重ならないように並べる。何通りの並べ方があるのかを表示しなければならない。
この問題は、組合わせ爆発を伴う有名問題だ。そして組合わせ爆発を伴う問題を、より効率的に解くためのアルゴリズムも研究されている。
もし受講生がアルゴリズム問題であることに気付かなかったら、このような成り行きが想像できる。
Bad pattern
- 「チェス クイーン」を検索する。チェス盤は8×8の碁盤であり、クイーンは飛車＋角のように動く駒であると知る。
- 8x8の碁盤を作成し、条件に見合うように駒を並べてみる。
- なかなか条件に合致する配置を見つけられない。
- 色々試すのだが、全然見つからない。
- もしかして条件を満たせる配置は、かなり限られているのでは？
- 少し前提を変更して、計算してみることを思いつく。
- もしクイーンが１駒／縦列とすれば、何通りに配置できる？
- 8 x 8 x 8 x 8 x 8 x 8 x 8 x 8 = 1,677,216
- もしクイーン＝飛車であるとしたら、何通りの配置ができるのだろう？
- 8 x 7 × 6 x 5 x 4 x 3 x 2 x 1 = 40,320
- かなり少ない...クイーン＝飛車＋角ならもっと少ないはずだ。
- もしクイーンが１駒／縦列とすれば、何通りに配置できる？
- 「チェス クイーン」以外で検索してみる。例えば「チェス クイーン 並べ方」
- 検索結果はチェスのルールばかり。
- ※検索結果の下の方でバックトラック法がヒットしている事に注意。だが、その単語を知っていたとしても気付くことができるだろうか？
- もう一度検索してみる。「チェス クイーン 8個」
- なんかこれっぽい！→Good patternへ
配置を自分で検証してみることは、ロジック問題であれば有効なアプローチになり得るのだが、今回のケースは特殊だ。検証すべき配置は多すぎ、そのうち条件に合致する配置は少なすぎることに、この受講生は気付いていない。
計算してみることを思いつくが、条件を緩和したとしても目的とする配置の割合は極端に少ないことに気付く。クイーン＝飛車が成り立つ割合は0.24%。クイーン＝飛車＋角が成り立つ割合は、もっと少ない。実際それは92通りしかない。160万通りに比すれば、その割合はほぼ0%だ。
考えることを諦めて検索を始めた。このシナリオでは、参考になりそうな資料にたどり着けた。現実には、このときの検索キーワード「8個」を思いつく保証はない。アルゴリズム問題をロジック問題として対応したならば、ドハマりするリスクがあることに気づいただろうか。
Good pattern
もし適用できるアルゴリズムを知っていた場合、おそらくバックトラック法を解説したwebサイトへ直行することだろう。しかし、それでも受講生は楽できない。
前述のバックトラック法のページを参照し、まず本文を入念に、さらにプログラムも一通り読む。そして次のことに気付く。
- Piscineの要件に沿って、プログラムを書き直す必要があること。
- 関数や制御文、記法などなど。
- ロジックには、開発者なりの独自の工夫が盛り込まれていること。
この工夫が何らかの事情により不要な場合には、書き直しに伴い、この工夫も排除する必要がある。例えば、アルゴリズムそのものを理解するのに、その工夫が邪魔な場合だ。
この工夫を残す場合、Peer learningでは工夫を含めたロジックを第三者に説明する必要があるだろう。ロジックの関連と有用性を説明できる程度には理解しておく必要がある。
場合によっては、説明相手にはロジック以前に、前提となるバックトラック法、後戻り法そのものについても説明する必要があるかもしれない。
- それがやっていること
- やっていることが、どのようにロジックに反映されているのか
- ロジック上の工夫
ただwebサイトに掲載されているだけの情報をなぞるだけでは、上辺の紹介に留まるだろう。説明できるほどの理解を得るにはプログラムだけでは済まず、オンライン、オフラインを問わず資料や文献の探求も避けられないだろう、ことに気付くのではないだろうか。
この問題の山場はロジックを見出すことではなく、解決法を探し出し、第三者へ説明できる程度までに理解することにある。
ちなみにGitHubに掲載されている該当課題のコードは、あからさまなダミーだ。
Exercise 09
• Create a function that displays all possible placements of the eight queens on the chessboard, without them being able to reach each other.
• Recursivity is required to solve this problem.
• The sequence goes from left to right. The first digit represents the first Queen’s position in the first column (the index starting from 1). The Nth digit represents the Nth Queen’s position in the Nth column.
• Your function must return its result in less than two seconds.
Exercise 08と完全に地続きの問題だ。Exercise 08で得た知識、情報、経験の再活用がカギとなるのは自明だ。
Exercise 08の条件を満たすクイーンの配列を列記せよ、というのが課題だ。
チェス盤上の升目に座標(x, y)を割り当てたとしよう。列記の一例が「15863724」だとする。チェス盤の横軸をx、縦軸をyと見なせば、これは次のように表現できる。
- 1列目の1マス目=(1, 1)、
- 2列目の5マス目=(2, 5)、
- 3列目の8マス目=(3, 8)、...
課題で列記すべき数字はyだけでよい。どのようにアプローチするだろうか。
アプローチ１
Exercise 08を通じて、92通りの組み合わせがあることが分かっている...とか、そういうこと以前に、Exercise 08の学習、特にバックトラック法の学習を通じて、すでにExercise 09の回答を得ているのではないだろうか？
Exercise 08を通じて、Exercise 09も終わらせていないか？ということだ。素直に、その成果を活用すればよい。おそらく大多数の受講生はそうしているはずだ。
アプローチ２
アプローチ１に問題があるわけではないのだが、欠点は存在する。わずか92通りの回答を得るために、バックトラックを再び回さなければならないのか？ということだ。まさかとは思うのだが、特に次の要件を満たせないときの参考にしてほしい。
Your function must return its result in less than two seconds.
exercise 08を通じて、92通りの組み合わせがあることが分かっている。その内訳をよく調べただろうか？前述のwikiを改めて、入念に読んでほしい。
基本解は12種類ある。下記の解1〜11は、回転と鏡像でそれぞれ8種類の変形がある。解12は点対称なので、4種類の変形しかない。したがって、解の総数は 92（＝8×11＋4）になる。
基本解に基づいた12個の数値配列に対して、
- 回転（この課題の場合は90度）
- 鏡像
- 点対象
の数値計算（座標計算）をし、配列の重複を排除することで、結果を求めることができる。対象は12列の数値配列に限定されるので、バックトラックに比べループ回数は遥かに少ないし、数値計算は簡単なので、より高速に処理を終えるはずだ。
回転、鏡像、点対象の座標計算も「アルゴリズム」だが、それはアルゴリズムと呼ぶには、あまりに簡単な計算だ。中学校レベルの数学、義務教育の範囲内にある話題で、言うなれば常識レベルの範囲にある計算だ。
一度、簡単な図を書いて、回転、鏡像、点対象で座標がどのように変化するか、パターンを見出してみてほしい。そのパターンを応用して、基本解の数値配列を計算し直すのだ。
２次元図形の変換
余談－万年カレンダーとアルゴリズム
既知のロジックと化しているアルゴリズムが存在するならば、それらの存在を知り、ロジックと特性、使いどころを学ぶ必要がある。実際Piscineは、そのような知識の有無、あるいは学習、理解を試すかのような課題を含んでいる。定番のソートやフィボナッチ数列、素数探索から組合わせ爆発を伴う問題まで、様々だ。
Piscineに限らず、アルゴリズムの存在を知っている場合、知らない場合では、Day04のアプローチで示したように、作業着手までの瞬発力が違うし、作業に必要な労力も軽減される。
カレンダーのプログラム作成を要請されたとしよう。
- 指定された年月のカレンダーを表示する。
- カレンダーの1行は、日曜日スタートで7日間。
- 1日から月末まで、各週の曜日を揃えて表示する。
どのようなロジックを考えるだろうか？そもそも、指定された年月の1日は何曜日だろうか？
特定日（例えば2020年1月1日、水曜日）を基準日として、基準日から指定年月日までの日数を計算すれば、曜日を算出することができる。Excel等が提供する関数を用いれば簡単に計算できるのだが、Piscineの様に使用禁止とすれば、必要なものを見つけ、自分で実装しなければならない。
日数を計算すればよいとはいえ、閏年を気にする必要もある。閏年は厳密に4年に一度だっただろうか？
このようなことを自分で考え、実装することは、個人のプログラミング学習上、大変意義がある。自分で考える学習ばかりでは、見識が広がりにくい一面もある。
そのロジックは既に他人が考え、公式化されているとなれば、その事実に気付くのはいつになるだろう。そのような既知のロジックの存在を知り、その活用を学ぶ機会を模索する必要がある。
アルゴリズムはプログラム言語に依存することのない、共通のロジックだ。言語のバージョンや出版年の古さを気にすることはない。基本的にロジックそのものが経年劣化することはない。事典（辞典）的な一冊を持っておくと、長く参照することができるのでお勧めだ。
例えば、私は投稿末尾の1冊を所有している。説明が平易でありながら、数式とコードを併記しており、入門としている割に、数値計算からソート、サーチ、再帰、データ構造の一通りを網羅している。
投稿末尾に同書の目次（大見出し）とキーワードを併記しておいた。アルゴリズムの本を購入するならば、せめてこの程度の話題は網羅したものを参照してほしい。ちなみに「バックトラッキング」が、この投稿で言うところのバックトラック法に該当している。
先日の投稿でも述べたことだが、まずは書籍の中身を確認するために、立ち読みなり、図書館で借りるなりすると良い。
最後に、先の曜日を求めるロジックは、ツェラーの公式として数式化されている。
By Odin, by Thor ! Use your brain !!!
