42 SILICON VALLEY Piscineの個人プロジェクト、2つ目はmatch/nmatch。2つの課題で構成されるプロジェクトだ。問題文には明記されていないが、再帰構造の理解と実装が求められている。加えてDay04の話題で触れたバックトラック法の実践だ。
再帰はややこしく、理解し難いと言われる。実際その通りだと思う。しかし再帰を用いずにロジックを組むと、さらに複雑になるだろう。再帰の流れを理解するのは難しくとも、ロジックの「見た目」は、それを用いない場合に比べて、非常にシンプルになる。
題材は文字列比較だ。C言語の練習プログラムの定番の一つだが、難易度を上げているのがワイルドカードの存在だ。私自身、ワイルドカードを含む文字列比較は、正規表現などの与えられた関数を、当然のごとく用いるばかりだったので、このロジックを考えるのは少々手間取った。
今回の投稿では一つ目の課題、matchだけを採り上げる。サンプル・コードはPythonで記述したが、Piscine受講生に配慮して、C言語的な記述になるよう配慮した。
準備
Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io
match
• s1 and s2 are considered to match when s1 and s2 are identical.
• If s2 contains a star (’*’), we can replace this star by any characters string (even empty) to make s1 and s2 identical.
• s2 may hold as many stars as you’d like.
s1、s2として与えられた文字列を比較し、合致していればTrueを、そうでなければFalseを返す関数を作成する。
「*」の取り扱いについて注意が必要だ。s1に含まれる「*」ただの文字だが、s2に含まれるものはワイルドカードとして機能する。これは0文字以上の文字列の代わりを果たす。「*」は複数含まれる可能性がある。
これをロジック、アルゴリズム問題のどちらと解釈するかは、人それぞれだ。また第三の解釈もある。Piscineの課題では、関数やシェル・コマンドの再現を求められることがある。実際のところ、C言語にはmatchという関数が存在している。Piscineの課題流に解釈するならば、C言語のmatch関数を再現せよ、と言ったところだ。
とはいえ厳密には、そのmatch関数の簡易版だ。match関数はワイルドカードとして、「*」に加えて「?」も存在する。この課題では、その考慮は無用だ。
文字列比較
まず「*」のことは無視して、単純な文字列比較のコードを書く。こんな感じだ。
def my_match(list1, list2): i1 = 0 i2 = 0 if list1[i1] == list2[i2] == '\n': return True if list1[i1] == list2[i2]: return my_match(list1[i1+1:], list2[i2+1:]) return False s1 = 'abcde' + '\n' s2 = 'abcde' + '\n' s1_list = list(s1) s2_list = list(s2) print(my_match(s1_list, s2_list))
関数名はmy_matchとした。s1、s2に比較文字列を代入する。最後尾に改行を追加したのは、C言語の終端文字列「\0」の代用だ。
素のPythonには配列が存在せず、代わりにListを用いている。文字列をchar配列的に1文字ずつ分割し、C言語流にポインタ（char配列）での操作を再現しようと試みた。
my_matchでは先頭から一文字ずつ、再帰呼び出しで比較する。不一致が見つかればFalseを返す。見つからずに終端文字までたどり着ければTrueを返す。この処理中に、「*」遭遇した場合の処理を挿入する必要がある。
ワイルドカードを考える
s1、s2にそれぞれ「abcde」、「a*e」が与えられたと考えよう。愚直に先頭から文字列比較していく。2文字目の比較で「*」に遭遇する。1文字ずつ比較する前提では、次の3通りの方法が考えられる。どれが有効だろうか。
- s1を1文字進める。s2はそのまま「*」を参照する。
- s1、s2の両方を1文字進める。不一致の場合、s2だけを戻す（「*」を再参照する）。
- s2を1文字進める。s1はそのまま。不一致の場合、s2を戻し、s1を1文字進める。
頭で考えてもわかりにくい。いつも通りExcelで図解してみる。
s2の「*」に遭遇後、処理は3パターンに分かれる。上記3パターンが左から順番に並んでいる。
赤い矢印「↓↑」がs1、s2のポインタ参照、黄色が参照されている文字だ。
ちなみにs1に「*」が含まれていた場合はどうなるか？考える必要はない。s2の「*」と合致するならば問題ない。s1の「*」はワイルドカードとして機能しないので、合致しなければ不一致の結果を返すだけだ。
s1を1文字進める。s2はそのまま「*」を参照する。
これは一目で、あまり有意義ではないパターンと分かる。s2側ポインタが停滞したまま、s1は終端文字に達することは明らかだ。「*」に遭遇したら、次の文字の処理に移らざるを得ない。結局次の2パターンのいずれかを考える必要に迫られる。
ただし「*」がs2末尾に配置されている場合には問題なく機能する、有効なパターンだ。
s1、s2の両方を1文字進める。不一致の場合、s2だけを戻す（「*」を再参照する）。
図解での処理の流れを追うと、この方法は正常に機能しそうだ。この方法をパターンAと呼ぶことにする。コードの全体は、code - pattern Aとして投稿末尾に掲載している。
「*」遭遇後の処理は次のようになる。
if list2[i2] == '*': if list1[i1] == '\n': return my_match(list1[i1:], list2[i2+1:]) else: if my_match(list1[i1+1:], list2[i2+1:]) == True: return True else: return my_match(list1[i1+1:], list2[i2:])
関数から自分自身を呼び出すのが再帰だ。加えて最後のif文でバックトラックしている。list2[i2+1]で「*」の次の文字を参照している。結果がFalseであれば次のif文に飛ぶ。そこではlist2[i2]、つまり「*」に参照を戻して再帰を繰り返している。
s2を1文字進める。s1はそのまま。不一致の場合、s2を戻し、s1を1文字進める。
この方法も正常に機能しそうだ。この方法をパターンBと呼ぶことにする。コードはパターンAと、ほんの僅かに異なる。異なる部分だけを引用する。コードの全体は、code - pattern Bとして投稿末尾に掲載している。
if my_match(list1[i1:], list2[i2+1:]) == True:
どちらが正解なのか？
パターンA、Bのコードの違いは、ほんの些細なものだ。そして、どちらも文字列比較においては、正常に機能しているように見える。図解を再確認する。パターンA、Bの違いと言えば、
- パターンAは、パターンBよりも処理が短い。
- パターンAには、比較していない組み合わせが含まれている。
- 赤い楕円で囲った部分
特に後者のポイントは、比較上の漏れがあることを意味しており、より完全を期すならばpattern Bを正解と考えるべきだろう。
とはいえ課題で求められている文字列比較の上では、決定的な違いは見つからない。この違いは致命的だろうか？
次の課題であるnmatchを試すことで決定的な違いを示すことができる。練習の上では、両方のコードでnmatchを試せばよいのだが、Piscine受講生にとっては、この時点で説明できることが致命的に重要だ。それは次の二点を意識してのことだ。
- peer learning
- パートナーに説明し、理解させなければならない。
- パートナーに違いの説明を求められたらどうする？
- nmatchの評価への影響
後者が致命的なのだ。それはプロジェクト資料の投稿で触れた、次の事柄についてだ。
• 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.
プロジェクト課題は難易度順に実施され、簡単なプロジェクト課題に失敗していたら、たとえ難しいプロジェクト課題が正解であっても評価されないのだという。
もし、ここで選択を誤ればnmatchは評価されないことになる。実際のところ、ここで誤るとnmatchは評価されない以前に、誤った結果を出力することになる。
次の課題であるnmatchと合わせて、この話題を次の投稿で説明する。
impsbl.hatenablog.jp
余談－再帰が理解できない人へ
一通りの文章に目を通していただいて、ありがとう。
matchは理解できただろうか。もし再帰が分からないのであれば、nmatchへ進む前に、次のページに目を通してほしい。Piscineの問題を一度離れ、再帰を説明するページを用意した。
matchでは再帰を多用している。そしてnmatchでも再帰を多用する。再帰を理解せずに読み進めても、理解が深まることがない。分からないことを解決しないまま学習を進めると、後戻りが大きくなるばかりか、何が原因で理解できないのか、何が理解できていないのかすら分からなくなる。こうなると後戻りすらできない。一からやり直しだ。こういう時、大体の人は挫折する。
まず必要な知識を積み重ねてほしい。問題を解くのはその後だ。
By Odin, by Thor ! Use your brain !!!
サンプル・コード
code - pattern A
def my_match(list1, list2): i1 = 0 i2 = 0 if list1[i1] == list2[i2] == '\n': return True if list2[i2] == '*': if list1[i1] == '\n': return my_match(list1[i1:], list2[i2+1:]) else: if my_match(list1[i1+1:], list2[i2+1:]) == True: return True else: return my_match(list1[i1+1:], list2[i2:]) if list1[i1] == list2[i2]: return my_match(list1[i1+1:], list2[i2+1:]) return False s1 = 'abcde' * 4 + '\n' s2 = 'a*e*e*e' + '\n' s1_list = list(s1) s2_list = list(s2) print(my_match(s1_list, s2_list))
code - pattern B
def my_match(list1, list2): i1 = 0 i2 = 0 if list1[i1] == list2[i2] == '\n': return True if list2[i2] == '*': if list1[i1] == '\n': return my_match(list1[i1:], list2[i2+1:]) else: if my_match(list1[i1:], list2[i2+1:]) == True: return True else: return my_match(list1[i1+1:], list2[i2:]) if list1[i1] == list2[i2]: return my_match(list1[i1+1:], list2[i2+1:]) return False s1 = 'abcde' * 4 + '\n' s2 = 'a*e*e*e' + '\n' s1_list = list(s1) s2_list = list(s2) print(my_match(s1_list, s2_list))
