The Hidden Word (Alice In Wonderland) - 複数行文字列の縦横検索

どんな問題？

The Hidden Word
http://www.checkio.org/mission/hidden-word/

複数行の文字列に、あるワードが縦または横方向に含まれている。
そのワードの開始位置と終了位置を取得せよ。

• 複数行の文字列に含まれるスペースは除去する。（除去したものをCutと呼ぶ。）
• 複数行は(\n)で区切られている。
• 検索時は大文字小文字は区別しない。
• 検索ワードは小文字で与えられる。
• 横方向は左から右へ、縦方向は上から下へ進む。
• 位置は1ベースで取得する。（1から数える）

引数は、複数行の文字列(Rhyme)と検索ワード。
戻り値は、[開始行,開始列,終了行,終了列] のリスト形式で返す。

例題：

checkio("""DREAMING of apples on a wall,
And dreaming often, dear,
I dreamed that, if I counted all,
-How many would appear?""", "ten") == [2, 14, 2, 16]

checkio("""He took his vorpal sword in hand:
Long time the manxome foe he sought--
So rested he by the Tumtum tree,
And stood awhile in thought.
And as in uffish thought he stood,
The Jabberwock, with eyes of flame,
Came whiffling through the tulgey wood,
And burbled as it came!""", "noir") == [4, 16, 7, 16]

Rhymeというのは押韻詩という意味らしい。言われてみれば、例題の文章も、

～wall, ～dear,
～all, ～appear?

と韻を踏んでいる。まあ、問題を解くには関係ないんだけど。

どうやって解く？

1. Rhymeからスペースを除去してCutにする。
2. 横方向に、ワードが含まれているか調べる。
3. 文字列を縦向きに並び替える。
4. 縦方向に、ワードが含まれているか調べる。

という流れ。

まず、Rhymeに含まれるスペースを除去するのは、replace()でいいかな。

    cut = [line.replace(' ', '').lower() for line in text.splitlines()]

ワード検索するには、位置情報が必要なので、find()を使う。

文字列を縦向きに並び替える

文字列を縦向きに並び替える。これは、以前にやった転置行列でもやった。

>>> a = [[1, 2, 3], [4, 5], [6, 7, 8]]
>>> list(zip(*a))
[(1, 4, 6), (2, 5, 7)]

ただ、zipを使うと、一番短い文字列に合わせて、余りは削除されてしまうので、今回は、itertools.zip_longestを使う。

>>> import itertools
>>> list(itertools.zip_longest(*a))
[(1, 4, 6), (2, 5, 7), (3, None, 8)]

zip_longest()では、足りない部分がNoneで埋められるが、fillvalueを使うことで、任意の値を指定できる。

まとめ

from itertools import zip_longest
 
def checkio(text, word):
    def find_word_in_multiline(lines):
        # 複数行からワード検索して位置を取得（1ベース）
        for row, line in enumerate(lines):
            col = line.find(word)
            if col != -1:
                # 見つかったら、(True, 行番号, 列番号) を返す
                return True, row + 1, col + 1
        else:
            # 見つからなければ、(False, 0, 0) を返す
            return False, 0, 0

    # まず横向き(cut)でワード検索
    cut = [line.replace(' ', '').lower() for line in text.splitlines()]
    found, y, x = find_word_in_multiline(cut)
    if found:
        return [y, x, y, x + len(word) - 1]

    # 見つからなければ、縦向き(transposed_cut)でワード検索
    transposed_cut = [''.join(chars) for chars in zip_longest(*cut, fillvalue=' ')]
    found, x, y = find_word_in_multiline(transposed_cut)
    if found:
        return [y, x, y + len(word) - 1, x]
 
    return [0, 0, 0, 0]

http://www.checkio.org/mission/hidden-word/publications/natsuki/python-3/first/

他の人の答え

スペースを除去するには、replace()を使う以外にも、splitして再結合という方法もあるようだ。

    cut = [''.join(line.split()) for line in text.splitlines()]

この問題では、なんとPython開発者のGuido氏も解答している。
http://www.checkio.org/mission/hidden-word/publications/guido/python-3/generator/
コメント欄でいっぱい指摘されているGuidoたん・・・(^_^;