Technically Impossible

Lets look at the weak link in your statement. Anything "Technically Impossible" basically means we haven't figured out how yet.

42 SILICON VALLEY Piscine 2017 match/nmatchを考える(後編) 最後は力業

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」としている。赤い矢印から青い矢印へ、そして緑の矢印へ処理を辿り、それを繰り返していく。
f:id:espio999:20191214151531p:plain
青い矢印を辿りながら、「*」と比較されているs1の文字に注目してほしい。最後までTrueが戻り切ったときに、「*」と対になっている文字のパターンがカウントすべき対象になる。
次の図は、最もシンプルなパターンの一つだ。s1、s2が「aaaa」、「a**」の場合、

一つ目の「*」 aaa
二つ目の「*」 \n

となっているのが分かるだろう。このような対象を一つずつ、総当たりで見つけながら集計していく。
f:id:espio999:20191214151944p:plain

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.

プロジェクト課題は難易度順に実施され、簡単なプロジェクト課題に失敗していたら、たとえ難しいプロジェクト課題が正解であっても評価されない、ということだ。
くれぐれも慎重に。可能性を広く想定し、落ち着いてテストすることにしよう。

テスト1
s1 abcdeabcdeabcdeabcde
s2 a*e*e*e
pattern A 3 正解
pattern B 3 正解
スト2
s1 aaaa
s2 a**
pattern A 6 誤答
pattern B 4 正解

余談-再帰が理解できない人へ

一通りの文章に目を通していただいて、ありがとう。

match/nmatchは理解できただろうか。もし再帰が分からないのであれば、次のページに目を通してほしい。Piscineの問題を一度離れ、再帰を説明するページを用意した。
matchでは再帰を多用している。そしてnmatchでも再帰を多用した。再帰を理解せずに読み進めても、理解が深まることがない。分からないことを解決しないまま学習を進めると、後戻りが大きくなるばかりか、何が原因で理解できないのか、何が理解できていないのかすら分からなくなる。こうなると後戻りすらできない。一からやり直しだ。こういう時、大体の人は挫折する。

まず必要な知識を積み重ねてほしい。問題を解くのはその後だ。

By Odin, by Thor ! Use your brain !!!

impsbl.hatenablog.jp

サンプル・コード

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))