42 SILICON VALLEY Piscineの個人プロジェクト、2つ目はmatch/nmatch。2つの課題で構成されるプロジェクトだ。問題文には明記されていないが、再帰構造の理解と実装が求められている。
再帰はややこしく、理解し難いと言われる。実際その通りだと思う。しかし再帰を用いずにロジックを組むと、さらに複雑になるだろう。再帰の流れを理解するのは難しくとも、ロジックの「見た目」は、それを用いない場合に比べて、非常にシンプルになる。
今回の投稿では二つ目の課題、nmatchを採り上げる。一つ目の課題であるmatchについては、前回の投稿を参照してほしい。
題材は文字列比較だがmatchとは求められていることが異なる。単純な比較結果を出力するのではなく、合致するパターン数を出力しなければならない。前回同様、これまで考えもしなかったロジックで、かなり手間取った。
前回同様、サンプル・コードはPythonで記述したが、Piscine受講生に配慮して、C言語的な記述になるよう配慮した。
準備
Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io
nmatch
• When we have two or more stars, multiple string combinations can be suitable.
• nmatch calculates the total amount of combinations.
matchと地続きの課題だ。matchでは一致、不一致の結果を返したが、今回は一致するパターン数を返さなければならない。単純な例で考えてみよう。
s1、s2にそれぞれ「aaaa」、「a**a」が与えられたとしよう。一致、不一致で考えるならば、一致だ。ただし一致する場合は3通りある。次のような具合だ。
| 一つ目の「*」 | 二つ目の「*」 |
| a | a |
| aa | \0 |
| \0 | aa |
文字列比較再訪
パターン数を検出するため、一致する件数を集計しなければならない。件数に直結するような手がかりはないか、仮説を立ててみる。バックトラックの回数が件数に一致しないだろうか？これは簡単に反証できる。
s1、s2にそれぞれ「abcdeabcdeabcdeabcde」、「a*e*e*e」と与えられたとしよう。考えられる組合わせは次の3通りだ。バックトラック回数よりもはるかに少ない。
| 一つ目の「*」 | 二つ目の「*」 | 三つ目の「*」 |
| bcd | abcd | abcdeabcd |
| bcd | abcdeabcd | abcd |
| bcdeabcd | abcd | abcd |
アスタリスク数が件数と合致することはないか？これも反証は簡単だ。s1、s2が「aaaa」、「a**」とすれば、パターン数はアスタリスク数を超える。
| 一つ目の「*」 | 二つ目の「*」 |
| a | aa |
| aa | a |
| aaa | |
| aaa |
どう考えてもロジックが思い浮かばなかったので、総当たりの力技でプログラムすることにした。バックトラックは捨てることになる。「*」遭遇時の処理は次のようになる。
if list2[i2] == '*': if list1[i1] == '\n': return my_match(list1[i1:], list2[i2+1:]) else: a = my_match(list1[i1:], list2[i2+1:]) b = my_match(list1[i1+1:], list2[i2:]) return a + b if list1[i1] == list2[i2]: return my_match(list1[i1+1:], list2[i2+1:]) return 0
s1、s2を順番に先頭から一つずつ進め、True（実際にはint(1)）を返したものだけを集計している。戻り値としてa、bを取得しているが、ここには再帰した全てのa、bが集まる仕掛けだ。訳が分からないかもしれない。
上記処理の冒頭部分を書きだすと図のようになる。「M」がmy_nmatchで、特にa=、b=での再帰呼び出しを、それぞれ「a」、「b」としている。赤い矢印から青い矢印へ、そして緑の矢印へ処理を辿り、それを繰り返していく。
青い矢印を辿りながら、「*」と比較されているs1の文字に注目してほしい。最後までTrueが戻り切ったときに、「*」と対になっている文字のパターンがカウントすべき対象になる。
次の図は、最もシンプルなパターンの一つだ。s1、s2が「aaaa」、「a**」の場合、
| 一つ目の「*」 | aaa |
| 二つ目の「*」 | \n |
となっているのが分かるだろう。このような対象を一つずつ、総当たりで見つけながら集計していく。
matchの答え合わせ
前回投稿したmatchにはパターンA、Bの2通りの可能性があった。「*」遭遇時のポインタを、どのように進めるかの違いについて、その違いは致命的なのかか？ということが前回からの懸案だった。実際のところ、致命的なのだ。
両コードを次のケースでテストした結果を比較してみてほしい。パターンAはテスト2で誤りを出力した。
文字列の比較だけであればパターンAでも問題はないのだが、パターンBとの差異に気づかないまま課題を進めてしまった場合、Piscine評価に致命的な影響を与えかねない。プロジェクト資料の投稿で触れた事柄を、警鐘のために再掲しておく。
• These exercises are carefully laid out by order of difficulty - from easiest to hardest. We will not take into account a successfully completed harder exercise if an easier one is not perfectly functional.
プロジェクト課題は難易度順に実施され、簡単なプロジェクト課題に失敗していたら、たとえ難しいプロジェクト課題が正解であっても評価されない、ということだ。
くれぐれも慎重に。可能性を広く想定し、落ち着いてテストすることにしよう。
テスト１
| s1 | abcdeabcdeabcdeabcde | |
| s2 | a*e*e*e | |
| pattern A | 3 | 正解 |
| pattern B | 3 | 正解 |
テスト２
| s1 | aaaa | |
| s2 | a** | |
| pattern A | 6 | 誤答 |
| pattern B | 4 | 正解 |
余談－再帰が理解できない人へ
一通りの文章に目を通していただいて、ありがとう。
match/nmatchは理解できただろうか。もし再帰が分からないのであれば、次のページに目を通してほしい。Piscineの問題を一度離れ、再帰を説明するページを用意した。
matchでは再帰を多用している。そしてnmatchでも再帰を多用した。再帰を理解せずに読み進めても、理解が深まることがない。分からないことを解決しないまま学習を進めると、後戻りが大きくなるばかりか、何が原因で理解できないのか、何が理解できていないのかすら分からなくなる。こうなると後戻りすらできない。一からやり直しだ。こういう時、大体の人は挫折する。
まず必要な知識を積み重ねてほしい。問題を解くのはその後だ。
By Odin, by Thor ! Use your brain !!!
サンプル・コード
code - pattern A
def my_nmatch(list1, list2): i1 = 0 i2 = 0 if list1[i1] == list2[i2] == '\n': return 1 if list2[i2] == '*': if list1[i1] == '\n': return my_nmatch(list1[i1:], list2[i2+1:]) else: a = my_nmatch(list1[i1+1:], list2[i2+1:]) b = my_nmatch(list1[i1+1:], list2[i2:]) return a + b if list1[i1] == list2[i2]: return my_nmatch(list1[i1+1:], list2[i2+1:]) return 0 s1 = 'abcde' * 4 + '\n' s2 = 'a*e*e*e' + '\n' s1_list = list(s1) s2_list = list(s2) print(my_nmatch(s1_list, s2_list))
code - pattern B
def my_nmatch(list1, list2): i1 = 0 i2 = 0 if list1[i1] == list2[i2] == '\n': return 1 if list2[i2] == '*': if list1[i1] == '\n': return my_nmatch(list1[i1:], list2[i2+1:]) else: a = my_nmatch(list1[i1:], list2[i2+1:]) b = my_nmatch(list1[i1+1:], list2[i2:]) return a + b if list1[i1] == list2[i2]: return my_nmatch(list1[i1+1:], list2[i2+1:]) return 0 s1 = 'abcde' * 4 + '\n' s2 = 'a*e*e*e' + '\n' s1_list = list(s1) s2_list = list(s2) print(my_nmatch(s1_list, s2_list))
