【POH7】パターンマッチング(「めがね」)

みなさんこんばんは。

昨年12月に開催されたPaizaさんのPOH7の解説、第2回で「めがね」の問題を解説します。その他の問題は難しくないのでこれで最終回(笑)です。

さて、「めがね」の問題ですが、これは白黒画像のパターンマッチングの問題で、たとえば、

0 0 1 0
0 1 1 0
0 1 0 1
1 1 1 0

 という全体画像(0と1のどちらが黒でも白でも問題の本質には変わりないのですが、問題ページの説明では、1が黒で表現されていました)の中から

0 1 1
0 1 0
1 1 1

のパターン画像に一致する場所を調べて、その位置を出力する問題です。この例の場合で全体画像のうち最初の行を0行目、最初の文字を0文字目として数えると、1行0文字目からの3文字3行分が一致するので、

1 0

と出力をするようなプログラムを書く問題です。

全体画像は N x N ピクセル、パターン画像は M x M ピクセルの大きさで、 10 <= N <= 100, 2<= M <= 10 に限られ、パターンがマッチするのは全体画像のなかで1か所という制約が設定されています。N と M は全体画像・パターン画像に先立って入力され、この例では

4
0 0 1 0
0 1 1 0
0 1 0 1
1 1 1 0
3
0 1 1
0 1 0
1 1 1

と表現されるというのが入力データの仕様です。

左上の座標からひとつひとつ一致するかチェックするナイーブなやり方でも問題なさそうに思いますが、きっと時間切れになるようにテストケースが設定されているでしょうから、何か工夫が必要なのだと思います。

パターン比較するといっても、ひとつの座標にたいして0と1が合致しているかをパターン画像の M x M 回繰り返すのはちょっとマヌケな感じがしますし、パターンは1行あたり2つの組み合わせで高々10桁ですから、符号なし2進数としてみても 0 〜 1023 までの範囲に収まるので、パターン画像は符号なし2進数で読んでしまうとよさそうです。先にあげた例の場合では

3
2
7

となります。全体画像については、それぞれの行についてパターン画像の桁数分だけ、すなわち0〜2文字分(最初の行では 0 0 1 なので 1)と 1〜3文字分(同じく最初の行で 0 1 0 なので 2)についてを符号なし2進数で読んで

1 2
3 6
2 5
7 6

と作っておきます(2文字目以降と3文字目以降はパターン画像が全体画像をはみ出してしまうので考えません)。加工した全体画像とパターン画像データから一致するものを探すわけですが、パターンのデータは1文字M行のものになってしまうので、行と列を入れ替えて

1 3 2 7
2 6 5 6

から

3 2 7

を検索する問題に帰着できます。普通であれば扱うのが文字列で、string.findでカタがつくくのですが、よい演習の機会だということで、BM(Boyer-Moore)法を改良したSundayのquick searchを実装して、こんな感じに書いてみました。

#! /usr/bin/env python2

def make_qt(pat, n):
    q_t = [n+1] * 2**n
    for i in range(n):
        q_t[pat[i]] = n-i
    return q_t

def qs_search(buf, pat, q_t):
    n = len(buf)
    m = len(pat)
    i = 0
    while i <= n - m:
        j = 0
        while j < m:
            if buf[i + j] != pat[j]:
                break
            j += 1
        if j == m:
            return i
        if i+m>=n:
            break
        i += q_t[buf[i + m]]
    return -1

def do_calc(n,m,fld,pat):
    n_pat = map(lambda x:int(x,2),pat)

    q_t = make_qt(n_pat,m)
    
    f_pat = []
    for l in range(n):
        n_l = []
        for p in range(n-m+1):
            n_l.append(int(fld[l][p:p+m], 2))
        f_pat.append(n_l)
    
    t_pat = map(list,zip(*f_pat))
    
    for q in range(len(t_pat)):
        p = qs_search(t_pat[q],n_pat,q_t)
        if p>=0:
            print p,q
            return
    return

n = int(raw_input())
f = [ ''.join(raw_input().split()) for _ in range(n) ]
m = int(raw_input())
p = [ ''.join(raw_input().split()) for _ in range(m) ]

do_calc(n,m,f,p)

真面目に考えると(きっと)こんな感じになるのですが、この問題については大変ものぐさな人向けの大技が使えます。この例の場合で考えると、スペース文字や改行を無視するとパターン画像は正規表現で任意の文字を示す'.'を使って、

011.010.111

と書くことができます( '.' の数はそれぞれの行間ごとに N-M = 1 文字分使用します)。全体画像についてもスペースと改行を無視すると、

0010011001011110

と表現できるので、文字列の正規表現マッチの問題に帰着できます(出現文字位置から座標を計算するのは簡単ですよね?)。パターン画像が全体画像をはみ出ることを考慮する必要がありますが、「下ごしらえして(おそらく)検索一発」なテイストで問題を解くことができます。

ここまで処理を圧縮できたので、折角なので悪趣味にもCode Golf 的な仕上げをして

import re;i=input;a=range;w=raw_input;b=lambda c:[w()for _ in a(c)];n=i(
);f=''.join(b(n)).replace(' ','');m=i();r=n-m;p=r*'.'.join(b(m)).replace
(' ','');j=filter(lambda a:a%n<=r,[x.start()for x in re.finditer(p,f)])[
0];print j/n,j%n
( 表示の都合上折り返していますが、全部まとめて1行で書いてください )

と書いてみたのでした(解読は各自挑戦してみてください)。