文字列の八方向検索 in Python DouKaku?

与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを
書いてください。
文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを
対象とします。出力は起点"ウ"の座標と方向のリストにしてください。

サンプル入力：

リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ

サンプル出力：

(2, 0), 左
(0, 1), 右
(0, 1), 下
(3, 1), 右
(4, 3), 左上

--
より一般には、任意の検索文字列への対応も考えてみてください。

11行目のif文をもう少しどうにかしたかったけど、思いつかなかったので投稿。

# -*- coding: utf-8 -*-

def f(data, s):
  a = [('-j', '+0'), ('+j', '+0'), ('+0', '-j'), ('+0', '+j'), ('-j', '-j'), ('-j', '+j'), ('+j', '-j'), ('+j', '+j')]
  for y in range(len(data)):
    for x in range(len(data[0])):
      if data[y][x] == s[0]:
        for i in range(8):
          try:
            b, c = a[i]
            if ''.join([data[y+eval(c) if y+eval(c) >= 0 else len(data)][x+eval(b) if x+eval(b) >= 0 else len(data[0])] for j in range(len(s))]) == s:
              print '(%d, %d) %s' % (x, y, ['左', '右', '上', '下', '左上', '左下', '右上', '右下'][i])
          except:
              pass

data = [u'リオウウリウ', u'ウオリウオリ', u'オリリオリウ', u'リリオオウオ']

f(data, u'ウオリ')

単純に全探索。

# coding: shift_jis

import sys
import codecs

def main():
    if not len(sys.argv) == 3:
        sys.stderr.write("usage: input_file_name search_string\n")
        return
    matrix = [list(s.rstrip("\r\n")) for s in codecs.open(sys.argv[1], "r", "shift_jis")]
    string = sys.argv[2].decode("shift_jis")
    if not string:
        raise ValueError("empty search string")
    ycount = len(matrix)
    if not ycount >= 1:
        raise ValueError("empty sample input")
    xcount = len(matrix[0])
    for a in matrix:
        if not len(a) == xcount >= 1:
            raise ValueError("invalid length of line")
    for y in xrange(ycount):
        for x in xrange(xcount):
            if matrix[y][x] == string[0]:
                for dy in xrange(-1, 2):
                    for dx in xrange(-1, 2):
                        if dx == dy == 0:
                            continue
                        for i in xrange(1, len(string)):
                            x2 = x + dx * i
                            y2 = y + dy * i
                            if not(0 <= x2 < xcount and 0 <= y2 < ycount and matrix[y2][x2] == string[i]):
                                break
                        else:
                            print "(%d, %d), %s%s" % (x, y, [u"", u"右", u"左"][dx], [u"", u"下", u"上"][dy])

if __name__ == '__main__':
    main()

DouKaku?

文字列の八方向検索

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq