acokikoy's notes

最近気になる=[NoCode, Shopify], I am..=[Python, ウクレレ, マニュアル車, CMS] LoveなWebディレクター

毎朝Codewars@2019.06.14(金): Coding with Squared Strings

毎朝ちびちびCodewars。

[5 kyu] Coding with Squared Strings www.codewars.com

今日のお題:

"""n x n文字列のエンコード・デコード

Code(暗号化):

    与えられた文字列 s をn文字ごとに改行して、n x n の正方形に並べる。
    これを時計回りに90°回転させた結果を返す。

    ただし、
    ・n は、その二乗が sの文字長以上 となる整数の最小値。
    ・s が n x n 文字に満たない時は、"\v(0x0b VT(垂直タブ))" で補完する。


Decode(復号化):

    暗号化された n x n の文字列 s が与えられるので復号する。
    すなわち、sを反時計回りに90°回転させ、余計な文字(\vとか\n)を取り除いた
    結果を返す。


例:
    s = "I.was.going.fishing.that.morning.at.ten.o'clock"

    code(s) -> "c.nhsoI\nltiahi.\noentinw\ncng.nga\nk..mg.s\n\voao.f.\n\v'trtig"
    decode(code(s)) -> "I.was.going.fishing.that.morning.at.ten.o'clock"    

"""

コード

今回は、スライシングとリスト内包表記を活用してすっきり解けたと思う。

Code

エンコードは次のように考える。

例として、 s = "I.was.going.fishing.that.morning.at.ten.o'clock" だとする。

・文字長は 47 文字。\sqrt{47} は6.86 なので n = 7
・足りない2文字分"\v"を補い 7 x 7 文字に並べるとこうなる。

    I.was.g
    oing.fi
    shing.t
    hat.mor
    ning.at
    .ten.o'
    clock\v\v

90°時計方向に回転させるとこうなる。

    c.nhsoI
    ltiahi.
    oentinw
    cng.nga
    k..mg.s
    \voao.f.
    \v'trtig

これを 暗号化の結果として返す。
code(s) -> "c.nhsoI\nltiahi.\noentinw\ncng.nga\nk..mg.s\n\voao.f.\n\v'trtig"

import math

def code(s):
    n = math.ceil(math.sqrt(len(s)))
    s += '\v'*(n**2 - len(s))
    
    rows = [s[-n+i::-n] for i in range(n)]
    return '\n'.join(rows)
  1. n は sの文字長の平方根を取って切り上げて求める。。
  2. 90°時計回りに回した文字列 [s[-n+i::-n] for i in range(n)] は s = "I.was.going.fishing.that.morning.at.ten.o'clock\v\v" を、 末尾文字から始めて7(=n)飛ばしで拾うのを先頭に行き着くまで行う。 次は末尾から2番目の文字から始めて7飛ばしで拾う。。。というのを繰り返して作る。
  3. 最後に改行コードでjoinして返す。

Decode

デコードは、上の逆を行う。

        c.nhsoI
        ltiahi.
        oentinw
        cng.nga
        k..mg.s
        \voao.f.
        \v'trtig

を反時計回りに90°回すとこうなる。

        I.was.g
        oing.fi
        shing.t
        hat.mor
        ning.at
        .ten.o'
        clock\v\v

改行コードと、垂直タブコード("\v")を取り除いて返す。
となって、めでたく最初の文字列に戻る。
decode(code(s)) -> "I.was.going.fishing.that.morning.at.ten.o'clock"

def decode(s):
    rows = s.split('\n')
    n = len(rows[0])
    
    result = [row[-1-i] for i in range(n) for row in rows if row[-1-i]!='\v']
    return ''.join(result)
  1. 与文字列を'\n' で splitして、各行の文字列を要素とするリストする。
  2. n を求める。元々 n x n の文字列なんだから、n は 1行分の文字長に等しい。
  3. 反時計回りに回すのは、リストの各要素(=各行)から、同じ位置の文字を拾ってきてつなげればいい。
    お尻から順に拾う点がポイント。また、垂直タブは余分な文字なので除去する。
入れ子のリスト内包表記
[row[-1-i] for i in range(n) for row in rows if row[-1-i]!='\v']

丁度、試験勉強で「Pythonチュートリアル 第3版」§5.1.4 入れ子のリスト内包 に
行列の処理例として類似のコードを習った直後だったので良い復習になった。

ちなみにforとif を使って書くとこうなる。

result = []
for i in range(n):
    for row in rows:
        if row[-1 - i] != '\v':
            result.append(row[-1-i])